I think we reach for CPU optimisation too quickly.
A multiply or an add is easy to point at and count. Can I remove it? That makes the arithmetic a tempting place to spend an afternoon. The cost of keeping its answer around is less obvious in the source. My starting point is that simple arithmetic is cheap. What does the rest cost? I'll look at memory allocation, moving values around, waiting for them. I'd happily ask the processor to repeat itself if that makes the whole job finish sooner.
A small Floatyboat compiler experiment gives me a particularly satisfying example. At 4,194,304 elements with one worker:
- Live pool storage falls from 32 MiB + 8 bytes to 8 bytes.
- Wall time drops roughly 53% with C optimisation disabled (
-O0) and 88% with aggressive optimisation (-O3).
The faster version repeats a multiplication and an addition for every element. Saving those operations was keeping a four-million-entry array alive.
The storage figure counts working buffers still in use from Floatyboat's allocation pool. The remaining eight bytes hold one scalar result. Freed buffers can stay in the pool for reuse without being counted as live. The executable, runtime and worker stacks still need memory.
I'd enjoy an eight-byte process.
Seymour Cray put memory at the centre of this problem. In his 1995 Smithsonian interview, he said that “memory has dominated the speed of computation throughout these decades”. He also described arranging the Cray-1's modules to keep their connecting wires short.
His attention to memory and connecting wires interests me as much as the arithmetic. That interest is behind my harvester picture of keeping data moving. The parts have to work together to finish the job quickly. A lovely little calculation can sit inside an expensive process, and polishing the calculation leaves the expensive process intact.
The workers can't fix the serial part
Asking a computer to do less and asking it to finish sooner are different things. Especially once the work is parallel. I can save arithmetic in the workers, then spend more time in a serial orchestrator arranging their work. The workers don't get to help with that bit.
Gene Amdahl raised this problem in 1967, writing, “The nature of this overhead appears to be sequential”. Amdahl's law puts a ceiling on the speedup. If 5% of a fixed job's original running time stays serial and unchanged, even infinitely fast workers can't make the whole job more than twenty times faster. Spending longer in that serial part lowers the ceiling. Saving worker arithmetic can be a poor trade if I make everyone wait longer for instructions.
Two sums and one shared array
Here is mapfan, the Floatyboat benchmark behind the memory saving:
elementCount := 4194304.0
source := indices(count: elementCount)
shared := source * 3.0 + 1.0
fanOne := shared * 2.0
fanTwo := shared * 0.5
return sum(fanOne) / elementCount + sum(fanTwo) / elementCount
indices supplies the integers from zero through 4,194,303. Each element of shared needs one multiply and one add. Two sums use the result, so calculating it once and saving it looks like the sensible thing to do.
The compiler already combines each final multiply with its sum. There are no separate arrays for fanOne and fanTwo. But shared stays in memory until its second reader finishes.
Creating that column takes three passes. First generate the indices, then multiply them, then add one. Those passes reuse one buffer. We still have to fill it, keep it alive and read it back through two reductions. That's a lot of activity hidden behind the comforting word shared.
Two questions from the earlier notes meet here. Who still reads this value, and what does keeping it cost? The graph explains why shared stays alive, while the traffic through that array gives me a reason to try doing without it.
The alternative calculates index * 3 + 1 inside each reduction. Each loop makes the value where it needs it, and the 33,554,432-byte column disappears.
Two cheap operations per element and an array with four million entries are different items on the bill altogether, which makes 'do the arithmetic once' a less obvious saving.
Caches can make array accesses cheap, but their space is finite and other data needs it too. A stored intermediate can consume bandwidth and displace useful data. Repeating this expression keeps its result local to the loop that uses it. The machine gets more arithmetic and less work managing the answers.
The compiler term is rematerialisation. We calculate a value again where it's needed instead of preserving it in storage. Floatyboat already does this in other cases. Here, an overly narrow check gets in the way.
The patch follows every reader of a fixed-length, one-dimensional expression, including intermediate calculations already folded into another loop, and requires every path to end in an eligible whole-array reduction with the same known length. The reduction code already supports a constant loop limit.
That word every includes the inconvenient readers too. Returning the array, capturing it for later or reading its stored contents would still require those values. The rule leaves matrix reductions alone because a flat count doesn't describe rows and columns. Runtime lengths keep their existing treatment, and the cost limit still guards against repeating expensive expressions.
It also preserves each element's operation order and each sum's grouping of additions. Floating-point rounding makes those choices observable. I'm asking the compiler to change where values live while keeping the calculation's answer.
Let the compiler spend the arithmetic
The existing check looks for an array input that can supply the loop's length. That usually works. In this expression, though, the indices become the loop index itself, leaving only scalar constants. There is no array left to ask.
For a moment that sounds like a reason to keep the array, until I look back at indices(count: elementCount). Right, the length is already in the source. I don't need an array to discover it. The eligibility check has to accept the information I already have.
Check the calculation first
I have two questions for the checks, whether repeating this expression preserves the bits and removes the allocation, and whether my compiler actually makes that change.
For the first question, I used standalone C versions with the same two separate reductions and Floatyboat's existing reduction tree. They covered block boundaries and empty inputs as well as rounding-sensitive values. One worker or four? Both were checked. I kept an allocation deliberately to test the storage observation. Changing the arithmetic tested whether a wrong result was caught.
Did the compiler make the change?
Then I compared the programs that the preserved baseline and patched Floatyboat compilers produced, keeping the runtime the same so the comparison stayed between those two compilers. Each comparison holds the C optimisation setting fixed. The ranges beside the timing ratios estimate how uncertain those ratios are. They're 95% intervals calculated from repeated samples of the recorded run pairs. Here is the elapsed time remaining at four million elements:
| Elapsed time at 4,194,304 elements | Baseline | Patched, with 95% interval |
|---|---|---|
-O0, one worker | 100% | 47% (46–48%) |
-O0, four workers | 100% | 27% (27–28%) |
-O3, one worker | 100% | 12% (11–14%) |
-O3, four workers | 100% | 17% (15–19%) |
Both build settings leave eight bytes of peak live pool storage.
Each timing starts a fresh process. The runs alternate baseline and candidate. Baseline-against-baseline runs expose noise. All three tested sizes from 262,144 to 4,194,304 elements pass the workload's benefit checks at both worker counts and optimisation levels.
I care about the result as well as the stopwatch. Both completed reductions and the final answer agree bit for bit at -O0, -O2 and -O3, including rounding-sensitive inputs. Two control programs and the compiled self-hosted frontend come out byte-identical. The change leaves them alone and self-compilation gets no faster.
I'm still running wider validation on the compiler.
There's still room to make the CPU happier
At -O3, removing the shared array also loses SIMD, which lets the processor calculate several elements with one instruction, yet the storage saving wins despite that loss. I find that especially persuasive. But having got rid of the array, can I get the arithmetic advantage back and keep the storage saving?
A separate generated-C experiment gets that advantage back. These indices start at zero and fit in a signed 32-bit integer. Making that range explicit in the conversion and adding a SIMD hint restores packed conversion, multiplication and addition in a loop with eight independent running totals. Those are its accumulator lanes. Each keeps its addition order.
At four million elements with one worker, this takes another 11% off the already-rematerialised program's elapsed time. It uses 89% of that time, with a 95% interval of 86–91%, and passes the noise check. With four workers it's no slower, though the runs don't show it getting faster. Result bits and the eight-byte pool peak stay intact.
Anyway, I like that order. First, stop keeping and fetching four million answers to a cheap calculation. Then make the remaining loops better at calculating them. Before I spend an afternoon saving a multiplication, I want to ask what keeping its answer is costing me.