Intel® oneAPI Threading Building Blocks
Ask questions and share information about adding parallelism to your applications when using this threading library.

problem about concurrent_priority_queue order

david_l_3
Beginner
749 Views

I want use TBB concurrent_priority_queue in my program. so I did some tests
insert 6 elements with different priority into queue.
job priority
------------------
job0   2
job1   0
job2   1
job3   0
job4   2
job5   1

when pop them one by one, The result is supposed to be job1 3 2 5 0 4. the actual result is 1 3 5 2 0 4
two of them seems not follow FIFO rules. same result in many times test.

0 Kudos
7 Replies
david_l_3
Beginner
749 Views

another question : Are there any env limit for using TBB ?  effective on intel platform only ?

0 Kudos
david_l_3
Beginner
749 Views

test on a linux machine  Intel(R) Pentium(R) CPU G2030

gcc (SUSE Linux) 4.3.4 [gcc-4_3-branch revision 152973]

0 Kudos
RafSchietekat
Valued Contributor III
749 Views

This property is not generally implied for a priority queue, perhaps because it is not provided by the most efficient implementations, which is probably sufficient reason for it not to be mentioned in the documentation for tbb::concurrent_priority_queue, although a warning about that would still be helpful of course.

You should compare this with the heap-related functions in C++, repackaged by specification in std::priority_queue.

 

0 Kudos
RafSchietekat
Valued Contributor III
749 Views

Have you been able to confirm this for std::priority_queue, as well?

If FIFO within priority is important to you, a possible general workaround could be to store time-related information, e.g., obtained from an atomic ticket dispenser, alongside the element, and let it be a minor order to the priority's major order. If priority is categorical from a small and fixed set, other workarounds could be considered, with different properties.

(Added) As expected, the property is known as "stability" (but is not always provided).

0 Kudos
david_l_3
Beginner
749 Views

I have tested it with std::priority_queue. There is the same result.  I think i made wrong idea about priority_queue.  Thank you.

with 3 level priority, concurrent_priority_queue keep FIFO order in 1 and 3 level  . std keep 1 only.   It seems look like that.

0 Kudos
RafSchietekat
Valued Contributor III
749 Views

So... "same result" in the sense that neither is stable, but they do differ in the exact outcome, if I understand correctly. Somewhat surprising, thanks for letting us know.

0 Kudos
RafSchietekat
Valued Contributor III
749 Views

I've tested this myself, anyway, and my outcome differs from yours: stable/tbb/std is 132504/135204/132540, i.e., concurrent_priority_queue and priority_queue (consistently) preserve order in priorities 1 and 3 resp. 1 and 2, not 1 and 3 resp. 1 (adding 1 to the actual priorities each time as you did). This is on up-to-date OS X with tbb42_20140601oss (TBB 4.2 update 5, most recent). Please check your result again?

The reason seems to be that TBB's concurrent_priority_queue does not use C++ heap operations as std::priority_queue does (at the mandate of the Standard). Of course that mandate is slightly suboptimal even for manipulating one element at a time, strictly speaking, because there's no apparently valid reason to, e.g., implement priority_queue::pop() as pop_heap() followed by pop_back(), either before or since C++11 move semantics, and it might have been better to leave the details up to the implementation. TBB will aggregate concurrent operations, and by not using the heap operations it can avoid several unnecessary actions.

In doing that, TBB apparently favours the left child to resolve ties while descending from the root node when popping the current top, while pop_heap() maybe favours the right child in my environment. At any rate, reversing that in TBB reproduces the outcome from std::priority_queue, in my environment.

Other than that, TBB seems to descend too far into the tree when there are many equivalent elements, but that does not manifest itself in this little test. (Just goes to show that unit tests should be considered with suspicion...)

Here's my test code for the convenience of whoever also might want to try this (the small dependency on C++11 is easily removed):

#include <stdlib.h> // EXIT_SUCCESS
#include <iostream> // std::cout
#include <queue> // std::priority_queue
#include <vector>
#include <tbb/tbb.h>

// tbb::concurrent_priority_queue does not accept a Compare instance (why not?)
struct MyCompare {
    int operator() (int x, int y) { return y%10 < x%10; } // highest first
};

int main(int argc, char *argv[]) {
    std::vector<int> v { 02, 10, 21, 30, 42, 51 };

    std::cout << "132504 stable\n";

    /* tbb::concurrent_priority_queue */ {
        tbb::concurrent_priority_queue<int, MyCompare> cpq;
        for (int i: v) cpq.push(i);
        int i; while (cpq.try_pop(i)) { std::cout << i/10; }
        std::cout << " tbb\n";
    }

    /* std::priority_queue */ {
        std::priority_queue<int, std::vector<int>, MyCompare> pq;
        for (int i: v) pq.push(i);
        while (!pq.empty()) { std::cout << pq.top()/10; pq.pop(); }
        std::cout << " std\n";
    }

    return EXIT_SUCCESS;
}

(2014-09-01 Edited) My earlier remark about C++11, now removed, was about 4.2 update 5; TBB 4.3 does implement the new features.

(2014-09-04 Edited) TBB avoids "several" actions by not using the standard heap operations not just "a few".

0 Kudos
Reply