13 The machinery of speed — the birth of the standard

13.1 The pipeline — instructions on an assembly line#

Think of a laundry. If washing takes 30 minutes, drying 30 and ironing 30, then finishing one load before starting the next takes 270 minutes for three loads. But put the second load in the washer the moment the first moves to the dryer, and three machines handle different loads at the same time; once the flow fills up, one load comes out every 30 minutes.

The CPU’s handling of an instruction divides into stages in exactly the same way — fetch, decode, execute, write back. Making an assembly line of those stages is the pipeline. Individual instructions do not get faster — what increases is the number of instructions completed per unit of time. Modern CPU pipelines run to more than ten stages, and go further by having several lines so that multiple instructions complete per beat. Chapter 2′s “one step per beat” collapses like this — the apparent order is kept, but inside things overlap.

One trick from the same era is worth recording. To save the management cost of each turn of a loop (counting, judging the fork), there is a technique of handling several items per turn — loop unrolling. In 1983 a programmer named Tom Duff pushed this technique to its limit by grotesquely overlapping two pieces of C syntax, and the code became a legend under the name Duff’s device. The code itself cannot be shown yet — this book has not introduced those constructs. A reunion is booked (chapter 33). One sentence suffices for now: in those days people squeezed the machine’s beats with acrobatics like this, and today the acrobatics are the compiler’s job (chapter 14).

13.2 Branch prediction — guessing the fork in advance#

The pipeline has a sore spot: the fork. Meet an instruction like “if the result is zero, jump over there” (a branch) and, until the result is known, there is no telling which road’s instructions to load onto the line. Halt the line and wait, and the gain from overlapping evaporates.

So the CPU guesses. Like a café that prepares a regular’s order in advance, it learns from history that “this fork usually goes this way” and loads that road’s instructions onto the line ahead of time — branch prediction. Right, and it was free; wrong, and it throws away everything prepared, flushes the line and starts again. Because that penalty is as large as the depth of the pipeline, modern CPUs invest serious circuitry in the predictor, and hit rates in everyday code run well past 90%.

13.3 Measuring it — an easy condition and a hard one#

How much branch prediction is worth can be asked as well.

The experiment: prepare two arrays holding exactly the same values, one shuffled and one sorted. Run the same loop over each — “add the values that are 128 or more”. The number of comparisons, of additions and of values read is the same. Only the order in which the condition is true or false differs.

/* Same data, same condition --- only the order differs. Ask the machine about the gap.
   * This example measures time. No absolute times, only ratios (they vary by run). */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>

#define N      (1u << 20)     /* one million elements */
#define ROUNDS 5

static volatile uint64_t sink;

static uint64_t rng = 0x9E3779B97F4A7C15ULL;
static uint32_t rnd(void)
{ rng ^= rng << 13; rng ^= rng >> 7; rng ^= rng << 17; return (uint32_t)(rng >> 32); }

static int cmp_u8(const void *a, const void *b)
{ int x = *(const unsigned char *)a, y = *(const unsigned char *)b; return (x > y) - (x < y); }
static int cmp_d(const void *a, const void *b)
{ double x = *(const double *)a, y = *(const double *)b; return (x > y) - (x < y); }

/* Add only the values that pass the test --- whether that test is easy to predict
   is the subject of this example */
static double sum_over(const unsigned char *v)
{
    clock_t t0 = clock();
    uint64_t acc = 0;
    for (unsigned round = 0; round < 8; round++)
        for (uint32_t i = 0; i < N; i++)
            if (v[i] >= 128) acc += v[i];
    clock_t t1 = clock();
    sink = acc;
    return (double)(t1 - t0);
}

int main(void)
{
    unsigned char *shuffled = malloc(N), *sorted = malloc(N);
    if (!shuffled || !sorted) { puts("out of memory"); return 1; }
    for (uint32_t i = 0; i < N; i++) shuffled[i] = (unsigned char)(rnd() & 0xFF);
    for (uint32_t i = 0; i < N; i++) sorted[i] = shuffled[i];
    qsort(sorted, N, 1, cmp_u8);

    double a[ROUNDS], b[ROUNDS];
    sum_over(shuffled); sum_over(sorted);                    /* warm-up */
    for (int r = 0; r < ROUNDS; r++) { a[r] = sum_over(shuffled); b[r] = sum_over(sorted); }
    qsort(a, ROUNDS, sizeof *a, cmp_d);
    qsort(b, ROUNDS, sizeof *b, cmp_d);
    double mixed = a[ROUNDS / 2], ordered = b[ROUNDS / 2];

    puts("the two arrays hold exactly the same values;");
    puts("one is shuffled, the other is sorted.");
    puts("the loop is the same: add the values that are 128 or more.\n");
    if (ordered > 0.0)
        printf("the shuffled array took %.2f times as long as the sorted one\n",
               mixed / ordered);
    else
        puts("the clock is too coarse on this machine to tell them apart");
    puts("\nsame data, same comparisons, same additions --- only the order differs.");
    puts("(no absolute times: they differ by machine and by run.)");

    free(sorted); free(shuffled);
    return 0;
}

the two arrays hold exactly the same values;
one is shuffled, the other is sorted.
the loop is the same: add the values that are 128 or more.

the shuffled array took 2.90 times as long as the sorted one

same data, same comparisons, same additions --- only the order differs.
(no absolute times: they differ by machine and by run.)

In the sorted array the condition is false for a long stretch and then true from some point on; a predictor gets almost all of that right. In the shuffled array true and false arrive at random, so it is wrong about half the time, and each time it is wrong the pipeline is emptied and refilled. That cost shows up as a ratio of several times.

★ So “branches are expensive” is imprecise. What is expensive is a branch that cannot be predicted. A regular condition is nearly free even a million times over.

Rebuild this example with optimisation on and the gap may disappear. The compiler turns a short condition like this into branch-free code — compute both sides and select one — and then there is no branch left to predict. The examples in this book are built without optimisation, which is why the result above appears. How far the compiler rewrites what we wrote is the subject of chapter 14.

★ That “may disappear” has been actually measured in the appendix on measuring the machine. Built with optimisation on, the difference between sorted and shuffled falls to 1.00; turn off only that one transformation, so a branch survives, and it is 4.98. What vanished is not the cost of the branch but the branch itself.

13.4 The limit of the clock, and multicore#

Despite all this overlapping, a wall arrived in the mid-2000s. Raising the clock further meant power and heat rising beyond what could be handled — a physical limit. The decades-long “a faster clock next year” stopped.

The industry’s answer was a change of direction — instead of making one worker faster, increase the number of workers. CPUs began to contain two, four, dozens of engines that independently execute instructions — cores. Even today’s phones commonly have about eight. The free lunch was over — the era in which programs got faster by themselves ended, and the problem of dividing work among many workers became the programmer’s (outside this book’s scope, but worth knowing as terrain).

And once there were many workers, chapter 12′s cache became the scene of an unexpected accident.

The accident is called false sharing. Two cores touch different variables — they share nothing at all — but if the two variables happen to sit side by side in the same cache-line box, then to the hardware’s eye two cores are fighting over the same box. Every write by one invalidates the box on the other’s desk, the box ping-pongs between the two desks, and both cores slow down by tens of times. Look at the code and nothing is shared, so the cause is invisible — a representative modern accident that can only be diagnosed by knowing chapter 12′s fact that memory moves in boxes.

13.5 The same era: C wrote a contract — pre-standard C and C89#

While machines were shaking like this, the world of C had turmoil of another kind.

C had no official standard for a long time. K&R’s 1978 book “The C Programming Language” served as the de facto standard — not a specification of the language, but one well-written book standing in for a statute book. As C spread with Unix into universities and industry, every company built its own compiler, and dialects grew in every corner the book had not pinned down. The C of that era looks loose today — a function declaration did not state the types of its arguments (there were no prototypes), and a name without a stated type quietly passed as int. Code that worked on one compiler failing on another was routine, and porting was an adventure every time.

Unable to bear it, the industry formed a standards committee (ANSI X3J11) in 1983, and after six years of heated argument C89 — the first official C standard — appeared in 1989. It brought in function prototypes (declarations that state argument types too, chapter 25) so compilers could catch mistakes at call sites, tightened the loose corners, and above all pinned down in a document, for the first time, “what the programmer is promised and how far the implementation is free.” It is within a few years of chapter 7′s IEEE 754 (1985) — an “age of contracts”, in which numbers in hardware and syntax in languages alike, arbitrary from vendor to vendor, began to be governed by written agreements.

13.6 The places the contract does not cover — grey areas#

Once there is a contract, one question follows at once: what about the things the contract does not mention?

The standard speaks in three ways — it promises (this is how it goes everywhere), the implementation decides (it varies, but must be documented), and it says nothing at all. The proper names for the three and the exact distinctions are chapter 54′s business.

And practice holds one more place that has no name at all — not guaranteed by the standard’s words, yet working on every major implementation, and so widely used that it became the practice. This book calls that place, together with the three above, a grey area.

Why do such places arise? The standard writes the lowest common denominator — it promises only as much as would hold even on very odd machines. Real implementations usually give more. And once large codebases build on that extra room, compilers cannot easily take it back — break it and half the world stops running.

Here are a few grey areas this book will meet, listed in advance. For now the names are enough.

13.7 When a standard outside C promises instead#

Among the grey areas, some have a different character: C says nothing, and another standard makes the promise in its place.

Do not read this as “C did not settle it, so anything goes”. Another contract is lying in that place, and it too was written with care.

/* This file assumes POSIX: conversion between function pointers and void * (dlsym). */
static_assert(sizeof(void (*)(void)) == sizeof(void *),
              "a platform where function and data pointers differ in size");

Why does this notion of a contract matter more and more? Because machines, as this chapter has shown, increasingly overlap and guess and divide, and a programmer cannot know every detail of that vortex. Between the vortex and the programmer stands one more layer — a layer that takes source code and translates it into the machine’s language, holding the right to rework anything at all as long as the meaning is kept. The compiler. It is the protagonist of the next chapter.