Part 3: Building the benchmark harness

<- Part 2: Reimplementing the TeX data structures in C++ Part 4: Running the benchmarks -> (Not yet published)
   

Benchmarks purport to give generalizable results. We don’t really care that one specific run, of a specific program, on a specific machine configuration, took a specified time. We care what that might indicate more generally. For a benchmark to provide useful generalizations, its conditions must be accurately recorded.

In my experience, recording the run conditions is surprisingly difficult. Just recording the timing results isn’t informative. What optimization level did I compile the program with? And was every file compiled with the same level? Which version of the code produced that output?

Furthermore, first runs of the benchmarks don’t answer questions definitively, they suggest new avenues to investigate. The benchmarks get parameterized and new options are introduced in the code. These new conditions must be stored with the timing results so that the analysis can attribute the results to the run conditions.

As the conditions mount and the questions become more detailed, the analysis becomes more complicated. The data must be recorded in a format supporting detailed analysis.

All these requirements are too much for any manual recording method. A test harness has to be built that ensures the benchmark is built according to a specification, sets any runtime parameters, then records the timing results alongside the conditions that produced them.

My harness for these benchmarks comprises a Makefile target, benchmarking code within the C++ app, and a Python program. The output of each run is lines in a CSV file of specified columns.

Strengths and limitations of microbenchmarks

These are microbenchmarks, estimates of the relative performance of several data structures for specified patterns of access. Their results are never definitive or final and the choice of data structures is informed by other considerations (security, clarity, suitability for future use cases, separation of concerns, and so forth), considerations that might well be more important than raw performance.

Furthermore, microbenchmarks will rarely point to the actual hot spots in an application that dominate performance. That requires profiling runs of the full application.

Finally, microbenchmarks are strongly tied to the circumstances of their execution: the specific operating system, compiler, and machine on which they were run.

Taking all the above into account, although the scope of microbenchmarks is limited, they do have a use. They help to refine a programmer’s intuition of what data structures might be best-suited to a given use case. They inform the range of initial choices you might make when designing a solution. So long as you’re mindful of their limitations, microbenchmarks are useful.

How Catch2 / nonius benchmarks run

A Catch2/nonius benchmark run comprises the following steps:

  1. Estimate the clock resolution: Call the clock repeatedly over a 500 ms interval and take the mean duration.
  2. Estimate the clock cost: Estimate how much time it takes to call the clock twice and compute the difference.
  3. Compute the number of iterations required per sample: A single sample consists of repeated calls to the benchmarked code long enough to consume 1000 clock ticks.
  4. Warm up the memory hierarchy: The benchmarked code is called several times, as is the timing code. These calls serve only to load the code and data into the memory hiearchy and their results and timings are discarded.
  5. Take the samples: The number of samples (a command-line parameter with a default of 100) are taken. Each sample measures the time to run iterations/sample iterations of the benchmarked code. The cost of the two clock calls is subtracted from the elapsed time and the result is divided by the iteration count, producing the time required for a single iteration.
  6. Analyze the samples.

These steps are executed by function Catch::Benchmark::Benchmark::run():

An interesting note about the clock tick estimation (Step 1): On my configuration, the estimate produced by code compiled without optimization (-O0) is around 45 ns / tick, while the estimate produced when compiled with full optimization (-O3) is half that, around 21 ns / tick.

Analysis

A benchmark is ultimately not a single estimate but an estimated range of possible performance of the routine under test. The execution time of a routine can vary for any number of reasons. In the language of experimental design, we can seprate these into two categories:

Ideally, we want to remove most confounds, account for the effect of any that remain, and be left with the inherent variability of the routine of interest. In practice, it is impossible to completely separate the confounds and our performance estimates are a mixture of the actual performance and artifacts of our experiment.

Ultimately though, a benchmark is not considered in isolation but in comparison with the benchmarks of alternative approaches. So long as the estimated ranges of the alternatives are sufficiently distinct, the benchmarks provide useful guidance for choosing the preferred approach.

Details of Catch2’s benchmark analysis code are provided in Appendix 1.

Reporters

Catch2 can report its benchmark results in several serialization formats. The caller selects a format by specifying a reporter, a module that outputs in a given format, via the -r/--reporter command-line option. For these benchmarks, I only use two reporters:

A full listing of available reporters is available by specifying --list-reporters on the command-line.

Capturing all pertinent factors of the benchmark

Although the Catch2 xml reporter records all the statistics from the benchmark analysis, this is an incomplete record of the benchmark conditions. Other factors essential to the analysis include:

All the above are fixed for every benchmark in a given run. In addition to them, each benchmark must have a distinct name to identify its line in the resulting CSV.

These values are not entered in the XML output by the standard Catch2 code, so I had to find a way to encode them into the standard output, then split them out into dedicated columns of the CSV. I solve this by extending the benchmark name with a field for each factor, separated from the actual benchmark name by a designated separator character, ‘|’. The Python code processing the XML output separates the encoded name into its constituent parts, writing each in its dedicated CSV column.

Ensuring accuracy of command-line values

Note that while some of the above can be computed in the C++ code, such as the timestamp, or hardcoded, such as the basic benchmark name, other factors, such as the optimization level, must be passed in from the command line. This introduces the risk that the command-line values are inaccurate. For example, how do we ensure that the optimization level passed in was the actual value with which the code was compiled?

The Makefile is written to ensure this. The standard way to run a benchmark is the benchmark target, potentially specifying a non-default optimization level and traversal count,

make TRAVERSALS=100 OPT_LEVEL=-O3 benchmark

which first recompiles all the files at the specified optimization, encodes that optimization level into the benchmark names, then runs the benchmarks with the specified traversals and appends the resulting benchmark values into the default results file, ../benchmarks.csv.

Recompiling before every benchmark is inconvenient, so the Makefile includes an alternative target, fast_benchmark, that takes the same arguments but does not recompile the code. Note that although the OPT_LEVEL argument can still be specified, it is ignored, as the optimization level was compiled in to the code when the executable was built.

Both Makefile targets support an optional EXTERNALS argument, used for noting any external factors about a given run that might be pertinent for later analsysis. For example, you might use this to note that noisy programs were deliberately run in the background during the benchmarks to assess the benchmarks’ sensitivity to contention. This argument can be nearly any string, typically enclosed in single quotes to protect from the shell, though the string cannot contain commas or pipe (‘|’) characters. See the repository README for details.

Output of harness

The benchmark processes described above append one line to ../benchmarks.csv for each benchmark, with the following fields. All times are in nanoseconds, as indicated by the _ns suffix of the fieldnames:

The above entries record all the factors that might vary between benchmark runs. These will vary against the backdrop of the fixed environment for all runs, described in Appendix 2.

Final thoughts

This harness automatically captures as much of the crucial details about a benchmark as possible and stores them in a format that is readily accessible to analysis software. The analyst only has to ensure that any external factors are recorded in the EXTERNALS parameter, factors that by definition are inaccessible to the harness.

Benchmarks even benefit the analyst before they are run. The planning and the consideration of what factors to measure and which to control, the effort to eliminate potential confounds, all prompt the analyst to think more deeply about their code, how it might be called by higher-level routines, and in what sort of environment it might be run. Actually running the benchmarks and analysing the results typically prompts a new round of questions and perhaps more benchmarks. The process does not really have a definitive endpoint, only the exhaustion of the analyst. (Or in this case, the reader.)

In any case, at this point we’ve done enough initial work to start the process, so in the next chapter we’ll run our first benchmarks.

Appendix 1: Details of the analysis code

This appendix describes the computation of the Catch2 / nonius benchmark statistics, with links to the code performing the computations.

Mean and standard deviation

The benchmark code estimates point values and 95% confidence intervals each for the mean and standard deviation of every benchmark. These estimates are computed using the bias-corrected and accelerated (BCa) bootstrap. For details, read the Catch::Benchmark::Detail::bootstrap() code alongside the section “Approach #3: Bias corrected and accelerated (BCa) bootstrap” of Erik Drysdale’s “Implementing the bias-corrected and accelerated bootstrap in Python”.

Outliers

The estimates of the mean and standard deviation are supplemented with two analyses of outliers. The first analysis uses Tukey’s fence criterion to count the number of “mild outliers”, defined as 1.5 times the IQR from the 25th or 75th percentiles, and “severe outliers”, defined as 3 times the IQR from the 25th or 75th percentiles (see classify_outliers()).

The second analysis uses a formula (see outlier_variance()) whose provenance I have not tracked down. The formula takes the estimates of the mean and sample deviation, together with the sample size, and computes a modified variance assuming one sample value was substantially far from the mean. It returns the ratio of this modified variance to the original estimate.

A hint to interpreting this statistic comes from the Haskell Criterion benchmarking package, the basis of the Catch2 benchmarking routines. The Criterion function for computing the identical outlier variance formula suggests a criterion for interpretation of the resulting ratio r:

My initial benchmarks have always produced results above 0.90, which these criteria consider a massive outlier effect. The only way I was able to produce a “slight effect” by this criterion was to contrive a highly consistent routine that simply does a 100 ms wait and the only way I was able to produce a “no effect” was to increase that wait to 500 ms. The criterion seems sensitive to the length of the routine being benchmarked, penalizing short routines.

I remain unclear how to really interpret this statistic and so I do not refer to it often in my benchmark analyses.

Appendix 2: Fixed run conditions

All the benchmark runs are done on the same combination of computer and operating system:

I chose to build and run the software in a container to ensure an exact, reproducible environment. This inevitably introduces potential confounding interactions between the Ubuntu container and the underlying macOS. In particular, an Ubuntu-based memory allocator might be suboptimal for macOS or even pathologically bad. On the other hand, running TeX in a Linux container atop macOS is a plausible use case, as it’s a simple way to distribute the code.