Modern servers have dozens or even hundreds of cores, which can execute many threads of computation in parallel. In such a system, the difference between the performance of a bad implementation and a good one can easily be 100x.

This lecture uses concurrent data structures as examples to explain high performance implementation techniques and surprising performance pitfalls. Along the way, we will cover linearizability, which is a way to define what correctness means for a concurrent data structure.

Students should finish with knowledge of some simple linearizable concurrent data structures, and an understanding of how these data structures interact with various aspects of real systems, with a special focus on processor caches.

Slides and exercises