9 ms·
A collection of lock-free data structures written in standard C++11
- bluGill 3y agoFrom the FAQ: > The biggest reason you would want to use a lockfree data structure in such a scenario would be performance. Locking has a non-neglegible runtime cost on hosted systems as every lock requires a syscall. This is misleading. While a lock does have a runtime cost, in some cases that cost is less than all the force CPU cache synchronization calls that lock free needs to do. With a lock you only have to sync once, after all the operations are done. You need to carefully measure this to see which is more performant for your application.
- dnedic 3y agoThe linked talk from Herb Sutter says as much, but it is a good suggestion to make that visible upfrontm, thanks. Additionally, cacheline alignment of indexes is something that's there to mitigate the false sharing phenomenom and reduce some of the cache synchronization cost.
- planede 3y agoMoreover, is "every lock requires a syscall" accurate? Probably depends on target platform and standard library, but my impression was that at low contention it doesn't really require syscalls, at least on Linux and glibc's pthread.
- kevincox 3y agoDefinitely not. I don't think there many standard libraries that use syscalls for every lock. It is near universal to attempt a lock in user space (maybe even spin a few times) and only call the kernel if you need to wait. So low-contention locks should very rarely make a syscall.
- adzm 3y agoCritical sections in Windows certainly behave this way with a configurable spin count.
- m4nu3l 3y agoThat's my understanding too. In Linux mutexes are implemented by futexes (Fast User-Space mutexes). If there is no contention they are guaranteed to not perform a syscall https://en.wikipedia.org/wiki/Futex https://en.wikipedia.org/wiki/Futex
- cout 3y agoMaybe this has changed, but last time I looked at futexes there was no syscall for locking (assuming no contention), but unlocking always made a syscall. This was many years ago so it could be different now.
- m4nu3l 3y agoThe code isn't the easiest to read but in glibc it seems that the syscall is only performed if waiters are detected in userspace during an unlock operation https://github.com/lattera/glibc/blob/master/nptl/pthread_mutex_unlock.c#LL161C2-L161C16 https://github.com/lattera/glibc/blob/master/nptl/pthread_mu...
- gpderetta 3y agoIndeed You only need to FUTEX_WAKE if you know there are waiters (or of you lost track of the number of waiters).
- m4nu3l 3y agoWhat can cause the mutex to lose track of the number of waiters?
- ot 3y agoGenerally you have a small number of bits to count the waiters, because the mutex state has to be a word you can CAS and so you have either 32 or 64 bits to pack all the state you need. If your counter saturates you lose track of the waiters, and you have to fallback somehow.
- maldev 3y agoYou can literally just do an atomic swap on some memory location. Three lines of assembly, like. mov rax, 1 ; load the value to exchange into rax acquire_lock: ; attempt to acquire the lock xchg byte [ADDR_LOCK], al ; atomically swap the lock value with rax test al, al ; test if the original lock value was 0 (unlocked) jnz acquire_lock ; if it was not, loop until we can acquire the lock The downside is you want a backoff to sleep the thread so it doesn't go into a loop. But the actual lock code is simple. You can easily have this be your function "AcquireLock()" and then do while(!AcquireLock()) { //pause thread execution. } And I think this is where they get the syscall being needed, since this will normally require a syscall to pause the thread from the scheduler.
- RcouF1uZ4gsC 3y agoFor me the biggest benefit of lock free programming is avoiding deadlocks. Locks are not composable. Unless you are aware of what locks every function in your call tree is using, you can easily end up with a deadlock.
- ot 3y agoThis is true in principle and it is good calling it out, but in practice I've never seen a mutex-based data structure beat an equivalent lock-free data structure, even at low contention, unless the latter is extremely contrived. A mutex transaction generally requires 2 fences, one on lock and one on unlock. The one on unlock would not be strictly necessary in principle (on x86 archs the implicit acquire-release semantics would be enough) but you generally do a CAS anyway to atomically check whether there are any waiters that need a wake-up, which implies a fence. Good lock-free data structures OTOH require just one CAS (or other fenced RMW) on the shared state. Besides, at large scale, no matter how small your critical section is, it will be preempted every once in a while, and when you care about tail latency that is visible. Lock-free data structures have more predictable latency characteristics (even better if wait-free).
- OskarS 3y agoAssuming low or no contention, it is easy to imagine a scenario where a mutex vastly outperforms it: if you need to push a 1000 things into the queue, it's still just two fences for the mutex but it's now a 1000 CASes. Moreover: the point with mutexes is that your data structure can be the optimized assuming no thread-safety. There are lots of, like, hyper-optimized hash table variants (with all sorts of SIMD nonsense and stuff) that are just not possible to do lock-free. The very "lock-freedomness" of the datastructure slows it down enough that in low contention scenarios mutexes clearly would outperform them without being particularly contrived.
- dnedic 3y agoThis is why you would use the Ring Buffer or Bipartite Buffer to place 1000 elements at a time, not the queue. Check the documentation for more info.
- deleted 3y ago[deleted]
- ot 3y agoIf you are going to do batch operations, your data structure should be optimized to support them, so you're back to one CAS. The same would apply to the locked scenario, where you probably don't want to copy 1000 elements in the critical section. About the sufficiently smart optimizations, sure, everything is easy to imagine, but in my experience this never happened, and I'd be curious to hear practical examples if you have any.
- smat 3y agoI assume the author of the library works under a hard real-time constraint. Under such circumstances (an example would be low latency audio) you can not tolerate the latency impact of a sporadic syscall.
- duped 3y agoYou often can tolerate the latency. The problem of locks is they are potentially unbounded and you can miss a deadline. It's not about performance so much as determinism.
- bluGill 3y agoLock free doesn't solve this. One thread will always make progress, but you have no way to ensure it is your thread so you can miss a deadline with lock free. When the data is under a lot of contention across many cores this is an issue (most of us don't have hundreds of cores so we don't see this). Generally lock-free is better for these situations as odds are when you hold a lock at least some CPU cycles are used for something that isn't directly modifying the data that needs the lock - those cycles the other CPU can touch it when lock-free. (note that when using a lock there is a trade-off, often it is better to hold the lock for longer than needed instead of dropping, doing a couple operations and then locking again)
- tialaramex 3y agoIf you must make progress locally (not just globally) the guarantee you need is wait freedom which is even stronger than lock freedom. (All wait free algorithms are lock free because necessarily if every thread is guaranteed to eventually make progress then overall progress is definitely made)
- quietbritishjim 3y agoPerhaps, but that is almost the opposite of what they said: in hard real time you can tolerate a longer average latency in return for needing a shorter maximum latency. That matches from what I would expect from a lock free data structure. But that doesn't match the (dubious) claim that locks are usually slower.
- ashvardanian 3y agoBoth lock-free and mutex-based approaches have their applications. The general rule of thumb, for 2-4 threads in the same NUMA node lock-free is faster. Need more cores? Use a proper heavy mutex.
- dragontamer 3y agoPikus has a number of C++ Parallelism performance talks that discusses this issue. In particular, the "cost of synchronization" is roughly the price of a L3 memory read/write, or ~50 cycles. In contrast, a read/write to L1 cache is like 4 cycles latency and can be done multiple times per clock tick, and you can go faster (IE: register space). So an unsynchronized "counter++" will be done ~4-billion times a second. But a "counter++; sync()" will slow you down 50x slower. That is to say, the "sync()" is the "expensive part" to think about. ------------ A lock is two sync() statements. One sync() when you lock, and a 2nd sync() when you unlock. Really, half-sync() since one is an acquire half-sync and the other is a release half-sync. If your lock-free data structure uses more than two sync() statements, you're _probably_ slower than a dumb lock-based method (!!!). This is because the vast majority of lock()/unlocks() are uncontested in practice. So the TL;DR is, use locks because they're so much easier to think about. When you need more speed, measure first, because it turns out that locks are really damn fast in practice and kind of hard to beat. That being said, there's other reasons to go lock-free. On some occasions, you will be forced to use lock-free code because blocking could not be tolerated. (Ex: lock-free interrupts. Its fine if the interrupt takes a bit longer than expected during contention). So in this case, even if lock-free is slower, the guarantee for forward progress is what you're going for, rather than performance. So the study of lock-free data-structures is still really useful. But don't always think of for performance reasons, because these data-structures very well will be slower than std-library + lock() in many cases.
- gpderetta 3y agoA sync, assuming it is your typical memory barrier, is not bound by the L3 latency. You pay (in first approximation) the L3 cost when you touch a contended cache line, whether you are doing a plain write or a full atomic CAS. Separately fences and atomic RMWs are slower than plain read/writes, but that's because of the (partially) serialising effects they have on a CPU pipleline, and very little todo with L3 (or any memory) latency. Case in point: A CAS on intel is 20ish cycles, the L3 latency is 30-40 cycles or more. On the other hand you can have multiple L3 misses outstanding, but CAS hardly pipelines.
- 3y ago
- bcrl 3y agoThis is why RCU, aka Read-Copy-Update, exists. RCU avoids the expensive synchronization part by delaying the release of the older version of the data structure until a point at which all CPUs are guaranteed to see the new version of the data. The patents have now expired, so it's worth investigating for people that need to write high performance multithreaded code that hits certain shared data structures really hard.
- andersced 3y agoShould be benchmarked against -> https://github.com/Deaod/spsc_queue https://github.com/Deaod/spsc_queue If proven faster OK.. If not.. Well.. back to the drawing board. I gave it a try -> https://github.com/andersc/fastqueue https://github.com/andersc/fastqueue Deaod is the kingpin.
- jcelerier 3y agohttps://max0x7ba.github.io/atomic_queue/html/benchmarks.html https://max0x7ba.github.io/atomic_queue/html/benchmarks.html for an existing set of benchmarks where this could be added
- whiteboardma 3y agoI've only looked at the queue implementation, but both push and pop contain obvious race conditions; I would highly suggest adding tests that actually use the data structures from multiple threads.
- dnedic 3y agoCould you elaborate on the alleged race conditions? Any advice on reliably testing the race conditions? The problem with adding those is the fact that they will give lots of false negatives and if you rely on them you have a problem.
- whiteboardma 3y agoLooking at the Push operation defined in queue_impl.hpp, if multiple threads perform concurrent pushes, they might end up writing their element to the same slot in _data since the current position _w is not incremented atomically
- dnedic 3y agoThis is a multi producer scenario, the README clearly states that these data structures are only single producer single consumer multi thread/interrupt safe. I will also add disclaimers to the javadocs comments on methods just to reduce confusion.
- whiteboardma 3y agoWops, my bad
- ape4 3y agoJust add a lock ;)
- gjadi 3y agoYou could use TLA+ to model the data structure operations and check the invariant. Checking the invariant with assert is also useful in my limited experience with concurrency. https://lamport.azurewebsites.net/tla/tla.html https://lamport.azurewebsites.net/tla/tla.html
- Notbrainiac 3y agoEvery datastructure is lock free. Locks are required when you have multiple writers. The article states the usefull only for certain circumstance: for single consumer single producer scenarios. So yea within these assumptions you can make something work.
- jimktrains2 3y agoYou may need a lock if you have operations that are not atomic, even with a single writer, as a reader could find an inconsistency.
- ot 3y agoThis seems unnecessarily pedantic. Lock-free conventionally implies concurrent, otherwise it's meaningless.
- dnedic 3y agoEven in single producer single consumer scenarios you need locks for multithreaded/interrupt use if you're not properly using atomics and proper fences.
- elbigbad 3y ago[flagged]
- Koshkin 3y agoNote that "lock-free" is a technical term that has a very specific, precise meaning (implying that the user of the structure does not need to use locking explicitly).
- josephcsible 3y agoLock-free doesn't mean "doesn't have locks". It means "doesn't need locks to be used concurrently".
- asmnzxklopqw 3y ago[flagged]
- 12323 3y ago[flagged]
- cjensen 3y agoAn issue in C++ is that it only supports atomic changes to the builtin types. For example, you can only CAS a 64-bit value if your largest integer/pointer type is 64-bits. Good lock free algorithms use double-width instructions like cmpxchg16b which compare 64-bits but swap 128-bits. You can then use the compared 64-bits as a kind of version number to prevent the a-b-a problem. Using only the built-in atomics is working with a hand tied behind your back. With the wider version, it's trivial to write multi-producer multi-consumer stacks with no limits to the number of objects stored. It's also pretty easy (if you copy the published algorithm) to do the same with queues.
- dnedic 3y agoTrue, that would help immensely in creating MPMC data structures, but as these are SPSC there is no problem. Also to clarify, this is only for the indexes, the data members can be anything. Using these intrinsics or inline assembly would break portability or create situations where platforms have different feature levels, which is not something I intend to do. I want the library to be compatible with everything from a tiny MCU to x86.
- hedora 3y agoI've had good luck assuming double-word CAS, portability-wise. Old ARMs have 32 bit pointers, so 64 bit CAS is pretty good. The main problem is that some algorithms go from a bit under 64 bits for a nonce to a bit under 32, which starts to get into "this could hit in practice" territory.
- gpderetta 3y agoActually C++ only requires TriviallyComparable for std::atomic. The issue with 2CAS is that intel until very recently only provided cmpxchg16b[1] but no 128 atomic load and stores: SSE 128 bit memory operations were not guaranteed to be atomic (and in fact were observed not to be on some AMDs). So a 128 bit std::atomic on intel was not only suboptimal as the compiler had to use 2cas for load and stores as well, but actually wrong as an atomic load from readonly memory would fault. So at some point the ABI was changed to use the spinlock pool. Not sure if it has changed since. If you do it "by hand", when you only need a 2cas, a 128 bit load that is not atomic is fine as any tearing will be detected by the CAS and 'fixed', but it is hard for the compiler to optimize generic code. [1] which actually does full 128bit compare and swap, you are probably confusing it with the Itanium variant.
- kilotaras 3y ago- A lot of code won't work for types with no default constructors, but that is at least compile error - Using memcpy[0] for arbitrary types is just wrong, see [1] [0] https://github.com/DNedic/lockfree/blob/main/lockfree/inc/bipartite_buf_impl.hpp https://github.com/DNedic/lockfree/blob/main/lockfree/inc/bi... [1] https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p1144r7.html#non-trivial-samples https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p11...
- dnedic 3y agoThis is already noted in the Queue readme, only the Queue constructs the type, the other 2 data structures are meant for PODs only. I will take a look at adding support for constructing in-place for the other 2 data structures, but at the moment, they are just for PODs.
- jylam 3y agoMaybe I don't understand the concept, but aren't lock-free structures "just" delegating the locking mechanism to the CPU via atomic operations ? (although even if that's the case I can understand the speedup) (and if so, why aren't all those lockfree structures the default, instead of using mutexes ?)
- gpderetta 3y agoAtomic operations can't be meaningfully said to perform any locking. In any case lock-free is defined in term of progress guarantees.
- samsquire 3y agoI think I lean towards per-thread sharding instead of mutex based or lock free data structures except for lockfree ringbuffers. You can get embarassingly parallel performance if you split your data by thread and aggregate periodically. If you need a consistent view of your entire set of data, that is a slow path with sharding. In my experiments with multithreaded software I simulate a bank where many bankaccounts are randomly withdrawn from and deposited to. https://github.com/samsquire/multiversion-concurrency-control https://github.com/samsquire/multiversion-concurrency-contro... ShardedBank.java ShardedBank2.java ShardedBankNonRandom.java ShardedHashMap.java ShardedNonRandomBank2.java ShardedTotalOrder.java ShardedTotalRandomOrder.java I get 700 million requests per second over 12 threads due to the sharding of money over accounts. Here I prioritise throughput of transacitons per second over balance checks (a consistent view of the data). I am also experimenting with left-right concurrency control which trades memory usage for performance, it basically keeps two copies of data, one that is currently being read and written to and another inactive copy that is not active. You switch the data structures around periodically to "make changes visible" to that thread.
- saagarjha 3y agoThis is a great way to structure your code if it’s possible to do so, but this isn’t always the case unfortunately :(
- up2isomorphism 3y agoDuring my entire career as a system programmer, I only see 1 situation where lock free is actually justified, 99% percent of the time it is completely unnecessary and even harmful.