try_pop in concurrent_queue

[leemeng]

hi all,

Can anyone kindly explain the behavior oftry_pop in detail? When I useconcurrent_queue in my program, the queue is filled up with a large number of elements, even push and try_pop are in the same thread. Here is what I have done:

In a loop of a thread,

- Perform some actions, which result in pushing a couple of elements into the queue

-execute

while(q.try_pop())

{ process data}

Of cause, I was supposed to do producer and consumer inter thread communication with the queue, but even in single thread, I hit on trouble already. After the program runs for while, I find the queue is getting longer and longer. How this could happen? will try_pop return false even the queue is not empty? What is the right way to consume up the data in the queue?

Please suggest, and thanks in advanced!

/Lee

[RafSchietekat]

Could it be that the consumer temporarily catches up with the producer, stops consuming altogether, and so never considers the elements produced after that? If that is the issue, have a look at concurrent_bounded_queue::pop() instead.

[leemeng]

Thanks Raf! it is good guess, but it seem not my case. In my program, producor is reading messages from external. If I stop inputing messages into the program, then the queue can eventually be clean.

[RafSchietekat]

I don't quite understand what you mean. Even if the producer gets its data from an external source, a compute-bound consumer could still catch up, and the loop you showed would cause it to self-terminate, leaving the producer to send messages into an ever-expanding queue.

[jimdempseyatthecove]

Lee,

It sounds as if you have exposed a bug relating to the push when the push causes the queue to expand.
As a test of the theory, prior to your main loop display the queue (available) size, then after each push display the in-use size. If the problem occures just before, at, or just after the original size, then it smells more like a bug.

A second potential problem which you can check is to see if try_pop has an issue when queue is at max capacity (next push expands). Boundary conditions are more sensitive to bugs.

Jim Dempsey

[jimdempseyatthecove]

>>and the loop you showed would cause it to self-terminate, leaving the producer to send messages into an ever-expanding queue

Look again, I read:

loop:
push some number of items
while(try_pop())
{
workOnPopedItem()
}
goto loop ! this line not listed in sketch code


The queue will never get longer than the largest"push some number of items" (x # threads).

Jim Dempsey

[leemeng]

Hi Jim,

This is exactly what my program is doing. It push in 8 elements at a time, as you point out, I expect the queue never go beyond 8. But it queue up more than 500 ! I will try out dig out more debug info when I'm back to my desk. Great thanks!

/lee

[leemeng]

Hi Raf,

Please see Jim's post in #5. He has a better explanation of my program.

/lee

[jimdempseyatthecove]

>>It push in 8 elements at a time, as you point out, I expect the queue never go beyond 8.

It could go to 8 x number of threads performing loop. However, if your code fails with 1 thread, this is a clear indication of a bug in the try_pop.

Verification test:

Configure for 1 thread

int pushCount = 0;
loop:
assert(pushCount == 0);
n x (
q.push(...)
++pushCount
}
while(q.try_pop())
{
--pushCount;
...
}
goto loop

The above should not fail.

*** However, the designers of TBB concurrent_queue may have taken the liberty of declaring it need not always succeed when queue not empty. A hyptotetical may be, when a push causes a wraparound, the next try_pop will fail, but in the process resets the pop pointer to front of queue. This will work as long as another thread or threads are poping the queue and thus the pushes and pops are not synchronous.

A possible correction for this would be

while(q.try_pop() || q.try_pop())
{
...

Which seems redundant for you to do since, assuming above hypothetical is true, the try_pop should do this internally on said assumed wrap around condition.

Jim Dempsey

[leemeng]

Great thank to you Jim,

I test as you suggested it is not failing. I might push on a wrong alarm. I have not got time to test with multithread yet, will try it when I am back to office on Monday.

I also take Raf's suggestion and replace the queue with a bounded queue instead, they both behave the same in my program, not sure if there will be any difference for performance wise, though

Thanks for the great help again!

[RafSchietekat]

"However, the designers of TBB concurrent_queue may have taken the liberty of declaring it need not always succeed when queue not empty."
I'm not sure about those technical details, but in a class with unsafe_size() it would seem likely that empty() and try_pop() may fail spuriously. In fact, the opposite would surprise me, and either situation deserves clear documentation. However, this would only be when the queue is close to being really empty, and I'm not sure how you would distinguish spurious failure from unfortunate timing between producer and consumer. As for "wraparound", a bug fix is logged for 4.0 update 2, but it would only occur after about 4 billion pushes on x86_32. Otherwise I'm still a bit mystified about the details of the observed problem, but Jim seems to have a handle on it.

[jimdempseyatthecove]

One of my posts got dropped.

Lee, as a potential fix for your problem try

while(q.try_pop(...) || q.try_pop(...))
{

if the first one succeeds, the second one is not called
if the first one fails, the second one is called

Therefore, if there is a wrap around incident that causes a one time glitch in try_pop, that this will fix it.

However, if the glitch is always a two-time thing then you will need to add an additional try_pop

This is kludgy, since the real fix needs to be made to try_pop.

Jim Dempsey

[jimdempseyatthecove]

>>As for "wraparound", a bug fix is logged for 4.0 update 2, but it would only occur after about 4 billion pushes on x86_32.

Not necessarily so. This depends on the implimentation.

Wrap around may occures at size() intervals (number of elements in buffer).

[RafSchietekat]

"Not necessarily so. This depends on the implimentation."
I was just repeating informaton from the CHANGES file...

[Terry_W_Intel]

Hi Lee,
If you are still seeing a problem, please post a reproducer program so that we can look into it. I cannot get any bug to reproduce based on the pseudocode provided here. Also, let us know what version of TBB you have.
Thanks!
Terry