15 ms·
This is a decent, if space inefficient, implementation of an optimistically concurrent algorithm. The general idea is that all threads have the same "goal", so
by wwwigham 9y ago
This is a decent, if space inefficient, implementation of an optimistically concurrent algorithm. The general idea is that all threads have the same "goal", so if one thread notices partial work done by another thread (in this case, unupdated neighbors), then it does the work itself (checking to make sure its not already done before writing it) or moves on to work elsewhere instead. Many lock-free queues are based on this concept of work-finishing.
This is, however, storing 31 bits of generation-counter per bit of state to try to make the ABA linearization problem unlikely. Except it's using signed ints and doesn't account for overflow, so I think the behavior is going to get a bit less intended once the generation count hits 0x3FFFFFFF, rather than 0x7FFFFFFF; but I'm no expert on integer overflow in Java.
The claim that this is unsynchronized feels dubious, however! (Lock-free, sure! Unsynchronized? Not so fast!) This looks like it doesn't have synchronization primitives, but it _does_ - it has atomic reads and writes of ints [1]. (Thanks, Java!) So it never has to worry about reading partially updated data from a cell. If you were to try this in C, you'd potentially get piles of garbage as your thread is preempted partway through reading an int32 without a proper atomic intrinsic operation call.
[1] https://stackoverflow.com/questions/1006655/are-java-primitive-ints-atomic-by-design-or-by-accident https://stackoverflow.com/questions/1006655/are-java-primiti...
- omazurov 9y agoI'm not aware of any unsynchronized concurrent queue implementation. Being lock-free implies using Compare-And-Swap - a very powerful synchronization primitive. I agree that the current implementation won't survive integer overflow, Java or not. That's fixable, though. Theoretically, algorithm's description would still use unbounded integers. I disagree on atomic reads/writes. If the algorithm can deal with totally wrong values, why would partially wrong values make any difference? Atomic reads/writes certainly help with error probabilities but it's not clear to me to what extent. A C implementation will be as robust, Java doesn't add any magic here. A totally different CPU with no guarantee of atomic 4-byte updates would be needed. Do those exists?
- burgerdev 9y ago> I'm not aware of any unsynchronized concurrent queue implementation. Would the queues from https://www.liblfds.org/ https://www.liblfds.org/ qualify?
- omazurov 9y agoNo, as it clearly qualifies for the second part of my statement: > Being lock-free implies using Compare-And-Swap - a very powerful synchronization primitive. Just look inside https://github.com/liblfds/liblfds7.1.1/blob/master/liblfds7.1.1/liblfds711/inc/liblfds711/lfds711_porting_abstraction_layer_compiler.h https://github.com/liblfds/liblfds7.1.1/blob/master/liblfds7... It's full of synchronization stuff. By "unsynchronized" I mean NOT using that.