- Published on
When the Compiler Computes the Answer Before the Benchmark Runs
- Authors
- Name
- Mehdi Akiki
Investigation · Part 3 of 20 · When the benchmark lies
On my laptop, summing all the numbers below one thousand takes 0.81 nanoseconds. Summing all the numbers below one billion takes 0.81 nanoseconds too.
A million times more work, and the same time. I wanted to see this with my own eyes, so I made the smallest program that shows it. The short answer: the loop is not there. The compiler found the formula that every school student learns, and the benchmark measures one multiplication.
In the first part of this series, black_box on the input and on the output was enough to keep the work alive. Here black_box is in the right place, and it is still not enough.
First, with a constant
The function is a plain loop:
fn sum_below(n: u64) -> u64 {
let mut s = 0;
for i in 0..n {
s += i;
}
s
}
#[no_mangle]
#[inline(never)]
fn sum_below_1000() -> u64 {
sum_below(1000)
}
With rustc +1.98.0 -O, the whole function sum_below_1000 becomes this:
sum_below_1000:
movl $499500, %eax
retq
Two instructions: put the number 499,500 in the return register, and return. The sum of 0 to 999 is 999 times 1000 divided by 2, that is 499,500. The compiler computed it during the build. This is constant folding, and it is not a surprise: everything about this call is known at compile time.
The usual fix is to hide n, so that the compiler cannot know it. This is what black_box is for.
Then, with n hidden
The second function takes n as an argument, and the benchmark gives it through black_box, so it can be any value:
#[no_mangle]
#[inline(never)]
fn sum_below_n(n: u64) -> u64 {
sum_below(n)
}
Now the compiler cannot compute the answer during the build. So I expected a loop in the assembly. Here is what I got:
sum_below_n:
testq %rdi, %rdi
je .LBB21_1
leaq -1(%rdi), %rax
leaq -2(%rdi), %rcx
mulq %rcx
shldq $63, %rax, %rdx
leaq (%rdi,%rdx), %rax
decq %rax
retq
.LBB21_1:
xorl %eax, %eax
retq
There is no loop. n arrives in rdi. If it is zero, the function returns zero. Otherwise it computes n - 1 in rax and n - 2 in rcx, and mulq multiplies them. The result of mulq has 128 bits, the high half in rdx and the low half in rax. Then shldq $63 shifts this 128-bit number one bit to the right and keeps 64 bits, that is a division by two. At the end it adds n and subtracts one.
So the function returns (n - 1)(n - 2) / 2 + (n - 1). If you simplify it, this is n(n - 1) / 2, the formula for the sum of 0 to n - 1. The compiler did not need to know n. It needed only to know what the loop computes as a function of n.
For me this case is more interesting than the deleted loop of the first part. That loop had no effect, so deleting it was easy to accept. This loop has a real result, and the result is correct for every n. The compiler did not remove the work, it replaced the work with a better algorithm.
The same thing in the LLVM IR
The intermediate code of LLVM shows the idea more clearly than the assembly. This is the core of sum_below_n from rustc -O --emit llvm-ir:
%0 = add i64 %n, -1
%1 = zext i64 %0 to i65
%2 = add i64 %n, -2
%3 = zext i64 %2 to i65
%4 = mul i65 %1, %3
%5 = lshr i65 %4, 1
%6 = trunc nuw i65 %5 to i64
%7 = add i64 %n, %6
%8 = add i64 %7, -1
i65 is an integer of 65 bits. I liked this detail a lot. In a release build, the += on u64 wraps around on overflow, so for a very big n the loop gives the true sum modulo 2 to the power 64. The formula must give exactly the same answer, also in this case. The division by two would lose the top bit of a 64-bit product, so LLVM makes the product with one bit more. After the shift, the low 64 bits are exactly the bits the loop would produce. So the optimizer keeps even the overflow behavior of the loop.
Who does this: scalar evolution
The part of LLVM that does this is called scalar evolution, or SCEV. I only explain it as far as the LLVM documentation goes. Its page about passes describes the analysis like this: it "specializes in recognizing general induction variables", and "given this analysis, trip counts of loops and other important properties can be obtained".
An induction variable is a value that changes in a regular way at every turn of a loop. i starts at 0 and gets plus one at each turn. s starts at 0 and gets plus i at each turn. So s grows by a value that grows by one, and this is a polynomial of the number of turns. The number of turns is n, and it is known when the loop starts. So the final value of s can be computed without running the loop.
Then a transform pass uses it. The same page says that the pass indvars changes the uses of such values after the loop, so that the value is computed outside of the loop, and: "If the only purpose of the loop is to compute the exit value of some derived expression, this transformation will make the loop dead." That is exactly our case. The only purpose of the loop is the final value of s. Once the formula computes it, the loop is dead, and it is deleted.
I wanted to be sure that it is really this pass, so I asked LLVM to print the function after every pass that changed it (the option -print-changed, through -C llvm-args). The 65-bit multiplication appears for the first time here:
*** IR Dump After LCSSAPass on sum_below_n ***
*** IR Dump After IndVarSimplifyPass on loop %bb2 in function sum_below_n ***
%4 = mul i65 %1, %3
IndVarSimplifyPass is the class behind the pass called indvars. OK, so the documentation and the experiment agree.
The time does not depend on n
Now the benchmark. The harness gives n through black_box, and each sample calls the function 100,000 times. This is the second of three runs:
sum_below_n(1000) = 499500
below_n_1000 min 0.759 median 0.810 p90 0.810 max 0.811 ns/call (n=21)
sum_below_n(1000000) = 499999500000
below_n_1000000 min 0.760 median 0.810 p90 0.810 max 0.923 ns/call (n=21)
sum_below_n(1000000000) = 499999999500000000
below_n_1000000000 min 0.760 median 0.810 p90 0.819 max 0.839 ns/call (n=21)
The answers are correct for the three values, and the median is 0.81 ns for all three. The third run gives 0.79 ns for all three. The first run was about six times slower, between 4.6 and 5.0 ns. When it started, the load average was 11.1 and my CPU was already 24 percent busy, so my first idea was the load. But when I ran this part a second time, on a quieter laptop, the first run was again slower: 1.8 to 2.1 ns, against 0.53 to 0.67 for the two others (p03-closed-form.txt). So the load is not the whole story, and I do not know the rest. But even in the slow runs, n = 1,000 and n = 1,000,000,000 take the same time.
A real loop of one billion additions cannot do this. Even a vector loop with four additions per cycle needs 250 million cycles, that is more than 50 milliseconds at 4.7 GHz. The benchmark says 0.81 nanoseconds. If I would divide, I would get more than one billion additions per nanosecond. The number is not wrong as a measurement. It measures a multiplication, a shift and two additions. It just does not measure a loop.
A benchmark that really grows with n
The difference is that sum_below only computes with the loop counter. No formula can replace a loop over data that the compiler does not know. So the third function sums the content of a slice:
fn sum_array(data: &[u64]) -> u64 {
let mut s = 0;
for &x in data {
s += x;
}
s
}
The assembly has the same vector loop as in the first part, four numbers per turn, and the times grow with the length:
array_1000 min 86.816 median 91.546 p90 95.598 max 97.116 ns/call (n=21)
median per element 0.092 ns
array_10000 min 877.704 median 907.720 p90 933.049 max 981.644 ns/call (n=21)
median per element 0.091 ns
array_100000 min 8771.733 median 9041.989 p90 9255.420 max 11372.089 ns/call (n=21)
median per element 0.090 ns
array_1000000 min 137569.810 median 155274.060 p90 191915.700 max 229885.680 ns/call (n=21)
median per element 0.155 ns
array_10000000 min 4333094.900 median 4738471.600 p90 4996801.600 max 5362493.800 ns/call (n=21)
median per element 0.474 ns
Good, that is what a real loop looks like. Ten times more elements, ten times more time, at least in the first steps: 0.09 ns per element up to 100,000 elements. Then the time per element grows, to 0.155 ns and 0.474 ns. At one million elements the array is 8 MB, more than the L2 cache of one core (1.25 MiB), and at ten million it is 80 MB, more than the L3 cache that all cores share (18 MiB). So the elements come from further away. A later part of the series measures exactly this. Here it is enough to see that the time follows n. That is the proof that the work happens.
How I check this now
The first part gave the rule "hide the input, use the output". This part adds one more:
black_box hides a value. It does not hide the structure of the computation. If the loop computes something that has a closed form in terms of the input, the compiler can find the closed form without knowing the input.
So when I write a microbenchmark, I check two things now. First, I run it with two or three sizes that are ten times apart, and I look if the time follows. If the time stays flat when the work should grow, I do not trust the number before I read the assembly. Second, I make sure that the work depends on data, not only on a counter: an array, a string, the bytes of a file. Real programs almost always work on data, so this also makes the benchmark more similar to the real thing.
And sometimes the closed form is the real thing. If your production code has a loop like sum_below, it can be optimized in the same way, and 0.81 ns is its true cost. The benchmark is only wrong when you believe it measures the loop.
The program and the output are in the fixture, in p03-closed-form.txt.