rtcompare

package module
v0.7.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 27, 2026 License: MIT Imports: 14 Imported by: 1

README

rtcompare

Go Reference Linter Tests coverage Vulnerabilities

Statistically significant runtime comparison for codepaths in golang

rtcompare is a small Go library for deciding whether one code path is genuinely faster than another. It measures both candidates, resamples the measurements to estimate how confident that conclusion is, and — the part that distinguishes it — measures what the machine invents on its own so that the conclusion can be read against it.

New to this and not a statistics person? Read HOWTO.md — it walks through what to actually do, in plain language, including what each warning means and what to do about it.

Keywords: benchmarking, performance, bootstrap, runtime comparison, statistics, deterministic prng, go

Features

  • Answer the whole question in one call: Compare sizes the batches, measures what the harness invents on its own, runs the comparison, tests for drift, picks the resampling scheme from the dependence it observed, and reports a verdict with the fine print that qualifies it.
  • Collect timing or memory samples for two implementations under a harness that interleaves their measurement order, keeps setup out of the measured region, and places garbage collection deterministically.
  • Size batches automatically, so that the system clock contributes at most a chosen share of error. This is what makes differences far below the clock's resolution measurable: a per-operation difference of 1.89 ns was recovered to within 0.07 percentage points against a 41 ns clock floor.
  • Estimate, by bootstrap resampling, the confidence that A beats B by at least a given relative margin.
  • Measure the harness against itself, so that a result can be compared with the difference the same setup reports between two runs of identical code.
  • Detect a trend across a measurement run, which resampling structurally cannot see because it discards the order the samples arrived in.
  • Resample in blocks when the measurements are correlated enough that treating them as independent would overstate confidence.
  • Run a comparison in several processes, each with its own heap layout, and pool the results into an interval that covers the scatter between processes (multiproc, Combine, PerturbHeap).
  • Deterministic PRNG for reproducible inputs, and a crypto/rand-backed one where unpredictability is wanted.
  • Compare mutable data structures under realistic insert/delete workloads in one call (workload), with separate answers for the steady state and for building to size; the streams are valid by construction, reproducible from a seed, and cyclic, so that a batch can replay them endlessly without rebuilding the structure.

What this cannot tell you

Two limits are worth knowing before the first run, because neither is visible in a confidence figure.

Attenuation. What is measured is the loop, not the function. Whatever fixed per-operation cost the batch body carries — the loop itself, an accumulator, regenerating an input the candidate mutates — is present in both candidates and shrinks the difference between them. In a controlled experiment where the true difference was exactly 50%, the measured difference was 35%, because 1.81 ns/op of loop overhead sat on top of 2.13 ns/op of real work. Subtracting an empty-loop baseline does not repair it: the compiler optimizes an empty loop differently, and that correction recovered 2 of the 15 missing percentage points. Read a result as the speedup of the measured region, not of the isolated function.

The process. Every interval a single run reports covers the noise within that one process. A process fixes its memory layout for its whole life, and for data larger than the caches or full of pointers that layout alone has moved a difference by several points — 4 to 10 times the reported interval, and sometimes past zero. Where that applies, one process is one observation: run several with the multiproc package and read the pooled result. See One process is one observation.

The noise floor. Resampling quantifies how much an estimate would move if the same measurements were drawn again. It cannot see a bias that affected all of them equally, and will report a tight confidence around one. Measured on identical code, this package has seen apparent differences from a few tenths of a percent to well over one, carried with high confidence. ValidateHarness exists to measure that floor for your machine and your options; a result below it has resolved nothing, however confident the number looks.

Install

Use as a normal Go module dependency:

go get github.com/TomTonic/rtcompare

Import:

import "github.com/TomTonic/rtcompare"

Quickstart example

package main

import (
	"fmt"

	"github.com/TomTonic/rtcompare"
)

var sink float64

func main() {
	candidateA := rtcompare.Candidate{Name: "A", Batch: func(n uint64) {
		var acc float64
		for range n {
			acc += doSomething()
		}
		sink += acc
	}}
	candidateB := rtcompare.Candidate{Name: "B", Batch: func(n uint64) { /* ... */ }}

	// Everything is left at its default: the batches are sized so that the clock
	// contributes at most a tenth of a percent, both candidates are validated
	// against themselves, the order is interleaved, and the resampling scheme is
	// chosen from the dependence actually measured.
	report, err := rtcompare.Compare(candidateA, candidateB, rtcompare.CompareOptions{
		Thresholds: []float64{0.05, 0.10, 0.20},
	})
	if err != nil {
		panic(err)
	}

	fmt.Println(report)

	if report.Resolved {
		fmt.Printf("A is faster by %s\n", report.Estimate)
	}
}

which prints something like

A 712.7 per op, B 1262 per op
difference +43.52% [+42.31%, +44.48%] at 95% confidence
noise floor 1.765%, autocorrelation +0.344, resampled in blocks of 5
resolved: A is faster than B
  warning: candidate B drifted during the run, shifting -7.12% from its first
  half to its second; the machine did not hold still
  confidence that A beats B by 5.00%: 100.0%

Compare validates both candidates against themselves before comparing them, so it costs a few seconds. Set SkipValidation to pay only for the measurement, accepting that the result then has no noise floor to be read against. The individual steps are all exported too, and cmd/rtcompare-example shows both: the one call, and then the same measurements taken apart by hand.

Not sure what a warning like "resampled in blocks" or "does not clear the noise floor" means, or what to do about it? HOWTO.md goes through each step Compare performs and each warning it can produce, with a plain-language explanation and a concrete fix.

Technical background

  • Batching is what beats the clock. A single batch measurement is off by at most one clock tick p. Spread over n operations that is p/n per operation, so the relative error is p/(n·c) where c is one operation's cost. Since n·c is just the batch duration T, the whole thing collapses to p/T: the error depends only on how long a batch runs, not on how fast the operation is. CalibrateInnerLoops therefore searches for the smallest batch that reaches a target duration, which is why an expensive operation can calibrate to a batch of two while a cheap one needs thirteen thousand.

  • Bootstrap-based inference. Rather than a single mean, rtcompare resamples the collected measurements. CompareSamples answers "how confident can I be that A beats B by at least x", which is what you want when a threshold is given. EstimateDifference answers "how large is the difference and how precisely is that known", which is what you want when none is. Its interval is a percentile bootstrap, measured to cover at 96–97% against a nominal 95%: conservative rather than optimistic, and well centred.

  • Why the median. Each replicate is summarised by its median. Interference is one-sided, which argues for a low quantile instead, but simulation against a known difference says otherwise: below roughly 30% disturbed batches the median wins on RMSE, because with contamination on fewer than half the samples the middle one is already drawn from the clean part. Past 40% the median degrades sharply — and so does the noise floor ValidateHarness reports, from 1.2% to 20.5%, so that regime announces itself.

  • What resampling cannot see. The bootstrap treats the samples as an unordered bag, which discards the order they were measured in. A machine that drifted during the run leaves no trace in its output. DetectDrift tests for that separately, using Spearman's rank correlation against measurement position; its false positive rate was verified at 4.80% against a nominal 5% over 6000 permutations of real measurement series.

  • Dependence between neighbouring measurements. Resampling single observations also assumes they are exchangeable, and real measurements are mildly correlated. In AR(1) simulations the rate of false signals from identical inputs stayed at its nominal 10% up to a lag-1 correlation of 0.08, reached 13.5% at 0.2 and 21.7% at 0.4. ValidateHarness reports the correlation it observed; above roughly 0.2, BlockBootstrapConfidence resamples contiguous blocks instead.

  • Deterministic input generation. DPRNG generates reproducible inputs across runs. CPRNG, backed by crypto/rand, is there when unpredictability or cryptographic quality is wanted instead.

When to use rtcompare instead of testing.B

Use rtcompare when you want:

  • Distribution-aware comparisons rather than single-number reports.
  • Statistical confidence estimates for relative speedups (e.g., "A is at least 20% faster than B with 95% confidence").
  • A library you can easily call from small programs, CI jobs, or dedicated comparison tools without the testing harness.

The standard testing package is excellent for microbenchmarks and tight per-op measurements. rtcompare complements it by focusing on sampling strategy, resampling inference, and reproducible comparisons across implementations.

API highlights

The one call:

  • Compare(a, b, CompareOptions) — runs the whole protocol and returns a Report. Report.Resolved is the short answer, Report.Warnings is the fine print, and the rest of the struct is the evidence: the samples, the estimate, the per-candidate validations, the drift tests and the resampling choice.

The individual steps, for when the summary is not enough:

Measuring:

  • Candidate / Batch — one implementation under test, with optional Setup and Teardown that run outside the measured region.
  • Collect(a, b, CollectOptions) — runs both candidates and returns one timing sample per repeat each, ready to hand to CompareSamples. Owns measurement order, warm-up, GC placement and batch sizing. The warm-up alternates the candidates for at least WarmupDuration (300 ms by default), so that neither starts the measurement with the caches to itself.
  • CalibrateInnerLoops(candidate, CalibrationOptions) — sizes batches for a target quantization error. Called automatically when CollectOptions.InnerLoops is left at zero.

Judging:

  • CompareSamples(a, b, relativeGains, resamples) — confidence per requested relative speedup. CompareSamplesDefault uses DefaultResamples.
  • EstimateDifference(a, b, level, resamples) — the point estimate of the relative difference with a bootstrap interval around it. Excludes(0) asks whether a difference has been established at all.
  • BootstrapConfidence — the same, returning a map, with control over the PRNG seed.
  • BlockBootstrapConfidence — resamples contiguous blocks, for measurements correlated with their neighbours.
  • F2T(timesFaster) — converts a multiplicative speedup to the relative threshold the API uses. It signals invalid input by returning NaN, which CompareSamples rejects with an error rather than silently answering.

Checking the measurement itself:

  • ValidateHarness(candidate, ValidationOptions) — runs a candidate against itself and reports the noise floor, the tie rate, the drift rate and the autocorrelation. Resolves(difference) answers whether a result clears that floor. The floor is the 90th percentile of the differences observed on identical code, not their maximum, so that it converges as you validate longer instead of growing; roughly one A/A run in ten exceeds it. Validate both candidates and use the worse floor.
  • ValidatePair(a, b, ValidationOptions) — validates two candidates together, interleaved batch by batch, and returns one HarnessValidation each. Use it instead of two ValidateHarness calls before comparing the two: a candidate validated on its own last would start the comparison with a warm cache.
  • DetectDrift(samples) — tests a sample series for a trend across the run.
  • Report.Suspended — how long the machine slept during a Compare, from the gap between the wall clock and the monotonic clock.
  • Report.LiveHeap — the program's live data; above 16 MB, Compare warns that one process is not enough and points to multiproc.

Across processes:

  • multiproc.Main(Options, pairs...) / multiproc.RunTest(t, Options, pairs...) — the whole job in one call: each Pair says how to build candidate A and B, and the program is re-executed as child processes, one at a time, each with its own heap layout and with the build order alternating, until every pooled interval is within ±2 points or ±10% of the difference (at least 5, at most 20 processes). multiproc.Run(Options, suite) does the same for a suite function of your own.
  • Combine(reports, level) — pools per-process reports of one comparison into a Pooled result: a t interval over the per-process deltas, plus how far the processes scatter beyond their own intervals (Inflation, Cochran's Q, I²).
  • PerturbHeap(seed) — allocates seeded filler in every small size class and one large block, so that data built afterwards lands at different addresses in each process.

Primitives:

  • DPRNG / CPRNG — deterministic and cryptographic generators with Uint64, Float64 and Uint32N. DPRNG.Shuffle permutes, e.g. the order in which fixtures are built.
  • SampleTime() / DiffTimeStamps() — high-resolution timestamps, and GetSampleTimePrecision() for the smallest interval they can resolve here.
  • Median / QuickMedian / Statistics — small statistics helpers.

Workloads for mutable data structures (github.com/TomTonic/rtcompare/workload):

  • workload.Compare(target, a, b, Options) — the whole job in one call: each Structure says how to create an empty structure and apply operations to it, and you get two reports, one for the steady state (per insertion or deletion, after one untimed cycle) and one for building from empty (per whole build, growth included).
  • workload.Cycle(target, Config) / workload.Build(target, Config) — the streams: a cycle of insertions and deletions that ends where it started, and a build from empty with a realistic history.
  • workload.Replay — replays a cycle on one structure instance, with the untimed first pass, and Settle to return it to its start state. workload.Cursor is the bare position, for doing it by hand.
  • workload.Check(ops, start, end) — replays a stream against a model and reports the first invalid operation.

A note on the threshold of 0.0: every threshold is evaluated as delta >= t, so at zero the question is "at least as fast", not "faster". Quantized timings tie often, and every tie counts towards it. Ask for a threshold above zero if you mean strictly faster.

Note on negative relativeGains: Negative thresholds are allowed and are interpreted as tolerated relative slowdowns rather than speedups. A threshold of -0.05 means "A is within 5% of B" (i.e., A is not more than 5% slower than B). Use negative values when you want to ask whether one implementation is approximately as fast as another within a relative tolerance instead of requiring a strict speedup.

Choosing resamples

The number of bootstrap resamples controls the Monte‑Carlo error of the confidence estimates. Common recommendations from the bootstrap literature (Efron & Tibshirani; Davison & Hinkley) are:

  • Use at least 1,000 resamples for reasonable standard-error estimation.
  • Use 5,000–10,000 when you need stability in the tails, which here means confidences close to 0 or 1.

Both quantities this package computes have that Monte-Carlo behaviour: the proportion of replicates meeting a threshold, and the quantiles of the resampled differences that EstimateDifference uses for its interval.

The Monte‑Carlo standard error of a proportion estimated from resamples decreases approximately as 1/sqrt(R) where R is the number of resamples. Increase resamples when you require low Monte‑Carlo noise (for example, precise reporting of extreme thresholds). See Efron & Tibshirani (1993) and Davison & Hinkley (1997) for more details.

See the package docs and the example in cmd/rtcompare-example for detailed usage.

Contributing

Contributions welcome. Please open issues or PRs for bug reports, performance tweaks, or additional comparison strategies. Add tests for any behavioral changes and keep CPU/memory overheads small.

License

MIT — see LICENSE file.

Documentation

Index

Constants

View Source 
const AutocorrelationThreshold = 0.2

AutocorrelationThreshold is the lag-1 autocorrelation above which Compare stops treating the samples as independent and resamples them in blocks.

Below it there is nothing to repair and blocks only cost variance; above it the ordinary bootstrap believes it has more information than it does. The value comes from AR(1) simulations in which the rate of false signals from identical inputs held at its nominal 10% up to a correlation of 0.08, reached 13.5% at 0.2 and 21.7% at 0.4. See BlockBootstrapConfidence for the full tables.

View Source 
const DefaultConfidenceLevel = 0.95

DefaultConfidenceLevel is the interval level EstimateDifference uses when asked for zero.

View Source 
const DefaultMaxInnerLoops uint64 = 100_000_000

DefaultMaxInnerLoops caps how far CalibrateInnerLoops will grow the batch size before giving up, when CalibrationOptions.MaxInnerLoops is left at zero.

The cap is generous: reaching it means one operation costs so little that a hundred million of them still do not fill the target batch duration, which in practice means the compiler removed the work rather than that the code is fast. See the error returned in that case.

View Source 
const DefaultMaxQuantizationError = 0.001

DefaultMaxQuantizationError is the share of the per-operation result that CalibrateInnerLoops allows the system clock's granularity to contribute, when CalibrationOptions.MaxQuantizationError is left at zero.

One tenth of a percent is deliberately well below the harness noise floor, which in A/A experiments has ranged from a few tenths of a percent to over one. Once quantization is an order of magnitude smaller than the noise it stops mattering: against 0.6% of noise, adding 0.1% of quantization in quadrature yields 0.608%. Buying more precision than that only lengthens batches without making the magnitude of a difference more trustworthy.

It is sized for that question, the magnitude of a difference, and not for the separate question of whether a difference exists at all. Quantization also collapses distinct measurements onto equal values, and equal values tie; at this target an ordinary candidate tied in about 15% of bootstrap replicates, which inflates the confidence at a threshold of zero. Tightening the target tenfold took that to 0.6% at ten times the batch length. See CollectOptions.MaxQuantizationError for the measurements.

View Source 
const DefaultRepeats = 101

DefaultRepeats is the number of timing samples Collect gathers per candidate when CollectOptions.Repeats is left at zero.

It is comfortably above MinimumDataPoints, so that the bootstrap has enough distinct values to resample from, and it is odd, so that Median returns the true middle sample. That package's Median never interpolates; for an even count it returns the upper of the two middle values, which biases it slightly upwards. An odd count avoids the question.

Note that raising this does not make a coarse measurement finer. More repeats draw more values from the same quantized set; only a longer batch adds resolution. See CollectOptions.MaxQuantizationError.

View Source 
const DefaultResamples uint64 = 5_000

DefaultResamples is a sensible package-level default for bootstrap resamples. Use this when you want a balanced trade-off between Monte-Carlo precision and runtime cost. This default (5k) follows common recommendations in the bootstrap literature; increase it for extreme-tail accuracy or highly precise confidence estimates.

View Source 
const DefaultValidationLevel = 0.95

DefaultValidationLevel is the confidence level ValidateHarness judges false signals against when ValidationOptions.Level is left at zero.

View Source 
const DefaultValidationRuns = 40

DefaultValidationRuns is the number of A/A experiments ValidateHarness performs when ValidationOptions.Runs is left at zero.

It is sized for the rates the report quotes, not for the noise floor, which needs far fewer runs. FalseSignalRate and DriftRate are proportions estimated from Runs observations, so their standard error is sqrt(p(1-p)/Runs). At the nominal 10% that FalseSignalRate is compared against, ten runs give a standard error of 9.5 percentage points, which is as large as the quantity being estimated: a perfectly calibrated setup would print 0.0% about 35% of the time and 20% or more about 26% of the time, and neither number would mean anything. Forty runs bring that to 4.7 points, which is enough to tell a calibrated setup from a badly broken one, though still not enough to resolve small departures.

The cost is linear in Runs and small in absolute terms. On the machine these notes were written on, validating a candidate calibrated to 48 microsecond batches took 0.76 s at ten runs and 3.03 s at forty. Validation is a thing done once per setup, not once per comparison, so that is a good trade.

View Source 
const DefaultWarmup = 1

DefaultWarmup is the least number of unmeasured batches Collect runs per candidate before collecting samples, when CollectOptions.Warmup is left at zero. The warm-up also runs for at least DefaultWarmupDuration, which is the bound that usually decides how long it takes.

View Source 
const DefaultWarmupDuration = 300 * time.Millisecond

DefaultWarmupDuration is the least wall-clock time Collect spends warming up both candidates, together, before it collects samples, when CollectOptions.WarmupDuration is left at zero.

A fixed number of batches is not a warm-up when the working set is about the size of the last-level cache. Whatever ran alone last before the measurement, be it an A/A validation, a calibration or the caller's own fixture build, leaves the cache full of its own data. Calibrated batches are short, often a fraction of a millisecond, and a whole run of them may touch too little memory to turn the cache over, so the head start survives into the medians. Two identical 16 MB pointer chases on a machine with 32 MB of L3 measured the candidate that ran alone last 5 to 50% faster after one warm-up pair, and within noise of each other after about 400 pairs of 0.3 ms batches, some 250 ms in all. See issue #111 and the reproduction in cmd/rtcompare-aa.

Time is the bound rather than a batch count because what has to happen, the cache turning over, takes a roughly fixed amount of work, and batches are calibrated to a duration rather than to a volume. The cost is paid once per Collect and once per validation, not once per validation run; see ValidateHarness.

View Source 
const DriftLevel = 0.05

DriftLevel is the significance level at which ValidateHarness counts a run as having drifted. It is a conventional 5%: on data with no trend the drift test fires this often by construction, so DriftRate is only interesting when it sits well above this.

View Source 
const LargeHeapThreshold = 16 << 20

LargeHeapThreshold is the live heap above which Compare warns that a single process's result is not to be trusted on its own.

Above roughly the size of a last-level cache, where the data lies in memory starts to decide how fast it is, and that placement is fixed for a process and different in the next. Measured on 1M-node lists, processes scattered 4.5 times as widely as their own intervals said. The threshold sits at the lower end of common last-level caches, so that the warning comes early rather than late; it is a hint drawn from the heap as a whole, not a measurement of what the candidates touch, and can fire for a program that holds much memory the candidates never read.

View Source 
const MinimumDataPoints uint64 = 11
View Source 
const NoiseFloorQuantile = 0.90

NoiseFloorQuantile is the quantile of the observed A/A differences that HarnessValidation.NoiseFloor reports.

The floor used to be the maximum, which turned out to be the wrong statistic for the job. A sample maximum has no population value to converge on: it grows with the number of runs, without limit. Measured here, eight repetitions per row, the same candidate throughout: 

Runs    max (old floor)         90th percentile
   5              0.779%                  0.493%
  10              0.208%                  0.169%
  20              0.230%                  0.144%
  40              0.313%                  0.165%
  80              0.356%                  0.166%

The max climbs steadily from twenty runs onward while the quantile settles; an independent earlier run reproduced the same climb, 0.236% to 0.491% over Runs 5 to 40. The five-run row is unreliable in both columns, one repetition there having caught a disturbed machine. The spread across repetitions tells the same story: at eighty runs the max ranged over 0.168% to 0.834% while the quantile ranged over 0.164% to 0.168%, a band forty times tighter.

That mattered in practice, because HarnessValidation.Resolves compares against this number. With a maximum, validating more carefully raised the bar, so the natural response to an uncertain result — run it again with more runs — made the gate stricter rather than better informed. A quantile converges, so the gate stops moving once there are enough runs to estimate it.

The price is that this is no longer an observed bound. Roughly one A/A run in ten exceeds it, by construction. HarnessValidation.MaxObservedNoise still reports the largest difference actually seen, for anyone who wants it.

View Source 
const SuspendThreshold = time.Second

SuspendThreshold is how far the wall clock may run ahead of the monotonic clock during a Compare before the machine is taken to have been suspended.

On Linux and macOS the monotonic clock stops while the machine sleeps and the wall clock does not, so the gap between them is the time spent asleep. A second is far above what clock adjustments produce in the span of one comparison and far below the idle sleeps that have actually paused comparisons, which lasted 15 to 25 minutes.

Variables

This section is empty.

Functions

func AutoBlockLength added in v0.6.0 

func AutoBlockLength(n int) int

AutoBlockLength selects the block length from the sample size, as BlockBootstrapConfidence does when told to choose for itself.

It returns the nearest integer to the cube root of n, with a floor of one. That rate is the standard choice for the moving block bootstrap: the block has to grow with n so that dependence reaching further than one lag is eventually captured, and it has to grow more slowly than n so that the number of blocks keeps growing too. For the sample sizes this package works with it lands between two and five.

func BlockBootstrapConfidence added in v0.6.0 

func BlockBootstrapConfidence(A, B []float64, relativeGains []float64, resamples uint64, blockLength int, prngSeed uint64) map[float64]float64

BlockBootstrapConfidence is BootstrapConfidence with contiguous blocks of observations instead of single observations, which is what makes it usable on measurements that are not independent of their neighbours.

The ordinary bootstrap draws one observation at a time, which assumes the samples are exchangeable: that the order they arrived in carries nothing. Real timing measurements violate this, mildly but measurably. Correlated samples carry less information than the same number of independent ones, so a method that assumes independence believes it knows more than it does and produces confidences that are too extreme in both directions. Resampling whole blocks keeps neighbours together and preserves that dependence.

The cost is that this is only worth paying when the dependence is strong enough to matter, and often it is not. Measured against A/A simulations of an AR(1) process, where identical inputs mean every reported difference is a false signal and 10% of runs should land outside a 90% band: 

lag-1 rho    false signals    verdict
     0.00            8.0%     conservative
     0.08           10.0%     nominal
     0.20           13.5%     inflated
     0.40           21.7%     badly inflated
     0.60           33.1%     unusable

Across 600 real measurement series on the machine these notes were written on, the lag-1 autocorrelation averaged +0.10 with a true spread between series of about 0.07 once the estimator's own noise is removed, putting roughly 6% of series above 0.2 and almost none above 0.3. At that distribution the aggregate inflation is a fraction of a percentage point, and blocks buy nothing. A busier machine, a candidate that interacts with the collector, or a shared CI runner can be a different story, which is why this is available and why ValidateHarness reports the autocorrelation it observed.

What blocks actually recover, from the same simulation: 

lag-1 rho    plain    blocks    verdict
     0.00     8.5%      9.4%    no harm done
     0.08    10.0%     10.0%    no harm done
     0.20    12.8%     10.9%    repaired
     0.40    20.6%     12.7%    much improved, still inflated
     0.60    32.2%     16.7%    halved, nowhere near repaired

So this is a partial remedy, not a cure. It restores calibration through about 0.2 and merely improves matters beyond that, which is what fixed-length blocks can do: a block captures dependence reaching as far as its own length, and making it longer to capture more costs variance. At the point where a machine produces series correlated at 0.4 the statistics are not the problem; the measurement is, and a quieter machine or shorter runs will do more than any resampling scheme. Note also the last row of the earlier table read against this one: blocks that are too long for the dependence present are themselves mildly over-dispersed, which is why the automatic length is worth preferring over a guessed one.

blockLength of zero selects AutoBlockLength, and so does any negative value, which has no sensible reading. A blockLength of one is the ordinary bootstrap exactly, drawing the same values in the same order, so there is no reason to pass it deliberately. Blocks are overlapping and drawn uniformly from every valid start position, which is the moving block bootstrap of Künsch (1989); the last block of a replicate is truncated so that every replicate has exactly as many observations as the input.

A blockLength longer than half the input is reduced to half. A block as long as the input has only one start position, so every replicate would reproduce the input exactly, the resampled difference would be a constant, and the confidence would come out as exactly 0 or 1 — indistinguishable from certainty, and wrong. Halving guarantees at least two blocks per replicate. The clamp is applied to each input separately, so inputs of different lengths are each handled on their own terms. There is no good reason to approach that bound in any case: long blocks cost variance, and AutoBlockLength stays far below it.

All other behaviour, including threshold handling and the meaning of prngSeed, is that of BootstrapConfidence.

func BootstrapConfidence added in v0.2.0 

func BootstrapConfidence(A, B []float64, relativeGains []float64, resamples uint64, prngSeed uint64) map[float64]float64

BootstrapConfidence estimates the probability (confidence) that the relative speedup of A over B meets or exceeds each requested threshold using bootstrap resampling.

The function performs `resamples` bootstrap replicates. In each replicate it draws a bootstrap sample from A and from B (via bootstrapSample), computes their medians and evaluates the relative speedup as: 

delta = 1 - median(A_sample)/median(B_sample)

A positive delta indicates A is faster than B by that relative amount. For every threshold t in `relativeGains` the function increments a counter when delta >= t. After all replicates it returns a map that maps each threshold to the estimated confidence (fraction of replicates meeting delta >= t).

Numerical and edge-case behavior (important):

  • If `resamples` is zero the function returns a map with each threshold mapped to math.NaN().
  • If either sample median is NaN (for example QuickMedian returned NaN for an empty sample), the replicate produces delta = NaN and that replicate does not count as meeting any threshold.
  • To avoid divide-by-zero and extreme ratios when median(B_sample) == 0 (or is numerically extremely small), the implementation uses a small, scale-aware epsilon fallback. Concretely it chooses an epsilon = max(|median(B)| * rel, SmallestNonzeroFloat64) with a small relative factor (e.g. rel = 1e-12). If |median(B)| < epsilon the code uses epsilon as the denominator. This guarantees a finite, bounded delta while preserving the correct ratio for typical non-zero medians.
  • If both medians are zero (or both are equal/infinite in the same direction), the replicate sets delta = 0.0 (no relative difference).

Parameters:

  • A, B: observed samples (e.g. runtimes or throughputs) used as the population for bootstrap sampling.
  • relativeGains: slice of relative-speedup thresholds to evaluate (e.g. 0.05 for 5% faster).
  • resamples: number of bootstrap resamples to run (the greater the resamples, the lower the Monte Carlo sampling error).
  • prngSeed: DPRNG seed used for reproducible sampling. Provide a specific non-zero seed to reproduce results across runs. If prngSeed is zero, the function uses a CPRNG with cryptographic strength randomness.

Note on choosing `resamples` (literature guidance): There is no one-size-fits-all value; common recommendations in the bootstrap literature (Efron & Tibshirani; Davison & Hinkley) are to use at least 1,000 resamples for standard-error estimation and often 5,000–10,000 (or more) when estimating percentile confidence intervals, especially for tail probabilities. The Monte Carlo error of a proportion estimated from resamples decreases approximately as 1/sqrt(R) where R is the number of resamples, so doubling `resamples` reduces that error by about 1/sqrt(2). For many practical uses `resamples` in the range 1,000–10,000 is a reasonable default; increase it when you need precise confidence estimates near extreme thresholds or when you require reproducible low-variance results.

Returns: 

A map[float64]float64 where each key is a threshold from `relativeGains` and the corresponding value is
the estimated confidence in [0,1] that the relative speedup of A over B is at least that threshold.

Repeated thresholds are collapsed before counting, so the returned confidences are always in [0,1]. Without that step a threshold listed n times would score n hits per replicate and report a confidence of n. The caller's slice is not modified.

NaN thresholds are silently skipped and do not appear in the returned map. This function has no error channel, and a NaN key would be an entry no caller could ever look up, because NaN compares equal to nothing including itself. Prefer CompareSamples, which rejects NaN thresholds with a proper error. Infinities are kept: they behave consistently, with -Inf mapping to 1 and +Inf to 0.

func Collect added in v0.6.0 

func Collect(a, b Candidate, opt CollectOptions) (samplesA, samplesB []float64, err error)

Collect measures two candidate implementations and returns one timing sample per repeat for each, in nanoseconds per operation. The returned slices are suitable as direct inputs to CompareSamples or CompareSamplesDefault.

Collect owns the measurement loop so that it can control the things that systematically bias a comparison and that are easy to get wrong by hand: measurement order, warm-up, garbage collection placement, and the division by the inner loop count. It deliberately does not own the inner loop, see Batch.

A note on attenuation, which the returned numbers cannot express: every batch includes whatever fixed per-operation overhead the batch body carries (loop counter, accumulator, call frames, any input regeneration the candidate needs). That overhead is present in both candidates and therefore never flips the sign of a comparison, but it does shrink its magnitude. In a controlled experiment where the true difference was exactly 50%, the measured difference was 35%, because a fixed 1.81 ns/op of loop overhead sat on top of 2.13 ns/op of real work. Subtracting an empty-loop baseline does not repair this, because the compiler optimizes an empty loop differently than a real one; that correction recovered 2 of the 15 missing percentage points. Use Candidate.Setup for everything that can be hoisted out of the loop, and read the result as the speedup of the measured region as a whole, not of the isolated function.

A note on the noise floor, which choosing an Order does not remove: across many A/A runs of identical candidates, the observed difference between the two sample sets has reached anywhere from a few tenths of a percent to well over one, under every order strategy. Differences of that size are indistinguishable from machine noise in a single run no matter how many bootstrap resamples are spent on them, because the bootstrap only quantifies the spread of the samples it was given and cannot see a bias that affected all of them. Treat a result below roughly 1% as "not resolved" rather than as a small but real effect.

A note on what ran before: the warm-up alternates the candidates for at least CollectOptions.WarmupDuration so that neither starts the measurement with the caches to itself, whichever of them the caller built, validated or calibrated last. See DefaultWarmupDuration for why a count of batches is not enough, and ValidatePair for validating both candidates without handing one of them that head start in the first place.

Collect returns an error if either candidate has a nil Batch, if Repeats, Warmup or WarmupDuration is negative, if Repeats is below MinimumDataPoints, if Order is not one of the defined constants, or if automatic calibration of InnerLoops fails. It does not otherwise inspect the collected samples.

func DiffTimeStamps 

func DiffTimeStamps(t_earlier, t_later TimeStamp) int64

Retruns the difference between two timestams in nanoseconds with the highest possible precision (which might be more than just one nanosecond). The function assumes that t_later is later than t_earlier and will return a negative value if this is not the case. Please note that the call to this function does NOT have constant runtime on other systems but Windows.

func F2T added in v0.4.0 

func F2T(timesFaster float64) float64

F2T (FactorToThreshold) converts a multiplicative speedup timesFaster (e.g. 3.0 => A is 3× faster) to the internal relative‑reduction threshold used by CompareSamples and BootstrapConfidence.

func FloatsEqualWithTolerance 

func FloatsEqualWithTolerance(f1, f2, tolerancePercentage float64) bool

FloatsEqualWithTolerance reports whether f1 and f2 are approximately equal, using a percentage-based absolute tolerance computed from each operand.

The tolerancePercentage parameter is interpreted as a percentage (for example, 5 means 5%). For each value v the function computes 

absTol = |v * tolerancePercentage / 100|

and checks whether the other value lies within [v - absTol, v + absTol]. The function returns true if either check succeeds (i.e. if f2 is within the tolerance computed from f1 OR f1 is within the tolerance computed from f2).

Important notes:

  • The comparison uses absolute tolerances derived from the operands, which makes the check effectively two-sided: a small value may be considered equal to a much larger one if the larger value's tolerance range contains the smaller value.
  • A tolerancePercentage of 0 requires exact equality.
  • Negative tolerancePercentage values are treated equivalently to their absolute value because the computed tolerance is wrapped with math.Abs.
  • Comparisons involving NaN follow IEEE754 semantics and will not be true; interactions with ±Inf follow IEEE754 and may produce true results when a computed tolerance range is infinite.
  • This function performs simple arithmetic checks and returns a boolean.

func GenerateScrambler added in v0.5.0 

func GenerateScrambler() uint64

GenerateScrambler generates reasonable scrambler constants for the DPRNG. The generated scrambler constant is always an odd number with a good bit density. This ensures maximal period and good mixing properties. You can use the returned scrambler constant when creating a new DPRNG instance to get a different permutation (i.e., sequence) of generated numbers.

func GetSampleTimePrecision 

func GetSampleTimePrecision() int64

GetSampleTimePrecision returns the smallest interval that can actually be measured with SampleTime() on this machine, in nanoseconds. It is determined empirically on first use and cached for the lifetime of the process.

This is the practical floor of the measurement: no single timing can be trusted below it, and it is the quantity that determines how long a batch has to run for a given quantization error, which is what CalibrateInnerLoops uses it for.

It is deliberately not "the clock's resolution", and the two can differ. What the function observes is the smallest gap it can produce between two consecutive SampleTime calls, which is bounded from below by whichever is larger: the clock's tick, or the cost of the two calls themselves. Which one dominates depends on the platform.

  • On macOS/arm64 the timebase runs at 24 MHz, one tick every 41.667 ns, and the observed gaps come out as its multiples, rounded to whole nanoseconds: 41, 42, 83, 84, 125, 166, 167, 208. Here the tick dominates and the returned value is the resolution.
  • On Linux/amd64, where clock_gettime resolves to a nanosecond through the vDSO, the call is expected to be the larger of the two, which would make the returned value closer to that overhead than to any tick. Measured on a GitHub Actions runner under coverage instrumentation, that overhead came to 60 ns, well above the 50 ns an earlier version of this comment assumed without measuring; a shared, virtualized machine plausibly makes the vDSO call itself slower than a quiet dedicated one does. The tests no longer assert a tighter bound than that, because the number this function returns is a property of the machine it runs on, not a constant the test suite can know in advance.
  • On Windows the timestamp comes from QueryPerformanceCounter, whose frequency comes from the platform's hardware abstraction layer rather than from measuring call overhead, and is effectively always 10 MHz on modern Windows, giving a 100 ns tick. Being a hardware fact rather than a benchmark result, this one is asserted exactly; it is not exercised by this project's own CI, which runs on Linux only.

In every one of those cases the returned number answers the same question and is the one worth having: this is as fine as measurement gets here. Note that this is unrelated to the coarse Windows system clock of about 15.6 ms that GetSystemTimeAsFileTime is subject to; SampleTime does not use it.

func Median 

func Median(data []float64) float64

Median computes the median of the provided slice of float64. If data is empty, Median returns 0.0. The function makes a copy of the input and sorts the copy, so the original slice is not modified. For an odd-length slice it returns the middle element; for an even-length slice it returns the element at index len(data)/2 (the upper middle). Time complexity: O(n log n). Space complexity: O(n) due to the copy required for sorting.

func QuickMedian 

func QuickMedian(xs []float64) float64

QuickMedian returns the median in expected O(n) time. In case of an odd number of elements, it returns the middle one. In case of an even number of elements, it returns the higher of the two middle ones. Returns math.NaN() for an empty input slice. Note: This function modifies the input array. To avoid this, pass a copy.

func Statistics 

func Statistics(data []float64) (mean, variance, stddev float64)

Statistics computes the arithmetic mean, population variance, and standard deviation of the provided slice of float64 values.

It returns three float64s in order: mean, variance, and stddev.

The variance returned is the population variance (sum of squared deviations divided by n). The standard deviation is the square root of that variance.

If the input slice is empty, the function returns mean = 0 and variance = stddev = -1 to indicate that the values are undefined for an empty dataset.

Types

type Batch added in v0.6.0 

type Batch func(n uint64)

Batch runs the code under test exactly n times.

The batch function owns its inner loop. This is deliberate and is the central design decision of Collect: the library resolves the function value once per batch, not once per operation. Two consequences follow.

First, the cost of the indirect call is amortized over n operations and is therefore negligible (measured at roughly 0.01 ns/op for n = 20000). Second, and more importantly, the compiler's optimization boundary sits at the batch body rather than around every single operation. Code inside the batch is inlined, hoisted and register-allocated the same way it would be in production. A per-operation callback would forbid inlining of the candidate entirely and would measure a call boundary that the real program does not have.

A batch function must perform exactly n units of the work under test and must not perform work whose cost depends on anything other than n. Work that is not part of the comparison belongs in Candidate.Setup, which runs outside the measured region.

type CPRNG added in v0.4.0 

type CPRNG struct {
	// contains filtered or unexported fields
}

CPRNG is a cryptographically secure random number generator ("CryptographicPrecisionRNG") that reads random bytes in batches to reduce the number of calls to the underlying crypto/rand.Reader (OS call). This improves performance while maintaining security and provides high-precision output suitable for statistical and numerical work. This RNG is thread-safe as long as each goroutine uses its own instance. The memory footprint can be adjusted by changing the capBytes parameter in NewCPRNG.

func NewCPRNG added in v0.4.0 

func NewCPRNG(capBytes uint32) *CPRNG

NewCPRNG creates a new CPRNG with a buffer capacity of capBytes. The buffer is filled with random bytes upon creation and refilled as needed. A larger buffer reduces the number of operating system calls to crypto/rand.Reader, improving performance. A smaller buffer reduces memory usage. This random number generator is not deterministic in the sequence of numbers it generates. This random number generator is not deterministic in its runtime (i.e., it does not have a constant runtime as it needs to periodically refill its buffer via crypto/rand.Reader, an OS call). This random number generator is cryptographically secure (relying on crypto/rand, see https://pkg.go.dev/crypto/rand). This random number generator is thread-safe as long as each goroutine uses its own instance. This random number generator has a varying memory footprint (usually a few kilobytes).

func (*CPRNG) Float32 added in v0.4.0 

func (c *CPRNG) Float32() float32

Float32 returns a uniformly distributed float32 in [0.0, 1.0). This function will never return -0.0. This function will never return 1.0. This function will never return NaN or Inf. If you need random values in a different range, scale and shift the result accordingly. This function uses 23 random bits for the mantissa. This is the maximum randomness that can be represented in a float32 without breaking uniformity. If you need more randomness, use Float64 instead. See: https://en.wikipedia.org/wiki/Single-precision_floating-point_format

func (*CPRNG) Float64 added in v0.4.0 

func (c *CPRNG) Float64() float64

Float64 returns a uniformly distributed float64 in [0.0, 1.0). This function will never return -0.0. This function will never return 1.0. This function will never return NaN or Inf. If you need random values in a different range, scale and shift the result accordingly. This function uses 52 random bits for the mantissa. This is the maximum randomness that can be represented in a float64 without breaking uniformity. See: https://en.wikipedia.org/wiki/Double-precision_floating-point_format

func (*CPRNG) Int8 added in v0.4.0 

func (c *CPRNG) Int8() int8

Int8 returns a uniformly distributed int8.

func (*CPRNG) Int16 added in v0.4.0 

func (c *CPRNG) Int16() int16

Int16 returns a uniformly distributed int16.

func (*CPRNG) Int32 added in v0.4.0 

func (c *CPRNG) Int32() int32

Int32 returns a uniformly distributed int32.

func (*CPRNG) Int64 added in v0.4.0 

func (c *CPRNG) Int64() int64

Int64 returns a uniformly distributed int64.

func (*CPRNG) Uint8 added in v0.4.0 

func (c *CPRNG) Uint8() uint8

Uint8 returns a uniformly distributed uint8.

func (*CPRNG) Uint16 added in v0.4.0 

func (c *CPRNG) Uint16() uint16

Uint16 returns a uniformly distributed uint16.

func (*CPRNG) Uint32 added in v0.4.0 

func (c *CPRNG) Uint32() uint32

Uint32 returns a uniformly distributed uint32.

func (*CPRNG) Uint32N added in v0.4.0 

func (c *CPRNG) Uint32N(n uint32) uint32

Uint32N returns a non-negative pseudo-random number in the half-open interval [0,n). Use this function for generating random indices or sizes for slices or arrays, for example. Even though this function will probably not be inlined by the compiler, it has a very efficient implementation avoiding division or modulo operations. This function compensates for bias. For n=0 and n=1, Uint32N returns 0.

For implementation details, see: 

https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction
https://lemire.me/blog/2016/06/30/fast-random-shuffling

func (*CPRNG) Uint64 added in v0.4.0 

func (c *CPRNG) Uint64() uint64

Uint64 returns a uniformly distributed uint64.

type Calibration added in v0.6.0 

type Calibration struct {
	// InnerLoops is the batch size to use, i.e. the value for
	// CollectOptions.InnerLoops.
	InnerLoops uint64

	// NsPerOp is a rough estimate of one operation's cost, taken from the
	// calibration batch. It is a single unreplicated measurement and is meant
	// for sanity checking, not for reporting. Use [Collect] for real numbers.
	NsPerOp float64

	// BatchDuration is how long one batch of InnerLoops operations took, in
	// nanoseconds. This is the quantity the calibration actually targets.
	BatchDuration float64

	// ClockPrecision is the smallest interval the system clock resolved, from
	// [GetSampleTimePrecision], in nanoseconds.
	ClockPrecision int64

	// QuantizationError is the relative per-operation error the clock's
	// granularity contributes at this batch size, i.e.
	// ClockPrecision/BatchDuration. It is at most the requested
	// MaxQuantizationError.
	QuantizationError float64
}

Calibration reports what CalibrateInnerLoops determined about a candidate.

func CalibrateInnerLoops added in v0.6.0 

func CalibrateInnerLoops(c Candidate, opt CalibrationOptions) (Calibration, error)

CalibrateInnerLoops determines how many operations one batch must perform so that the system clock's granularity contributes at most MaxQuantizationError of relative error to the per-operation result.

This is the mechanism that makes measuring below the clock's resolution work, and the arithmetic behind it is simple. A single batch measurement is off by at most one clock tick p. Spread over n operations that becomes p/n per operation, so the relative error is p/(n*c) where c is the cost of one operation. Since n*c is just the batch duration T, the whole thing collapses to p/T: the error depends only on how long the batch runs, not on how fast the operation is. Calibration therefore searches for the smallest n whose batch reaches a target duration of p/MaxQuantizationError.

On a machine where GetSampleTimePrecision reports 41 ns, the default target of 0.1% means batches of about 41 microseconds. On Windows, where QPC resolves to roughly 100 ns, the same target means about 100 microseconds per batch. In both cases a per-operation difference of a fraction of a nanosecond survives, because it is never the individual operation that is timed.

The search starts at one operation per batch and grows geometrically, using each measurement to predict the next size, with a safety margin and a cap on how fast it may grow. Each candidate size is measured several times and judged by its shortest run, so that a batch which only reached the target because a scheduler hiccup stretched it is not accepted. An expensive operation may well calibrate to a batch size of one; the criterion is the batch duration, not the number of operations.

The search itself is cheap, a few hundred microseconds in practice. The first call in a process additionally pays for GetSampleTimePrecision, which probes the clock until its minimum stops improving, about 4 ms on the machine these notes were written on. That result is cached for the lifetime of the process, so it is a one-time startup cost rather than a per-call one.

A failure to reach the target within MaxInnerLoops means a batch did not get longer as the batch size grew. In Go the usual explanation is a Batch function that ignores its n parameter, not dead code elimination: unlike some C and C++ compilers, the Go compiler does not remove a loop merely because nothing reads its result, so a loop that computes an unused value still runs and still takes time. Work that the compiler can fold to a constant is the second candidate. Writing a result to a package-level variable remains good practice for keeping a candidate honest, but it is not what this error is usually pointing at.

type CalibrationOptions added in v0.6.0 

type CalibrationOptions struct {
	// MaxQuantizationError is the largest relative per-operation error the clock
	// granularity may contribute. Zero selects [DefaultMaxQuantizationError].
	// Must be greater than zero and less than one.
	MaxQuantizationError float64

	// MaxInnerLoops caps the batch size the search will try. Zero selects
	// [DefaultMaxInnerLoops].
	MaxInnerLoops uint64

	// GCBetween requests an explicit garbage collection before every trial
	// batch, mirroring CollectOptions.GCBetween so that calibration measures
	// the same conditions the real run will use.
	GCBetween bool

	// DisableGC turns off the automatic collector for the duration of the
	// calibration, mirroring CollectOptions.DisableGC. See its documentation
	// for the caveats.
	DisableGC bool
}

CalibrationOptions configures CalibrateInnerLoops. The zero value is usable and selects the documented defaults.

type Candidate added in v0.6.0 

type Candidate struct {
	// Name is an optional label used in error messages. It has no effect on
	// measurement.
	Name string

	// Setup runs before every batch, outside the measured region and before the
	// optional garbage collection requested by CollectOptions.GCBetween, so that
	// garbage produced by Setup is collected before the clock starts. May be nil.
	Setup func()

	// Batch is the code under test. Must not be nil.
	Batch Batch

	// Teardown runs after every batch, outside the measured region. May be nil.
	Teardown func()
}

Candidate bundles one implementation under test with its per-batch lifecycle.

Setup and Teardown exist so that preparation and cleanup can be kept out of the measured region. Anything done inside the Batch function is measured, including work the caller only needs in order to make the measurement possible at all: allocating a working buffer, restoring state that the previous batch mutated, building an input corpus. Charging that to the candidate is what causes attenuation, see the note in Collect.

The distinction that matters is per-batch versus per-operation. Per-batch preparation can be hoisted into Setup and disappears from the measurement entirely. Per-operation preparation cannot: if the code under test mutates its input, the input has to be refreshed inside the loop, and its cost is measured along with the candidate. Setup does not solve that case, and no harness can.

Setup and Teardown also run around the warm-up batches, so that the warm-up exercises exactly the same code path as the measurement.

A caveat that Setup makes easy to introduce accidentally: the two candidates' setups leave the machine in different states before their measured regions begin. If one candidate's Setup allocates a large buffer and the other's does not, the first candidate starts with a colder cache and more GC pressure, and that difference is charged to the candidate rather than to its Setup. Keep the two setups comparable in cost and allocation behaviour, or move the asymmetric part outside Collect entirely.

type CollectOptions added in v0.6.0 

type CollectOptions struct {
	// Repeats is the number of timing samples to collect per candidate.
	// Zero selects [DefaultRepeats]. Must be at least [MinimumDataPoints],
	// because that is what CompareSamples requires of its inputs.
	Repeats int

	// InnerLoops is the number of operations each batch invocation performs,
	// i.e. the n handed to the [Batch] function.
	//
	// This value is what makes measurement below the system clock's resolution
	// possible: the quantization error of a single batch is at most the clock's
	// granularity, so per operation it shrinks to granularity/InnerLoops. With a
	// 100 ns clock (Windows QPC) and InnerLoops = 20000 the residual quantization
	// error is 0.005 ns/op. Differences far below one clock tick are recoverable
	// this way; a per-operation difference of 1.89 ns was recovered to within
	// 0.07 percentage points against a 41 ns clock floor.
	//
	// Zero calibrates the value automatically via [CalibrateInnerLoops], sizing
	// batches so that the clock contributes at most MaxQuantizationError of
	// relative error. Both candidates are calibrated and the larger of the two
	// results is used for both, so that each batch is at least long enough and
	// both candidates run the same number of operations. Note that the first
	// calibration in a process pays for [GetSampleTimePrecision].
	InnerLoops uint64

	// MaxQuantizationError bounds the relative per-operation error the clock's
	// granularity may contribute when InnerLoops is calibrated automatically.
	// Zero selects [DefaultMaxQuantizationError]. Ignored when InnerLoops is set
	// explicitly.
	//
	// It has a second effect worth knowing about. Quantization does not only
	// blur a measurement, it also collapses distinct measurements onto the same
	// value, and equal values produce equal medians. That matters for the
	// confidence at threshold zero, which asks whether delta >= 0 and so counts
	// every tie as "A at least as fast". Measured on one candidate here:
	//
	//	MaxQuantizationError   InnerLoops   batch      tie rate
	//	                0.01          387   4.5 us       100.0%
	//	               0.001         4072    46 us        15.3%   (the default)
	//	              0.0001        44710   482 us         0.6%
	//
	// The default is sized for accuracy of a difference's magnitude, where it
	// performs well. If the question is instead "is A faster at all", tighten it
	// by an order of magnitude and pay ten times the batch length for it.
	// [ValidateHarness] reports the tie rate a setup actually produces.
	MaxQuantizationError float64

	// MaxInnerLoops caps the batch size automatic calibration will try. Zero
	// selects [DefaultMaxInnerLoops]. Ignored when InnerLoops is set explicitly.
	MaxInnerLoops uint64

	// Order selects the measurement order within each repeat. The zero value
	// is [OrderABBA].
	Order Order

	// Warmup is the least number of unmeasured batches run per candidate before
	// sample collection starts, to fault in pages, grow stacks and train branch
	// predictors and caches. Zero selects [DefaultWarmup]. To run no warm-up at
	// all, set SkipWarmup rather than passing a negative number.
	//
	// The warm-up continues until both this count and WarmupDuration have been
	// reached, and it alternates the order of the candidates the way the
	// measurement does, so that neither of them ends it with the caches to
	// itself.
	Warmup int

	// WarmupDuration is the least wall-clock time the warm-up runs for, across
	// both candidates together. Zero selects [DefaultWarmupDuration], whose
	// documentation explains why a count alone is not enough. Negative values
	// are rejected. To warm up by count alone, set it to [time.Nanosecond].
	WarmupDuration time.Duration

	// SkipWarmup disables warm-up entirely, both the count and the duration.
	// This exists as its own field so that Warmup keeps a single unambiguous
	// meaning; "no warm-up" is a mode, not a count. Measuring without warm-up
	// means the first samples include one-time costs such as page faults and
	// stack growth, and that whichever candidate ran alone last before Collect
	// starts with a warm cache.
	SkipWarmup bool

	// GCBetween requests an explicit garbage collection before every batch,
	// after Setup and outside the measured region. This reduces the chance that
	// a collection triggered by one candidate's allocations lands inside the
	// other candidate's measured region. It is applied symmetrically to both
	// candidates. An explicit collection runs even when DisableGC is set.
	//
	// Measured on an allocating candidate in an A/A setup, over 8 runs of 101
	// samples each, by the relative standard deviation of the samples:
	//
	//	neither flag      157.3 ns/op   spread 10.26%
	//	GCBetween         139.5 ns/op   spread  6.10%
	//	DisableGC         132.3 ns/op   spread  5.93%
	//	both              139.4 ns/op   spread  5.12%
	//
	// Both flags together roughly halve the spread. Note what the ns/op column
	// shows about DisableGC on its own, and see its documentation.
	GCBetween bool

	// DisableGC turns off the automatic garbage collector for the duration of
	// the Collect call via [debug.SetGCPercent], restoring the previous setting
	// before returning. Combined with GCBetween this gives fully deterministic
	// collection points: never during a measured region, always between them.
	//
	// Three caveats. The setting is process-global, so it affects any other
	// goroutine running concurrently with Collect. The heap is not collected
	// automatically while it is in effect, so an allocation-heavy candidate over
	// many repeats can grow memory use substantially. And it removes GC assist
	// work from allocating candidates, which makes them look faster than they
	// would be in a program where the collector is running: in the measurement
	// tabulated under GCBetween, an allocating candidate ran at 132.3 ns/op with
	// the collector disabled versus 157.3 ns/op with it enabled, a 16%
	// difference that exists only in the harness. That is an acceptable trade
	// when comparing two algorithms and a misleading one when estimating what a
	// service will do, so it is off by default.
	//
	// Do not use it alone. Without GCBetween the heap grows monotonically over
	// the run, which turns into drift across the samples; in the same A/A
	// measurement, DisableGC on its own produced the largest spurious difference
	// of all four configurations. Pair it with GCBetween so that collection
	// happens at deterministic points between measured regions.
	DisableGC bool

	// Seed drives the order decisions when Order is [OrderRandom]. Zero selects
	// a non-deterministic seed. Set it to a fixed non-zero value to reproduce a
	// run's measurement order exactly.
	Seed uint64
}

CollectOptions configures a Collect run.

Every count in this struct is a Go int with the usual Go convention for counts: zero selects the documented default, and a negative value is a programming error rather than a mode. Negative values are rejected with an error instead of being silently clamped, because in practice they arise from arithmetic at the call site (a subtraction that underflowed) and failing loudly is more useful than measuring something unintended. An unsigned type would turn exactly those bugs into enormous positive counts instead.

type CompareOptions added in v0.6.0 

type CompareOptions struct {
	// Collect holds the measurement options, and its documentation is the place
	// to look for the knobs that matter: batch sizing, measurement order,
	// garbage collection. Leaving InnerLoops at zero, which is the default,
	// lets the batches be sized automatically.
	Collect CollectOptions

	// Thresholds are relative speedups to report a confidence for, e.g. 0.05 for
	// "at least 5% faster". Optional: when empty, Report.Confidence is nil and
	// the estimated difference and its interval are the whole answer. Use these
	// when a threshold is given to you, such as a regression budget.
	Thresholds []float64

	// ValidationRuns is the number of A/A experiments per candidate. Zero
	// selects [DefaultValidationRuns]; anything else must be at least two, since
	// a floor cannot be estimated from one observation. Ignored when
	// SkipValidation is set.
	//
	// This is the dominant cost of a comparison, and lowering it costs
	// precision in exactly the figures that justify the result. See
	// [DefaultValidationRuns] for what the rates are worth at a given count.
	ValidationRuns int

	// SkipValidation omits the A/A experiments. They are what turns a confident
	// number into a trustworthy one, so this is worth setting only when the
	// noise floor of this exact setup is already known, or in a test that cares
	// about speed rather than truth. Report.Warnings says so when it is set.
	SkipValidation bool

	// Level is the coverage level of the reported interval. Zero selects
	// [DefaultConfidenceLevel].
	Level float64

	// Resamples is the bootstrap resample count. Zero selects
	// [DefaultResamples].
	Resamples uint64
}

CompareOptions configures Compare. The zero value is usable and selects the documented defaults throughout.

type DPRNG 

type DPRNG struct {
	State     uint64
	Scrambler uint64
	Round     uint64 // for debugging purposes
}

DPRNG is a Deterministic Pseudo-Random Number Generator based on the xorshift* algorithm (see https://en.wikipedia.org/wiki/Xorshift#xorshift*). This random number generator is by design deterministic in the sequence of numbers it generates. It has a period of 2^64-1, i.e. every single number occurs every 2^64-1 calls and has the same successor and the same predecessor. This random number generator is deterministic in its runtime (i.e., it has a constant runtime). This random number generator is not cryptographically secure. This random number generator is thread-safe as long as each goroutine uses its own instance. This random number generator has a very small memory footprint (24 bytes). The initial state must not be zero.

func NewDPRNG added in v0.1.1 

func NewDPRNG(seed ...uint64) DPRNG

NewDPRNG creates a new Deterministic Pseudo-Random Number Generator instance. If no seed is provided, it initializes the state with a random non-zero value. If the provided seed is zero, it initializes the state with a random non-zero value. Otherwise, it uses the provided seed value. If a second uint64 value is provided, it is used as the scrambler constant. The scrambler constant creates a permutation (different sequence) of the generated numbers. If no scrambler constant is provided, Vigna's default scrambler constant is used. The only requirement for the scrambler constant is that it must be an odd number to ensure maximal period, but this is automatically enforced by the code. You can use GenerateScrambler to generate good quality scrambler constants.

func (*DPRNG) Float64 

func (thisState *DPRNG) Float64() float64

Float64 returns a pseudo-random float64 in the range [0.0, 1.0) like Go’s math/rand.Float64(). It has a deterministic (i.e. constant) runtime and a high probability to be inlined by the compiler. The generated float64 values are uniformly distributed in the range [0.0, 1.0) with the effective precision of 53 bits (IEEE 754 compliant).

func (*DPRNG) Shuffle added in v0.7.0 

func (thisState *DPRNG) Shuffle(n int, swap func(i, j int))

Shuffle puts n elements in a pseudo-random order by calling swap(i, j) for the pairs a Fisher-Yates shuffle exchanges, like math/rand's Shuffle.

Parameters: n is the number of elements, at most 2^32; swap exchanges the elements at two indices. Zero or one element leaves nothing to do, and a negative n does nothing either.

Its intended use is the build order of benchmark fixtures. Whatever is allocated last lands in different memory, and is the last data the caches saw, so a fixed order hands one candidate the same advantage in every process. Shuffling the order per process, with a seed per process, turns that into scatter that pooling across processes can average out; see Combine. 

rng := rtcompare.NewDPRNG(seed)
builders := []func(){buildA, buildB}
rng.Shuffle(len(builders), func(i, j int) { builders[i], builders[j] = builders[j], builders[i] })
for _, build := range builders { build() }

The bias of Uint32N for n that are not powers of two carries over, and it is far below anything a benchmark could notice.

func (*DPRNG) UInt32N deprecated added in v0.2.0 

func (thisState *DPRNG) UInt32N(n uint32) uint32

UInt32N is DPRNG.Uint32N under its original name.

Deprecated: the capitalisation was inconsistent with CPRNG.Uint32N and with the Go convention of treating an initialism as one word, which math/rand/v2 follows in its own Uint32N. Use Uint32N instead. This wrapper delegates and is small enough to be inlined, so it costs nothing; it exists so that callers written against the old name keep compiling.

func (*DPRNG) Uint32N added in v0.6.0 

func (thisState *DPRNG) Uint32N(n uint32) uint32

Uint32N returns a pseudo-random uint32 in the range [0, n) like Go’s math/rand.Intn(). Use this function for generating random indices or sizes for slices or arrays, for example. This code avoids modulo arithmetics by implementing Lemire's fast alternative to the modulo reduction method (see https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/). It has a deterministic (i.e. constant) runtime and a high probability to be inlined by the compiler. Note: This implementation may introduce a slight bias if n is not a power of two.

func (*DPRNG) Uint64 

func (thisState *DPRNG) Uint64() uint64

This function returns the next pseudo-random number in the sequence. It has a deterministic (i.e. constant) runtime and a high probability to be inlined by the compiler.

type DriftReport added in v0.6.0 

type DriftReport struct {
	// N is the number of samples examined.
	N int

	// Spearman is the rank correlation between each sample and its position in
	// the run, in [-1,1]. Positive means later measurements tended to be larger,
	// that is, the machine grew slower as the run went on.
	//
	// Ranks are used rather than the values themselves because timing samples
	// are heavy-tailed: a single preempted batch would dominate a correlation
	// computed on raw values. Tied values receive their average rank.
	Spearman float64

	// Z is Spearman standardized by its null distribution, Spearman*sqrt(N-1),
	// which is approximately standard normal when no trend exists.
	Z float64

	// PValue is the two-sided probability of seeing a rank correlation at least
	// this strong if the samples were in fact exchangeable, i.e. if the order in
	// which they were measured carried no information.
	PValue float64

	// FirstHalf and SecondHalf are the medians of the first and last N/2
	// samples, with the middle sample excluded when N is odd. RelativeShift is
	// their difference over FirstHalf, giving the size of the drift where PValue
	// gives its significance. A drift can be highly significant and too small to
	// care about, or large and indistinguishable from noise.
	FirstHalf     float64
	SecondHalf    float64
	RelativeShift float64
}

DriftReport describes whether a series of measurements trended over the course of the run that produced them.

func DetectDrift added in v0.6.0 

func DetectDrift(samples []float64) (DriftReport, error)

DetectDrift looks for a monotone trend across a series of measurements taken in run order, such as one of the slices returned by Collect.

This answers a question the bootstrap structurally cannot. Resampling treats the samples as an unordered bag and asks how much the estimate would move if they were drawn again; it discards the order in which they arrived, so a machine that grew steadily slower during the run leaves no trace in its output. That is precisely the situation in which a comparison is most misleading, because the drift is charged to whichever candidate was measured later.

The test is Spearman's rank correlation between each sample and its position, standardized as rho*sqrt(N-1), which is approximately standard normal under the null hypothesis that the samples are exchangeable. Ranks rather than values, because a single preempted batch is an enormous outlier and would otherwise dominate; tied values, which are common in quantized timings, take their average rank.

Significance and size are reported separately and should be read separately. A long run resolves a drift of a fraction of a percent as highly significant, which is worth knowing but may be far too small to affect a conclusion. The converse also happens.

The false positive rate was checked rather than assumed, because timing samples are quantized and heavily tied, and a rank test on tied data is not obviously well behaved. On synthetic series collapsed onto 3, 8 and 35 distinct values it fired at 4.9%, 3.9% and 3.9% against a nominal 5% with a standard error of 0.4, so ties do not break it and it errs slightly conservative. On real timing series with their order randomly permuted, which preserves the value distribution exactly while destroying any trend, it fired at 4.80% over 6000 permutations drawn from 600 series, a 95% interval of [4.27%, 5.33%] that covers the nominal rate. Permutations of one series are not independent of one another by construction, so that is the cluster-robust interval; it happens to match the naive binomial one almost exactly, the design effect being 0.95.

Those same 600 series, left in the order they were measured, tripped the test in 13.0% of runs, a 95% interval of [10.3%, 15.7%]. The gap to the permuted rate is 8.2 percentage points at z = 5.9. Their mean lag-1 autocorrelation was +0.083, with a 95% interval of [+0.069, +0.096] built from the spread actually observed across series rather than one assumed from the null. So measurement series on an ordinary machine do carry order structure, and it is not a quirk of how their values are distributed. Whether a given series carries a slow trend or short-range correlation between neighbours is not something this test separates; both make the samples non-exchangeable, which is what the bootstrap assumes they are.

An error is returned for fewer than four samples, or if any sample is not finite. Note that power is poor below roughly twenty samples: a real drift can easily go unnoticed there, so a large PValue from a short series is weak evidence of calm rather than evidence of no drift.

func (DriftReport) Drifted added in v0.6.0 

func (d DriftReport) Drifted(level float64) bool

Drifted reports whether the trend is significant at the given level, e.g. 0.05. It says nothing about whether the trend is large enough to matter; read RelativeShift for that.

func (DriftReport) String added in v0.6.0 

func (d DriftReport) String() string

String renders the report as one line.

type Estimate added in v0.6.0 

type Estimate struct {
	// Delta is the relative difference computed on the measurements themselves,
	// 1 - median(A)/median(B). Positive means A is smaller, which for runtimes
	// means faster. It is the point estimate, taken from the data rather than
	// from the resampling, so it does not move when Resamples changes.
	Delta float64

	// Low and High bound Delta at the requested Level. They are the empirical
	// quantiles of the resampled deltas, i.e. a percentile bootstrap interval.
	Low, High float64

	// Level is the interval's coverage level, e.g. 0.95.
	Level float64

	// Resamples is how many bootstrap replicates the interval was built from.
	Resamples uint64

	// BootstrapMedian is the median of the resampled deltas. Comparing it with
	// Delta shows the resampling bias: a large gap means the statistic behaves
	// awkwardly on this data and the interval deserves suspicion.
	BootstrapMedian float64
}

Estimate is a point estimate of the relative difference between two sets of measurements, together with an interval around it.

It answers a different question from CompareSamples. That one takes thresholds and reports how confident one can be that each is met, which is what you want when a threshold is given: a release gate, a regression budget. This one reports how large the difference appears to be and how precisely that is known, which is what you want when no threshold is given and the honest answer might be "somewhere between 2% and 19%".

func EstimateDifference added in v0.6.0 

func EstimateDifference(A, B []float64, level float64, resamples uint64) (Estimate, error)

EstimateDifference reports how much smaller the measurements in A are than those in B, as a relative fraction, with a bootstrap interval around it.

The point estimate is computed on the measurements directly. The interval is a percentile bootstrap: resample both inputs, recompute the difference for each replicate, and take the empirical quantiles at (1-level)/2 and (1+level)/2. Ties in the resampled distribution are handled by the quantile definition below, which interpolates.

Coverage was measured rather than assumed, by simulating pairs drawn from distributions whose true difference is known and counting how often the interval contained it. At a nominal 95%, over 2000 trials per cell with 1000 resamples, the standard error being half a point: 

samples per side    normal    lognormal    one-sided contamination
              11     97.2%        97.0%                      96.9%
              25     96.7%        96.9%                      96.7%
              51     96.5%        96.2%                      96.8%
             101     96.0%        96.4%                      96.3%

The interval is therefore conservative by one to two points rather than optimistic, consistently across shapes and sizes, and it narrows towards nominal only slowly. The reason is discreteness: a resampled median can only take values that appear in the sample, so the bootstrap distribution of the median is coarser than its true sampling distribution and its quantiles sit further apart. Erring wide is the safe direction, but a stated 95% is closer to 96 or 97 in practice.

The misses split evenly between the two ends, about 1.8% on each side against a nominal 2.5%, so the interval is well centred and not merely shifted.

A caveat that no interval width can express: this covers sampling uncertainty only. It says nothing about a bias that affected every measurement, and a machine that drifted during the run will produce a tight interval around the wrong number. Read it alongside ValidateHarness and DetectDrift. Nor does it cover the next process: measurements from one run of a program share that run's memory layout, which for large or pointer-heavy data can shift the difference far beyond this interval. Pool several processes with Combine where that matters.

Level zero selects DefaultConfidenceLevel. Resamples zero selects DefaultResamples. An error is returned if either input holds fewer than MinimumDataPoints values or if level is not strictly between zero and one.

func (Estimate) Excludes added in v0.6.0 

func (e Estimate) Excludes(value float64) bool

Excludes reports whether the interval lies entirely on one side of the given value, i.e. whether the data rule that value out at this level. Excludes(0) asks whether a difference has been established at all.

func (Estimate) String added in v0.6.0 

func (e Estimate) String() string

String renders the estimate as one line, in percent.

type HarnessValidation added in v0.6.0 

type HarnessValidation struct {
	// Runs is how many A/A experiments were performed.
	Runs int

	// InnerLoops is the batch size used, after calibration if it was requested.
	// It is fixed across runs so that they are comparable.
	InnerLoops uint64

	// NoiseFloor is the [NoiseFloorQuantile] quantile of the absolute relative
	// differences observed between the two sample sets of identical code, as a
	// fraction. It is the practical resolution limit of the setup: a real
	// comparison reporting less than this has measured nothing.
	//
	// It is a quantile rather than the maximum because a maximum has no value to
	// converge on and grows with Runs, which made the gate stricter the more
	// carefully a setup was validated. See NoiseFloorQuantile for the
	// measurements. The consequence to keep in mind is that this is not a bound:
	// about one A/A run in ten exceeds it by construction, so clearing it is
	// evidence rather than proof. See MaxObservedNoise for the largest
	// difference actually seen and TypicalNoise for the middle of the
	// distribution.
	NoiseFloor float64

	// MaxObservedNoise is the largest absolute relative difference seen across
	// the runs. It is what NoiseFloor used to report. Read it as the worst case
	// this validation happened to catch, remembering that it grows with Runs and
	// so describes the length of the validation as much as the setup.
	MaxObservedNoise float64

	// TypicalNoise is the median absolute relative difference across runs.
	TypicalNoise float64

	// MeanConfidence and MedianConfidence average the confidence that "A is
	// faster than B" across the runs. Since A and B are the same code, an
	// unbiased setup must centre on 0.5. A systematic departure indicates that
	// something about the measurement favours one position over the other,
	// which is what interleaving the order is meant to prevent.
	//
	// These are computed with ties split rather than as the plain confidence at
	// threshold zero, which would centre above 0.5 even on a perfect setup. See
	// TieRate.
	MeanConfidence   float64
	MedianConfidence float64

	// TieRate is the share of bootstrap replicates in which both resampled
	// medians came out exactly equal, taken as the median across the runs.
	//
	// The median rather than the mean, because of how the per-run figure is
	// obtained. It is recovered as confAB + confBA - 1 from two independent
	// bootstrap runs, so it carries the Monte Carlo error of both and can come
	// out slightly negative when the true rate is near zero. Clamping those to
	// zero would bias a mean upwards by a few tenths of a point on a setup that
	// ties hardly at all; the median is unaffected, since half the estimates
	// land on either side. The cost is that a true rate below the Monte Carlo
	// noise reports as zero, which is the honest answer at that resolution.
	//
	// Timing measurements are quantized, so identical values are common and ties
	// with them. One A/A run here produced 102 samples holding only 35 distinct
	// values, and tied medians in 14.4% of its replicates. Since the confidence
	// at threshold zero asks whether delta >= 0, every one of those ties counts
	// as "A at least as fast", which lifts it by half the tie rate. Over 40 runs
	// of that setup the mean tie rate was 17.8% and the offset against the
	// tie-split figure was 0.089, matching half of it to three decimals.
	//
	// A high tie rate means the measurement is coarse relative to the
	// differences being asked about. The fix is longer batches, and only longer
	// batches. One measurement is an integer count of clock ticks divided by the
	// batch size, so its granularity is precision/InnerLoops: raising InnerLoops
	// makes the individual value finer and ties correspondingly rarer. Raising
	// Repeats does not, and measurably does not; it draws more values from the
	// same coarse set.
	//
	// Measured on one candidate here, holding Repeats at 51 and varying only the
	// batch size:
	//
	//	InnerLoops    granularity    tie rate
	//	     1,000     0.042 ns/op       86.3%
	//	     5,000     0.008 ns/op       15.0%
	//	   100,000     0.0004 ns/op       1.5%
	//	   400,000     0.0001 ns/op       0.0%
	//
	// and varying only Repeats at a fixed batch size of 20,000, tie rates of
	// 2.2%, 2.3%, 2.8% and 1.8% for 21, 51, 101 and 201 repeats: no trend.
	//
	// In practice the knob to turn is CollectOptions.MaxQuantizationError, which
	// is what sizes the batch. See its documentation for what the default costs
	// here.
	TieRate float64

	// FalseSignalRate is the fraction of runs whose confidence fell outside
	// [1-Level, Level], that is, runs that would have reported a difference in
	// one direction or the other where none exists. Under perfect calibration
	// it should come to about 2*(1-Level).
	FalseSignalRate float64

	// Level is the confidence level FalseSignalRate was judged against.
	Level float64

	// DriftRate is the fraction of runs in which at least one of the two sample
	// series showed a significant trend across the run, as judged by
	// [DetectDrift] at [DriftLevel].
	//
	// A trend means the machine did not hold still while it was being measured,
	// which is the one situation where measurement order turns into an apparent
	// difference between candidates. It is also invisible to the bootstrap,
	// which treats the samples as an unordered bag. On a quiet machine this
	// should sit near DriftLevel itself, that being the rate at which the test
	// fires on calm data by construction; substantially above it means runs are
	// long enough for the machine to change during them.
	//
	// Note that DetectDrift looks for a monotone trend but will also respond to
	// strong short-range correlation between neighbouring batches. Both violate
	// the exchangeability the bootstrap assumes, so either is worth knowing
	// about, but this figure does not distinguish them.
	DriftRate float64

	// MedianDriftShift is the median *absolute* relative shift between the first
	// and second half of a run's samples, across the runs and both series. It is
	// the size of the drift where DriftRate is its prevalence.
	//
	// Absolute, so it does not matter whether a run sped up or slowed down; both
	// are the machine failing to hold still, and averaging them signed would let
	// them cancel. It is therefore never negative, and it carries no direction.
	// Read DriftReport.RelativeShift from [DetectDrift] on an individual series
	// if the direction matters.
	MedianDriftShift float64

	// Autocorrelation is the median lag-1 autocorrelation of the sample series,
	// across the runs and both candidates. It says how much each measurement
	// resembles the one taken before it.
	//
	// Its use is deciding whether the ordinary bootstrap can be trusted here.
	// Resampling assumes the samples are exchangeable, and correlated samples
	// carry less information than the same number of independent ones, so beyond
	// some point a method that assumes independence grows overconfident. The
	// point is around 0.2: in AR(1) simulations the rate of false signals from
	// identical inputs held at its nominal 10% up to 0.08, reached 13.5% at 0.2,
	// 21.7% at 0.4 and 33.1% at 0.6. Below roughly 0.2 there is nothing to fix;
	// above it, see [BlockBootstrapConfidence].
	//
	// For reference, 600 real series on the machine these notes were written on
	// averaged +0.10, with about 6% of them genuinely above 0.2 once the noise of
	// the estimator itself is accounted for.
	Autocorrelation float64

	// Deltas and Confidences hold the per-run values the summary is built from,
	// in the order the runs were performed. Their sequence is worth a look:
	// a trend across them is drift rather than noise.
	Deltas      []float64
	Confidences []float64
}

HarnessValidation reports what repeated A/A experiments revealed about a measurement setup: the same candidate measured as both A and B, under exactly the options a real comparison would use.

Everything an A/A experiment finds is noise by construction, because there is no difference to find. That makes it the one experiment that can say how much of an apparent difference a setup invents on its own.

func ValidateHarness added in v0.6.0 

func ValidateHarness(c Candidate, opt ValidationOptions) (HarnessValidation, error)

ValidateHarness measures how much difference a setup reports between two measurements of identical code, and returns it as a HarnessValidation.

It runs the candidate against itself through Collect, repeatedly, using the options supplied. Any difference it finds is by definition an artefact: of measurement order, of drift, of the scheduler, of the collector. The result is therefore the floor below which that setup cannot distinguish a real difference from its own noise, and it is the honest companion to any confidence figure the same setup produces.

This matters because bootstrap resampling cannot supply it. Resampling quantifies how much the estimate would move if the same measurements were drawn again; it cannot see a bias that affected every measurement equally, and it will report a tight confidence around one. Measured on identical code, this package has seen apparent differences ranging from a few tenths of a percent to well over one, carried with high confidence. Only an A/A experiment exposes that.

The cost is Runs times one Collect plus one calibration, and rather more bootstrap work than a single comparison: each run resamples twice, once in each direction, because splitting ties needs the confidence both ways. The resampling dominates. Measured on a candidate calibrated to 48 microsecond batches, the whole validation took 0.76 s at ten runs and 3.03 s at forty, of which the measurement itself was under a tenth. On top of that comes one warm-up of CollectOptions.WarmupDuration, DefaultWarmupDuration unless set, before the first run only; the later runs warm up by count alone, since the candidate has been running all along.

A worked use, and the reason the API exists: measure the noise floor first, then require a real result to clear it.

Validate both candidates, not just one: they need not be equally well behaved, and a comparison is only as trustworthy as the worse of them. When the two are about to be compared, validate them together with ValidatePair rather than calling this function twice. A candidate validated on its own runs alone for the whole validation and leaves the caches full of its own data, so the one validated last starts the comparison warm and the other cold; with a working set near the size of the last-level cache that alone has produced differences of 10 to 50% between identical code. 

va, vb, err := rtcompare.ValidatePair(fast, slow, rtcompare.ValidationOptions{Collect: opts})
floor := max(va.NoiseFloor, vb.NoiseFloor)

sa, sb, err := rtcompare.Collect(fast, slow, opts)
observed := 1 - rtcompare.Median(sa)/rtcompare.Median(sb)
if math.Abs(observed) <= floor {
    // The difference is within what this machine invents on its own.
}

func ValidatePair added in v0.7.0 

func ValidatePair(a, b Candidate, opt ValidationOptions) (va, vb HarnessValidation, err error)

ValidatePair runs the A/A validation of two candidates together, and returns the same HarnessValidation for each that ValidateHarness would.

Parameters: a and b are the two candidates that are about to be compared, and opt holds the options the comparison will use, exactly as for ValidateHarness. When opt.Collect.InnerLoops is zero, both candidates are calibrated and the larger batch size is used for both validations, as Compare and Collect do it, so that the floors describe the batch size the comparison will measure at.

Use it in place of two calls to ValidateHarness whenever the validation is followed by a comparison of the same two candidates, which is what Compare does. The difference is the order in which the batches run. Called one after the other, the two validations each let one candidate run alone for a long time, and whichever ran last starts the comparison with the caches full of its own data. For a working set near the size of the last-level cache that is a head start large enough to report identical code as tens of percent apart (issue #111). ValidatePair instead runs every A/A experiment of a interleaved with one of b, batch by batch in the balanced order A, B, B′, A′ and back, so neither candidate ever runs alone for more than two batches. The floors are measured with the other candidate competing for the caches, as it will during the comparison; see pairSlots for why the order is that one.

The cost is the same as the two separate calls, minus one warm-up.

An error is returned if either candidate has a nil Batch, for the option errors of ValidateHarness, or if calibration fails. 

va, vb, err := rtcompare.ValidatePair(a, b, rtcompare.ValidationOptions{Collect: opts})
if err != nil { ... }
floor := max(va.NoiseFloor, vb.NoiseFloor)
sa, sb, err := rtcompare.Collect(a, b, opts)

func (HarnessValidation) Resolves added in v0.6.0 

func (v HarnessValidation) Resolves(relativeDifference float64) bool

Resolves reports whether a relative difference of the given size is larger than the noise this validation observed, and so whether the setup can tell it apart from nothing at all. The sign is ignored.

This is a necessary condition, not a sufficient one, in two separate ways. Clearing the floor says the difference is not obviously an artefact of the harness; it says nothing about whether it is caused by the code rather than by the compiler's layout choices or the machine's mood. And the floor is the NoiseFloorQuantile quantile rather than a bound, so about one A/A run in ten produces a difference that would clear it. Treat a result just above the floor as unresolved and a result well above it as resolved.

The floor is also measured on one candidate against itself. Two genuinely different candidates can be noisier than that, since they need not allocate alike or occupy the cache alike, so validate both and use the worse of the two floors.

func (HarnessValidation) String added in v0.6.0 

func (v HarnessValidation) String() string

String renders the validation as a short multi-line report.

type Order added in v0.6.0 

type Order int

Order selects the sequence in which the two candidates are measured within each repeat.

Measurement order is a classical source of systematic bias. If the machine changes over the course of a run, through thermal throttling, frequency scaling or page cache warm-up, then a fixed A-then-B order turns that change into an apparent difference between the candidates, because one of them is always measured in the later, altered conditions. Interleaving removes the mechanism, and it is free: the order is decided before the clock is read.

Whether it matters on a given machine is a separate question, and one worth checking rather than assuming. Across 40 A/A experiments here, no strategy was measurably biased: mean confidences of 0.487 (Sequential), 0.475 (ABBA) and 0.517 (Random), each within one standard error of about 0.04 of the 0.5 that an unbiased setup must produce. Treat interleaving as insurance with a zero premium rather than as a demonstrated correction, and use ValidateHarness to find out what your own machine and options actually do. 

const (
	// OrderABBA alternates the order every repeat: A then B on even repeats,
	// B then A on odd repeats. Over each block of four batches both candidates
	// occupy the same mean position in the run and are each preceded by the
	// other exactly half the time, which cancels a first-order trend across the
	// run as well as carry-over between neighbouring batches. It is the zero
	// value, so the arrangement that removes the mechanism is what you get
	// without asking.
	OrderABBA Order = iota

	// OrderRandom picks the order independently at random for each repeat,
	// driven by CollectOptions.Seed for reproducibility. Use it when the
	// interference you are worried about might itself be periodic and could
	// alias with the strict alternation of ABBA; prefer OrderABBA otherwise,
	// since its balance is exact rather than expected.
	OrderRandom

	// OrderSequential always measures A before B. It is the naive arrangement,
	// kept for comparison and for regression testing: it is the one order in
	// which a trend across the run maps directly onto an apparent difference
	// between the candidates. Prefer OrderABBA for results.
	OrderSequential
)

func (Order) String added in v0.6.0 

func (o Order) String() string

String implements fmt.Stringer.

type Pooled added in v0.7.0 

type Pooled struct {
	// Processes is the number of per-process results that were combined.
	Processes int

	// Delta is the mean of the per-process deltas, each 1 - median(A)/median(B).
	// Positive means A is faster. The mean is unweighted on purpose: the
	// per-process intervals understate each process's real uncertainty, which is
	// the problem this type exists to solve, so weighting by them would give the
	// processes that happened to be least noisy inside the most say.
	Delta float64

	// Low and High bound Delta at Level: a Student t interval over the
	// per-process deltas with Processes-1 degrees of freedom. With few processes
	// it is wide, and honestly so.
	Low, High float64

	// Level is the coverage level of the interval.
	Level float64

	// SpreadBetween is the standard deviation of the per-process deltas.
	SpreadBetween float64

	// SpreadWithin is the median standard error that a single process's own
	// interval implies, (High-Low)/(2z) at that interval's level.
	SpreadWithin float64

	// Inflation is SpreadBetween/SpreadWithin: how many times more the
	// processes scatter than one process's interval says they should. Near one,
	// a single process could be trusted on its own; measured on large,
	// pointer-heavy data it has been 5 and more. Zero when SpreadWithin is zero.
	Inflation float64

	// Q is Cochran's heterogeneity statistic, the sum of the squared deviations
	// of the per-process deltas from their inverse-variance mean, in units of
	// each process's own standard error. Without variance between processes it
	// is about Processes-1. NaN when a process reported an interval of zero
	// width, since its standard error is then unknown.
	Q float64

	// I2 is the share of the scatter between processes that their own intervals
	// do not explain, max(0, (Q-(k-1))/Q), in [0,1]. Above about 0.5 the
	// variance between processes dominates. NaN when Q is.
	I2 float64

	// Validated reports whether every combined process ran its A/A validation.
	Validated bool

	// NoiseFloor is the median of the validated processes' noise floors, zero
	// when none was validated. Resolved requires Delta to clear it, as for a
	// single Report.
	NoiseFloor float64

	// Resolved is the short answer: the pooled interval excludes zero and Delta
	// clears the noise floor.
	Resolved bool

	// Warnings lists everything that undermines the pooled result, in plain
	// sentences.
	Warnings []string
}

Pooled is one comparison combined across several processes by Combine.

It treats each process as a single observation of the difference. Its interval therefore covers what a single Report's interval cannot: that each process lays its data out in memory differently, and that the layout can move the difference by more than the noise within any one of them.

func Combine added in v0.7.0 

func Combine(reports []Report, level float64) (Pooled, error)

Combine pools the reports of the same comparison, run once in each of several processes, into one estimate whose interval includes the scatter between processes.

Parameters: reports holds one Report per process, all of the same comparison, with the same candidates in the same roles; at least three are required, and five or more are advisable. level is the coverage level of the pooled interval, zero selecting DefaultConfidenceLevel.

It returns the Pooled result, or an error if there are fewer than three reports, if level is not strictly between zero and one, or if a report holds a non-finite estimate.

Use it whenever the data of a comparison does not fit in the caches or is full of pointers. A single process reports an interval that covers only the noise within that process. The process's memory layout is fixed for its whole lifetime, and it can move the difference by several points, so the next process reports a different, equally narrow interval somewhere else. Observed on 1M-key trees, the processes scattered 4 to 10 times more widely than their own intervals implied, and two processes resolved the same comparison with opposite signs. Combine treats each process as one observation: Delta is the mean of the per-process deltas and the interval is a t interval over them, which is honest for few processes where random-effects weighting is known to be too narrow. Q, I2 and Inflation say how much the processes disagreed beyond their own intervals.

Pooling only helps if the processes sample different layouts. A process that allocates the same things in the same order gets much the same layout every time, and its bias repeats rather than averages out; see PerturbHeap. The multiproc package starts the processes, perturbs each one's heap and calls Combine for you. 

var reports []rtcompare.Report // one per process, e.g. read back from files
pooled, err := rtcompare.Combine(reports, 0)
if err != nil { ... }
fmt.Println(pooled)

func (Pooled) Precise added in v0.7.0 

func (p Pooled) Precise(abs, rel float64) bool

Precise reports whether the interval is narrow enough for the question: its half-width is at most abs, or at most rel times |Delta|. The multiproc package uses it as its rule for when to stop starting processes, with defaults of 0.02 and 0.10.

func (Pooled) String added in v0.7.0 

func (p Pooled) String() string

String renders the pooled result as a short multi-line summary.

type RTcomparisonResult 

type RTcomparisonResult struct {
	// RelativeSpeedupSampleAvsSampleB is the relative speedup threshold that was evaluated.
	RelativeSpeedupSampleAvsSampleB float64
	// Confidence is the estimated confidence (in [0,1]) that the relative speedup of sample A over sample B
	// meets or exceeds RelativeSpeedupSampleAvsSampleB.
	Confidence float64
}

RTcomparisonResult holds the result of comparing two sets of runtime measurements. For each requested relative speedup threshold it contains the estimated confidence that the speedup of sample A over sample B meets or exceeds that threshold.

func CompareRuntimes deprecated 

func CompareRuntimes(measurementsA, measurementsB []float64, relativeGains []float64, resamples uint64) (result []RTcomparisonResult, err error)

Deprecated: Use CompareSamples instead. This function is retained for backward compatibility.

func CompareSamples added in v0.3.0 

func CompareSamples(measurementsA, measurementsB []float64, relativeGains []float64, resamples uint64) (result []RTcomparisonResult, err error)

CompareSamples compares two sets of scalar measurements (for example: runtimes, memory footprints, or other numeric metrics) and estimates the confidence that values from `measurementsA` are smaller than those from `measurementsB` by at least the requested relative thresholds.

The function is intentionally metric-agnostic: it treats each input slice as a sample of independent measurements where *smaller* values indicate a better outcome (this matches runtimes or memory consumption). If you have a "larger-is-better" metric (e.g., throughput), transform the inputs before calling this function (for example by taking the reciprocal or negating the values) so that smaller means better.

For each bootstrap replicate the implementation draws a resampled population from `measurementsA` and `measurementsB`, computes their medians and evaluates the relative improvement as: 

delta = 1 - median(A_sample)/median(B_sample)

A positive `delta` indicates that `measurementsA` are smaller than `measurementsB` by that relative fraction (e.g. delta=0.2 → A is 20% smaller). For each requested relative gain the function reports the fraction of replicates where `delta >= threshold` as the confidence.

Parameters:

  • measurementsA, measurementsB: samples of scalar measurements (float64). Prefer measurements that share the same units and scale (e.g., both in milliseconds).

  • relativeGains: relative improvement thresholds to evaluate (e.g. 0.05 means "A is at least 5% smaller than B"). If nil or empty, the function evaluates a single relative gain at 0.0.

    A threshold of 0.0 deserves a word of warning, because it is the one place where the inclusive comparison bites. Every threshold is evaluated as `delta >= t`, so at t = 0 the question is "is A at least as small as B", not "is A smaller". Replicates in which both medians come out exactly equal count towards the confidence.

    With quantized inputs such as timings, that is not a rare corner case. A measurement is an integer count of clock ticks divided by a batch size, so distinct measurements collapse onto identical values: at this package's default calibration target, an ordinary run tied in about 15% of replicates, lifting the confidence at t = 0 by half that. Ask for a threshold above zero if you mean strictly faster, or shrink the quantization; see CollectOptions.MaxQuantizationError and the tie rate reported by ValidateHarness.

    Negative values in `relativeGains` are allowed and are interpreted as tolerated relative *slowdowns* of A vs. B. Concretely, a threshold `t < 0` is evaluated as `delta >= t` where `delta = 1 - median(A)/median(B)`. For example, `t = -0.05` corresponds to the statement "A is not more than 5% slower than B" (i.e., A is within 5% of B). A replicate with `delta = -0.03` would count as meeting `t = -0.05` because `-0.03 >= -0.05`.

    Use negative thresholds when you want to ask whether A is *within* a relative tolerance of B rather than strictly faster. Zero remains the boundary "is A smaller than B?" and positive thresholds require A to be faster by at least that relative fraction.

  • resamples: number of bootstrap resamples to run (larger → more precise estimates, longer runtime). See the note in `BootstrapConfidence` for guidance and literature references about choosing the number of resamples.

Why the median

Each replicate is summarised by its median rather than its mean or its smallest value, and that choice was checked against the alternative rather than assumed. Interference is one-sided — a disturbed batch is slower, never faster — which is an argument for a low quantile, on the reasoning that it sits below the contamination. Simulated against a known difference with lognormal measurement noise, 101 samples per side and 3000 trials, that reasoning turns out to be wrong in the ordinary case: 

disturbed batches    median RMSE    p10 RMSE
                0%        0.0055      0.0079
               10%        0.0063      0.0079
               20%        0.0076      0.0082
               30%        0.0101      0.0086
               40%        0.0285      0.0091
               50%        0.0818      0.0098

Below about 30% the median is the better estimator and a low quantile is merely noisier, because the median is already immune: with contamination on fewer than half the samples, the middle one is drawn from the clean part of the distribution. The smallest value is worse still at every rate, its variance being several times the median's once the noise has no hard floor.

Past 40% the median degrades sharply, as it must: it is approaching the boundary of the contaminated region and begins jumping between clean and disturbed values. But that regime does not need a different estimator so much as a different machine, and it does not go unnoticed. In A/A simulations the noise floor that ValidateHarness reports rises from 1.2% with no interference to 3.1% at 30% and 20.5% at 40%, so a setup in which the median is failing announces itself as one whose measurements are worthless anyway.

Returns a slice of RTcomparisonResult where each entry contains the requested relative threshold and the corresponding confidence in [0,1]. If either input contains fewer than `MinimumDataPoints` values an error is returned.

The results are ordered by ascending threshold and contain one entry per *distinct* threshold: passing the same value several times yields a single result for it, not several. The caller's `relativeGains` slice is left untouched; sorting and deduplication happen on an internal copy.

Non-finite thresholds are treated differently from one another:

  • NaN is rejected with an error naming its index. It cannot be answered meaningfully, since `delta >= NaN` is false for every delta, and the resulting confidence of zero would be indistinguishable from a genuine result. Watch for this when feeding F2T results in unchecked: F2T signals invalid input by returning NaN.
  • +Inf and -Inf are accepted. They are degenerate but well defined and internally consistent: `delta >= -Inf` holds for every non-NaN delta, so -Inf always yields confidence 1, and no finite delta reaches +Inf, so +Inf always yields confidence 0. They are of little practical use as thresholds, but they do not misreport anything.

func CompareSamplesDefault added in v0.3.0 

func CompareSamplesDefault(measurementsA, measurementsB []float64, relativeGains []float64) (result []RTcomparisonResult, err error)

CompareRuntimesDefault calls CompareRuntimes using `DefaultResamples`. This convenience wrapper avoids repeating the numeric literal in callers and documents the recommended default in the public API.

type Report added in v0.6.0 

type Report struct {
	// NsPerOpA and NsPerOpB are the median per-operation costs, in the units the
	// batch functions produced, which for timing candidates is nanoseconds.
	NsPerOpA, NsPerOpB float64

	// SamplesA and SamplesB are the raw measurements in the order they were
	// taken, for anyone who wants to do their own analysis.
	SamplesA, SamplesB []float64

	// Estimate is how much smaller A is than B, with an interval around it.
	// Positive means A is faster.
	//
	// The interval covers the noise within this one process and nothing else.
	// Each process gets its own memory layout, and for data larger than the
	// caches or full of pointers that layout alone can shift the difference by
	// several points, far beyond this interval, and differently in the next
	// process. Where that matters, run the comparison in several processes and
	// read [Combine]'s pooled interval instead; see the multiproc package.
	Estimate Estimate

	// Confidence maps each requested threshold to the confidence that it is
	// met. It is nil when CompareOptions.Thresholds was empty.
	Confidence map[float64]float64

	// Validated records whether the A/A experiments were performed. When false,
	// NoiseFloor is zero because it is unknown, not because it is small.
	Validated bool

	// ValidationA and ValidationB are the A/A results for each candidate.
	ValidationA, ValidationB HarnessValidation

	// NoiseFloor is the worse of the two candidates' noise floors, and so the
	// difference this setup can invent from identical code. A result that does
	// not clear it has resolved nothing.
	NoiseFloor float64

	// Autocorrelation is the worse of the two candidates' lag-1
	// autocorrelations, and is what BlockLength was chosen from.
	Autocorrelation float64

	// BlockLength is the resampling block length that was used. One means the
	// samples were treated as independent, which is the ordinary bootstrap.
	BlockLength int

	// DriftA and DriftB test each series for a trend across the run. A zero N
	// means the test could not be run.
	DriftA, DriftB DriftReport

	// LiveHeap is the live heap in bytes as of the last garbage collection
	// during the comparison, zero if the runtime did not report it. Above
	// [LargeHeapThreshold] the warnings recommend running the comparison in
	// several processes.
	LiveHeap uint64

	// Suspended is how much longer the wall clock ran than the monotonic clock
	// during the comparison, when that exceeded [SuspendThreshold], and zero
	// otherwise. Non-zero means the machine was asleep for about that long in
	// the middle of the measurement, which neither the samples nor the drift
	// tests can show reliably. See SuspendThreshold for the platforms this
	// works on.
	Suspended time.Duration

	// DriftRatio tests the ratio B/A of each pair of neighbouring batches for a
	// trend across the run. A zero N means the test could not be run.
	//
	// It sees what DriftA and DriftB cannot: a machine that slows down slows
	// both candidates alike and leaves the ratio flat, while one candidate that
	// started with the caches to itself and loses them over the run moves the
	// ratio and nothing else. A trend here means the two had not reached a
	// steady state when the measurement began, so the difference depends on how
	// long the run was; see [DefaultWarmupDuration].
	DriftRatio DriftReport

	// Resolved is the short answer: the difference is both statistically
	// distinguishable from zero and larger than what this setup invents on its
	// own. It is deliberately conservative, and false does not mean the
	// candidates are equally fast; it means this run did not establish that they
	// are not.
	Resolved bool

	// Warnings lists everything that undermines the result, in plain sentences.
	// An empty slice is the good case. They are worth reading even when Resolved
	// is true.
	Warnings []string
}

Report is everything Compare found, with Resolved and Warnings as the short answer and the rest as the evidence for it.

func Compare added in v0.6.0 

func Compare(a, b Candidate, opt CompareOptions) (Report, error)

Compare measures two candidates and answers, in one call, whether one is genuinely faster than the other on this machine.

It exists because the honest procedure has several steps and three judgement calls, and getting any of them wrong quietly produces a confident wrong answer. Compare performs the whole protocol and makes the judgement calls from what it measured:

  1. Size the batches once, so that the clock contributes at most a fixed share of error, and hold that size fixed for everything that follows. This is what makes differences far below the clock's resolution measurable.
  2. Run each candidate against itself, repeatedly, to find out what this setup reports as a difference when there is provably none. That is the noise floor, and it is the number every result has to be read against. The two candidates' validations are interleaved batch by batch, see ValidatePair, so that neither enters the comparison with the caches to itself.
  3. Warm both candidates up, alternately, for at least CollectOptions.WarmupDuration, then measure them against each other, interleaved.
  4. Test each series, and the ratio between them, for a trend across the run, which resampling cannot see because it discards the order the samples arrived in.
  5. Resample in blocks if the measurements turned out to be correlated with their neighbours, and as single observations if they did not.
  6. Report the difference, an interval around it, and whether it clears both zero and the noise floor.

Both candidates are validated, not just one, because they need not be equally well behaved and the comparison is only as trustworthy as the worse of them. The batch size is determined before validation rather than inside it, so that the floor describes the same setup the measurement used; calibrating separately would let them differ.

Report.Resolved is the short answer and Report.Warnings is the fine print. Read the warnings even when Resolved is true: a run can clear both bars and still have drifted.

Cost

Validation dominates, at CompareOptions.ValidationRuns experiments per candidate against one measurement run. Comparing this package's own two median implementations at every default took about six seconds. Set SkipValidation to pay only for the measurement, accepting that the result then has nothing to be read against.

Two warm-ups of CollectOptions.WarmupDuration come on top, one before the validation and one before the measurement, which at DefaultWarmupDuration is 0.6 s in all, or 0.3 s with SkipValidation.

What ran before it

Whatever touched one candidate's data last before Compare, such as building its fixture, starts that candidate with a warm cache. The warm-ups are there to wash this out, and with a working set near the size of the last-level cache they need the time they take. Building the two candidates' data in an interleaved or balanced order costs nothing and removes the question. When a head start survives anyway, Report.DriftRatio shows it as a trend and Report.Warnings says so.

What it still cannot tell you

The measured difference is that of the whole batch body, not of the isolated function, so any fixed per-operation overhead in the loop shrinks it; see the note on attenuation in Collect. And a noise floor measured on identical code is a lower bound on the noise between two different ones. Neither is repaired by more resamples.

An error is returned if either candidate has a nil Batch, if batch sizing fails, if any threshold is NaN, or if the underlying measurement or validation fails. See Collect for the option-validation errors.

func (Report) String added in v0.6.0 

func (r Report) String() string

String renders the report as a short multi-line summary.

type Spacers added in v0.7.0 

type Spacers struct {
	// contains filtered or unexported fields
}

Spacers holds the allocations PerturbHeap made. Its only purpose is to stay reachable: while it is, the memory it occupies is not handed to anything else.

func PerturbHeap added in v0.7.0 

func PerturbHeap(seed uint64) *Spacers

PerturbHeap allocates a pseudo-random amount of filler in every small allocation size and one large block, so that data allocated afterwards lands at addresses and in cache sets that differ from one seed to the next.

Parameters: seed selects the perturbation; zero is a valid seed like any other. Give each process a different one, and record it, so that a process can be repeated exactly.

It returns the spacers, which must stay reachable until the measurement is over: `defer rtcompare.PerturbHeap(seed).KeepAlive()` does that. If they were collected, their memory could be handed to the code under test and the perturbation would partly undo itself.

The multiproc package calls it in every child process before the suite runs, so that code using multiproc never needs to. Call it yourself only when running processes by other means, at the start of a process, before building the data the candidates work on. The problem it addresses is that a Go program's heap layout is deterministic: the same allocations in the same order give much the same addresses in every run. For data larger than the caches or full of pointers, that layout moves a measured difference by several points, and a program that repeats its layout repeats its bias in every process, which pooling across processes cannot remove (issue #109). Perturbing the heap per process turns the layout into a random effect, which Combine can average over. It does not replace varying the order in which the fixtures are built: in the reproduction in cmd/rtcompare-aa, whichever of two identical lists was built second stayed about 3% faster whatever the perturbation, so the build order has to alternate between processes as well; see the multiproc package. The idea follows Curtsinger and Berger, "STABILIZER: Statistically Sound Performance Evaluation", ASPLOS 2013, which randomizes code, stack and heap layout for the same reason.

It only moves the heap. Code layout, stack addresses and the size of the environment, which also shift performance (Mytkowicz et al., "Producing Wrong Data Without Doing Anything Obviously Wrong!", ASPLOS 2009), are untouched.

The filler costs a few megabytes of spacers across the size classes, both with and without pointers, plus a large block of up to 16 MB whose pages are mostly never touched, and about a millisecond.

func (*Spacers) Bytes added in v0.7.0 

func (s *Spacers) Bytes() int

Bytes returns how much memory the spacers occupy, for reporting.

func (*Spacers) KeepAlive added in v0.7.0 

func (s *Spacers) KeepAlive()

KeepAlive keeps the spacers reachable up to the point of the call. Call it after the last measurement, e.g. with defer right after PerturbHeap.

type TimeStamp 

type TimeStamp = time.Time

A relative TimeStamp with the highest possible precision on the current runtime system. The values aren't comparable between computer restarts or between computers. They are only comparable on the same computer between two calls to SampleTime() within the same runtime of a program.

func SampleTime 

func SampleTime() TimeStamp

SampleTime returns a timestamp with the highest possible precision on the current runtime system.

type ValidationOptions added in v0.6.0 

type ValidationOptions struct {
	// Collect holds the measurement options to validate. Pass the same options
	// the real comparison will use: a noise floor measured under different
	// conditions describes a different setup. If its InnerLoops is zero it is
	// calibrated once and then held fixed for every run.
	Collect CollectOptions

	// Runs is the number of A/A experiments to perform. Zero selects
	// [DefaultValidationRuns]. At least two are required for a floor to mean
	// anything.
	Runs int

	// Resamples is the bootstrap resample count per run. Zero selects
	// [DefaultResamples].
	Resamples uint64

	// Level is the confidence level that FalseSignalRate is judged against.
	// Zero selects [DefaultValidationLevel]. Must be in (0.5, 1).
	Level float64
}

ValidationOptions configures ValidateHarness. The zero value is usable.

Source Files

View all Source files

Directories

Path Synopsis
cmd
rtcompare-aa command
Command rtcompare-aa compares two identical, separately allocated data structures with each other, so that the true difference is zero by construction and everything rtcompare reports is an artefact of the measurement.
 Command rtcompare-aa compares two identical, separately allocated data structures with each other, so that the true difference is zero by construction and everything rtcompare reports is an artefact of the measurement.
rtcompare-example command
Command rtcompare-example compares two median implementations and reports whether the difference between them is one this machine can actually resolve.
 Command rtcompare-example compares two median implementations and reports whether the difference between them is one this machine can actually resolve.
Package multiproc runs rtcompare comparisons in several processes and pools their results, so that the reported interval covers the scatter between processes and not only the noise within one.
 Package multiproc runs rtcompare comparisons in several processes and pools their results, so that the reported interval covers the scatter between processes and not only the noise within one.
Package workload generates realistic streams of insertions and deletions for benchmarking mutable data structures such as maps, sets, trees, tries, indexes, caches and queues with rtcompare.
 Package workload generates realistic streams of insertions and deletions for benchmarking mutable data structures such as maps, sets, trees, tries, indexes, caches and queues with rtcompare.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.