Saturday, January 18, 2014

A dissertation on the progress conditions of LongAdder

On a more "academic" note, I have some minor doubts on whether LongAdder::increment() may actually be blocking, the reasoning being the following:

Suppose that a thread has decided to create a new larger cells[] and as such, has set cellsBusy to 1, created a new cells[] with the first half of the entries copied from the old one, and the second half still at null, and then for some reason this thread goes to sleep for a very long time, leaving cellsBusy at 1.
Some other thread doing an increment() may end up on one of the new entries for which there is no Cell instance, and because cellsBusy is 1, it can't put in its own Cell instance, so, it will call "h = advanceProbe(h)" to get another index of cells[] through "a = cells[(n-1) & h]".

The advanceProbe() function uses a XorShift algorithm which has a very high period (maybe close to 2^31 ?), but we only use the last few bits of h to get a new index of cells[]. One could theoretically conceive that there is some seed h for which all of the calls to advanceProbe() return an h whose least significant bits are such that the index always falls in one of the cells that
is not yet allocated, and in that case, longAccumulate() would be blocking.
Even if such a thing is possible, it will certainly be a very unlikely event, and having into consideration the definition of lock-free taken from "The Art of Multiprocessor Programming":
"A method is Lock-Free if it guarantees that infinitely often some thread calling this method finishes in a finite number of steps" where the key part here is the "infinitely often", I'm still leaning towards saying that LongAdder::increment() is Lock-Free.

So why is this long and boring incursion into the (theoretical) progress conditions of LongAdder?
Well, LongAdder is one of the possible readIndicator implementations for the Left-Right technique, but the problem is that LongAdder is (at best) Lock-Free so if we use it, we lose the Wait-Free progress condition on the read operations provided by Left-Right mechanism... what we gain is the code simplicity and low memory usage  (kind of), because most of the complexity of the readIndicator gets abtracted away in the code for LongAdder.

If you don't know what LongAdder is you can check it out here:

Like I said, this is mostly academic  ;)

No comments:

Post a Comment