9 ms·

> If you're fighting with the JVM this much, why not just use C++? The problems were garbage collection, lack of control over memory layout, and bloated types.

by strlen 15y ago

> If you're fighting with the JVM this much, why not just use C++? The problems were garbage collection, lack of control over memory layout, and bloated types. Tool for the job, no? Here's why. Compare these two: http://hg.openjdk.java.net/jdk7/hotspot/jdk/file/9b8c96f96a0f/src/share/classes/java/util/concurrent/ConcurrentLinkedQueue.java http://hg.openjdk.java.net/jdk7/hotspot/jdk/file/9b8c96f96a0... <-- Doug Lea's java.util.concurrent.ConcurrentLinkedQueue https://github.com/afeinberg/lockfree/blob/master/src/lockfree_queue.cc https://github.com/afeinberg/lockfree/blob/master/src/lockfr... <-- my port of above to C++0x https://github.com/afeinberg/lockfree/blob/master/src/hazard_ptr_rec.cc https://github.com/afeinberg/lockfree/blob/master/src/hazard... <-- essentially an implementation of garbage collection that's needed to to work around the ABA problem tl;dr Shared memory concurrency is surprisingly hard with manual memory management. Not impossible, not infeasible, not impractical. Just hard. C++ is still a valid choice for many products: JVM isolates you from the underlying OS, the VM subsystem, and there are cases where the cost of garbage collection is prohibitive. However, I'll argue that vast majority of a site like Twitter (or LinkedIn, another high-scale JVM powered property) is best served by runtime like the JVM or CLR. Erlang is another great option, but it's more of something you'll have _along with_ JVM/CLR and C/C++: Erlang's model is (highly efficient, well abstracted) concurrency with message passing -- which is awesome, but not a full substitute for shared memory concurrency -- i.e., it's a great tool for some jobs, but not others. C++ makes more sense for things like a B+Tree implementation: I've been using a pure Java B+Tree implementation -- BerkeleyDB Java Edition, and can certainly mention the negatives of that approach. On the other hand, look at something like the routing layer of Voldemort, multi-Paxos implementation in ZooKeeper, or (as an example of another high scale, Java based service) the modified Paxos implementation in Google's MegaStore, non-storage parts of Amazon's SimpleDB (written at Java at one point, in Erlang at another -- not sure what it's written in now). I'll also argue that I'd rather use a less verbose and more functional language than Java -- and honestly, in some cases C++ far outdoes Java in terms of expressiveness. Go, Scala, languages in the ML family and Erlang (especially with tools like dialyzer and quick check, to get around the dynamic typing) are the right way forward for building highly concurrent user-land "systems-y" software (think more databases or distributed middleware than an OS) -- the parts where memory layout is critical and which tend to produce a lot of garbage can always be implemented in C/C++. tl;dr Programming language choice involves trade offs, Java is too verbose, but garbage collected languages/runtimes have their role in building highly scalable applications or service

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 ago
  Well, 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/

by strlen 15y ago

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 ago
Well, 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/