If the odds for contention are low then something like a futex is pretty snappy, too.

Lockless solutions do naturally fit in certain cases. For example, producer-consumer queues where there's only some invariants that need to be respected. There the producer must not overwrite what the consumer hasn't consumed yet and the consumer must not advance to areas that the producer hasn't yet filled. Using a lockless approach both the producer and the consumer can continue to operate as long as they won't step on each others' toes. Instead, using a mutex or read-write locking would basically make the access to the queue mutually exclusive to the producer and consumer.

I, myself, like the approach of building my data out of near-immutable blocks and just replacing the references using atomic compare-and-swap, for example.

There are two-lock queues that allow consumers to mostly run independently from the producers while still using bog-standard locks.

Still you are right that lock-free algos really shine in implementing message queues, but mostly because they can be implemented with fewer or cheaper memory operations, so even in the uncontended case, the lock-free queue can shave some cycles.

> I, myself, like the approach of building my data out of near-immutable blocks and just replacing the references using atomic compare-and-swap, for example.

Yes, one huge advantage of lock free algorithms is that you can have read mostly data structures with no contentions between readers (most rw-lock implementations do require readers to write on some shared state).

Yup using a layer of indirection definitely works well. Regarding the futex, I definitely agree that most futex implementations on most hardware are designed to spin and resolve quickly in low contention scenarios, but this won't be true on all consoles/hardware/OS configurations. For certain cases (like a game engine), I'd be less inclined to rely on the futex to do the right thing.

Futex are a linux kernel-level specific waiting primitive [1]. The point of the OP is that mutex implemented on top of a futex has a purely userspace fast path that needs only a single CAS for each acquire and release in the uncontended space, so in this scenario an userspace spin-lock is not often significantly better (a spin lock release only need a store on some machines though). Spin locks are significantly worse in the contended space though.

[1] futexes enable Fast Userspace muTEXES, but futex themselves are kernel space and not particularly fast.

OpenBSD implements futex now, too. Major league userland responsiveness improvements for futex based mutexes.

I think it's usually the other way around: when the odds of contention is very low, locks are better. Uncontended lock acquisition is relatively cheap, and it can be done once. The downside of using a lock is that it prevents other threads which are contending for that lock from proceeding, hence why locks are better when contention is low.

Lock free algorithms are generally better when the odds of contention are high, as you can devise algorithms that allow all threads to make progress at the same time. In general, this allows more parallelism, but the cost is that it typically requires more overall atomic operations.

> Lock free algorithms are generally better when the odds of contention are high, as you can devise algorithms that allow all threads to make progress at the same time. In general, this allows more parallelism, but the cost is that it typically requires more overall atomic operations.

I can't say I agree here. It really depends on the cost of the swap operation required to make this work. Consider a lock-free map for example. Under high contention, I'd prefer to wait for a lock than copy the map while spinning on an atomic. What would push the needle for me one way or another (with respect to locking vs lockless) is a blend between the probability of contention, the cost of the loop itself, and the cost of the swap.

I don't know what you mean here: "than copy the map while spinning on an atomic." Why would we copy the map? And by "spinning on an atomic", do you mean just spin-waiting on some flag? That's, morally, a lock. A well designed lock free algorithm allows all threads to make progress at the same time, and if there is contention, an alternative that hopefully is not just redoing that same work. The cost is more atomic operations, which means that if there is low contention, you're paying more overhead than needed.

It depends, on high contention, waiting writer threads will only touch a single shared cache line containing the lock (all the time if spinning, once if there is a proper thread queue). In a lock free algo, the writers might be stepping on each other toes all the time, with heavy cache-line pingpoing, which is not good for general throughput.

Lock free algos are very good when you have many pure readers and few or occasional writers.

In my experience, once you get up to the 100s of threads potentially touching global structures, locks impeded scalability significantly. Even if each of those threads is modifying the global data. The key is to design your algorithms around the kind of structures that are amenable to lock free algorithms. (The experience I'm referring to: http://www.scott-a-s.com/files/pldi2017_lf_elastic_schedulin...)

Is a program that has 100s of threads realistic?

The Vega64 GPU that AMD just released has 4096 "threads" operating at one time (actually in flight), with up to 40,960 of them "at the ready" at the hardware level (kinda like Hyperthreading, except GPUs keep up to ~10 threads per "shader core" in memory for quick swap in-and-outs). Subject to memory requirements of course. A program that uses a ton of vGPR Registers on the AMD system may "only" accomplish 4096 threads at a time, and maybe only 5 per core (aka 20,480) of them are needed for maximum occupancy.

Its a weird architecture because of how each "thread" shares an instruction pointer (ie: NVidia has 32 threads per wavefront, AMD has 64 workitems per Work Group), so its not "really" the same kind of "thread" as in Linux pthreads. But still, the scope of parallelism on a $500 GPU today is rather outstanding.

All of these threads could potentially hit the same global memory at the same time. I mean, if you want bad performance of course, but its entirely possible since the global memory space is shared between all compute units in a GPU.

Yes. See the paper I linked to. I work on a parallel and distributed dataflow system called IBM Streams. When we have thousands of our operators running on a large system, it is realistic for there to be 100s of threads.

there are fairly mainstream machines with more than 100s of hardware threads.

The lock could still be faster. atomic ops are more expensive than regular opcodes even when there is zero contention. On x86, a lock requires only a single atomic opcode and can be released with a normal write (because of TSO). Since it's uncontended it won't spin at all. Therefore, any alternative lock-free algorithm that uses more than a single atomic op is actually more expensive.

Lock-less algorithms sometimes have more CAS instructions on the critical path, so may be slower under zero contention.

I think you’re right in many cases though.