An Introduction to Lockless Algorithms

One point that's frequently misunderstood about locks is that there's essentially no cost unless the lock is contested. This leads a lot of people to they must go lockless, when a simpler lock-based system would meet their requirements. A lot of systems fit neatly into a paradigm of a single threaded hot path, plus a lot of infrequent peripheral threads that only have a low statistical contention cost. For example let's say you want to process packets off the network…

"Lockless" sounds very positive, and it's tempting to think that everything should be made lockless. However, it's less great than it sounds. Mutexes are very cheap in the uncontended case, and in the contended case they have some nice properties. You should only consider going for a lockless algorithm if you can prove it is better than just using a mutex. Sometimes lockless algorithms are in fact slower than algorithms using locks, as things like atomic compare-and-exchange instructions can have…