Mehdi Akiki
Published on

Compare Two Versions by Interleaving the Runs

Authors
  • Mehdi Akiki avatar
    Name
    Mehdi Akiki
    Twitter

Investigation · Part 13 of 20 · When the benchmark lies

I compared a program with itself, and the copy was 6.5 percent faster.

Not a different build, not a different input: cmp says that the two files are identical. The comparison was the most usual one: run version A 50 times, then version B 50 times, and compare the medians. The bootstrap interval of the difference went from -7.6 to -3.9 percent, so by the usual rule this is a significant result. In the previous part, the median of my laptop moved by 10 percent within one set of runs. Here is what this does to a comparison, and the simple change that fixes most of it.

Three versions

The benchmark is the sort of the previous part: one sort of a million pseudo-random u32 values in a fresh process, which prints its time. I built three binaries:

  • A sorts 1,000,000 values.
  • B is a copy of the file A.
  • C sorts 1,040,000 values, 4 percent more.

Sorting is n log n work, so C should be about 4.3 percent slower than A: 1.04 times the elements, and the logarithm grows by 0.3 percent. That is my true answer for A against C, and zero is the true answer for A against B.

Each experiment makes 50 runs of each of the two versions, pinned to CPU 2, in one of two orders. Blocks: 50 runs of the first version, then 50 runs of the second. Interleaved: first, second, first, second, 50 times. Every experiment is repeated 5 times, so the result file has 20 experiments.

For blocks, the interval of the difference comes from an unpaired bootstrap: it resamples the runs of each version separately. For interleaved runs it is a paired bootstrap: each pair of neighboring runs gives one ratio, and the bootstrap resamples whole pairs. The verdict is "no difference" when the 95 percent interval contains zero.

A against A, in blocks

experiment                            first   second  difference   95% interval      verdict
rep1-AB-blocks                       13.826   14.034       +1.5%     -0.7% to  +3.1%   no difference
rep2-AB-blocks                       16.425   15.349       -6.5%     -7.6% to  -3.9%   second is faster
rep3-AB-blocks                       13.873   13.841       -0.2%     -1.7% to  +0.4%   no difference
rep4-AB-blocks                       13.533   13.804       +2.0%     +1.3% to  +2.6%   second is slower
rep5-AB-blocks                       14.162   13.934       -1.6%     -2.4% to  -0.7%   second is faster

Two identical programs, and three of the five experiments say that one of them is faster, in both directions. This one surprised me. The worst one is the repetition 2: the first block had a median of 16.4 ms, the second block 15.3 ms. Nothing else in the output is wrong. The intervals are computed correctly, from real data.

The problem is the design. All runs of A happened in one second, and all runs of B in the next second. Between them the machine changed, as it changed in every experiment of the last parts: the clock, the other programs, the caches. So the difference between the two blocks measures the difference between two moments. And the interval can not know this, because it assumes that every run is an independent sample from the same distribution. Inside one block the runs are similar to each other, so the interval is narrow, and narrow around the wrong thing.

A against A, interleaved

The same two binaries, the same number of runs, only the order changes:

rep1-AB-interleaved                  15.721   15.722       +0.3%     -0.4% to  +0.6%   no difference
rep2-AB-interleaved                  15.593   15.636       -0.3%     -0.9% to  +0.7%   no difference
rep3-AB-interleaved                  13.621   13.680       +0.2%     -0.1% to  +0.6%   no difference
rep4-AB-interleaved                  13.587   13.543       +0.1%     -0.3% to  +0.2%   no difference
rep5-AB-interleaved                  13.841   13.848       -0.1%     -0.6% to  +0.5%   no difference

Five times "no difference", and all differences within 0.3 percent. Look also at the medians: between repetitions they move from 13.5 to 15.7 ms, so the machine changed as much as before. But inside each repetition, A and B saw the same changes, because their runs were neighbors, about 20 milliseconds apart. A slow moment makes both runs of a pair slow, and the ratio of the pair stays close to one. The drift is still there, but it cancels in the comparison.

Good, this is the result I wanted to see. It is also the cheapest fix of the whole series: the same runs, in a different order.

A real change of 4 percent

Now A against C, where the true answer is about +4.3 percent:

rep1-AC-blocks                       16.916   18.245       +7.9%     +5.4% to +10.5%   second is slower
rep2-AC-blocks                       14.210   14.559       +2.4%     +0.3% to  +4.7%   second is slower
rep3-AC-blocks                       13.757   14.459       +5.1%     +4.4% to  +5.9%   second is slower
rep4-AC-blocks                       13.523   14.829       +9.7%     +7.7% to +12.3%   second is slower
rep5-AC-blocks                       13.899   14.601       +5.0%     +4.0% to  +5.9%   second is slower
rep1-AC-interleaved                  16.256   16.925       +4.1%     +3.5% to  +4.8%   second is slower
rep2-AC-interleaved                  13.803   14.387       +4.6%     +4.2% to  +4.8%   second is slower
rep3-AC-interleaved                  13.825   14.380       +4.3%     +3.6% to  +4.6%   second is slower
rep4-AC-interleaved                  14.421   14.843       +4.0%     +3.3% to  +4.5%   second is slower
rep5-AC-interleaved                  13.721   14.255       +4.0%     +3.7% to  +4.5%   second is slower

Both designs say "slower" every time, so in this case the blocks did not miss the change. But read the sizes. In blocks, the same change measured +2.4, +5.1, +5.0, +7.9 and +9.7 percent. Three of the five intervals do not even contain the true value. If I had to decide whether a change of 4 percent is acceptable, the block design could tell me anything between "almost nothing" and "almost 10 percent".

Interleaved, the five answers are +4.0 to +4.6 percent, and the intervals are around the true value. The A/A results above say that the noise of this design is about 0.3 percent, so a difference of 4 percent stands far above it.

The A/A test

The most useful habit from this part is not interleaving. It is the A/A test itself: before I trust a method to compare two versions, I use it to compare a version with itself. It is the question of the first part, "is this number possible?", asked about a difference.

The A/A test measures the method, not the program. Here it showed that the block design has a noise floor of several percent, with false results in both directions, and that the interleaved design has a floor of a few tenths of a percent. A difference smaller than the A/A noise of the method can not be believed, whatever the interval says. And it costs almost nothing: the same script, with the same binary twice.

When I ran this part a second time, on a quieter laptop, I saw why the A/A test belongs to every run. The block design was wrong only once in five A/A experiments (-3.3 percent, in the very first one, at the start of the run), and its A/C answers were between +3.3 and +4.8 percent. The interleaved design gave the same answers as above. So the noise of the block design is not a property of the method alone: it depends on how much the machine changes during the run (p13-interleaving.txt).

Limits

Interleaving fixes slow changes of the machine. It does not fix everything:

  • If running A changes the conditions for the next run of B (a warm cache, a file in the page cache), the order inside the pair matters. Alternating the order (A B, then B A) or a random order per pair removes a systematic effect of this kind. Here every run is a fresh process, which limits the problem, but does not remove it completely.
  • It can not help when the difference is in the binaries themselves but not in the code. Two builds can differ only in how the code is placed in memory, and a later part of the series asks if this alone can change the speed.
  • It needs both versions available at the same time. Comparing with a number from last month is the block design with a very long gap between the blocks.

The same idea is called a paired comparison in statistics, and it works for the same reason with evaluation scores of AI systems: when both versions see the same items, the noise that is common to both cancels. Eval Scores Move Between Runs shows that a paired comparison detects a real improvement with a much smaller sample.

For my benchmarks, the rule is now simple. Never run all of A and then all of B. Alternate them, compute the difference inside each pair, and run an A/A test first to know the noise of the method.

The programs, the raw times of all 20 experiments and the analysis are in the fixture, in p13-interleaving.txt.