6 ms·
Contention is not binary, or, rather, its effects aren't binary. A lock that is held for 10 microseconds potentially causes a lot more contention than a CAS tha
by pron 13y ago
Contention is not binary, or, rather, its effects aren't binary. A lock that is held for 10 microseconds potentially causes a lot more contention than a CAS that takes a few nanos. OTOH, thousands of short contentions are as bad as, or worse, than few long contentions (there's a whole great talk by Doug Lea about how Java's fork/join tricks modern CPU out of crazy power-saving optimizations to reduce thread wakeup time).
Intel's TBB were modeled after java.util.concurrent, BTW. Later, the Java memory model inspired the C++11 memory model (and the Java people were called to help with that, too). When it comes to concurrency, Java is usually at least 5 years ahead of C++ (perhaps with the exception of fork/join, which was inspired by Cilk, but has since come to surpass it).
> I'm not sure what is so hard about Hazard Pointers
Hazard pointers are expensive without RCU (the hazards need to be visible to other threads, which means store-load barriers), and RCU requires kernel cooperation, and besides this entire class of techniques is either very limited or incredibly complicated (what do you do if you have thousands of threads?). A good GC vs hazard pointers with or without RCU is like driving down a highway vs stumbling in a swamp when it comes to lock-free data structures.
Here's Herb Sutter on the issue (source: http://herbsutter.com/2011/10/25/garbage-collection-synopsis-and-c/ http://herbsutter.com/2011/10/25/garbage-collection-synopsis...):
All existing C++ garbage collectors, notably the Boehm collector, aren’t enough for many interesting uses for several reasons, the main one being that they’re conservative, not accurate. See Hans Boehm’s page Advantages and Disadvantages of Conservative Garbage Collection for more discussion of tradeoffs.
As usual, there’s something to standardize iff we want to enable portability. So in this case the question is whether it’s interesting to enable portable programs that rely on GC — and note that typically if they rely on GC, they rely specifically on accurate GC, not conservative “maybe-GC.” For example, C++11 atomics enable writing many kinds of portable lock-free code, but not all; we need a standard for #2 if we want to enable people to write portable lock-free singly-linked lists, where the only known practical algorithms require automatic (non-refcount) GC and so they cannot be implemented in portable C++ today without some nonportable platform-specific code underneath.
Again, appeals to hazard pointers fail because the obscure convolutions and limitations of hazard pointers only expose the limits of even the most heroic efforts to work around the lack of true automatic GC. The main contribution of hazard pointers, unfortunately, is that they thoroughly motivate why direct support for automatic GC is needed.
- haberman 13y ago> A lock that is held for 10 microseconds potentially causes a lot more contention than a CAS that takes a few nanos. See, if you're trying to compare those two things, you're comparing a lot more than locking vs lock-free; you're comparing two completely different designs. All you can do with a single CAS is a very primitive operation like queue enqueue/dequeue, stack push/pop, set add/remove, etc. If you're holding a lock for 10us you're doing a whole lot more than that; you're doing something that isn't possible to do lock-free, and your design is inherently less concurrency-friendly. If your experience comes from taking a coarse-grained mutex-heavy design in C++ and reimplementing it in Java with a design that communicates between threads only with lock-free data structures, then your results aren't indicative of locking vs. lock-free or C++ vs. Java. If you really want to compare locks vs. lock-free apples-to-apples, then use data structures that have the same API as your lock-free data structures, but are implemented by taking a lock for a very short amount of time -- just enough time for the operation you would have performed lock-free. And if you want to compare C++ vs. Java, use an equally concurrency-friendly design with both. If you're using high-performance lock-free data structures in Java, use the same in C++, since they are available in both. The memory management complications can be confined to the container library; at the application level exclusive ownership of objects can be passed from thread to thread.
- pron 13y agoObviously. But lock-free data structures in C++ are not as good as their Java counterparts (because of GC), and besides, most lock-free DS are often implemented in C++ several years after they're implemented in Java, if at all. For example, Java's nonblocking hash map (by Cliff Click) is still not available for C++, 6 years after its release. There are a few very limited/half baked implementations, but nothing "canonical" (and nothing so thoroughly researched, optimized and used). BTW, part of the reason is that the world's leading low-level concurrency researchers and implementers (Doug Lea, Nir Shavit and others) do most of their work in Java (most of my own work is designing non-blocking data structures, BTW; not that I'm comparing myself to Lea or Shavit in any way). To get a sense for the quality of Java data structure implementations, I strongly suggest you watch this talk by Doug Lea: https://www.youtube.com/watch?v=sq0MX3fHkro https://www.youtube.com/watch?v=sq0MX3fHkro His work is incredible. Even if you don't use Java, there is so much to learn in the talk. One of the coolest things there (which I already hinted at), is how to spin properly on modern Intel processors.