ContentsThe library

Memory, All the Way Down

Two Threads, No Shared Variables, and One of Them Is Ten Times Slower

Last timeThe Two Places Things Live

Caches must agree, so a write by one core takes a block away from another. Two threads that share nothing can still fight, purely over where their data happens to sit.

Why the caches must agree

Every core has its own nearest cache. Two cores reading the same block each

hold a copy, which is fine and is the point. Then one of them writes.

If nothing were done, the two copies would differ, and a program would see a

value it had already overwritten, or two threads would read different values

from the same address at the same moment. That is not slowness, it is the

machine failing to be a machine. So the hardware runs a protocol on every

write to keep the copies in agreement.

The protocol is simpler than its reputation. A block in a core's cache is in

one of a few states, the important two being shared, meaning other copies may

exist and this one may only be read, and exclusive, meaning this core is the

only holder and may write. To move from shared to exclusive, a core sends a

message that invalidates every other copy and waits for the acknowledgements.

FIG 1What happens when a core writes a block others hold
The loop at the bottom is the whole phenomenon. One core writing repeatedly pays nothing after the first write. Two cores writing alternately pay the full transfer on every single write, which is why this scales so badly.

What a write costs when it is shared

An uncontended write that hits in the nearest cache is a few cycles. A write

that has to take ownership from another core on the same chip is around sixty

to a hundred nanoseconds, because the message has to travel across the chip,

find the holders, and come back.

FIG 2Time spent moving one contested block
total time spent transferring ownership
the number of writes to the block by a core that did not already own it
the cost of one ownership transfer, around a hundred nanoseconds
Two threads each incrementing a shared counter ten million times produce roughly twenty million transfers. At a hundred nanoseconds each that is two seconds of pure traffic, for an operation that takes a fraction of a nanosecond when uncontended.

Note what this does to scaling. Adding cores to a program with a contested

block does not merely fail to help, it actively hurts, because each additional

core adds another participant to the ping-pong. A four-thread version can be

slower in absolute terms than the single-threaded one, which is a result people

find hard to believe until they measure it.

The lesson stops here

5 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the planThe contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

The rest of this course

  1. 01Two Programs Can Hold the Same Address and Never Collide
  2. 02A Few Hundred Entries Decide Whether Your Program Falls Off a Cliffopening only
  3. 03Most Faults Cost a Microsecond and One Costs Ten Thousandopening only
  4. 04If a Cache Hit Took One Second, Main Memory Would Take Four Minutesopening only
  5. 05You Asked for Four Bytes and Sixty-Four Arrivedopening only
  6. 06Predict the Speedup on Paper Before You Change a Lineopening only
  7. 07One Allocator Adds a Number, the Other Goes Lookingopening only
  8. 08Two Threads, No Shared Variables, and One of Them Is Ten Times Sloweryou are here

Read alongside