Part 3: Building the benchmark harness
17 Nov 2026 Tags: Programming, C++| <- 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:
- Estimate the clock resolution: Call the clock repeatedly over a 500 ms interval and take the mean duration.
- Estimate the clock cost: Estimate how much time it takes to call the clock twice and compute the difference.
- 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.
- 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.
- 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/sampleiterations 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. - Analyze the samples.
These steps are executed by function Catch::Benchmark::Benchmark::run():
- Steps 1 and 2 are performed by calling function Catch::Benchmark::Detail::measure_environment(). The estimates are only done once, before the first benchmark, then saved and reused for any succeeding benchmarks.
- Steps 3 and the first half of Step 4 are performed by calling function Catch::Benchmark::Benchmark::prepare().
- The second half of Step 4 and all of Step 5 are performed by calling function Catch::Benchmark::ExecutionPlan::run().
- Step 6 is performed by calling functionCatch::Benchmark::Detail::analyse().
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:
- Inherent variability: Variations in execution time due to nondeterminism in the code, initial contents of the cache and other portions of the memory hierarchy, branch prediction results, calls to other services, kernel data structures, and similar factors.
- Confounding factors: Variability imposed by external factors unrelated to the code under test, such as other processes running concurrently, unrealistic initial conditions due to the benchmarking harness, and similar factors.
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:
console: The default reporter, this summarizes the results in a short text paragraph. This reporter is only useful for initial tests. Its output does not include all statistics and the format is unsuitable for detailed analysis.xml: Full statistics in XMl syntax. I specify this reporter for runs that will feed into later analysis. The XML output is parsed by the Python programparse-benchmarks.py, which appends the run statistics as a single line to a CSV file. The CSV file in turn can be loaded into a statistical analysis package.
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:
- The optimization level under which the code was compiled.
- The primary factor being compared, in the case of these benchmarks either “original” or “modern” code styles.
- The timestamp the benchmark was run. Although not inherently a factor in performance, this can distinguish different versions of the code and external conditions as the benchmarking process develops.
- The values of any benchmark parameters. For example, the initial benchmarks include a traversal count, specified on the command line.
- External factors, such as concurrent processes introducing contention, or other special circumstances.
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:
- name: Name of the benchmark. This is the name passed as
the first argument to
benchmark_utils::create_benchmark_name(). The other arguments multiplexed into the name by that routine, such as optimization level, are split out byparse-benchmarks.pyand written into their respective CSV columns. - code: Name of the code version. For this project, it will typically be
either
originalormodern. - traversals: Number of traversals for benchmarks that traverse the data structures. For benchmarks that do not do traversals, this field will be 0.
- optimization: The optimization parameter passed to the compiler when
the executable was built. Typically either
-O0or-O3. - externals: Any string passed as the EXTERNALS argument, if one was specified.
- UTC: The full UTC when this benchmark was started. If several benchmarks are performed in sequence in a run, their timestamps will be in close sequence.
- samples: The number of samples the benchmark routines should take. The
Makefilespecifies a value of 100. To specify a different value, either call the benchmark executable directly or modify theMakefile. - resamples: The number of resamples used in the BCa bootstrap algorithm (see Appendix 1) for the statistical analysis. This defaults to 100,000 and should likely be unchanged. However, if you increase the samples to a large value, say 1,000 or more, you will want to reduce the resample count to keep analysis time reasonable.
- iterations: Number of calls to the routine being benchmarked for each sample. This value is calculated by the benchmark routines and is not a settable parameter.
- clock_resolution_ns: Estimated resolution of the system clock. Note this includes the time to call the operating system, which is likely why different optimization levels produce different estimated resolutions.
- estimated_duration_ns: Estimated time to run the requested number of samples. This is computed by the benchmark routines and is for information only.
- mean_value_ns: Mean time to run a single iteration of the benchmarked routine.
- mean_lower_bound_ns: Lower bound of the confidence interval for mean execution time.
- mean_upper_bound_ns: Upper bound of the confidence interval for mean execution time. As the confidence interval is nonparametric, it will not necessarily be symmetric about the estimated mean.
- mean_ci: Confidence level for the interval of the mean. Default to 0.95 and not modified in runs.
- sd_value_ns: Estimated standard deviation of the execution time of the benchmarked routine.
- sd_lower_bound_ns: Lower bound of the confidence interval for standard deviation.
- sd_upper_bound_ns: Upper bound of the confidence interval for standard deviation. As the confidence interval is nonparametric, it will not necessarily be symmetric about the estimated standard deviation.
- sd_ci: Confidence level of the interval for the standard deviation. Default to 0.95 and not modified in runs.
- outliers_variance_ratio: The variance ratio statistic for estimating the effect of outliers. See Appendix 1.
- outliers_low_severe: Count of low outliers meeting the Tukey fence criterion of 3 * IQR. See Appendix 1.
- outliers_low_mild: Count of low outliers meeting the Tukey fence criterion of 1.5 * IQR. See Appendix 1.
- outliers_high_mild: Count of high outliers meeting the Tukey fence criterion of 1.5 * IQR. See Appendix 1.
- outliers_high_severe: Count of high outliers meeting the Tukey fence criterion of 3 * IQR. See Appendix 1.
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:
- r < 0.01: No effect
- r < 0.10: Slight effect
- r < 0.50: Moderate effect
- r ≥ 0.50: Severe effect
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:
- Computer: MacBook Pro, Apple M1 Pro CPU, 32 GB RAM.
- Operating system: macOS Tahoe, Version 26.4.1.
- Runtime environment: Docker container running Ubuntu 25.10.
- Compiler: g++ 15.2.0.
- Bencharking tool: Catch2 v2.13 benchmarking, donated from the 2019 version of nonius (which appears to now be unsupported).
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.