Chapter 01 · The memory wall01 / 18

A fast core, a slow memory

A CPU core is absurdly fast. At 4 GHz its clock ticks every quarter of a nanosecond, and a modern core can finish several instructions on every tick.

Main memory is not. RAM, the DRAM chips on a separate stick, takes roughly 80–100 ns to answer a request. That's about 400 clock cycles, time in which the core could have run over a thousand instructions.

Watch the core walk a linked list. Each node sits somewhere random in memory, and the core can't ask for the next node until the current one arrives, because that's where the next address is written. The gauge counts the cycles it spends waiting.

Real cores don't just sit there: out-of-order execution keeps several loads in flight at once. But in a linked list every address comes out of the previous load, so there's nothing to overlap.

list.cin the real world
struct node { long value; struct node *next; };
 
long sum = 0;
for (struct node *p = head; p != NULL; p = p->next)
    sum += p->value;   // the next address is inside *p

The add takes one cycle. The load that feeds it can take four hundred.