--- title: "9. Concurrency" url: https://cpuperf.com/learn/concurrency/ source: https://github.com/usamahz/cpu-performance-engineering/blob/deb5a0bac46760503b6f4a2608bdfed470c8532e/README.md#L415 commit: deb5a0bac46760503b6f4a2608bdfed470c8532e --- ## 9. Concurrency Every cost below is a cache line moving between cores, so the ordering models and the measured line-transfer cost in the memory hierarchy section come first. ### Memory models and atomics - [Foundations of the C++ Concurrency Memory Model](https://rsim.cs.illinois.edu/Pubs/08PLDI.pdf) - Defines the data-race-free contract, sequential consistency for race-free programs and no meaning for a race. - [Atomic operations, C++ working draft](https://eel.is/c++draft/atomics) - The normative wording for every memory order, fence and read-modify-write, the text a compiler is checked against. - [C/C++11 mappings to processors](https://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html) - The table that turns each memory order into x86 and Arm instructions, so what an order costs is read off the page. - [Linux kernel memory-barriers.txt](https://www.kernel.org/doc/Documentation/memory-barriers.txt) - States what the kernel assumes any CPU may reorder and what each barrier and access primitive guarantees. - [herdtools7](https://github.com/herd/herdtools7) - Where herd7, litmus7 and klitmus7 live, the tools that run a litmus test against the x86, Arm and kernel models. ### Locks, contention and allocators - [Is Parallel Programming Hard, And, If So, What Can You Do About It?](https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html) - Derives counting, partitioning, locking and deferral with code that runs, the textbook the section assumes. - [Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors](https://www.cs.rochester.edu/u/scott/papers/1991_TOCS_synch.pdf) - The origin of the queue lock, each waiter spinning on its own line, measured against ticket and test-and-set locks. - [Futexes Are Tricky](https://www.akkadia.org/drepper/futex.pdf) - Derives a correct user-space mutex from futex and shows the lost wakeups and extra kernel entries naive versions pay. - [Hoard: A Scalable Memory Allocator for Multithreaded Applications](https://people.cs.umass.edu/~emery/pubs/berger-asplos2000.pdf) - Defines blowup and allocator-induced false sharing, which per-processor heaps under a bounded global heap avoid. - [TCMalloc: Thread-Caching Malloc](https://google.github.io/tcmalloc/design.html) - The design statement for per-CPU caches built on restartable sequences and a hugepage-aware back end for TLB reach. Reproduce it: [misc/benchmarks/09-false-sharing](https://cpuperf.com/benchmarks/09-false-sharing/), adjacent counters against padded counters across threads. ### Lock-free structures and RCU - [The Art of Multiprocessor Programming](https://shop.elsevier.com/books/the-art-of-multiprocessor-programming/herlihy/978-0-12-415950-1) - States linearizability and the consensus hierarchy and builds both into working stacks, queues, lists and hash tables. - [Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms](https://www.cs.rochester.edu/u/scott/papers/1996_PODC_queues.pdf) - The lock-free queue later libraries copy, with the counted pointer against ABA and a two-lock queue beside it. - [Hazard Pointers for C++26](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p2530r3.pdf) - The standard-track form of safe reclamation, fixing when a retired node may be freed while a reader still holds it. - [What is RCU?](https://docs.kernel.org/RCU/whatisRCU.html) - The kernel's own statement of RCU as publish, wait for readers and keep old versions, with a free read side. - [User-Level Implementations of Read-Copy Update](https://www.efficios.com/pub/rcu/urcu-main.pdf) - Defines liburcu's quiescent-state, signal-based and general RCU flavours and measures each read side against locks. ### Thread pools and work stealing - [Cilk: An Efficient Multithreaded Runtime System](https://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TM-548.pdf) - Defines work and critical path, proves the work-stealing bound, and shows they alone predict a runtime's speedup. - [The Implementation of the Cilk-5 Multithreaded Language](https://www.fftw.org/~athena/papers/cilk5.ps.gz) - States the work-first principle, that overhead belongs on the rare steal path and not on every spawn. - [Correct and Efficient Work-Stealing for Weak Memory Models](https://inria.hal.science/hal-00802885) - Gives the work-stealing deque a proven atomics form and derives which fence push, take and steal need on Arm and x86. - [OpenMP Specifications](https://www.openmp.org/specifications/) - Fixes fork-join and tasking semantics, and the wait and binding controls deciding if idle workers spin, sleep or move. - [oneTBB](https://github.com/uxlfoundation/oneTBB) - The shipping work-stealing runtime, arenas and task groups over a deque, the home of grain size and spin-before-sleep.