Data-structure references

Reading

Dmitry Vyukov’s 1024cores, notes on lock-free algorithms and scalable design, keeps “Unbounded SPSC Queue” at https://sites.google.com/site/1024cores/home/lock-free-algorithms/queues/unbounded-spsc-queue and “False-sharing” at https://sites.google.com/site/1024cores/home/lock-free-algorithms/false-sharing---false; the 1024cores.net address that older links use no longer serves them. Read the first for the producer’s local copy of the consumer’s position, re-read only when it runs out, and the padding between the two sides, and the second for its order of advice: remove sharing first, pad what is left.

The rtrb crate (https://docs.rs/rtrb/) is this chapter’s ring as a library, with head and tail in CachePadded and each side holding a cached copy of the other’s index. crossbeam-queue (https://docs.rs/crossbeam-queue/) has ArrayQueue, a bounded queue for many producers and consumers; read it for what a ring avoids by being one to one. crossbeam-utils documents CachePadded (https://docs.rs/crossbeam-utils/latest/crossbeam_utils/struct.CachePadded.html) and the size it pads to on each architecture, 128 bytes on x86-64.

Matt Kulukundis, “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step”, CppCon 2017 (https://www.youtube.com/watch?v=ncHmEUmJZf4), introduced Google’s SwissTable, and the standard HashMap’s documentation points to it for how its algorithm works; read it for the control bytes and the one-instruction compare of a group.

The hashbrown documentation (https://docs.rs/hashbrown/) describes the port of SwissTable behind the standard HashMap; read it for the hasher as a type parameter of the map, the change that turns 20–50 ns into 5–15 ns.

Jason Evans, “A Scalable Concurrent malloc(3) Implementation for FreeBSD”, BSDCan 2006 (https://people.freebsd.org/~jasone/jemalloc/bsdcan2006/jemalloc.pdf), introduced jemalloc: four separately locked regions of the heap per processor, threads spread over them, 2 MB chunks and size classes. Read it for the contention that makes a multi-threaded malloc need such regions, which a program avoids entirely by not calling it.

Jeff Bonwick, “The Slab Allocator: An Object-Caching Kernel Memory Allocator”, USENIX Summer 1994 (https://www.usenix.org/legacy/publications/library/proceedings/bos94/bonwick.html), describes the SunOS 5.4 kernel allocator. Read it for keeping objects in their prepared state between uses, which is what a pool does with its slots.

The Rustonomicon (https://doc.rust-lang.org/nomicon/) is the book on what unsafe code must uphold: read “repr(Rust)” and “Other reprs” (repr-rust.html, other-reprs.html) for what the default layout does not promise, and “Working with Uninitialized Memory” with its “Unchecked” page (uninitialized.html, unchecked-uninit.html) for why uninitialised memory is not a value and how MaybeUninit is filled.

Mara Bos, Rust Atomics and Locks (O’Reilly, 2023), is free to read at https://mara.nl/atomics/. Its chapter 5, “Building Our Own Channels”, builds a channel from a Mutex<VecDeque> and a Condvar that wakes the receiver, then one-shot channels around UnsafeCell<MaybeUninit<T>> and an atomic flag. It does not build a ring, but it shows the slot and the Release/Acquire flag the ring is made of.

Ulrich Drepper, What Every Programmer Should Know About Memory (2007), is at https://people.freebsd.org/~lstewart/articles/cpumemory.pdf, and LWN serialised it from https://lwn.net/Articles/250967/. Read its chapter on CPU caches and, in “What Programmers Can Do”, the parts on laying structures out to fit level 1 cache lines and on false sharing.

Nicholas Nethercote and others, The Rust Performance Book (https://nnethercote.github.io/perf-book/), is a practical guide to measuring and changing Rust code: its chapters “Heap Allocations”, “Hashing”, “Type Sizes”, “Bounds Checks”, “Inlining” and “Machine Code”.