- Published on
Can Environment Variables Change How Fast Your Code Runs?
- Authors
- Name
- Mehdi Akiki
Investigation · Part 14 of 20 · When the benchmark lies
My first scan said yes, and by a lot. With an environment of about 1,100 bytes, a simple copy loop was 91 percent slower than the median of all environment sizes. With 2,400 bytes, again 91 percent slower. Then I scanned the same sizes in the opposite order, and these sizes were normal.
This part is about a question that sounds strange: can the size of the environment variables change the speed of a program? There is a famous paper about this kind of problem, and there is a real mechanism that could make it possible. So I made the experiment carefully, and the most interesting result was in my own method.
Why it could matter
The paper is "Producing Wrong Data Without Doing Anything Obviously Wrong!" by Mytkowicz, Diwan, Hauswirth and Sweeney (ASPLOS 2009). Its abstract says that "changing a seemingly innocuous aspect of an experimental setup can cause a systems researcher to draw wrong conclusions from an experiment". They call this measurement bias, and they found it "significant and commonplace": on all the processors and both compilers they tried, and in most of the C programs of SPEC CPU2006.
The environment is a good candidate for such an innocuous detail, because of where it lives. When a process starts, the kernel writes the environment strings at the top of the stack, and everything else is built below them. Another series on this site shows this from the inside: with address randomization turned off, 4,000 bytes of environment move every local variable of main by 4,016 bytes.
I checked it with my own program. env -i starts it with an empty environment plus one variable PAD of n bytes, and setarch -R turns off address randomization, so that only the environment moves the stack:
pad 0: fib local 0x7fffffffdc90 660.8 us (sink 525175)
pad 1: fib local 0x7fffffffdc90 677.4 us (sink 525175)
pad 15: fib local 0x7fffffffdc80 656.9 us (sink 525175)
pad 16: fib local 0x7fffffffdc80 439.6 us (sink 525175)
pad 17: fib local 0x7fffffffdc80 333.5 us (sink 525175)
pad 32: fib local 0x7fffffffdc70 264.8 us (sink 525175)
pad 4096: fib local 0x7fffffffcc90 410.0 us (sink 525175)
The address of a local variable moves down in steps of 16 bytes, because the stack is aligned to 16 bytes, and with 4,096 bytes of padding it is exactly 4 KiB lower. (Do not read the times in these lines. They go from 660.8 to 264.8 microseconds in seven consecutive runs, and the snapshot of the machine just before them shows CPU 2 at 1.48 GHz: the core was waking up, as in part 6. Keep this in mind for the next section.) So by changing the environment I can put every stack variable at any position modulo 4 KiB, relative to the global data and the code, which do not move. If the speed of a loop depends on how its stack data and its other data are placed relative to each other, the environment can change its speed.
The experiment
The program has two workloads. copy reads a global array of 1,024 floats and writes an array of 1,024 floats on the stack, 20,000 times. fib is a recursive Fibonacci of 25, which is almost only calls and returns, so it uses the stack all the time. Each process measures its workload 7 times and prints the median.
The sizes go from 0 to 4,080 bytes in steps of 16, so 256 sizes, which covers every position of the stack modulo 4 KiB. And because of everything the previous parts showed about this laptop, I did not scan once. I made three passes over the 256 sizes: forward (0, 16, 32, ...), backward (4,080, 4,064, ...), and in a fixed shuffled order. Each pass runs both workloads at each size, pinned to CPU 2.
If the environment really changes the speed, a slow size must be slow in all three passes. If it does not, the three passes will disagree.
What the three passes said
The analysis compares each size with the median of its pass. First, the correlation between the passes, size by size:
copy: correlation of the deviations, pass 1 against pass 2: +0.03
copy: correlation of the deviations, pass 1 against pass 3: +0.03
copy: correlation of the deviations, pass 2 against pass 3: +0.06
...
fib: correlation of the deviations, pass 1 against pass 2: -0.07
fib: correlation of the deviations, pass 1 against pass 3: -0.10
fib: correlation of the deviations, pass 2 against pass 3: +0.13
All close to zero. A size that was slow in one pass was not more likely to be slow in another one. Then the same thing by region, the median deviation of each group of 16 sizes (256 bytes of padding), from the smallest sizes on the left to the largest on the right:
median deviation from the median of the pass, by region of 256 bytes of padding (0-255, 256-511, ...):
copy pass 1: -16.4 -17.2 -12.9 +1.1 +91.4 +45.9 +0.5 +0.8 +1.3 +90.6 +1.9 -3.6 -1.7 -2.7 +79.4 +6.6
copy pass 2: +4.2 +2.4 +0.8 +1.8 -2.6 +1.8 +0.4 -10.6 +0.0 -1.0 -8.3 +2.4 -1.2 -10.6 -20.6 -4.3
copy pass 3: -0.4 +2.0 +0.4 +0.2 -0.3 +0.6 -2.7 -0.4 +0.3 -1.1 +0.0 -0.1 +0.1 -0.1 -0.8 +4.0
fib pass 1: -14.4 -14.0 -10.1 -2.4 +6.3 +4.9 +0.4 -0.8 +0.4 +7.8 +4.2 -4.3 +2.2 -0.3 +2.8 +6.0
fib pass 2: +3.8 -0.1 +3.5 +6.9 -0.6 +1.9 +2.4 -8.0 +1.2 +0.7 -8.5 -0.1 -5.8 -9.4 -18.1 -3.7
fib pass 3: -3.9 +0.7 +0.7 +0.4 +2.0 +2.1 -1.3 -0.7 -0.4 +1.5 -1.1 +2.9 +0.9 -0.9 -0.6 -0.2
Pass 1, forward, is the scan of the first paragraph. If I had made only this pass, I would have reported three slow regions for copy, 79 to 91 percent slower, and the first sizes of fib 14 percent faster. Pass 2, backward, does not have the slow regions of pass 1 at all; its strange values are at the end of the table, which is the beginning of pass 2 in time. And pass 3, shuffled, is flat in this run: every region is within 4 percent of the median, for both workloads. This one surprised me.
So the pattern of the first pass did not belong to the sizes. It belonged to the moment when each size was measured. In a forward scan, small sizes are measured first and big sizes last, so any change of the machine during the scan becomes a "change with the size". Here the copy loop is very sensitive to such changes (the snapshot at the end of the run shows other programs busy on several CPUs, and part 7 showed what a busy neighbor does to this kind of loop), and its time varied between 4.1 and 15.2 ms within the first pass.
What I can conclude
On this laptop, for these two programs, I could not see an effect of the environment size. The correlations between the passes are close to zero, and in the shuffled pass the regions of 256 bytes are within 4 percent of the median. But a region mixes all sixteen positions of the stack, and one size alone moved much more from one pass to the next: in the shuffled pass, one size in ten was about 20 percent or more slower than the median for copy. So an effect of 10 or 20 percent at a few sizes could hide in this noise. And when I ran this part a second time, even the regions of the shuffled pass moved by up to 19 percent (p14-environment.txt). That is my answer to the title, and it is a modest one. It does not mean that the effect does not exist. The paper found it on other processors, with other programs, and a different loop could be sensitive to the position of its stack data on this CPU too. My result is only: I looked for it in a careful way, and here I did not find it.
But the experiment did show measurement bias very clearly, in my own method. The order of the scan alone produced differences of up to 91 percent. The remedy is exactly the one the paper proposes, setup randomization: measure the setups in a random order, or several times in different orders, and believe only what survives. It is the same lesson as the interleaving of the previous part, applied to 256 setups instead of two versions.
So my rule for any scan over a parameter (a size, a flag, a number of threads) is now: never in one direction only. A shuffled order, a second pass, and the correlation between the passes as a check. If the passes do not agree, the scan measured time, not the parameter. And the harness of the first part or any other careful benchmark does not protect against this, because the problem is not inside one measurement. It is in the order of all of them.
The program, the 1,536 raw measurements and the analysis are in the fixture, in p14-environment.txt.