Marek's totally not insane idea of the day 11 September 2012 I needed a queue implementation written in C for one of my ever-experimental projects. The complex part was to make it thread-safe - it was going to be used for exchanging data between threads. Usually, I'd just take the doubly linked list implementation from the linux kernel 1 , wrap it in a mutex and quickly move on to another challenge. This time though, I decided to make sure the queue is as efficient as possible. The mutex solution has at least few deficiencies: A queue is a much simpler data structure than way than a list. It has also smaller memory footprint - a FIFO queue requires a single pointer per element ( next ), while doubly linked list requires two ( prev and next ). Mutexes are relatively heavy. There is a better way. My CPU has CMPXCHG instruction for a reason - to enable lock-free al...