[concurrency-interest] How bad can volatile long++ be?

Boehm, Hans hans.boehm at hp.com
Mon Dec 10 14:19:29 EST 2007


In Java, ++ on volatiles is not atomic.  I strongly recommend against maintaining even statistical counters that way.  Use either java.util.concurrent.atomic.AtomicLong or per-thread counters.

The following non-Java anecdote from several years ago convinced me of this:

Our conservative garbage collector used to optionally maintain approximate counts of live objects this way, by having each GC thread increment a shared counter as it found a live object.  There are as many GC threads as processors.  After observing some misbehavior on a dual processor (2 sockets, 1 core/socket) machine, and tracking down what was going on, I discovered that:

1) Maintaining the shared counter slowed down the collector by about a factor of two, negating the benefit of running on two processors.

2) The final count was consistently off by about a factor of two.

The cause for (1) was no doubt contention on the cache line containing the counter.  As a result of that, both threads spent a lot of their time waiting on that cache line, and presumably the timing worked out such that there was a high probability the line got stolen between the load and the store of the ++, resulting in the loss of about half the updates.

(In the proposed C++ standard, ++ on atomic<long> WILL be atomic, as for java.util.concurrent.atomic.getAndAdd.  However, in the C++ case, ++ on a shared ordinary or volatile variable will result in completely undefined behavior, meaning your e-commerce app is allowed to start playing Rogue-O-Matic instead if you do this.  Indeed, those are the current rules for (C or C++) and pthreads.  Thus you definitely don't want to do this in C or C++ code.  Clearly I did not follow this advice in the above example, but the code has since been fixed. )

Hans

> -----Original Message-----
> From: concurrency-interest-bounces at cs.oswego.edu
> [mailto:concurrency-interest-bounces at cs.oswego.edu] On Behalf
> Of Chris Purcell
> Sent: Monday, December 10, 2007 10:04 AM
> To: Sam Berlin
> Cc: Concurrency-interest at cs.oswego.edu
> Subject: Re: [concurrency-interest] How bad can volatile long++ be?
>
> I can't answer with authority whether ++ is atomic; I don't
> believe so. However, I can answer the rest of the question.
>
> The reads and writes will be atomic. Even so, the
> non-atomicity of the increment may still result in a wildly
> wrong number being produced.
>
> As an example, consider two threads incrementing a shared
> counter like this a thousand times each. If the counter
> starts at zero, in one unlikely but possible execution
> history, the final value of the counter may be only 2. That
> is, one thousand nine hundred and ninety eight increments can
> be lost. (The same final value is possible for any number of
> threads and any number of increments.)
>
> If you're only maintaining statistics, however, the
> inaccuracy of the counter shouldn't be an issue.
>
> Cheers,
> Chris
>
> On 12/10/07, Sam Berlin <sberlin at gmail.com> wrote:
> > Hi Folks,
> >
> > I'm fairly certain that ++ is not an atomic operation, even on
> > volatile variables, on longs (and quite possibly ints).
> Given that is
> > true (which it very well might not be), is it suspectible
> to problems
> > where a wildly wrong number can be produced (due to different bytes
> > being updated at different times from different threads),
> or will it
> > just cause some increments to effectively not happen?
> >
> > Thanks!
> >  Sam
> > _______________________________________________
> > Concurrency-interest mailing list
> > Concurrency-interest at altair.cs.oswego.edu
> > http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
> >
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at altair.cs.oswego.edu
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>



More information about the Concurrency-interest mailing list