[concurrency-interest] Asynchronous-nature of ConcurrentLinkedQueue

Boehm, Hans hans.boehm at hp.com
Wed May 19 16:34:48 EDT 2010

> I was guessing that it would be sufficient to use a volatile 
> integer, and just live with the side effects of the data 
> races, performing explicit zeroing when the queue was empty.
I suspect that, in spite of folklore to the contrary, you rarely
want to do that sort of thing.  You still take the large performance hit
of all the coherence misses as ownership of the counter moves back and forth.
And, based on my own experience at least, the resulting value can easily be
complete junk.

It's not completely clear to me that incrementAndGet has to be more expensive,
at least on X86.  It could even conceivably be cheaper, since it may prevent
the case in which the cache line is stolen by another processor between the
load and the store, and you thus get two misses per operation.

Our garbage collector once had such a counter that kept track of reachable memory.
It was incremented for every traced object.

With two GC threads, the coherence misses had two effects:

1) The collector ran at around half speed, negating any parallel speedup.
2) The count was typically off by a factor of two.  I suspect that as a result
of the regular misses, the timing almost always worked out such that a store
took place between a load and a store in the other thread, losing half the counts.


More information about the Concurrency-interest mailing list