3 ms·

> most benchmarks show Java web-servers (of non-static content) to outperform or match C and C++ servers (http://www.techempower.com/benchmarks/#section=data-r6

> most benchmarks show Java web-servers (of non-static content) to outperform or match C and C++ servers (http://www.techempower.com/benchmarks/#section=data-r6&hw=i7... http://www.techempower.com/benchmarks/#section=data-r6&hw=i7...). Umm, there are no C or C++ servers in that benchmark, except for one extremely slow one I've never heard of. > and a high level of concurrency requires low contention, and low contention requires non-blocking data structures That really does not follow. Lock-free data structures are not about reducing contention, they are about eliminating blocking and improving performance when contention does occur. Contention occurs whenever multiple threads attempt to access the same resource, regardless of whether access to that resource is blocking or non-blocking. Lock-free data structures can still experience contention, and while they do not block, their performance does degrade under contention. Indeed later in your message you say that reference counting is a "huge contention point" -- refcounting a la C++'s shared_ptr is a lock-free algorithm. So while lock-free algorithms don't affect the amount of contention in the system, they do exhibit better performance under high contention, for the (small) subset of data structures that can be made lock-free. But this is only an issue when contention exists to begin with. Many highly parallel systems exhibit very low contention; for example, MapReduce. Even in systems with inherent contention, there are many strategies for reducing it, like partitioning and affinity schemes. > nonblocking data structures require either a GC, or some other method of automatic memory reclamation that's extremely hard to achieve in C++ (or any other language, for that matter) I'm not sure what is so hard about Hazard Pointers (http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf http://www.research.ibm.com/people/m/michael/ieeetpds-2004.p...). Maged Michael is a smart guy who figured this stuff out 10 years ago. But you don't even have to do it yourself. Non-blocking algorithms are extremely subtle by their nature (I hope you don't implement them yourself in Java; that would be a waste of effort). Just use an existing library like Thread Building Blocks, Grand Central Dispatch, etc. that are specifically designed to achieve maximum multi-threaded performance in C++.

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 ago
    Obviously. 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.

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 ago
  Obviously. 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.