The Ridiculous Fish guy is clearly very smart and writes lots of interesting stuff, but this is obviously not his area of expertise, and you can't afford to learn from someone who has any confusion on the topic.
In his conclusion he makes what I would consider a highly misleading comparison between locks and memory barriers. He calls locks "tanks" ("powerful, slow, safe, expensive, and prone to getting you stuck"). About memory barriers he says: "Memory barriers are a faster, non-blocking, deadlock free alternative to locks. They take more thought, and aren’t always applicable, but your code’ll be faster and scale better."
But memory barriers aren't an alternative to locks at all. Locks let multiple threads write to shared memory. Memory barriers by themselves aren't very useful; most lock-free algorithms need atomic operations like compare-and-swap, which are comparable in cost to locks (indeed, locks are implemented in terms of atomic operations).
Failed atomic operations aren't as expensive as failed lock acquisitions though. Locks aren't just implemented in terms of atomic operations - they need the kernel too. They potentially involve blocking the thread, a context switch out, a context switch back, etc. before being able to make progress again.
It's true that lock-free algorithms don't block, but they generally degrade under contention too, just in a different way. Whereas a contended mutex blocks, a contended lock-free data structure can cause the compare-and-swap step to fail a potentially arbitrary number of times (unless the algorithm is wait-free, which few are AFAIK).
Also, a surprisingly hard problem with lock free data structures is knowing when you can free/unmap any of their memory. Since there is no mutual exclusion, there is no way of knowing that another thread didn't just read the address of the thing you want to delete. He could read that address and then get swapped out for 100 years, and you can't unmap that memory until he gets rescheduled and finishes his load. Maged Michael published a technique for dealing with this problem he calls "Safe Memory Reclamation" or SMR.
Don't get me wrong, I like lock-free data structures. I just think it's important to understand that they have their issues too, and it's not as though everyone should replace all their mutexes with lock-free structures.
I also think it's important to realize that atomic operations and memory barriers are not application-level constructs as mutexes are. People should leave the atomic operations and memory barriers to the experts, and only use higher-level abstractions in applications, like lock-free stack, queue, etc. You wouldn't dream of implementing a mutex yourself in real code; the same should be true of using atomic operations or memory barriers, unless you're really an expert. One possible exception is atomic increment and decrement for simple reference counting.
Comments
Please read the Linux documentation on memory barriers instead of this: http://lxr.linux.no/linux+v2.6.35/Documentation/memory-barri...
The Ridiculous Fish guy is clearly very smart and writes lots of interesting stuff, but this is obviously not his area of expertise, and you can't afford to learn from someone who has any confusion on the topic.
In his conclusion he makes what I would consider a highly misleading comparison between locks and memory barriers. He calls locks "tanks" ("powerful, slow, safe, expensive, and prone to getting you stuck"). About memory barriers he says: "Memory barriers are a faster, non-blocking, deadlock free alternative to locks. They take more thought, and aren’t always applicable, but your code’ll be faster and scale better."
But memory barriers aren't an alternative to locks at all. Locks let multiple threads write to shared memory. Memory barriers by themselves aren't very useful; most lock-free algorithms need atomic operations like compare-and-swap, which are comparable in cost to locks (indeed, locks are implemented in terms of atomic operations).
Failed atomic operations aren't as expensive as failed lock acquisitions though. Locks aren't just implemented in terms of atomic operations - they need the kernel too. They potentially involve blocking the thread, a context switch out, a context switch back, etc. before being able to make progress again.
It's true that lock-free algorithms don't block, but they generally degrade under contention too, just in a different way. Whereas a contended mutex blocks, a contended lock-free data structure can cause the compare-and-swap step to fail a potentially arbitrary number of times (unless the algorithm is wait-free, which few are AFAIK).
Also, a surprisingly hard problem with lock free data structures is knowing when you can free/unmap any of their memory. Since there is no mutual exclusion, there is no way of knowing that another thread didn't just read the address of the thing you want to delete. He could read that address and then get swapped out for 100 years, and you can't unmap that memory until he gets rescheduled and finishes his load. Maged Michael published a technique for dealing with this problem he calls "Safe Memory Reclamation" or SMR.
Don't get me wrong, I like lock-free data structures. I just think it's important to understand that they have their issues too, and it's not as though everyone should replace all their mutexes with lock-free structures.
I also think it's important to realize that atomic operations and memory barriers are not application-level constructs as mutexes are. People should leave the atomic operations and memory barriers to the experts, and only use higher-level abstractions in applications, like lock-free stack, queue, etc. You wouldn't dream of implementing a mutex yourself in real code; the same should be true of using atomic operations or memory barriers, unless you're really an expert. One possible exception is atomic increment and decrement for simple reference counting.
Whilst most CPUs do imply a data dependency barrier on the read when a memory access depends on a read, not all do, so it may not be relied on.
That and the Alpha having a split cache where one half can be more up-to-date than the other, really sound like a lot of fun.