Awesome Concurrency

• The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software by Herb Sutter
• Concurrency is not Parallelism by Rob Pike

---

Memory [Consistency] Models

Intro

• How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs by Leslie Lamport

By Russ Cox

• Hardware MM
• Programming Language MM

Axiomatic

• Weak Ordering – A New Definition by Sarita Adve & Mark Hill
• Memory Models: A Case For Rethinking Parallel Languages and Hardware by Sarita Adve and Hans Boehm
• Foundations of the C++ Concurrency Memory Model by Hans Boehm, Sarita Adve
• The Problem of Programming Language Concurrency Semantics by Mark Batty et al
• Repairing Sequential Consistency in C/C++11 by Lahav et al + P0668R5: Revising the C++ memory model
• Weak Memory Consistency by Ori Lahav and Viktor Vafeiadis

Promising Semantics

• A Promising Semantics for Relaxed-Memory Concurrency
• Promising 2.0: Global Optimizations in Relaxed Memory Concurrency

Hardware MM

• Relaxed Memory by Peter Sewell & Shaked Flur

Arch

• A Better x86 Memory Model: x86-TSO
• A Tutorial Introduction to the ARM and POWER Relaxed Memory Models
• Simplifying ARM Concurrency: Multicopy-Atomic Axiomatic and Operational Models for ARMv8

Barriers

• Memory Barriers: a Hardware View for Software Hackers by Paul McKenney
• Linux Kernel Memory Barriers, Quotes of the week

Linux Kernel MM

• https://github.com/torvalds/linux/tree/master/tools/memory-model
• Explanation
• Frightening Small Children and Disconcerting Grown-ups: Concurrency in the Linux Kernel

C++ MM Index

• sequential consistency for DRF programs, sequential consistency vs weak ordering
• S (synchronization order)
• sequenced before
• synchronizes with, release sequence, fences
• modification order, read the last value
• coherence-ordered before
• stores eventually visible
• happens-before
• strongly happens-before
• visible side effect
• conflict, data race
• out-of-thin-air, self-fulfilling prophecy
• seq-cst-fix

PL MM

• Java Memory Model
• Go Memory Model, Don't be clever, Updating the Go MM
• LLVM Atomic Instructions and Concurrency Guide
• Multicore OCaml Memory Model, Bounding Data Races in Space and Time
• Rust Memory model, The Rustonomicon / Atomics

Compilation

• C/C++11 mappings to processors
• The JSR-133 Cookbook for Compiler Writers
• https://godbolt.org/

Cookbook

• Boost Atomics
• Using weakly ordered C++ atomics correctly by Hans Boehm
• A Relaxed Guide to memory_order_relaxed by Paul McKenney & Hans Boehm

---

Hardware

• WikiChip
• Moore on Moore
• The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software by Herb Sutter

Latency

• Latency Numbers Every Programmer Should Know
• Beer cache hierarchy
• Measuring CPU core-to-core latency
• Evaluating the Cost of Atomic Operations on Modern Architectures

Threads

TLS

• All about thread-local storage
• A Deep dive into (implicit) Thread Local Storage

Futures

• [Scala] Your Server as a Function, Systems Programming at Twitter, Futures aren't Ersatz Threads by Marius Eriksen, Finagle – Concurrent Programming with Futures
  • [C++] Futures for C++11 at Facebook, Folly Futures,
• [Rust] Zero-cost futures in Rust and Designing futures for Rust by Aaron Turon, RFC
• [C++] std::execution by Eric Niebler et al.

Fibers

• Fibers, Oh My! by Dale Weiler
• Why User-Mode Threads Are Good for Performance by Ron Pressler
• Project Loom: Fibers and Continuations for the Java Virtual Machine by Ron Pressler
  • State of Loom, Part 1, Part 2

Stacks & Continuations

• Segmented Stacks in LLVM
• [Go] How Stacks are Handled in Go, Continious Stacks Design Doc
• [JVM] Continuations – Under the Covers by Ron Pressler
• [Rust] Abandoning segmented stacks in Rust
• [Rust] Futures and Segmented Stacks
• From Folklore to Fact: Comparing Implementations of Stacks and Continuations

Coroutines

Stackless

• By Russ Cox
  • On Duff's Device and Coroutines
  • Storing Data in Control Flow

C#

• How Async/Await Really Works in C# by Stephen Toub

C++

• Asymmetric Transfer by Lewis Baker
  • Coroutine Theory
  • C++ Coroutines: Understanding operator co_await
  • C++ Coroutines: Understanding the promise type
  • C++ Coroutines: Understanding Symmetric Transfer
  • C++ Coroutines: Understanding the Compiler Transform

Kotlin

• Kotlin Coroutines Design Document
• Kotlin coroutines: design and implementation

Python

• A Curious Course on Coroutines and Concurrency by David Beazley

Syntax

• What Color is Your Function? by Bob Nystrom, Hacker news
• [C#] Asynchrony in C# 5 Part Six: Whither async? by Eric Lippert
• [Rust] A final proposal for await syntax
• [Kotlin] How do you color your functions? by Roman Elizarov

Cancellation & Structured Concurrency

• Asynchronous Exceptions in Haskell by Simon Marlow, SPJ et al
• Making Reliable Distributed Systems in the Presence of Software Errors by Joe Armstrong
• Structured Concurrency by Martin Sústrik
• Timeouts and cancellation for humans, Notes on structured concurrency, or: Go statement considered harmful by Nathaniel J. Smith
• Structured concurrency by Roman Elizarov

Structured programming

• Control Structures by Xavier Leroy
• Go To Statement Considered Harmful, Notes on Structured Programming by Edsger Dijkstra
• The Forgotten Art of Structured Programming by Kevlin Henney
• https://xkcd.com/292/

Scheduling

Work-stealing

• Scheduling Multithreaded Computations by Work Stealing
• Go scheduler: Implementing language with lightweight concurrency by Dmitry Vyukov
• Making the Tokio scheduler 10x faster
• Taskflow: A Lightweight Parallel and Heterogeneous Task Graph Computing System

Implementations

• [Golang] Runtime
• [Rust] Tokio Multi-Threaded Runtime
• [Kotlin] Coroutine Runtime
• [Scala] Cats Effect

Queues

Chase-Lev

• Dynamic Circular Work-Stealing Deque by Chase & Lev
• Correct and Efficient Work-Stealing for Weak Memory Models
  • Fence Cumulativity: Repairing Sequential Consistency in C/C++11
• https://github.com/taskflow/work-stealing-queue

BWoS

• BWoS: Formally Verified Block-based Work Stealing for Parallel Processing

Thread-per-core

• Shared-nothing Design, https://github.com/scylladb/seastar
• Introducing Glommio, a Thread-per-Core Crate for Rust & Linux, https://github.com/DataDog/glommio

---

Locking

Spinlocks

• Correctly implementing a spinlock in C++ by Erik Rigtorp
• A Close Look at a Spinlock by John Regehr
• Locking, from traditional to modern (playlist) by Nir Shavit

Linus Torvalds

• User-space spinlocks
• sched_yield

Lock-freedom

• Wait-Free Synchronization by Maurice Herlihy, 1991
• The Art of Multiprocessor Programming (chapters The Relative Power of Synchronization Methods & The Universality of Consensus) by Maurice Herlihy, 2020 (2nd edition)
• On the nature of progress by Maurice Herlihy & Nir Shavit, 2011
• Are Lock-Free Concurrent Algorithms Practically Wait-Free? by Dan Alistarh et al, 2013

~ Distributed Consensus

• Impossibility of Distributed Consensus with One Faulty Process – FLP theorem – by Fischer, Lynch, Patterson, 1985
• Unreliable Failure Detectors for Reliable Distributed Systems by Tushar Deepak Chandra and Sam Toueg, 1996

~ Linearizability

• Linearizability: A Correctness Condition for Concurrent Objects by Maurice Herlihy and Jannette Wing, 1990
• Reading the Herlihy & Wing Linearizability paper with TLA⁺, 📐 TLA⁺ Spec by Lorin Hochstein & Markus Alexander Kuppe

Data Structures / Algorithms

• Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms
• A Scalable Lock-free Stack Algorithm
• The Baskets Queue
• Lock-free deques and doubly linked lists
• Fast Concurrent Queues for x86 Processors
• moodycamel::ConcurrentQueue
  • Detailed Design of a Lock-Free Queue
• Lock-free структуры данных

Channels

• Go channels on steroids by Dmitry Vyukov
• Scalable FIFO Channels for Programming via Communicating Sequential Processes
• Fast and Scalable Channels in Kotlin Coroutines by Koval, Alistarh, Elizarov, 2022

Memory Management

Reference counting

• Differential Reference Counting by Dmitry Vyukov

Atomic shared ptr

Talks

• Implementing a Lock-free atomic_shared_ptr
• A Lock-Free Atomic Shared Pointer in Modern Cpp
• Lock-free Atomic Shared Pointers Without a Split Reference Count? It Can Be Done!

Implementations

• AtomicSharedPtr from Folly
• TAtomicPtr from YTsaurus
• atomic_shared_ptr by Anthony Williams

Hazard Pointers

• Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects by Maged M. Michael

Epochs

• Epoch-Based Memory Reclamation
• Lock-freedom without garbage collection by Aaron Turon

RCU (Read-Copy-Update)

---

Multi-Word CAS

Algorithms

• [HFP, 2002] A Practical Multi-Word Compare-and-Swap Operation
• [GKMZ, 2020] Efficient Multi-word Compare and Swap

Implementations

• Kcas — STM based on lock-free MCAS
  • Kcas: Building a Lock-Free STM for OCaml
  • k-CAS for sweat-free concurrent programming
  • Extending k-CAS with efficient read-only CMP operations

Reagents

by Aaron Turon

• Reagents: Expressing and Composing Fine-grained Concurrency
• Slides
• Thesis

Transactions

HTM

• Transactional Memory: Architectural Support for Lock-Free Data Structures by Maurice Herlihy
• Talk, Slides by Maurice Herlihy
• Understanding Hardware Transactional Memory by Gile Tene
• The Azul Hardware Transactional Memory Experience by Cliff Click
• Is Parallel Programming Hard, And, If So, What Can You Do About It?, 17.3 by Paul McKenney
• Глава 16 – Programming with Intel Transactional Synchronization Extensions
• Глава 15 – Intel TSX Recommendations
• TSX Anti-Patterns
• Lock Elision Implementation Guide

STM

• [Haskell] Composable Memory Transactions by Harris, Marlow, Peyton Jones, Herlihy, 2005
• A (brief) retrospective on transactional memory by Joe Duffy
• [Scala, ZIO] Introduction to Software Transactional Memory
• [Multicore OCaml] Kcas — STM based on lock-free MCAS
• Transactional Locking II

IO

Model

Readiness

• epoll
• kqueue

Completeness

• Windows IOCP
• Efficient IO with io_uring
• Lord of the io_uring

API

• A Universal I/O Abstraction for C++

~ FP

Monads

• Monads for functional programming
• Imperative functional programming
• Typeclassopedia
• A monad is just a monoid in the category of endofunctors, what's the problem?
• Abstraction, intuition, and the “monad tutorial fallacy”

Monadic Concurrency

• Concurrent Haskell by SPJ et al
• A Monad for Deterministic Parallelism by Simon Marlow, Ryan Newton & SPJ
• Composable Memory Transactions by Tim Harris, Simon Marlow, SPJ & Maurice Herlihy
• Reagents: Expressing and Composing Fine-grained Concurrency by Aaron Turon

Formal Languages

• Communicating Sequential Processes (CSP) by C. A. R. Hoare
• A Science of Concurrent Programs (TLA) by Leslie Lamport

Verification

Race detection

• ThreadSanitizer – data race detection in practice, compiler-rt/lib/tsan/rtl
• FastTrack: Efficient and Precise Dynamic Race Detection

PCT

• A Randomized Scheduler with Probabilistic Guarantees of Finding Bugs

DPOR

• Partial-Order Methods for the Verification of Concurrent Systems: An Approach to the State-Explosion Problem by Patrice Godefroid, 1996
• [SeqCst] Dynamic Partial-Order Reduction for Model Checking Software by Flanagan & Godefroid, 2005
  • Fair Stateless Model Checking by Musuvathi & Qadeer, 2008
  • Bounded Partial-Order Reduction by Musuvathi et al, 2013
• [C++11] A Practical Approach for Model Checking C/C++11 Code by Norris & Demsky, 2016
• [SeqCst] Source Sets: A Foundation for Optimal Dynamic Partial Order Reduction by Abdulla et al, 2017
  • Comparing Source Sets and Persistent Sets for Partial Order Reduction
  • Optimal Dynamic Partial Order Reduction with Observers
• [RC11] Truly Stateless, Optimal Dynamic Partial Order Reduction by Kokologiannakis et al, 2022