5 ms·

The Problem with Threads (2006) [pdf]

18 points by amzans 7y ago

bullen 7y ago
Another threads post another opportunity to discuss what I learned building a joint (on the same memory) parallel app. server: http://github.com/tinspin/rupy http://github.com/tinspin/rupy To fully use concurrency without monitors I think we need to accept the cost of cache misses. When Java rewrote the memory model of the JVM to allow for concurrent data structures they did something C/C++ still has not provided: a platform where you actually can build something that scales on many threads without causing more problems than it solves. To me this has divided the programming word into two: Avoid cache misses or use many threads. Pick one?!
- zzzcpan 7y ago
  Well, no, we don't need to accept that cost, it's just a constraint for a concurrency model to choose, i.e. maximizing locality. Apart from that another big one for massively multicore systems is minimizing cross-core synchronization. You can meet both, just not with threads as your programming model.
  - bullen 7y ago
    So what would you use instead of threads? How do you mean "maximizing locality"? My intuition is that the reason Java can be concurrent is that it uses a VM that incurs cache misses on all IO. So in practice you can't have both. In C you can try to use locks to achieve something but for a long time of development you will be in dead-lock and race condition hell.
- nwallin 7y ago
  What problems do you have with C++? Pre-C++11, threading was basically unusable, but since then with std::async, STL mutexes, RAII lock guards, condition variables, atomic types, etc, writing multithreading code in C++ is downright pleasant. Also std::scoped_lock in C++17 basically eliminates the possibility of deadlocks. I generally don't use them much though, because I'm diligent about const correctness. There's no need to lock to protect a const object or data structure. I actually have more trouble dealing with multithreading in Java and C# than in C++ because I can't leverage const.
  - bullen 7y ago
    This makes no sense, const is read-only memory! Specifically the challenge is joint (on the same memory) parallelism, I guess I need to add "on the same read+write memory"? The problem with C++ when it comes to threads is that there is no concurrent library (by default) that has any chance of not locking; which is bad for performance and hard to debug.
    - nwallin 7y ago
      Exactly. There are three types of data: 1. read only data should be abundant and shared. Ideally this is the most common type of data. 2. Private read/write data (that no other threads have access to) can be arbitrarily common. Ideally this is the second most common type of data. 3. Shared read/write data should be rare. Accessing data that needs to be protected by concurrency primitives (atomic operations, mutexes, critical sections, etc) will always be slower than data that doesn't. Java makes type one data hard and type three data easy. C++ makes type one data easy and type three data explicit. While Java's model of "everything has a pointer indirection+virtual function table lookup cost associated with it" certainly has its downsides, IMHO the fact that C++ lends itself to type one data and Java lends itself to type three data is the major reason normal C++ code by normal C++ programmers tends to be so much faster than normal Java code by normal Java programmers. For instance. You have a data structure, (perhaps a hash table) and you periodically need to scan all its elements, adding some, deleting some, and modifying some. 1. A Java programmer will reach for the concurrent hash table in the standard library, split the work up into multiple threads, and rely on the concurrent nature of the hash table to protect them. This will result in a very large number of mutex locks, incurring a significant performance penalty. 2. A C++ programmer who recently came to C++ from Java will do the same thing. But they'll manually lock on a mutex shared between all the threads doing the work, and it will be just as slow but less elegant. 3. A C++ programmer who's more familiar with the language will use parallel std::transform_reduce. Modifications can be done in place, and it will return/reduce a pair of insertion/deletion lists which will be done in bulk in a single thread after all the threads have completed work. This will emit very few concurrency primitives (probably just 1-2 per thread) and will be significantly faster than the Java version, despite the fact that the insertions/deletions are done in a single thread. 4. If modifications in place are rare, it could return a tuple of insertion/deletion/modification lists, and be given const references instead of mutable ones. (by using .cbegin() and cend() instead of .begin() and .end()) Solutions 1 and 2 are implicitly type three data. 3 is type two data. 4 is type one data. 3 and 4 will always be much faster than 1 and 2, and whether 3's improved performance over 4 is significant depends on how common modifications are. The point is, C++ makes the fast option easy, the slow option annoying but doable. > The problem with C++ when it comes to threads is that there is no concurrent library (by default) that has any chance of not locking; Define "not locking"? If you mean it lacks data structures for type three data, see above. If you mean it's easy to cause deadlocks, std::scoped_ptr solves that.

18 points by amzans 7y ago

Another threads post another opportunity to discuss what I learned building a joint (on the same memory) parallel app. server: http://github.com/tinspin/rupy http://github.com/tinspin/rupy To fully use concurrency without monitors I think we need to accept the cost of cache misses. When Java rewrote the memory model of the JVM to allow for concurrent data structures they did something C/C++ still has not provided: a platform where you actually can build something that scales on many threads without causing more problems than it solves. To me this has divided the programming word into two: Avoid cache misses or use many threads. Pick one?!

zzzcpan 7y ago
Well, no, we don't need to accept that cost, it's just a constraint for a concurrency model to choose, i.e. maximizing locality. Apart from that another big one for massively multicore systems is minimizing cross-core synchronization. You can meet both, just not with threads as your programming model.
- bullen 7y ago
  So what would you use instead of threads? How do you mean "maximizing locality"? My intuition is that the reason Java can be concurrent is that it uses a VM that incurs cache misses on all IO. So in practice you can't have both. In C you can try to use locks to achieve something but for a long time of development you will be in dead-lock and race condition hell.
nwallin 7y ago
What problems do you have with C++? Pre-C++11, threading was basically unusable, but since then with std::async, STL mutexes, RAII lock guards, condition variables, atomic types, etc, writing multithreading code in C++ is downright pleasant. Also std::scoped_lock in C++17 basically eliminates the possibility of deadlocks. I generally don't use them much though, because I'm diligent about const correctness. There's no need to lock to protect a const object or data structure. I actually have more trouble dealing with multithreading in Java and C# than in C++ because I can't leverage const.
- bullen 7y ago
  This makes no sense, const is read-only memory! Specifically the challenge is joint (on the same memory) parallelism, I guess I need to add "on the same read+write memory"? The problem with C++ when it comes to threads is that there is no concurrent library (by default) that has any chance of not locking; which is bad for performance and hard to debug.
  - nwallin 7y ago
    Exactly. There are three types of data: 1. read only data should be abundant and shared. Ideally this is the most common type of data. 2. Private read/write data (that no other threads have access to) can be arbitrarily common. Ideally this is the second most common type of data. 3. Shared read/write data should be rare. Accessing data that needs to be protected by concurrency primitives (atomic operations, mutexes, critical sections, etc) will always be slower than data that doesn't. Java makes type one data hard and type three data easy. C++ makes type one data easy and type three data explicit. While Java's model of "everything has a pointer indirection+virtual function table lookup cost associated with it" certainly has its downsides, IMHO the fact that C++ lends itself to type one data and Java lends itself to type three data is the major reason normal C++ code by normal C++ programmers tends to be so much faster than normal Java code by normal Java programmers. For instance. You have a data structure, (perhaps a hash table) and you periodically need to scan all its elements, adding some, deleting some, and modifying some. 1. A Java programmer will reach for the concurrent hash table in the standard library, split the work up into multiple threads, and rely on the concurrent nature of the hash table to protect them. This will result in a very large number of mutex locks, incurring a significant performance penalty. 2. A C++ programmer who recently came to C++ from Java will do the same thing. But they'll manually lock on a mutex shared between all the threads doing the work, and it will be just as slow but less elegant. 3. A C++ programmer who's more familiar with the language will use parallel std::transform_reduce. Modifications can be done in place, and it will return/reduce a pair of insertion/deletion lists which will be done in bulk in a single thread after all the threads have completed work. This will emit very few concurrency primitives (probably just 1-2 per thread) and will be significantly faster than the Java version, despite the fact that the insertions/deletions are done in a single thread. 4. If modifications in place are rare, it could return a tuple of insertion/deletion/modification lists, and be given const references instead of mutable ones. (by using .cbegin() and cend() instead of .begin() and .end()) Solutions 1 and 2 are implicitly type three data. 3 is type two data. 4 is type one data. 3 and 4 will always be much faster than 1 and 2, and whether 3's improved performance over 4 is significant depends on how common modifications are. The point is, C++ makes the fast option easy, the slow option annoying but doable. > The problem with C++ when it comes to threads is that there is no concurrent library (by default) that has any chance of not locking; Define "not locking"? If you mean it lacks data structures for type three data, see above. If you mean it's easy to cause deadlocks, std::scoped_ptr solves that.