9 ms·
Lock-free multithreading with atomic operations
- amelius 7y agoI think "lock free" is a misnomer because in many cases these atomic operations still perform locks at the hardware level.
- gambiting 7y agoI was about to say - purely atomic operations are neither guaranteed to be limited to a single operation, nor they are guaranteed to not have any hardware locks. Yes, such lock is "faster" than a kernel-level locking object(mutex), but you can have unexpected side effects - on the AMD Jaguar architecture(so on PS4 and XB1) you need to be careful because cores are split into two blocks, and cores in one block don't really know what the other block is doing - so issuing an atomic add for instance has the unexpected downside of locking the entire CPU while the caches are synchronized so that you don't end up with two separate cores running on different blocks incrementing the same variable.
- kccqzy 7y agoOn the hardware level for example the x86 some of these atomics translate into instructions with the lock prefix which locks the bus. It's different from the usual "lock" concept in concurrent programming.
- amelius 7y agoIt's still a lock in the sense that it momentarily prevents another process from using a resource.
- kccqzy 7y agoIt is different. The lock prefix in x86 is only relevant in a multiprocessing (i.e. parallel) environment. But the general concept of locking is applicable to concurrent environments as well. For example when there are multiple processes on a uniprocessor machine, you still need to use locks (mutexes) which are implemented using, say, cmpxchg8b (atomically compare and exchange eight bytes), but in the absence of a second processor there's no need to use the lock prefix. Here on a machine level there's never really on any locking, but on an application level you are using locks.
- denormalfloat 7y agoThe correct term to use here is blocking. The hardware bus locks finish in a bounded amount of time and allow the other processors to eventually make progress.
- amelius 7y agoThat is a good distinction, but I'm not sure if it's always true. A peripheral device on a shared bus could still hold the lock for an undetermined time.
- jasonwatkinspdx 7y agoWhen people say "lock the bus" they don't literally mean it's like there's a single bus and mutex. Atomic operations execute atop the cache consistency protocol, which typically looks like: https://en.wikipedia.org/wiki/MOESI_protocol https://en.wikipedia.org/wiki/MOESI_protocol It is indeed true that atomic operations will execute in a bounded time, and processors generally provide fairness guarantees as well.
- amelius 7y agoYes, and the cache hierarchy ultimately depends on the memory bus. I suppose this bus, which may be shared with many other devices, doesn't always have bounded-time guarantee.
- gpderetta 7y agoEven to main memory there is not necessarily a single memory bus. Intracore or even intrasocket synchronization need not (and usually doesn't) go through main memory anyway.
- amelius 7y agoTrue, but some atomic instructions may need to access main memory to complete their operation. Whether shortcuts can be taken in most cases is not relevant for worst-case considerations.
- gpderetta 7y agoThe only resource that is held exclusively during an RMW is a single cache line, and that's not due to the lock prefix.
- gpderetta 7y agoOutside of some very exotic scenarios, this hasn't been the case for about 20 years.
- zlynx 7y agoI read about one recently where an evil user program was able to bring a 28 core Xeon to its knees. Apparently a LOCK INC on an unaligned value that hangs over a page boundary forces this super-advanced CPU to lock everything in every cache as if it was a 386.
- gpderetta 7y agoYes, That's the very exotic scenario I had in mind:)
- fulafel 7y agoX86 use MESI derivative directory-based cache coherency protocols on the cache line level (when synchronizing across sockets), bus-locking was probably in the 486/Pentium 1 days when bus snooping was used.
- jrockway 7y agoI think thinking about write barriers as locks is slightly misleading. Rather it brings the real world into a state that looks like what a computer program executing from top to bottom would look like. Results of speculative execution are discarded. The differing views onto main memory of different processor caches are made consistent. If you think context switches are expensive, then this is also expensive, but in a different way. Nothing is ever locked, but certainly the computer slows down from its maximum performance potential. (But there are many similar effects that happen even without atomic operations, like mis-predicting a branch.) My experience in using both is that sometimes profiling dictates that a lock is too expensive. I used to maintain a program that incremented a counter from hundreds of threads. Using an OS-level mutex to achieve this resulted in way too many context-switches, to the point where we were only using about 30% of the CPU to run our program and the rest of the CPU time was spent on OS-level housekeeping. Using atomic load/store was much faster. Enqueuing all the writes in a thread-local counter and flushing them to the global structure in an OS lock was the fastest, but only provided eventual consistency.
- beagle3 7y ago"lock free" regards to being free from any process/thread/device holding a lock for an undetermined amount of time. The formal definition IIRC is "a system is lock free, at least one concurrent process makes progress towards finishing in a unit of time" (There's a hard to achieve version called "wait free" which means "every process makes amortized progress towards finishing") The important property of a lock free system is that pausing any thread/process does not stop the others from progressing; whereas with classical locks (mutex, semaphore, spin, whatever), if you pause a lock-holding process you risk starving the entire system.
- mehrdadn 7y agoI love your last paragraph. It's extremely intuitive and yet I don't think I've ever seen it explained that way.
- DSingularity 7y agoIf you like this kind of thing: http://courses.cs.vt.edu/~cs5204/fall07-kafura/Papers/TransactionalMemory/Linearizability.pdf http://courses.cs.vt.edu/~cs5204/fall07-kafura/Papers/Transa...
- vishnugupta 7y agoNot to take anything away from the parent's thoughtful comment. That important property is, in fact, the definition of lock-free. Lock-free and wait-free (which has a stronger guarantee) algorithms are sub-classifications of non-blocking algorithms. If I could recommend one book on this topic it'd be "The Art of Multiprocessor Programming". The authors have contributed to this subject through original research and make the topic quite approachable.
- deleted 7y ago[deleted]
- mehrdadn 7y ago> Not to take anything away from the parent's thoughtful comment. That important property is, in fact, the definition of lock-free. According to Wikipedia, it's the definition of non-blocking, not the definition of lock-free... which I guess is a correction for both the parent comment and yours. [1] As far as I recall ever seeing, people always talk about it in terms of guaranteed systemwide progress, which I don't find as enlightening as what happens when you pause a thread. [1] https://en.wikipedia.org/wiki/Non-blocking_algorithm https://en.wikipedia.org/wiki/Non-blocking_algorithm
- lordnacho 7y agoI think of it as "more fine-grained" locking. If you don't care too much, just use the OS locks. If you do, manage the primitives yourself.
- docker_up 7y agoIt's not a misnomer. Back in the day, I wanted to implement a cache in our software product that used reference counting to update objects and when the object went to 0, free it from the cache. Pretty straightforward, no rocket science, but this was also cross-platform including Solaris, HP-UX, etc. This was easy to do on Windows/Intel because they implemented a native CAS at the time (almost 20 years ago now), but the other systems didn't. The only way would be to add a mutex per object, which was a non-starter because it used real kernel memory and resources, so I had to abandon the feature entirely. The above is truly lock-free because it doesn't require any additional resources that have to be tracked or freed.
- microcolonel 7y agoThis presentation was fun, especially the part where he shows his spinlock beating atomic CAS. https://youtu.be/ZQFzMfHIxng https://youtu.be/ZQFzMfHIxng
- NKCSS 7y agoThe site is dead unfortinately.
- denormalfloat 7y agoI found it surprising that atomic operations in Java are converted in to locking when compiling for some versions of android. The guarantees of Java (before 9) on ordering are slightly too strong and result in locks being used under the hood.
- jillesvangurp 7y agoInteresting. This probably is because of some hardware limitations on some older android hardware platforms. The java.util.concurrent package was added in Java 5 and before that existed as a third party library (by Doug Lee). It contains a lot of concurrency primitives and makes use of a lot of things, including lock free instructions and optimistic locking: https://en.wikipedia.org/wiki/Java_concurrency https://en.wikipedia.org/wiki/Java_concurrency
- MaxBarraclough 7y agoThat would open the door to thread-starvation, right? Unlikely in practice, but the point being that it does affect the formal correctness of the algorithm. I imagine it also impacts real-world performance, but lock-free algorithms aren't assured to be faster anyway. Annoyingly I recall reading a good article on exactly this question - the importance of hardware atomics vs locking - but can't recall what it was. These locks still aren't as bad as ad-hoc locking, in terms of deadlock risk, as you're guaranteed that they are 'leaf locks', with no order-of-acquisition hierarchies/orderings to worry about.
- comex 7y ago> The spin until success strategy seen above is employed in many lock-free algorithms and is called spinlock: a simple loop where the thread repeatedly tries to perform something until successful. It's a form of gentle lock where the thread is up and running — no sleep forced by the operating system, although no progress is made until the loop is over. Regular locks employed in mutexes or semaphores are way more expensive, as the suspend/wakeup cycle requires a lot of work under the hood. A compare-and-swap loop is not a spinlock. (It is the primitive used to implement a spinlock, but that's different.) Pure spinlocks are almost always a bad idea, at least in userland, because threads spinning trying to acquire the lock look "busy" to the scheduler, so the scheduler may run them instead of the thread that owns the lock. It does make sense to spin a limited number of times before going through the slow path to acquire a mutex, but most OS mutex implementations have that functionality built in, so there's usually no need to do that manually.
- fulafel 7y agoNitpick: cas is the spinlock primitive on some hw platforms, others use eg ll/sc.
- archy_ 7y agoWhy would it make more sense to "spin a limited number of times before going through the slow path to acquire a mutex"? Does a mutex have more overhead in the short term than a spinlock but after a few cycles become more efficient? Off topic, but I remember reading that the Linux kernel prefers spinlocks to mutexes. Is there a good technical reason for that?
- dragontamer 7y ago> Does a mutex have more overhead in the short term than a spinlock but after a few cycles become more efficient? Think about what a true mutex does. The true mutex switches into kernel mode (aka: your program is no longer running, Linux is running). That means a spectre-guard / meltdown guard is executed (your TLB buffer may be flushed, as well as various other memory-guards to prevent Spectre from leaking data). Once the guards are executed, kernel-mode has to find more work to do. Traversing the kernel-data structures can take 1 to 10 microseconds, depending on how cold the cache is. Finally, since another thread may be running (before your thread comes back), you probably lost all your data from L1 cache (and at minimum: your branch-predictor state because of Spectre). A spinlock without any contention takes less than 10-nanoseconds to run, to maybe 50-nanoseconds with a bit of contention (!!). You're basically reading/writing data to L1 cache, maybe L3 cache under contention. However, a scheduler invocation will be on the order of 5000 nanoseconds (~5 microeconds) or so, due to all of the work that the scheduler has to do. -------- Window's default spincount is something on the order of 4000 cycles. Spinning for 4000-cycles (or less) is an advantage towards a spinlock-like methodology. (4000 cycles x 4GHz == 1-microsecond). Just to give you an idea of the speed-magnitudes that are being discussed here.
- jchw 7y agoNote that lock-free is not always faster because contention is complicated.
- vardump 7y agoAlso note that lock-free can scale worse, again due to contention. If you want scalability, you want to minimize inter-core and inter-socket traffic.
- jchw 7y agoThis is the more important point, realistically. I think I probably would've been better off saying 'lock-free is not a panacea.' All in all, scaling up contentious operations is hard.
- dragontamer 7y agoYet another article discussing atomics without discussing the memory model or memory fences. Atomics are the easy part to understand. Memory fences and memory-ordering is the hard part that needs far more discussion. If you use atomics with the wrong memory fence, everything will break. Memory fences are necessary to make the compiler, CPU, and caches put the data into main-memory in the correct order. ---------- Do NOT write Atomics unless you understand fences. It is absolutely essential, even on x86, to put memory fences in the correct spot. Even though x86 automatically has acquire/release consistency... the compiler may move your data ordering to the wrong location. Even with "volatile" semantics, your data may be committed to memory in the wrong order. Fredor Pikus has an amusing example where you can have a properly coded lock but the compiler (may) mess you up: https://youtu.be/lVBvHbJsg5Y?t=811 https://youtu.be/lVBvHbJsg5Y?t=811 ---------- EDIT: if you use locks (spinlocks, mutex, condition variables, etc. etc.), the author of the library would have put memory fences in the correct place for you. Only if you use synchronization "manually" (and... you probably are doing that if you are writing atomics), do you have to think about memory fences.
- rrss 7y ago> Topics like sequential consistency and memory barriers are critical pieces of the puzzle and can't be overlooked if you want to get the best out of your lock-free algorithms. I will cover them all in the next episode. Not every article has to be an exhaustive description of everything you need to know. Anywho, sequential consistency is the default for C++11 and C11 atomics, so you pretty much can use them without a complete understanding of memory consistency models.
- dragontamer 7y agoAh, you're right. They call them "barriers" instead of "fences", so I didn't pick up on that paragraph. Still, C11 and C++ atomics aren't widely implemented yet in the GPU world. OpenCL 1.2 doesn't have them (and OpenCL 2.0 is not commonly implemented), CUDA doesn't have them yet, AMD ROCm doesn't have them yet. And anyone with older compilers will probably be working with fence intrinsics, instead of "innate" barriers per atomic instruction.
- deleted 7y ago
- kabdib 7y agoBased on some experience on non-X86 systems, lock-free is where you start finding bugs in compilers and runtime libraries, and also hardware. How much do you trust random ARM-based SOCs to get this right at all of the necessary levels of cache consistency and memory access queues? Lots? Great, I am happy for you. Now, extend your confidence into some other chips, like PowerPC (various versions), MIPs and maybe a couple of others. Eventually you are going to hit some very odd bugs, the really difficult bugs that will make you tear your hair out, and eventually that lock-free stuff, too. "But we'll never run our stuff on a MIPS, or a Fthaghn-V1000." That's good . . . but the chipset you trust might get an update with slightly different memory behavior and you'll be sunk. The projects I've been on that have shipped lock-free structures have done so only when using them was (a) high value, (b) there was a way to choose an alternate method (usually at compile time), and (c) the use was very limited (e.g., just a handful of critical places).
- pornel 7y agoIf multi-threaded code is too easy for you, try multi-threaded code which is executed in a different order than written! Depending on access mode, the compiler, or the hardware, can still change the order of operations. It adds whole another level of WTF: https://llvm.org/docs/Atomics.html#atomic-orderings https://llvm.org/docs/Atomics.html#atomic-orderings > It is also possible to move stores from before an Acquire load or read-modify-write operation to after it, and move non-Acquire loads from before an Acquire operation to after it.
- MaxBarraclough 7y ago> If multi-threaded code is too easy for you, try multi-threaded code which is executed in a different order than written! Most multi-threaded code works this way. Even safe languages like Java permit this. I believe the exceptions tend to be interpreted languages like Python, using green threads. At the assembly level, most modern CPUs are permitted to perform out-of-order execution. I believe the exceptions are pretty rare these days. The custom PowerPC chip in the Xbox 360 guaranteed in-order execution, for instance [0]. GPUs are a different beast. [0] https://en.wikipedia.org/wiki/Xenon_(processor)#Specifications https://en.wikipedia.org/wiki/Xenon_(processor)#Specificatio...
- pornel 7y agoThe difference is that reordering is not observable with just one thread. Both language optimizations and CPU OOO don't change semantics within a single thread. If you use higher-level primitives like mutexes, they come with fences that also preserve that illusion. It does become observable when you try to do synchronization yourself with atomics, without setting appropriate ordering requirements. Lock-free algorithms are usually tricky, and implementing them with minimum ordering requirements makes them even more puzzling.
- pizza234 7y agoI see that, in a related article, they missed a nice in-joke: > A gentle introduction to multithreading — Approaching the world of concurrency, two steps at a time. (I wonder if "multiple steps at a time" sounds better) :-)