3 ms·
To be fair, the ConcurrentLinkedQueue class you linked to was apparently already so complex to implement that the developers had to go off the edge of type safe
by saurik 15y ago
To be fair, the ConcurrentLinkedQueue class you linked to was apparently already so complex to implement that the developers had to go off the edge of type safety into the land of sun.misc.Unsafe; given how much research you already need to understand to feel confident that this algorithm works at all, going the extra distance to understand hazard pointers (which I, at least, find refreshingly easy to understand in juxtaposition), seems minuscule. ;P
That said, since I've now taken the time to read your code, I have a suggestion that would drastically clean up the parts that are making the manual memory allocation feel "overtly manual": rather than allocating memory and then using the default placement new to construct your object, you could define a placement new/delete that operates over the allocator.
This not only would remove all of the reinterpret_cast<>s and sizeof()s from the queue code, but it would also allow a future modification where the queue was able to store values other than void *, while retaining exception safety (as when you template the Node by way of the Queue itself, its more complex constructor would suddenly be allowed to throw, and the memory would need to be collected).
- strlen 15y agoWell, you could also perform CAS using AtomicReference -- the examples in Maurice Herlihy's The Art of Multiprocessor Programming [1] and Brian Goetz' Java Concurrency In Practice [2] do that. So you don't really need to use sun.misc.Unsafe in your own code (of course, you need CAS to implement AtomicReference in the first place). You're also completely correct about placement new: I am working on a cleaned up version of this class, this was essentially a first pass to get myself more familiar with concurrency in c++0x. What complicates things a bit is that allocators are (much like all else in STL) meant to be used as class template arguments, which makes main separate compilation impossible -- hence the need of an adapter from an STL-style allocator to a pure virtual class. Separate compilation is why I also made a void* version of this initially. I have a much cleaned up version in the work that will handle more than void . There's an implementation I call it ConcurrentLinkedQueueImpl that handles just void , that is compiled separately -- and there is generic version ConcurrentLinkedQueue that is specialized for void * (ends up just proxying the calls to ConcurrentLinkedQueueImpl), with the generic version (in turn) using ConcurrentLinkedQueue<void *> and placement new to hold any type. Once again, the version posted there was a rough pass to get myself familiar with 0x concurrency constructs and hazard pointers -- the code is fairly messy. [1] http://www.amazon.com/Art-Multiprocessor-Programming-Maurice-Herlihy/dp/0123705916 http://www.amazon.com/Art-Multiprocessor-Programming-Maurice... [2] Everyone should read this book cover to cover -- http://jcip.net/ http://jcip.net/
- strlen 15y agoConcurrentLinkedQueue in jdk6, by the way, does not use Unsafe: http://hg.openjdk.java.net/jdk6/jdk6/jdk/file/b58af78ac79c/src/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java http://hg.openjdk.java.net/jdk6/jdk6/jdk/file/b58af78ac79c/s...