Designing fast lock-free algorithms by understanding cache coherence dynamics

The talk has several purposes:

• Introducing MESI cache coherence;
• Showing that lock-free algorithms aren't automatically faster than lock-based ones;
• Explaining why this happens (due to cache coherence dynamics);
• Introducing the idea of using non-failing atomic primitives instead of CAS as a way of speeding up lock-free algorithms.

The above goals are achieved by discussing the problem of designing a concurrent FIFO queue, starting from a simple lock-based algorithm, through a lock-free algorithm (that performs poorly), to the LCRQ algorithm, which is based on fetch-and-add (a non-failing primitive).