Appendix M — The machine, measured: caches, branches and cores in numbers

Chapter 12 taught that memory is a ladder: registers fastest, then the caches, main memory slow, disks very slow. chapter 13 showed pipelines and branch prediction.

All true. But how fast and how slow? “It is fast if it fits in cache” could mean a hundredfold or it could mean 1.2 times. That difference changes designs.

This appendix puts numbers on what those two chapters said in words. And one thing more — it teaches how to measure. A number measured wrongly is worse than no number.

Why measure — with concepts alone, what remains is wrong intuition#

Compare three sentences. All three are commonly said, and all three are “broadly true”.

• “It is fast if it fits in cache.”
• “Branches are expensive.”
• “More threads make it faster.”

No decision can be made from these. Whether to size an array at 4 MiB or 400 KiB, how much effort to spend removing a conditional, whether two threads may touch the same struct — every one of those needs a number.

Filling in those numbers is what this appendix is for. But before numbers, look at the instrument that measures them.

Measure the measuring instrument first#

The first thing people do when writing measurement code is read a clock. And reading a clock has a cost. If what you are measuring is shorter than that cost, what you are measuring is the clock.

★ The fourth row is the clock this appendix uses. The reason not to use the wall clock is simple — if time synchronisation happens mid-measurement you get a negative duration. Half the bug reports saying “sometimes it prints −3 ms” are this.

Figure 115.1 — Three traps in measuring, and the guard against each.

static void sum_discarded(const int *a, size_t n)
{
    long s = 0;
    for (size_t i = 0; i < n; i++) s += a[i];
    (void)s;
}
/* … */
static long sum_kept(const int *a, size_t n)
{
    long s = 0;
    for (size_t i = 0; i < n; i++) s += a[i];
    return s;
}
/* … */
const long N = 200000;
double t0 = ns();
for (long i = 0; i < N; i++) { struct timespec ts; clock_gettime(CLOCK_MONOTONIC, &ts); sink += ts.tv_nsec; }
double t1 = ns();
double call_ns = (t1 - t0) / (double)N;
/* … */
t0 = ns(); memset(b, 1, NA * sizeof *b); t1 = ns();
double first = t1 - t0;  sink += ((unsigned char *)b)[NA / 2];
t0 = ns(); memset(b, 2, NA * sizeof *b); t1 = ns();
double second = t1 - t0; sink += ((unsigned char *)b)[NA / 2];

== 1. this machine's numbers (the example reads them itself) ==
  L1 data cache          
    size        : 32768 bytes (32 KiB)
    line size   : 64 bytes
    associativity: 8-way
  L2 cache      : 256 KiB
  L3 cache      : 16384 KiB (16 MiB)
  page size     : 4096 bytes
  logical cores : 16

== 2. clock resolution --- how finely can it be seen ==
  CLOCK_MONOTONIC   (never goes backwards)   resolution 1 ns
  CLOCK_REALTIME    (wall clock --- it jumps when adjusted) resolution 1 ns
  CLOCK_PROCESS_CPUTIME_ID (CPU time I used) resolution 1 ns
  * a resolution of 1 ns does not mean 1 ns can be measured.
    Reading the clock costs more than that --- measured next.

== 3. the cost of reading the clock ==
  one clock_gettime : 16.7 ns
  smallest interval actually distinguishable : 17.0 ns
  * so anything shorter than this is never measured once. Repeat and divide.
    Every measurement in this appendix is built that way.

== 4. trap one: the optimiser removes what you meant to measure ==
  a sum whose result is discarded :          5 ns  (0.00 ns per element)
  a sum whose result is used      :     382420 ns  (0.36 ns per element)
  factor                          : 74984.3 x
  * if the first is near zero, that code never ran. The compiler removed it as
    a value nobody uses. When the result says your code is infinitely fast,
    suspect this before suspecting the machine.

== 5. trap two: the first round is slow (warming up) ==
  filling the same 4 MiB --- first  :  1850349 ns
                          second :   159377 ns
  factor: 11.6 x
  * the first round mixes in the cost of the OS attaching pages one by one (page faults).
    So warm up before measuring, and discard the warm-up rounds.

== 6. trap three: one interruption drags the mean ==
  results over 201 rounds
  minimum           12357 ns
  median            12796 ns  <- what this appendix uses
  mean              14479 ns
  99th percentile        25154 ns
  maximum           32877 ns
  mean / median = 1.13 x  (the further from 1, the more other work interfered)
  * this machine is shared. So the median is used rather than the mean, with the
    minimum alongside to show what it would be with no interference.

The demonstration comes in six pieces. One at a time.

1. The example reads the machine’s numbers itself#

sysconf is asked for the cache sizes, line size, page size and core count. The later demonstrations use those as the baseline — so instead of “past 32 KiB it slows down” we can say “past the L1 size it slows down”.

2 and 3. Resolution and call cost are different things#

clock_getres answers one nanosecond. But actually calling clock_gettime once costs about 17 nanoseconds on this machine, and the smallest interval two reads can distinguish is the same.

★ From which one rule follows. Anything shorter than 17 nanoseconds is never measured in a single reading. It is repeated a million times and divided. Every demonstration in this appendix is built that way.

4. The first trap — the optimiser removes what you meant to measure#

The same sum is measured twice: once discarding the result, once using it. The demonstration printed 3 ns against 216,713 ns — more than ten thousand times apart.

The first is not fast; it did not run. The compiler has the right to delete a computation whose value nobody uses (the as-if rule, chapter 14). A loop adding a million values disappeared entirely.

5. The second trap — the first round is slow#

The same 4 MiB was filled twice, and the first was about ten times slower. The reason is not computation but memory. The address malloc gave is not yet attached to real memory, and at each first touch the operating system attaches one page (page faults, chapter 12).

★ While writing this demonstration, we walked into trap 4 first. With nobody reading the filled result, memset disappeared entirely and produced the nonsense “4 MiB filled in 38 nanoseconds”. Only after adding a line that reads one byte afterwards did that difference appear. Traps do not arrive one at a time.

6. The third trap — one interruption drags the mean#

Measure the same work 201 times and the values scatter. On this machine the minimum was 12,354 ns, the median 12,531, the maximum 21,834 — the maximum 1.7 times the median. That round had other work cutting in.

★ In code with a deadline (an audio callback, a control loop, an interrupt handler) the maximum is the design figure. “One millisecond on average” is no comfort — one late round and the sound breaks. “Measure the worst case” from the appendix on C without an operating system is the same story.

The six disciplines of this appendix#

What has been seen so far, written down as a contract. Every demonstration that follows keeps it.

Measuring the memory ladder#

With the instrument measured, the first thing to measure: the ladder of chapter 12.

First the principle — why a ladder appeared#

CPUs got faster and main memory did not keep up. That gap widened over decades, and layers were inserted to fill it. Those are the caches.

Two things are needed to read the measurements that follow: the unit in which a cache moves data, and prefetching.

First, a cache moves in “lines”, not bytes. On this machine a line is 64 bytes. Read one int (4 bytes) and the 64 bytes around it come up whole.

Second, the machine guesses what will be read next. When addresses grow regularly, prefetching circuitry runs ahead and fetches them. So a program reading in order hardly feels slow memory at all.

So how must it be measured#

Because of the second property, measuring “how far away memory is” while reading in order gives no answer — the machine has already fetched it. To see the latency you must make the next address impossible to know in advance.

The classic method: pointer chasing — link the array into a single ring in random order, so that the value just read tells you where to read next.

static void make_cycle(size_t *next, size_t n)
{
    for (size_t i = 0; i < n; i++) next[i] = i;
    for (size_t i = n - 1; i > 0; i--) {
        size_t j = (size_t)(rnd() % i);
        size_t t = next[i]; next[i] = next[j]; next[j] = t;
    }
    /* turn the permutation into a ring: link next[a]=b so it reads "after a comes b" */
    size_t *cyc = malloc(n * sizeof *cyc);
    for (size_t i = 0; i < n; i++) cyc[next[i]] = next[(i + 1) % n];
    memcpy(next, cyc, n * sizeof *cyc);
    free(cyc);
}
/* … */
static double chase(size_t *next, size_t n, long steps)
{
    size_t p = 0;
    for (long i = 0; i < (long)n * 4 && i < 4000000L; i++) p = next[p];   /* warm-up */
    double t0 = ns();
    for (long i = 0; i < steps; i++) p = next[p];
    double t1 = ns();
    sink = p;
    return (t1 - t0) / (double)steps;
}

== the caches of this machine ==
  L1 32 KiB · L2 256 KiB · L3 16384 KiB (16 MiB)

== time for one read, by working set size ==
  it follows a random ring, so prefetching does not help --- pure latency.

  working set  where      random access  factor     sequential
  4 KiB        L1             1.44 ns     1.0x     0.38 ns
  8 KiB        L1             1.44 ns     1.0x     0.37 ns
  16 KiB       L1             1.45 ns     1.0x     0.37 ns
  32 KiB       L1             1.48 ns     1.0x     0.37 ns
  64 KiB       L2             2.64 ns     1.8x     0.39 ns
  128 KiB      L2             3.59 ns     2.5x     0.38 ns
  256 KiB      L2             5.68 ns     3.9x     0.39 ns
  512 KiB      L3             9.66 ns     6.7x     0.39 ns
  1 MiB        L3            12.59 ns     8.7x     0.63 ns
  2 MiB        L3            15.17 ns    10.5x     0.40 ns
  4 MiB        L3            33.49 ns    23.2x     0.40 ns
  8 MiB        L3            59.12 ns    41.0x     0.54 ns
  16 MiB       L3            74.67 ns    51.7x     0.60 ns
  32 MiB       main memory    82.82 ns    57.4x     0.60 ns
  64 MiB       main memory    86.73 ns    60.1x     0.59 ns
  128 MiB      main memory    91.40 ns    63.3x     0.68 ns

== how to read this ==
  1. reading down the table shows steps. Wherever the working set passes
     the size of a cache, the cost jumps.
  2. the last column (sequential) barely changes. Reading in order lets the
     machine prefetch the next line --- the latency is the same, but nothing waits.
  3. so "it is fast if it fits in cache" is only half right. More precisely:
     access it unpredictably and outside the cache is tens of times slower.

What was measured — the steps appear#

Figure 115.2 — The latency curve, actually measured. The vertical dashed lines are this machine’s cache boundaries.

★ This figure is measured, not drawn. The figure generator reads the values that demonstration left behind — run it on another machine and that machine’s steps are drawn.

Four things to read from the table the demonstration printed and from the figure.

First, the steps line up with the cache boundaries. Flat up to 32 KiB (L1), then a jump past it. The same happens at 256 KiB (L2) and 16 MiB (L3). The numbers we read through sysconf in section 1 have appeared as time.

Second, the innermost rung (L1) and the outermost (main memory) differ by tens of times. On this machine, about 1.4 ns against roughly 90 ns — sixty-odd times (each run moves by a few nanoseconds). The same code, the same instruction count — only where the data sits parts them by that much.

Third, the “sequential” column is nearly flat. It stays around 0.4 ns all the way. Main memory did not suddenly get faster — nothing waits. Prefetching has the next line up in advance.

Fourth, so the common advice must be rewritten.

Lines and strides — the unit a cache fetches#

The previous section passed over “a cache moves in lines” in one sentence. This section measures whether that line really exists, and what mark it leaves on code.

First the principle — why a line and not a single item#

Fetching 4 bytes from memory and fetching 64 cost about the same. Most of the time is sending the address and waiting; the transfer itself is small beside it. And a program usually reads nearby places soon after (locality). So while fetching, fetch the neighbourhood.

The method — vary the stride, fix the count#

The array is read jumping by 1, 2, 4, … bytes. What matters is fixing the number of accesses, so that what shows is not “how many reads” but “how much one read costs”.

for (long stride = 1; stride <= 4096; stride *= 2) {
    size_t mask = BUF - 1;               /* BUF is a power of two, so & can wrap it */
    double s[5];
    for (int r = 0; r < 5; r++) {
        size_t p = 0;
        long acc = 0;
        double t0 = ns();
        for (long i = 0; i < TOUCH; i++) { acc += buf[p]; p = (p + (size_t)stride) & mask; }
        double t1 = ns();
        sink = acc;
        s[r] = (t1 - t0) / (double)TOUCH;
    }
    qsort(s, 5, sizeof *s, cmp_d);
    if (base == 0) base = s[2];
    double lines_per_touch = stride >= line ? 1.0 : (double)stride / (double)line;
    double wasted = stride >= line ? (double)line - 1 : 0;
    printf("  %-10ld %8.2f ns %7.1fx  %-16.3f %.0f bytes\n",
           stride, s[2], s[2] / base, lines_per_touch, wasted);
    printf("#DATA %ld %.3f\n", stride, s[2]);
}
/* … */
struct particle { double x, y, z, vx, vy, vz; int id, flags; };  /* the real size is printed below */
/* … */
for (int r = 0; r < 5; r++) {
    double acc = 0, t0 = ns();
    for (size_t i = 0; i < N; i++) acc += aos[i].x;      /* only x, from the array of structs */
    double t1 = ns(); sink = (long)acc; s1[r] = (t1 - t0) / (double)N;

    acc = 0; t0 = ns();
    for (size_t i = 0; i < N; i++) acc += xs[i];         /* from an array holding only x */
    t1 = ns(); sink = (long)acc; s2[r] = (t1 - t0) / (double)N;
}

== the cache line of this machine: 64 bytes ==

== varying the stride --- the number of accesses fixed at 2000000 ==
  stride     each           factor     lines touched    bytes fetched in vain
  1              0.66 ns     1.0x  0.016            0 bytes
  2              0.67 ns     1.0x  0.031            0 bytes
  4              0.75 ns     1.1x  0.062            0 bytes
  8              0.86 ns     1.3x  0.125            0 bytes
  16             1.37 ns     2.1x  0.250            0 bytes
  32             2.25 ns     3.4x  0.500            0 bytes
  64             4.32 ns     6.6x  1.000            63 bytes
  128            6.18 ns     9.4x  1.000            63 bytes
  256            7.55 ns    11.5x  1.000            63 bytes
  512            7.95 ns    12.1x  1.000            63 bytes
  1024           8.62 ns    13.1x  1.000            63 bytes
  2048           8.20 ns    12.5x  1.000            63 bytes
  4096           6.93 ns    10.5x  1.000            63 bytes

  * the cost rises until the stride reaches 64 bytes (the line size), and
    then flattens. A stride narrower than a line uses one line several times,
    while a wider one takes a new line each step and has little room to worsen.
    (the rise again at very wide strides is pages and the TLB --- the next section.)

== the same data, laid out differently ==
  size of one struct : 56 bytes (line 64 bytes)
  4194304 elements --- 224 MiB in total

  layout                             per element     factor bytes used per line
  array of structs (AoS) --- reading x only   3.288 ns      2.7x  8 / 56
  structs of arrays (SoA) --- reading the x array only   1.215 ns      1.0x  64 / 64

  * the same values were added the same number of times. Only the layout changed.
    In the array of structs, 56 bytes are fetched to use 8 --- the rest merely
    occupy cache and are thrown away. So when one field is swept often,
    splitting into one array per field (SoA) wins.
  * the reverse holds too. Code using several fields of one element together
    prefers the array of structs --- there the whole fetched line is used. The access pattern decides.

Figure 115.3 — Cost per access against stride. The vertical dashed line is this machine’s cache line size.

What was measured — the line appears in the time#

A narrow stride is cheap. Strides of 1 to 8 bytes cost 0.6 to 0.8 ns. One line is fetched and used several times over — a 64-byte line with a stride of 8 is used eight times.

At the line size the cost jumps. At 64 bytes, 3.2 ns — five times. Now every step takes a new line and there is nothing to share.

After that it flattens. Widening to 128, 256, 512 bytes barely raises it. It is already “a line per step” and there is little room to worsen (the next jump in the curve comes from pages and the TLB, which is the next section).

The same data, laid out differently — AoS and SoA#

The practical conclusion of this section. Two ways of summing only the x of four million particles were measured.

The same values were added the same number of times, and the instruction counts are close. Only the arrangement changed, and they parted by more than a factor of two.

★ The last row joins the remark in chapter 41 that arrays are the friendlier side for vectorisation. For the compiler to process several elements at once, the same field must be contiguous. The layout opens the door to the optimisation.

Address translation has a cost too — the TLB and pages#

So far it was “where the data is”. But the addresses a program uses are not real addresses. As seen in chapter 12, what we see is a virtual address and the machine translates it to a real one. Translation has a cost, and sometimes that cost becomes visible.

First the principle — the translation table and its cache#

Translation is a table lookup. On 64-bit Linux that table has four levels, so translating one address means four reads of memory. Four extra memory reads per access would be unbearable.

So there is a small cache holding translation results: the TLB (translation lookaside buffer).

★ The three rows part by orders of magnitude. And the third is done by the operating system, not hardware, which is why its cost is another digit larger.

The method — little data, many pages#

To separate cache effects from translation effects, keep the amount of data small while raising only the page count. So only 8 bytes per page are touched, and the pages are linked into a random ring.

static double walk(unsigned char *mem, size_t pages, size_t page, long steps)
{
    size_t *order = malloc(pages * sizeof *order);
    for (size_t i = 0; i < pages; i++) order[i] = i;
    for (size_t i = pages - 1; i > 0; i--) {
        size_t j = (size_t)(rnd() % i);
        size_t t = order[i]; order[i] = order[j]; order[j] = t;
    }
    /* write "the next page's offset" in each page's first 8 bytes to make the ring */
    for (size_t i = 0; i < pages; i++) {
        size_t cur = order[i], nxt = order[(i + 1) % pages];
        *(size_t *)(mem + cur * page) = nxt * page;
    }
    free(order);

    size_t p = 0;
    for (size_t i = 0; i < pages; i++) p = *(size_t *)(mem + p);      /* warm-up */
    double t0 = ns();
    for (long i = 0; i < steps; i++) p = *(size_t *)(mem + p);
    double t1 = ns();
    sink = p;
    return (t1 - t0) / (double)steps;
}
/* … */
        madvise(aligned, bytes, mode ? MADV_HUGEPAGE : MADV_NOHUGEPAGE);
#endif
        memset(aligned, 0, bytes);
        long ah = anon_huge_kib(aligned);
/* … */
for (size_t i = 0; i < fp; i++) mem[i * page] = 1;      /* first touch of each page */
double t1 = ns();
double first = (t1 - t0) / (double)fp;
t0 = ns();
for (size_t i = 0; i < fp; i++) mem[i * page] = 2;      /* pages already present */

== the page size of this machine: 4096 bytes ==

== 1. how many pages before translation becomes the bottleneck ==
  only 8 bytes are touched per page. Little data, but the page count grows.

  pages      data touched each         factor
  16         64 KiB           3.57 ns    1.0x
  64         256 KiB          7.46 ns    2.1x
  256        1 MiB           15.70 ns    4.4x
  1024       4 MiB           16.14 ns    4.5x
  4096       16 MiB          47.86 ns   13.4x
  16384      64 MiB          89.01 ns   24.9x
  65536      256 MiB         98.04 ns   27.4x

  * the data is small (8 bytes per page), and yet more pages costs more.
    The bottleneck is address translation, not the cache. When the table
    holding translations (the TLB) runs out of room, the machine must walk
    the page tables again.

== 2. what happens with huge pages ==
  normal pages advised         backed by huge pages: 0 KiB (0%)
  huge pages advised           backed by huge pages: 0 KiB (0%)
  the same 256 MiB is walked the same way.
  normal pages (4 KiB)            98.69 ns
  huge pages advised (MADV_HUGEPAGE)    98.57 ns
  difference: 1.00 x --- no great difference in this run
  * one huge page replaces 512 pages of 4 KiB, so the translations needed to
    sweep the same data fall to a 512th. But madvise is a request, not an order.
    The "backed by huge pages" figure above says whether the request was taken ---
    if both runs are backed alike, similar times are only to be expected.
    (this machine uses huge pages by default, so even the "normal pages" run
     may already have some mixed in.)

== 3. the cost of touching a page for the first time ==
  touching a page the first time :   1180.2 ns
  touching an already-mapped page:      8.8 ns
  factor: 134 x
  * the address `malloc` returned is not memory yet. At each first touch the
    operating system attaches one page --- and that is its cost. Allocate a large
    buffer and measure at once and this cost is mixed in entire (hence warming up).

Three things measured#

1. More pages cost more. 3.5 ns at 16 pages (64 KiB) became 90 ns at 65,536 pages (256 MiB) — twenty-five times. The data touched is the same 8 bytes per page. The bottleneck is translation, not the cache.

2. The huge-page experiment came out “no difference” — and the reason was confirmed.

The demonstration compared a region advised with madvise for huge pages (pages far larger than the usual 4 KiB, so one TLB entry covers much more memory) against one not, and the times were equal. Stopping there would give the wrong conclusion, “huge pages are useless”. So the demonstration goes one step further — it reads /proc/self/smaps to check whether that region really was backed by huge pages. The answer was that the share backed by huge pages was the same for both regions — the figure for the run printed here is in the second part of the demonstration’s output.

3. Touching a page for the first time costs more than a hundred times as much as touching one already attached. Touching an already-attached page costs about 9 ns; touching a fresh one around a thousand. The address malloc returned is not memory yet, and at each first touch the operating system attaches one page.

The cost of a fork in the road — branch prediction#

Chapter 13 explained pipelines and branch prediction. Now the cost of a branch is measured.

First the principle — why the machine must guess#

The machine does not finish instructions one at a time; it overlaps them like an assembly line. An if creates a problem — the next instruction must be fed in while which way it goes is still unknown.

So the machine guesses: “last time the branch here was true, so it will be true again”. Right, and it flows on as if nothing happened; wrong, and everything filled in is thrown away and refilled.

Figure 115.4 — What happens in the pipeline when the prediction is right and when it is wrong.

Before measuring — is there still a branch#

There is a famous experiment: “sort the array first and a loop with a conditional gets faster”. Tried as it stands — there was no difference at all.

__attribute__((optimize("no-if-conversion", "no-if-conversion2", "no-tree-vectorize")))
static long sum_realbranch(const int *a, size_t n, int t)
{
    long s = 0;
    for (size_t i = 0; i < n; i++) if (a[i] >= t) s += a[i];
    return s;
}
/* … */
static long sum_branchless(const int *a, size_t n, int t)
{
    long s = 0;
    for (size_t i = 0; i < n; i++) {
        long mask = -(long)(a[i] >= t);      /* -1 (all ones) if true, 0 if false */
        s += a[i] & mask;
    }
    return s;
}

== the same data, the same computation, only the order differs ==
  summing only the values of 128 or more, over 4194304 elements (16 MiB).
  the two arrays hold exactly the same contents --- only sortedness differs.

                                     random order sorted order sorted/random
  source with an if (plain -O2)          0.667 ns     0.681 ns    0.98 x
  code that kept a real branch           4.384 ns     0.977 ns    4.49 x
  code with the branch turned into arithmetic     0.784 ns     0.758 ns    1.03 x

  * the first two rows have the same source. Only the compiler settings differ.
    In the first, the compiler turned the `if` into a conditional move (cmov), so
    there is no branch to predict and sorting brings no gain. That is why the
    famous "sorted arrays are faster" story often fails to reproduce today.

  extra time per element in the real-branch version: 3.407 ns
  / a miss probability of 0.5 = about 6.8 ns per misprediction

== how regular must it be to be predicted ==
  the same number of elements, with only the pattern of trues changed.

  pattern                              each note
  always true                      0.705 ns always predicted
  alternating                      1.002 ns short periods are memorised
  one in four                      1.145 ns short periods are memorised
  one in sixteen                   1.149 ns short periods are memorised
  random                           4.491 ns cannot be predicted

== how to read this ==
  0. today's compilers turn a short `if` into branchless code. So to measure
     branch prediction you must first check that a branch survives.
  1. "branches are expensive" is imprecise. On a sorted array a branch is cheap.
     What is expensive is a branch that cannot be predicted.
  2. on a random pattern the machine is wrong about half the time, and each miss
     empties and refills the pipeline --- the tens of nanoseconds computed above.
  3. short-period patterns are memorised, so even "one in four" is fast.
  4. branchless code takes the same time in any order --- but it always computes
     every element, so for an easily predicted branch it is a loss.

What was measured#

From this the cost of one misprediction can be extracted. Taking random data to miss about half the time: the extra 3.1 ns per element / 0.5 = about 6 ns per miss. On this machine that equals dozens of additions.

How regular must it be to be predicted#

Keeping the same number of elements and changing only the pattern of trues shows what the predictor can memorise.

★ This table corrects “branches are expensive” precisely. What is expensive is not a branch but a branch that cannot be predicted. A regular conditional is nearly free over a million iterations.

The cost between cores — false sharing and atomics#

So far it was one core. With several cores a new cost appears. Where chapter 95 dealt with how to share safely, here we measure how much that costs.

First the principle — a line belongs to one core at a time#

Caches are per core (at least L1). Then when two cores hold the same place, which one has the right value? So the hardware imposes a protocol — to write, the line must be owned exclusively.

★ The first row produces everything in this section. Writing is the act of erasing somebody else’s copy, and that erasing is communication between cores. And its unit is not a byte but a line.

False sharing — I slow down because of somebody else’s variable#

Here something strange happens. Two cores touch different variables, and if those sit in the same line the line is taken back and forth. Looking only at the code there is no sharing at all — hence false sharing.

Figure 115.5 — Two threads’ variables sharing a line, and kept apart.

struct slot { volatile long v; };
static unsigned char *arena;
static size_t slot_gap;

static void *bump(void *arg)
{
    long idx = (long)(intptr_t)arg;
    volatile long *p = (volatile long *)(arena + (size_t)idx * slot_gap);
    for (long i = 0; i < ITERS; i++) (*p)++;
    return NULL;
}
/* … */
static void *atomic_bump(void *arg)
{ (void)arg; for (long i = 0; i < ITERS / 10; i++) atomic_fetch_add_explicit(&shared_atomic, 1, memory_order_relaxed); return NULL; }
static void *mutex_bump(void *arg)
{ (void)arg; for (long i = 0; i < ITERS / 100; i++) { pthread_mutex_lock(&lock); shared_plain++; pthread_mutex_unlock(&lock); } return NULL; }

== this machine ==
  cache line 64 bytes · 16 logical cores

== 1. the baseline ==
  one thread incrementing its own slot : 1.555 ns each
  (measured on a local variable the compiler folds the loop away, so it is no baseline)

== 2. two threads each incrementing their own slot --- only the distance changes ==
  the two threads never touch each other's data. And yet…

  with two threads, a perfect split would make each increment half the
  baseline (0.778 ns). Anything above that is the loss.

  distance       per increment    vs perfect scaling same line?
  8                   1.098 ns       1.41x  same line --- false sharing
  16                  1.115 ns       1.43x  same line --- false sharing
  32                  1.095 ns       1.41x  same line --- false sharing
  64                  0.781 ns       1.00x  different lines
  128                 0.773 ns       0.99x  different lines
  256                 0.779 ns       1.00x  different lines

  * the two threads touch different variables. But in the same cache line the
    line is passed back and forth between the cores --- that is false sharing.
    Moving them apart changes it several fold, with not one line of code altered.

== 3. adding threads --- sharing a line, and apart ==
  threads    same line (8 bytes apart) different lines (128 bytes) factor
  2                 1.070 ns        0.772 ns    1.4x
  4                 0.752 ns        0.391 ns    1.9x
  8                 1.157 ns        0.211 ns    5.5x

== 4. when several really do touch one value ==
  uncontended increment (baseline)        1.555 ns each
  atomic increment --- 1 thread           5.241 ns each
  atomic increment --- 2 threads         14.357 ns each
  atomic increment --- 4 threads         17.846 ns each
  increment under a lock --- 1 thread     18.826 ns each
  increment under a lock --- 2 threads     65.099 ns each

  * uncontended (one thread), the atomic costs 3x and the lock 12x.
    But when several contend for one value it jumps several fold again --- one
    line has to be owned exclusively by each core in turn.
  * hence the discipline: count separately, and combine once at the end.

What was measured#

★ The loss disappears at exactly 64 bytes, this machine’s cache line size. The same number we saw as a stride appears here again. One structure showing a second face.

Really shared values — atomics and locks#

If false sharing is accidental communication, several threads changing one value is real communication.

Three things to read.

First, there is a cost even without contention. With a single thread the atomic costs three times and the lock eleven. Owning a line and guaranteeing an order costs something.

Second, contention raises it again. Two threads changing the same value make the atomic cost twelve times the baseline. One line has to be owned by each core in turn.

Third, more threads do not help. From two to four the per-increment cost is unchanged — that place is serial, not parallel. It is the story of “when the holder stops” in chapter 95, appearing as numbers.

The cost of numbers — floating point#

Can the same multiplication cost different amounts? It can. This section measures the cases where the same operation costs different amounts.

First, this section’s measurement failed once#

It began with arrays of a million elements. Multiply, add, divide and square root all came out at exactly 1.24 ns. Operations cannot cost the same.

a[i] = mode ? DBL_MIN / 8.0 : 1.0;      /* subnormal : normal */
b[i] = 1.0;                             /* multiplying keeps the size --- the result is subnormal too */
/* … */
__attribute__((optimize("O3", "fast-math")))
static double vec_double(const double *a, const double *b, int reps)
{
    double s = 0;
    for (int r = 0; r < reps; r++) for (size_t i = 0; i < N; i++) s += a[i] * b[i];
    return s;
}
/* … */
switch (k) {
case 0: a0 += a[i] * b[i]; a1 += a[i+1] * b[i+1];
        a2 += a[i+2] * b[i+2]; a3 += a[i+3] * b[i+3]; break;
case 1: a0 += a[i] + b[i]; a1 += a[i+1] + b[i+1];
        a2 += a[i+2] + b[i+2]; a3 += a[i+3] + b[i+3]; break;
case 2: a0 += a[i] / b[i]; a1 += a[i+1] / b[i+1];
        a2 += a[i+2] / b[i+2]; a3 += a[i+3] / b[i+3]; break;
case 3: a0 += sqrt(a[i]); a1 += sqrt(a[i+1]);
        a2 += sqrt(a[i+2]); a3 += sqrt(a[i+3]); break;
default: a0 += sin(a[i]); a1 += sin(a[i+1]);
         a2 += sin(a[i+2]); a3 += sin(a[i+3]); break;
}

== how this is measured ==
  two arrays, 32 KiB together --- they fit in L1. Repeated 2000 times.
  four accumulators keep it from waiting on the previous result (breaking the dependency chain).

== 1. denormals --- numbers very close to zero ==
  the smallest normal double: 2.22507e-308
  array filled with normals (1.0)    0.297 ns per element
  array filled with denormals    20.961 ns per element
  -> the denormal side is 70.7 x slower
  * here the magnitude of a value alone changes the time. On some machines it is
    tens of times; on recent chips it is almost nothing --- so measure before speaking.
    (this is the accident where audio processing slows suddenly as a sound fades.)

== 2. float and double ==
  double (8 bytes)                0.297 ns per element
  float  (4 bytes)                0.289 ns per element
  -> the float side is 1.03 x faster --- odd: no difference

  measuring the same computation again, this time allowing vector instructions:
  double (vectors allowed)        0.576 ns per element
  float  (vectors allowed)        0.287 ns per element
  -> this time the float side is 2.01 x faster
  * the benefit of narrower width appears only with vector instructions. But
    floating-point addition is not associative (reordering changes the result),
    so the compiler may not regroup freely. "float is twice as fast" has conditions.
  * do not compare across the two pairs: the scalar version above already overlapped
    execution with four accumulators. Read the ratio within each pair.

== 3. the operations cost differently ==
  operation                per element    vs multiply
  multiply  a*b               0.316 ns      1.0x
  add       a+b               0.521 ns      1.6x
  divide    a/b               1.157 ns      3.7x
  sqrt      sqrt(a)           1.728 ns      5.5x
  sin(a)                      8.464 ns     26.8x

  * multiply and add cost about the same. Divide is several times, trigonometry tens.
    Hence the common trick of one divide for a reciprocal and many multiplies.
  * and the earlier failure is the greater lesson --- with a large array all of
    this difference is buried in memory bandwidth. To measure arithmetic, keep the data in cache.

Measured 1 — denormals were 72 times slower#

Numbers very close to zero are called subnormal numbers, or, by their older name, denormals. They approach zero while losing precision (chapter 54).

The same instructions, the same count, the same place. Only the magnitude of the values changed, and the time is 72 times as long. The hardware cannot take denormals down its fast path and falls to a slow one.

Measured 2 — is float faster than double?#

“Half the width, twice the speed” is commonly said. Measured, there was no difference (both 0.286 ns). And the reason is the most instructive part of this section.

★ Do not compare across the two pairs of that table. The non-vector version already overlapped execution with four accumulators. What to read is the ratio within each pair. This is what chapter 14 means by “a measurement must be written down with its conditions”.

Measured 3 — the operations cost differently#

Everything measured, in one place#

The numbers measured so far, gathered. They are values measured on this machine and the ARM phone, and the ratios last longer than the absolute times.

★ There is no need to memorise this table. What to remember is the shape of the magnitudes — inside the cache is nanoseconds, main memory tens of nanoseconds, mispredictions and inter-core communication from a few to tens of nanoseconds, and storage microseconds to milliseconds (the last section of the appendix on how a disk is divided).

Measured again on real ARM hardware#

The numbers so far belong to one x86-64 Linux machine. The same examples were also run on an Android phone — built with clang in Termux using the book’s own options, with the single-thread examples pinned to the four performance cores. The false-sharing and sharing demonstrations were run once more each, pinned to the four performance cores and to the four efficiency cores. All of it was run five times in a row, and the “ARM phone” column in the tables above is the median of those five. The tables on the cost between cores take the run pinned to the performance cores. The branch-prediction and floating-point demonstrations split the code with GCC switches, so they could not be measured on a phone that has only clang.

The steps are there, in other places. On the performance cores the cost doubles past 64 KiB, and past 4 MiB it jumps about threefold. The phone does not report its cache sizes (the box in section 1), so the boundaries can only be read from the curve — and the curve shows them. The relation “L1 is tens of times faster than main memory” remained, and the ratio grew from a little over 60x on x86 to a little over 90x.

On the efficiency cores the first step comes one size earlier. The cost doubles as soon as 32 KiB is passed, the two clusters meet at the same values at 1–4 MiB, and main memory takes about 322 ns, close to twice the performance cores. Sweeping in order is about four times slower too. The two kinds of core on one chip differ from the position of the first step on — that is as far as the curve goes.

The cost of reading the clock differs by more than ten times. One clock_gettime, about 17 ns on x86, took about 200–220 ns on the phone. The rule “never time anything shorter than that with a single reading” still holds, but the threshold has to be measured again on each machine. Why it costs that much this measurement could not tell.

Read a ratio together with its denominator. Touching a page for the first time cost about the same on both machines, around a thousand nanoseconds, but writing again to a page already attached grew from about 9 ns on x86 to about 35 ns on the phone, so the ratio fell from a little over 100x to 30x. “Ratios confidently” holds only when what the ratio is against is written down with it.

False sharing showed on the performance cores and not on the efficiency cores. Even pinned to the four performance cores, the two-thread loss is small — a distance of 8 bytes on the same line comes to 1.19x a perfect split (1.15–1.42x over five runs), 16 and 32 bytes to 1.06x, close to the 1.02–1.05x of different lines, and unlike nearly 1.4x on x86. Clearer is the run with four threads: four on the same line took about 0.91 ns per increment and four on separate lines about 0.59 ns, a difference of 1.5x (over 1.4x in all five runs). Pinned to the four efficiency cores the same experiment gave about 1.0x (0.9–1.1x), and two threads came to about 1.0x at every distance too. So for the efficiency cores all that is said here is “under these conditions it did not show”. Why, this measurement could not tell.

Real sharing went the other way. Two threads contending for one value with an atomic increment took about 68 ns on the performance cores and about 32 ns on the efficiency cores — although a single uncontended thread was slower on the efficiency cores (about 11 against 6.7 ns). The guess “faster cores communicate faster too” did not hold on this phone.

The five runs agreed well with each other. Main memory took 166–168 ns and two contending atomic increments 62–69 ns. What scattered widely was little more than the lock with two contending (94–129 ns) and false sharing at a distance of 8 bytes on one line (1.15–1.42x).

Runs two months earlier differed. Of three runs on the same phone in September, one was about 25% slower from L1 on and took about 305 ns for main memory — the values earlier editions of this book printed came from that run. The other two took about 174–177 ns for main memory, close to November. Two contending atomic increments took about 39 ns in both September runs, consistently lower than in all five November runs. The examples and the compiler were the same, and the battery was warmer in September, 34–36 °C against 29–30 °C in November. Whether that was the cause, or what made the difference at all, this measurement could not tell. So the phone’s numbers are trusted only for their magnitudes and their shape.

★ Running on the phone gave more than numbers. The C library that does not know its cache sizes (the box in section 1), and clang removing the memory fill entirely in the cow example of the appendix on the machinery that governs memory (the promise example had the same flaw), both surfaced in these runs — exactly this appendix’s first trap, the optimiser removes what you meant to measure. The fixed cow, run again on the phone, reached the same conclusion as on x86-64.

How to use these numbers#

The value of measuring is not “making it fast” but deciding where to look.

What to take from this#