Keep in mind lockless algorithms are not necessarily more scalable than lock-based algorithms, usually have higher constant overheads, and are significantly easier to get wrong.
However, this post is, in part, about how to implement locks.
However, this post is, in part, about how to implement locks.
I haven't read the article in-depth but yeah, it seems like it maybe would have been better titled "What every C++ systems programmer should know about std::atomic". Which is still cool but from the title I was expecting some fancy voodoo algorithms for threadsafe non-locking FIFO queues or something.
I was hoping that there was some cool new trick I'd missed or fundamentally different way to do concurrency than locking. I get disappointed easily in cases like this. :/
https://www.amazon.com/C-Concurrency-Action-Anthony-Williams...
Also, I think it's worth noting that it's really not that much more complicated than a simple mutex if you use the default sequential consistency memory order on an atomic. When you start attempting to optimize around certain patterns using the weaker memory orders, yea, things get a lot tougher.
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.
[1] futexes enable Fast Userspace muTEXES, but futex themselves are kernel space and not particularly fast.
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).
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 algos are very good when you have many pure readers and few or occasional writers.
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.
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 think you’re right in many cases though.
An alternative lock-free approach is to segmented memory between threads and then coordinate between threads using messages passed with ring buffers. This can be done entirely without atomic operations but hits other scaling problems and is also extremely difficult to implement so probably not widely applicable.
Also any lock implementations also use a cas or equivalent internally (you could use the Dekker algorithm, but it is not cheper).
Perhaps "Cache Flush" is the wrong word, but as long as cores are forced to communicate, you're going to get a performance penalty.
I know when you do a simple atomic_increment on x86_64 platforms, things can be 2x slower at a minimum than a non-atomic increment.
"Cache Coherence" simply means that the CPU handles all of those edge cases for you. But it still needs to be handled, and that entails a performance penalty.
If you have a 4-core / 8-thread machine (Like a recent Intel i7), its faster to have 8-Non Atomic counters that are added up at the end... rather than to have 1-atomic counter with 8-threads doing atomic-increment on it.
----------------
Any core that modifies a memory location invalidates the cache for all other cores. (ie: Core 1 does atomic_inc(x), implies that Core2/Core3/Core4 all have an invalid value of "x". So atomic_inc(x) causes a cache-flush on Core2/Core3/Core4)
Again, I'm not an expert, but that's my understanding of how modern systems work.
-------
I looked up the Intel Architecture Manual, and they have the following table:
If the data is in another core's L1 cache, the latency increases dramatically, especially on a "Dirty Hit". (ie: Core1 is trying to read "x", but Core3 is telling the other cores that "x" has changed)
In effect, its more efficient for an Intel CPU to access something from L3 cache than for it to access a "Dirty" value from another core. Heck, based on these numbers, even a "Clean" hit is more costly than using the L3 cache!
The extra penalty introduced by common atomic operations that make strong guarantees about ordering is waiting for the store buffer to flush all prior stores before the result of the atomic operation is flushed out of the store buffers to L1 and then the atomic operation is flushed.
I hesitate to make generalizations about memory visibility requirements and costs as it is very API and hardware specific. Weaker guarantees exist and would have different costs.
TL;DR The total memory overhead is the same the difference is the atomic operation stalls the CPU that is performing the atomic operation unless it can speculate past it.
Also blind stores can be resolved in the background and don't block the CPU from continuing as long as the cache line is never read from.
Understanding how atomic instructions work and their effect (or lack of) on the system is important for optimizations.
Ultimately, I'm basing my viewpoint from this PDF: the "Is parallel programming Hard" free online book.
https://www.kernel.org/pub/linux/kernel/people/paulmck/perfb...
> Line 1 defines an atomic variable, line 5 atomically increments it, and line 10 reads it out. Because this is atomic, it keeps perfect count. However, it is slower: on a Intel Core Duo laptop, it is about six times slower than non-atomic increment when a single thread is incrementing, and more than ten times slower if two threads are incrementing.
The PDF changes over time. But this line can be found on page 42 at the moment.
--------
So according to the tests done by the author here, atomic operations are CERTAINLY slower, even in single-threaded cases.
I can't say I understand why they're slower, but something is definitely going on.
[1] atomic stores and loads are extremely cheap on x86.
[2] you can see that from the cost: a RMW or membar is around 20-30 clock cycles, while cross core communication costs in the order of 100s cycles.
edit: s/buffer/barrier/
Not in the sense of flushing from cache to memory, but yes in the sense of data from a local core cache needing to be sent to another core.
Caches may be coherent but coherency is definitely not free, especially on multi-processor systems, which you probably care about if you are writing this kind of code.
The only thing that can be said to be 'flushed' by a CAS (at least on a x86 where it has full barrier semantic) is the store buffer (which is not a cache), but even there the only thing it does is simply prevent more recent loads [1] to complete before any store older or equal than the cas has completed. The store buffer is not really flushed and is still drained at the same speed it would without at cas.
[1] or any other operation for simplicity of implementation.
But if you have a data-structure with say, 20 ints... you have two approaches.
1. Use a mutex (which may be CAS-based under the hood) at the beginning and end: 1 lock and 1 unlock. The 20-ints are then accessed with non-atomic operations.
2. Use atomic operations on those 20-ints. But in this case, you pay the "atomics cost" each time.
In many cases, #1 may be faster than #2.
-----
Sorry for the 2nd response, but this is a different idea than what I was talking in my 1st response.
I don't think it's as bad as that - I've heard it's only as expensive as hitting the L2 cache.