7 ms·
Safety and Performance – Threadsafe Datastructures in C++
- lordnacho 5y agoSeems like it starts with some examples of what doesn't work well and then teases the reader with potential solutions, which don't have examples.
- huhtenberg 5y agoIt does read like at some point the OP got tired of writing and just wrapped it up with a to-do list.
- AndrewStephens 5y agoHa, this is my article. Believe me when I say I had developed a truly remarkable solution of this problem which this blog post is too small contain. More believably, this is a very basic introduction to the problem. More complex solutions are possible but are very tied to the specific datastructure and access patterns. It is hard to generalize advice once the problems get more involved so I just declared them out-of-scope and only mentioned some ideas in passing. Maybe I will write a part II sometime. The comments here are interesting.
- jhgb 5y agoSounds like the famous "How to Draw an Owl" tutorial. ;)
- MontagFTB 5y agoThis is why it isn’t called Amdahl's suggestion. The use of std::mutex (especially in frequently accessed structures) will bring your application to a grinding halt. Better solutions abound with concurrent sequential processes, or the Actor architecture.
- jeffbee 5y agoIt will only bring your application to a grinding halt if it's on the critical path. Most data in most programs can be protected with a plain old mutex and everyone is happy with the performance. Even on the hot path you may get trivial scaling to 2 or 4 threads with a global mutex protecting critical data, as we see with memcached. Sharing doesn't start to offend Amdahl until you have many threads and the critical section is relatively costly compared to the rest of the program.
- lumost 5y agoWorth calling out that the introduction of multiple locks can lead to deadlocks etc. It would actually make for a nice library to have lock acquisition decoupled from lock scope in the caller. Eg every call to lock acquire passes some identifier, and the lock implementation decides what it will do with that identifier eg global lock, scoped lock etc
- jeffbee 5y agoI find that thread safety annotations in clang help prevent deadlocks when there’s a tricky section.
- paskozdilar 5y agoAgreed. The problem with mutex is that it's often hard to get right, since it's a low-level primitive for serializing access to shared memory, and it does not compose (cannot atomically lock two mutexes). CSP/Actor model simply takes the problem that mutex solves on the low level - concurrency - and makes the whole world concurrent-by-default, so that mutexes are not needed. Note the 1st Go proverb [0]: "Don't communicate by sharing memory, share memory by communicating." [0] https://www.youtube.com/watch?v=PAAkCSZUG1c&t=168s https://www.youtube.com/watch?v=PAAkCSZUG1c&t=168s
- vore 5y agoSure you can compose mutexes: https://en.cppreference.com/w/cpp/thread/lock https://en.cppreference.com/w/cpp/thread/lock In practice, if you have a global total ordering of mutexes, it's safe to lock any number of them provided you lock them in order. CSP is interesting but it doesn't apply in a lot of cases, e.g. designing a lock striping mechanism over a database as described in the article would not be very fun with CSP or actors, as the article calls out at the bottom.
- gituliar 5y agoThe story is managable as long as we use local operations, like read/write a value. Once we need iterators (read "aggregate operations") life becomes tough. In this case only copy-on-write strategy seem to work, doesn't it ?
- jhgb 5y agoTransactional memory would presumably work...if someone bothered to implement it properly.
- dragontamer 5y agoI've spent a lot of time studying parallel compute over the past few years, trying to understand how GPU-algorithms are so fast. Use barriers. Many data-structures are safe if: 1. Everyone is reading at the same time. 2. Only one thread is writing to any particular location. How to accomplish these two facts? Again, use barriers. Take GPU-merge path algorithm for example. (GPU Merge-path is just a parallel-implementation of the "Merge-pass" of Merge-sort, normally taking O(N) time on sequential computers): 1. All threads read their relevant values from the array, and performs a binary search along the diagonal (read-only over the data-structure). Binary search is O(lg(n)) 2. Barrier, all threads wait for all other threads to be done reading. 3. Write the "merge path". 4. Barrier, wait for everyone to finish writing. 5. Everyone reads the "merge path", which is all you need to figure out the "final location" of any particular value in your merge-sort in O(lg(n)) time. 6. Everyone writes their value "magically" to the correct, sorted, position of the array. Because everyone is writing to a different array location, there's no contention or race-conditions. Since all steps are O(lg(n)), your Merge-path algorithm executes in O(lg(n)) time where n is the data-size and parallelism factor (ex: 10,000 element array has 10,000 processors), which is possible on modern GPUs. Bonus points: all SIMD computation is innately barrier based. That's what SIMD means after all: all simd-lanes execute the same instruction at any given time. If your processor is on a "load" instruction, everyone's reading. If the processor is on a "store" instruction, everyone is writing. (Modern GPUs are MIMD though, and require explicit "barrier" instructions and/or kernel invoke calls if the SIMD-units from other compute-units are cooperating) Your "only" job as the programmer, is to therefore, just ensure that those writes are to all different memory locations. A difficult job for sure, but doable on a wide variety of algorithms. ------------ Very, very few GPU-algorithms use mutexes or even atomics (!!!). The "bread and butter" is thread-barriers and enabling concurrent writes (by having everyone write to different locations of memory, as well as barriers to ensure the other threads are done reading or done writing).
- eternalban 5y agoConcurrent =/= parallel. CPU thread safety is mostly manifested [or let's say much more challenging] in context of concurrent, not parallel, algorithms. I'm not aware of anyone doing concurrent programming on the GPU (because it is a poor fit).
- titzer 5y agoI'm surprised they didn't try std::atomic_long or a compare-and-swap.
- waynesonfire 5y agowhy? it doesn't matter. that'll will only get you so far, as you scale, you'll still run into synchronization contention. Maybe going from 16 to 64 threads you'll get some nice wins, but so what? What are you going to do when you need to double the number of threads again?
- RcouF1uZ4gsC 5y agoA very nice approach for read heavy structures is the Left-Right algorithm. http://concurrencyfreaks.blogspot.com/2013/12/left-right-classical-algorithm.html?m=1 http://concurrencyfreaks.blogspot.com/2013/12/left-right-cla... It does cost an extra instance, but it generalizes to any data structure and gives you wait-free reads.
- jlokier 5y agoIt's a fine algorithm, but in left-right those atomic increments/decrements on read can be costly, up to some 200x slower than the read itself. The "wait until" steps in the writer can also be an issue if the atomic decrements in the reads are not signalling writer wakeups, in a pre-emptive scheduling environment. The description doesn't mention the memory barriers that are also required, and which are also a little costly on some architectures. This is still better than a mutex or reader-writer lock for performance. (But it has different read-after-write behaviour than a mutex, so they aren't directly comparable; sometimes you still need a mutex). Where possible and optimising specifically for wait-free read performance, I would aim for RCU-style reads for speed. RCU reads are as fast as normal reads, because they are atomic-free as well as wait-free, and on almost all architectures do not require barrier instructions either. However the writes are more expensive and sometimes a lot more complicated. It is possible to combine left-right and RCU into a hybrid algorithm that uses fixed memory with grace periods, to combine the no-allocation property with the fast atomic-free reads property.
- gigatexal 5y agoNot much in the way of new stuff here. Good use of mutexes are the norm. But I was thinking they’d show some novel atomic or lock free algos
- cjensen 5y agoOne nitpick with this: when the author first uses a mutex to ensure safety, he says "the operations took over 50 times longer!" Well sure. But "the operations" were single read and writes to a small array likely held in cache. For more complex data structs, it's easy to see that they would take ten times or more longer than reading from a fixed location -- leading to only a 5X slowdown. That might still be a lot, but I'm still going to nitpick the "50" comment :-)