What is the meaning of the numbers outputted by a benchmark?

[ben-strasser]

Thank you for this nice library. I'm having trouble understanding what exactly the numbers outputted in a benchmark mean. Let's take the example of https://github.com/catchorg/Catch2/blob/devel/docs/benchmarks.md which states:

benchmark name                                  samples       iterations    est run time
                                                mean          low mean      high mean
                                                std dev       low std dev   high std dev
-------------------------------------------------------------------------------
Fibonacci 35                                            100       145169   87.1014 ms
                                                     468 ns       464 ns       473 ns
                                                      21 ns        15 ns        34 ns

I think it would be really helpful, if that page described in detail for each of the nine numbers how they were computed. I can write a paragraph once I understood them myself but I was not able to do so using a Google search or by reading the code, which I found really hard to follow.

I guess the number of "samples" (100) and the number of "iterations" (145169) somehow combine with the "est run time" (87.1014 ms) to get the "mean" (468 ns). I do not see how. I tried

(87.1014 * 10**6)/(100*145169) = 6.0 !=  468
(87.1014 * 10**6)/(145169) = 600.0 !=  468

[horenmar]

Samples: How many times the measurement was repeated.
Iterations: How many times the benchmarked code was looped for a sample.
est run time: How long do we think the benchmark will take (basically just time needed for first sample * 100)
mean/stddev: exactly what it says
low/high: lower and upper bound of 95 CI on those

[ben-strasser]

Thank you for your quick reply!

I still not not fully understand. Let me make it very specific.

Let's assume that samples is 4 and iterations is 3. Then the tested code will be executed 12 times in total.

Let's assume that the execution times are [in ms]: 11, 12, 9, 13, 15, 8, 12, 13, 14, 15, 12, 10

"est run time" is then (11+12+9) * 4 = 128 ms, right?

I assume "est run time" is already printed before all 12 executions are finished and therefore helps estimate whether one wants to wait for the benchmark to finish. Right? If not, then I do not understand the purpose of this number.

"mean" is then (11 + 12 + 9 + 13 + 15 + 8 + 12 + 13 + 14 + 15 + 12 + 10)/12 = 12 ms

"std dev" is then stdev([11, 12, 9, 13, 15, 8, 12, 13, 14, 15, 12, 10]) = 2.2 ms

Is this correct so far?

I'm unsure whether I understood the meaning of the remaining four. I'll write up what I understood. Is it correct? :)

We group the executions into samples [11,12,9] , [13, 15, 8], [12, 13, 14], [15, 12, 10]. For each, we now compute the 95% confidence interface. This means, we compute for [11,12,9]:

mean([11,12,9]) - stdev([11, 12, 9])/sqrt(3) * 2.920 = 8.09 ms
mean([11,12,9]) + stdev([11, 12, 9])/sqrt(3) * 2.920 = 13.24 ms

(The 2.920 comes from a t-table with 95% and 3-1 = 2 degrees of freedom.)

Next, we do the same for the other four samples and get the ranges [8.09, 13.24], [5.92, 18.08], [11.31, 14.69], [8.09, 16.58].

Next, we take the sequence of upper ends [13.24, 18.08, 14.69, 16.58] and compute the mean and standard deviation of that to get what is printed as "high mean" and "high std dev". So:

"high mean" is mean([13.24, 18.08, 14.69, 16.58]) = 15.65 ms
"high std dev" is stdev([13.24, 18.08, 14.69, 16.58]) = 2.12 ms

And the same with the lower ends [8.09, 5.92, 11.31, 8.09] gives the remaining two numbers

"low mean" is mean([8.09, 5.92, 11.31, 8.09]) = 8.35 ms
"low std dev" is stdev([8.09, 5.92, 11.31, 8.09]) = 2.22 ms

Is this correct? :)

[horenmar]

"est run time" is then (11+12+9) * 4 = 128 ms, right?

This is basically true.

I assume "est run time" is already printed before all 12 executions are finished and therefore helps estimate whether one wants to wait for the benchmark to finish.

It is sent to the reporters before the actual benchmark is run. It is up to the reporter to make sure the user sees it first (and not say, forget to flush the output so the user doesn't see it until the full benchmark results overflow the output buffer and are printed 😃 ).

---

For the rest, individual iterations are not measured, only the time to run all of them. The reason is that the user code is iterated if its runtime isn't long enough for good measurements.

The first time any benchmark is started, Catch2 does step that's internally called "environment estimation". It estimates the clock resolution and the overhead of getting current time from the clock.

Then, when the actual benchmark is run, Catch2 first looks for number of iterations required per sample to get good result. It will try running the user-provided benchmark code once, and compares the measured time with the environment estimation. If the difference is not sufficient, it will try running it twice, then 4 times, then 8 times, ..., every time measuring the time needed to finish all iterations and checking it against the environment estimate.

When the probe succeeds, the required number of iterations is kept for later and the measured time for the last try is multiplied with the number of samples to get the estimated benchmark running time, this is sent to the reporters, and then the actual benchmarking is done; we get N samples by running x iterations of the user code every time.

This means that with 4 samples of 3 iterations each, Catch2 would only work with 4 individual samples (and the rest of the stats Catch2 will do are going to be wildly off due to small number of samples). The statistics from samples are not calculated analytically, but by bootstrapping.

[ben-strasser]

Understood that Catch2 does not do individual measurements. Does it measure the length of the samples? So in my example, the individual running times 11, 12, 9, 13, 15, 8, 12, 13, 14, 15, 12, 10 exist but are not directly observed by Catch2. Instead what is observed are the running times of the samples, i.e., the four numbers 11+12+9 = 32, 13+15+8 = 36, 12+13+14 = 39, 15+12+10 = 37. From these four numbers all reported statistics about the individual running times are then derived. Is this correct? (I understand that 12 executions are far too few. However, I wanted to keep the example small. :) ) I understand, that Catch2 cannot compute the reported statistics using the way I described, as it does not have access to the individual running times. It will have to resort to some more complex math to derive them from the sample running times. However, is what I describe, what it tries to report? I interpreted "high mean" as meaning "the mean over the sequence of the upper bound of the 95% confidence intervals of the sequence of samples". Is this a correct interpretation? I'm asking because I can come up with quite a few different meanings for "high mean". What is the information that Catch2 tries to convey with "high mean"/"high std dev"/"low mean"/"low std dev" to the user? How should a user of Catch2 react to them? For "mean" and "std dev", this is clear to me. "mean" is the number the user wants to make smaller. "std dev" tells the user how useful the item he's measuring is by quantifying the "noise". I.e., small "std dev" = good, high "std dev" = measure something else. What are the others for? My gut feeling is that all four are there to tell the user whether the benchmark was successful, i.e., if "low mean" = "mean" = "high mean", then the reported numbers are meaningful and the user should act upon them. If they differ then it means that something got messed up during benchmarking (for example, user opened Firefox, virus scanner started running, ...) and the user should not rely on the results and rerun the benchmark. Is that what it boils down to?