8 ms·
From 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 runtim
by bluGill 4y ago
From 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 4y 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 4y 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 4y 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 4y agoCritical sections in Windows certainly behave this way with a configurable spin count.
- m4nu3l 4y 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 4y 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 4y 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 4y agoIndeed You only need to FUTEX_WAKE if you know there are waiters (or of you lost track of the number of waiters).
- m4nu3l 4y agoWhat can cause the mutex to lose track of the number of waiters?
- ot 4y 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 4y 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 4y 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 4y 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 4y 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 4y 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 4y ago[deleted]
- ot 4y 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 4y 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 4y 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 4y 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 4y 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 4y 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 4y 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 4y 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 4y 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.
- 4y ago
- bcrl 4y 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.