12 The machinery of speed — the birth of the standard

12.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 4′s “one step per beat” collapses like this — the apparent order is kept, but inside things overlap.

Let us record one trick from the same era. 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 32). 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 13).

12.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%.

12.3 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 11′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 11′s fact that memory moves in boxes.

12.4 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 24) 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 8′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.

12.5 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 52′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.

12.6 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.