Runtime: ConcurrentQueue.IsEmpty result freshness across cores

[MaximGurschi]

Hi team,

Am i right to understand that ConcurrentQueue.IsEmpty (and possibly other members) is not meant to be used in a way that relies on the invariant:
If the queue is modified (add or remove) by thread X, then some other thread Y will see the "fresh" result of calling IsEmpty?

I looked at the implementation of the property and concluded that there is no strict freshness guarantee actually implemented. Like for example if it were to use an atomic counter.

Can you please confirm that the queue is not to be used in such ways?

[msftbot[bot]]

Tagging subscribers to this area: @eiriktsarpalis, @jeffhandley
See info in area-owners.md if you want to be subscribed.

[stephentoub]

IsEmpty doesn't forcibly synchronize with other threads. It will see a consistent view of memory, but there's no guarantee it sees the absolute up-to-date view of memory at that exact instant. But even if it did, that's a very weak guarantee (which is part of why it doesn't bother): by the time it gathered its answer, the state of the world could have changed.

[MaximGurschi]

@stephentoub Thank you for confirming. Yes i appreciate the race condition around interpreting the value in general. However my use case is very specific. If it helps, i am asking this in the context of implementing a BlockingCollection with the relaxed constraint that there is only one producing and one consuming thread. If i implement my own logic based on the Concurrentqueue (+ an atomic counter to alleviate the IsEmpty not being synched to other cores) i managed to beat the throughput of the BlockingCollection by ~3x.

[Clockwork-Muse]

If it helps, i am asking this in the context of implementing a BlockingCollection with the relaxed constraint that there is only one producing and one consuming thread.

... you may as well look for a specific SPSC (single-producer, single-consumer) queue, because those exist (they're simpler and faster).

If i implement my own logic based on the Concurrentqueue (+ an atomic counter to alleviate the IsEmpty not being synched to other cores) i managed to beat the throughput of the BlockingCollection by ~3x.

Why a BlockingCollection, though? Note that an atomic counter doesn't completely solve your problem, since you also have to prevent add/remove until you finish with whatever you were doing, at which point you might as well just lock around a normal Queue+int. The various concurrent ones give you "good enough" for a lot of cases (for example, throttling or sized buffers).

[MaximGurschi]

@Clockwork-Muse My trivial implementation still beats a lock + Queue with ~20%.

"prevent add/remove until you finish with whatever you were doing" - what do you mean by that? The atomic counter is used in combination with Monitor (Pulse/Wiat). The counter is required in my implementation to have a way to check that the ConcurrentQueue is empty to the signal the Monitor.Pulse.

[Clockwork-Muse]

@MaximGurschi - Then you're probably preventing add/remove until "you're done".

(although there's ways to still deadlock if you're not careful, but if you've got a working implementation you've likely engineered them out)

[MaximGurschi]

@Clockwork-Muse I think i see what you mean. No Add/Remove is not blocked while the removed item is "worked" on.

Add is roughly:
1.ConcQueue.Enqueue
2.var c= Increment counter
3.if (c==1) Lock Monitor.Pulse

Remove is roughly:
1.If (!ConcQueue.TryDequeue)
Loop Wait to be pulsed.
2.TryDequeu
3.Decrement counter

There is no blocking on the work being done.

[Clockwork-Muse]

@MaximGurschi - As described, consumer can deadlock.

Assume the queue is empty.

• Consumer - TryDequeue, fails
• Producer - Enqueue
• Producer - Increment, returns 1
• Producer - Pulse (recall that this only releases if the monitor object is already awaited)
• Consumer - Wait (deadlocks)

Switching to a single TryDequeue doesn't help. Changing the producer condition to c >= 1 (or c > 0) would solve the issue, but pulse more than you want. You could use a ManualResetEvent/Slim to cover for this.

The problem is that queue modification isn't atomic with respect to the wait, which is what you need.

[MaximGurschi]

@Clockwork-Muse There cannot be a deadlock using Monitor.Pulse/Wait in general. Wait relinquishes the lock. Are you describing a situation where the Consumer calls Wait that is never pulsed and hence waiting forever? That should also not happen i believe because of the Memory Barrier that Monitor Enter implies. If after step 4 above Consumer calls Wait then it must see IsEmpty=false, and avoid Waiting.

[MaximGurschi]

@stephentoub Excuse me but on the same line of thought of IsEmpty "freshness", does the same hold of TryDequeue? Looking at the implementation of TryDequeue - there are code paths that seem to lead to a similar effect, ie

there's no guarantee it sees the absolute up-to-date view of memory at that exact instant

, which means that some other thread T can see TryDequeue returning false when in fact another thread has completed Enqueue prior to T calling TryDequeue? Can you please clarify the "freshness" of TryDequeue?

[Clockwork-Muse]

@MaximGurschi - Ah, yes, that's what I meant, waits forever.

I retract my other comments, because I didn't understand how things were being used.

[stephentoub]

does the same hold of TryDequeue?

It uses full memory barriers, so if something is in the collection, it will find it. But that of course doesn't rule out the possibility that immediately after it checks and finds the collection empty and before it returns to the caller that some other thread has added something... no amount of synchronization in the queue's implementation would enable that.

[MaximGurschi]

@stephentoub Thank you for confirming that! I think then the code paths i talked about (that return false) in TryDequeue that only kick in if certain conditions are met imply certain causality that makes it safe to return false.