Shared memory and its costs

3.1 What shared memory is made of

To the hardware, a thread is very little: an instruction pointer, a stack pointer and the contents of the registers. The operating system loads those into a core, and the core runs. Two threads of one process run in one address space, so an address means the same bytes to both of them, and a value one thread writes at an address is the value the other will eventually read there. That is everything shared memory promises, and the word eventually is where this chapter lives. Physically, there is no single memory that both threads look at. Each core works through caches of its own, and the bytes at one address can sit in several places at once.

Read it as the path of one store and one load. A store leaves the registers for the store buffer and waits there; it reaches the core’s own L1 later, and only then can another core see it. A load looks in the store buffer first and in L1 second, so a core always sees its own latest write. Below the private caches the cores share an L3 and an on-chip network that carries requests, invalidations and whole 64-byte lines between them. A second socket hangs off a link, and everything that crosses it costs two to three times as much.

The store buffer

The store buffer is a small queue between a core’s execution units and its L1 data cache. It holds stores that have executed but have not yet been written into the cache: between about 50 and 120 entries on current x86 cores.

A core needs one for two reasons. The first is speculation. The core runs ahead of branches it has not yet resolved, and a store on a path that turns out to be wrong must vanish without trace. Once a value is in the cache another core can read it, so a store may not touch the cache until it retires, the point at which the core knows the store really happened. The second is ownership. Writing a line needs the core to own it, and getting a line that another core holds takes 50–100 ns. A load has to wait for its data, because the next instruction needs it. Nobody waits for a store’s result, so the core parks the store and runs on. The buffer turns a 100 ns store miss into an instruction that costs one cycle.

After a store retires, the buffer writes it into L1, which is called committing it, as soon as the line is owned. x86 cores commit in program order, oldest first. ARM cores may commit a later store whose line is ready ahead of an earlier one that is still waiting for its line. A load to an address with a store still in the buffer takes its value from the buffer, which is called store-to-load forwarding. So the writing core sees its own store at once, and every other core sees it only after it commits: a few nanoseconds later when the line is already owned, 50–100 ns or more when it is not. For that interval the new value exists in exactly one place on the machine, and no other core can see it.

Ownership

The private caches keep their copies consistent with a coherence protocol, and its central rule is short. Many cores may hold a copy of a line in order to read it, but a core may write a line only while it holds the only copy. To get the only copy it sends a request for ownership: every other copy is invalidated, and if another core had modified the line, that core sends the current bytes across. The shared L3 keeps a directory of which cores may hold each line, so the request goes only where copies are. A line that changes hands this way costs about 50–100 ns between two cores on one socket, and two to three times that between sockets. The protocol works on whole lines, never on variables. That is why two threads writing different variables that happen to share a line slow each other down, which is called false sharing, and why values written by different threads are padded, placed on lines of their own; Chapter 1 measured both.

What is shared and what is not

Memory is shared, a line at a time, under the protocol. Registers are not shared, and neither is anything waiting in a store buffer, or any value the compiler decided to keep in a register instead of loading it again. The protocol makes two promises and no more. For any one line, every core agrees on the order of the writes to it. And every write eventually becomes visible to every core. It promises nothing about two different lines. Whether a core that sees the new value of one line also sees the new value of another depends on when each store left its buffer and when each load was served, and nothing in the protocol answers that.

Everything one thread hands to another travels this path, and its price is set by ownership rather than by bytes. Reading a line that several cores hold costs each of them a hit. Writing it costs an invalidation of every other copy, and the next reader on another core pays a transfer. A thread that writes a shared line a million times a second is asking the machine to move that line up to a million times a second.

Read more: Daniel Sorin, Mark Hill and David Wood’s A Primer on Memory Consistency and Cache Coherence is the standard account of coherence and of everything this chapter calls ordering. The Wikipedia articles on Cache coherence and Write buffer are the gentle entries.

3.2 The latency ladder of sharing

This ladder runs from the cheapest way two threads can touch the same memory to the most expensive, on a 4 GHz core, against the 1 µs budget. Several rows name things the later sections define. An atomic read-modify-write reads, changes and writes a value as one step no other core can interrupt. SeqCst is the strictest of the orderings a program can attach to an atomic access. futex is the system call a lock uses to put a waiting thread to sleep and wake it. A waiting thread spins when it re-reads a value in a loop until the value changes, and sleeps when it asks the kernel to stop running it until it is woken; a sleeper is a thread waiting that way. A thread is preempted when the kernel takes its core away to run another. Real parts vary by a factor of two either way; the shape of the ladder does not.

Read the table against the budget. The first five rows fit inside a microsecond many times over. A line transfer costs a tenth of the budget for one variable, and a contended atomic up to a third. Every row from the sleeping waiter down costs five budgets to several thousand, for no work at all: the thread is waiting for another thread.

Direct and indirect cost

Each row has two costs, and the table shows the first. The direct cost is paid by the core that runs the instruction. The indirect cost is paid by the others. A write invalidates every other copy of its line, and each of those cores pays a transfer on its next read. A read-modify-write or a SeqCst store empties the store buffer, so stores that were overlapping with useful work now stall it. A lock serialises: one thread’s time inside it is added to the wait of every thread queued behind it. The writer pays its row once. The indirect costs are paid by every reader, on every change, and by every waiter, on every hand-over.

Which rows matter

The rows above the line transfer are paid on every access, and they set the p50. The rows below it are paid only when two threads touch the same line close together in time, and they set the p99 and beyond. Collisions are rare until traffic is heavy. Two threads that each take one lock 100,000 times a second and hold it for 50 ns each hold it 0.5% of the time, so about one acquisition in 200 finds it held: the p99.5. Double the traffic and the collisions double, the waits lengthen, and some of them now reach the sleeping rows. The expensive rows live in the tail, and they grow faster than the load does.

Reading your own machine

Which cores share what decides which row a transfer lands in, and three facts about a box settle it. The first is the architecture, x86_64 or aarch64 as uname -m prints it, which decides which reorderings the hardware itself performs. The second is which logical CPUs are hyperthread siblings: lscpu -e lists each CPU with the physical core it belongs to, and two CPUs on the same core share its L1 and L2, so a line passed between them never moves.

The third is which cores share an L3. The last field of the CACHE column in lscpu -e is the L3 each CPU uses, and /sys/devices/system/cpu/cpu0/cache/index3/shared_cpu_list names the CPUs that share CPU 0’s. On many Intel parts every core of a socket shares one L3. AMD parts split each socket into core complexes with an L3 each, and a line that crosses between complexes costs two to three times one that stays inside. lstopo, from the hwloc package, draws the whole tree, and the core-to-core-latency crate measures the round trip between every pair of cores and prints the matrix; Lab 3.3 builds the same measurement by hand.