News for hackers. Stuff that matters.
Re:Lock-free multithreading with atomic operations by amelius on Tuesday July 30, 2019 @03:16AM (#20562732)
I think "lock free" is a misnomer because in many cases these atomic operations still perform locks at the hardware level.
Re:Lock-free multithreading with atomic operations by beagle3 on Tuesday July 30, 2019 @04:49AM (#20563157)
"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.

Re:Lock-free multithreading with atomic operations by dragontamer on Tuesday July 30, 2019 @10:59AM (#20565386)
> 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.

With that being said, stopping any thread/process is rare in high-performance circumstances. In many cases, it is easier to avoid getting your thread stopped (as simple as spinning up one-thread per logical core), rather than to switch to a lock-free algorithm.

Besides, your typical OS Mutex (CriticalSection in Windows) handles the pause situation just fine. The OS will keep track of which threads are waiting on which locks, and restart the threads as resources become available. Its the "known problem" and well studied by pretty much all programmers.

Lock-free data structures are exponentially more difficult to write, especially when you are handling "out of memory" edge cases. The general recommendation is to write "mostly lock free", but use a lock for corner-cases.

CAS-loop with pointer swapping gets you lock free in most cases, and is very easy to understand. The only problem is that it doesn't work in all cases or data-structures, so you inevitably end up using locks to finish your program.

EDIT: And it should be noted that locks can be faster. So if you're going for absolute performance, you should write both implementations and measure.

Re:Lock-free multithreading with atomic operations by beagle3 on Tuesday July 30, 2019 @04:57PM (#20569066)
> With that being said, stopping any thread/process is rare in high-performance circumstances.

While that's true from a performance perspective, it is not true from a reliability perspective - it's always possible that the thread holding a lock has faulted, was swapped out, or otherwise had a bug (e.g. in a library you called beyond your control) that caused it to stall. Also, if more than one lock is involved, a deadlock is possible as well (not all of which can be detected by an OS, and most OSes suck at detecting deadlocks if they even try).

> The OS will keep track of which threads are waiting on which locks, and restart the threads as resources become available.

But causes for a pause are not necessarily under your control or the OSes privilege; You can take a critical section, write to a local file .... and wait 20 seconds because the drive has gone to sleep, someone competing for the disk, swapping in/out, a recoverable disk error, or the fact that it is not actually local but rather virtualized SAN across the internet.

Also, someone might have paused a thread from the debug API for whatever reason (or kill -STOP on linux), which might be expected to only pause that thread -- but in a system that isn't lock free, that could pause anything and everything, in a non reproducible way.

> Lock-free data structures are exponentially more difficult to write

For sure. Personally, I find that they keep me on my toes "the right way", that is - they force me to consider what and where actually needs synchronization and can be contended (whereas a lock allows me to be lazy. which is sometimes good).

> The only problem is that it doesn't work in all cases or data-structures,

Yes. ABA problems are not solved by CAS, which is why I personally prefer LL/SC, but ... whatever, CAS is harder but still doable.

> So if you're going for absolute performance, you should write both implementations and measure.

Upon a quick review of history, my use of lock free structures and algorithms is dominated by reliability requirements ("nothing must unexpectedly pause the system" - mostly seqlocks), and only a few cases for performance - mostly shared lists and shared (often reference) counters.

Re:Lock-free multithreading with atomic operations by dragontamer on Tuesday July 30, 2019 @06:53PM (#20570064)
> But causes for a pause are not necessarily under your control or the OSes privilege; You can take a critical section, write to a local file .... and wait 20 seconds because the drive has gone to sleep, someone competing for the disk, swapping in/out, a recoverable disk error, or the fact that it is not actually local but rather virtualized SAN across the internet.

If the write to the local file needs to be protected by a critical section (seems unlikely to me, but... I can imagine some situations like that), the alternative is performing the write inside of a CAS loop instead.

When the CAS-loop fails (because its been 20-seconds and the compare-and-swap has a grossly different value you were waiting on) you have to perform a 2nd I/O operation and restart the entire computation.

What is more performant? Locking your other threads? Or potentially doing extremely expensive work repeatedly?

Locking your other threads (especially if there are some other threads that have work to do) could very much be the more performant answer. In fact, I would argue that the locking implementation is more likely to be work efficient.

> Upon a quick review of history, my use of lock free structures and algorithms is dominated by reliability requirements ("nothing must unexpectedly pause the system" - mostly seqlocks), and only a few cases for performance - mostly shared lists and shared (often reference) counters.

I think that is reasonable and typical. I think beginners think of "lock free" as a potential improvement to efficiency. But the advantages of lock free are entirely independent of performance, it has more to so with requirements as opposed to performance in most cases.

Re:Lock-free multithreading with atomic operations by mehrdadn on Tuesday July 30, 2019 @06:55AM (#20563649)
I love your last paragraph. It's extremely intuitive and yet I don't think I've ever seen it explained that way.
Re:Lock-free multithreading with atomic operations by vishnugupta on Tuesday July 30, 2019 @10:01AM (#20564909)
Not 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.

Re:Lock-free multithreading with atomic operations by mehrdadn on Tuesday July 30, 2019 @01:47PM (#20567289)
> 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

Re:Lock-free multithreading with atomic operations by MaxBarraclough on Tuesday July 30, 2019 @05:18PM (#20569270)
A good article on this hierarchy (if you can forgive the low-contrast style):

http://concurrencyfreaks.blogspot.com/2013/05/lock-free-and-...

Re:Lock-free multithreading with atomic operations by DSingularity on Tuesday July 30, 2019 @08:11AM (#20564079)
Re:Lock-free multithreading with atomic operations by DSingularity on Tuesday July 30, 2019 @08:13AM (#20564092)
Yeah, this is why -- for me -- lock free is more about blocking/reliability than performance.
Re:Lock-free multithreading with atomic operations by gambiting on Tuesday July 30, 2019 @05:11AM (#20563226)
I 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.
Re:Lock-free multithreading with atomic operations by jrockway on Tuesday July 30, 2019 @03:47AM (#20562872)
I 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.

Re:Lock-free multithreading with atomic operations by kccqzy on Tuesday July 30, 2019 @03:21AM (#20562747)
On 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.
Re:Lock-free multithreading with atomic operations by amelius on Tuesday July 30, 2019 @03:27AM (#20562780)
It's still a lock in the sense that it momentarily prevents another process from using a resource.
Re:Lock-free multithreading with atomic operations by denormalfloat on Tuesday July 30, 2019 @03:39AM (#20562829)
The 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.
Re:Lock-free multithreading with atomic operations by amelius on Tuesday July 30, 2019 @04:54AM (#20563178)
That 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.
Re:Lock-free multithreading with atomic operations by jasonwatkinspdx on Tuesday July 30, 2019 @05:34AM (#20563316)
When 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

It is indeed true that atomic operations will execute in a bounded time, and processors generally provide fairness guarantees as well.

Re:Lock-free multithreading with atomic operations by gpderetta on Tuesday July 30, 2019 @07:16AM (#20563750)
Yes. Even better than that, atomic instructions are usually completely local to a core. I think that the only interaction with with the coherency protocol is that a core is guaranteed to be able to hold a cache in exclusive mode long enough to execute an RMW (and even that it is not really required, but useful to guarantee forward progress).
Re:Lock-free multithreading with atomic operations by namibj on Wednesday July 31, 2019 @11:32AM (#20575214)
Since NVLink2 and POWER9, even a GPU can issue atomics over the bus, which will be executed local to the CPU that owns this cacheline. This is very useful in high-contention write-heavy workloads, like atomic counters or accumulators.
Re:Lock-free multithreading with atomic operations by amelius on Tuesday July 30, 2019 @06:31AM (#20563520)
Yes, 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.
Re:Lock-free multithreading with atomic operations by gpderetta on Tuesday July 30, 2019 @07:18AM (#20563766)
Even 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.
Re:Lock-free multithreading with atomic operations by amelius on Tuesday July 30, 2019 @08:07AM (#20564058)
True, 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.
Re:Lock-free multithreading with atomic operations by bonzini on Tuesday July 30, 2019 @10:43AM (#20565233)
They may need to access main memory, but the RMW operation don't happen over the memory bus. The processor appropriates the cache line just like any other memory access, and then operates atomically on the cache line.
Re:Lock-free multithreading with atomic operations by amelius on Tuesday July 30, 2019 @01:03PM (#20566804)
And what if the cache line is full/dirty?
Re:Lock-free multithreading with atomic operations by bonzini on Tuesday July 30, 2019 @02:20PM (#20567629)
The cache coherency protocol takes care of that. In other words the first part is just a memory load and can vary from 0 to a few hundred clock cycles, the second is local to the processor and has a more or less fixed cost. The worst-case execution time is completely dominated by the first part, the best case instead is dominated by the second.
Re:Lock-free multithreading with atomic operations by jasonwatkinspdx on Tuesday July 30, 2019 @03:47PM (#20568431)
I'd suggest reading the wiki articles about it for an introduction, and Ch 5 of https://www.amazon.com/Computer-Architecture-Quantitative-Jo... for a detailed understanding.

Right now you're asserting things about all this, while not being familiar with relatively basic aspects of how it works.

Re:Lock-free multithreading with atomic operations by gpderetta on Tuesday July 30, 2019 @08:59AM (#20564373)
Sure any memory access might access main memory. There is no special casing for atomic though.
Re:Lock-free multithreading with atomic operations by kccqzy on Tuesday July 30, 2019 @03:35AM (#20562816)
It 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.
Re:Lock-free multithreading with atomic operations by gpderetta on Tuesday July 30, 2019 @07:44AM (#20563922)
The only resource that is held exclusively during an RMW is a single cache line, and that's not due to the lock prefix.
Re:Lock-free multithreading with atomic operations by fulafel on Tuesday July 30, 2019 @10:03AM (#20564925)
X86 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.
Re:Lock-free multithreading with atomic operations by gpderetta on Tuesday July 30, 2019 @07:08AM (#20563710)
Outside of some very exotic scenarios, this hasn't been the case for about 20 years.
Re:Lock-free multithreading with atomic operations by zlynx on Tuesday July 30, 2019 @12:40PM (#20566551)
I 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.
Re:Lock-free multithreading with atomic operations by gpderetta on Tuesday July 30, 2019 @02:07PM (#20567500)
Yes, That's the very exotic scenario I had in mind:)
Re:Lock-free multithreading with atomic operations by docker_up on Tuesday July 30, 2019 @12:15PM (#20566305)
It'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.

Re:Lock-free multithreading with atomic operations by lordnacho on Tuesday July 30, 2019 @05:30AM (#20563292)
I 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.