rtcompare

package module
v0.8.1 Latest Latest
Warning

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

 Go to latest Published: Oct 9, 2026 License: MIT Imports: 17 Imported by: 1

README

rtcompare

Go Reference Linter Tests coverage Vulnerabilities

Benchmark two code paths and know whether the difference is real

rtcompare answers one question: is A really faster than B, and by how much? Benchmarking that well means dodging a long list of traps, and this library deals with each of them for you, statistical significance included. One call, rtcompare.Compare, returns a verdict together with the fine print that qualifies it. You do not need to know statistics to use it; when it warns you, HOWTO.md explains in plain language what the warning means and what to do.

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

What goes wrong when you compare two benchmarks, and what rtcompare does about it

The problem What rtcompare does
The clock is coarse. A single call to a fast function is below its resolution. Sizes the batches automatically so the clock contributes at most a chosen share of error. Differences far below the clock's resolution become measurable.
Whichever code runs second finds warm caches, or the other way round. Interleaves the two candidates, alternates who goes first, and warms both up together.
Setup and garbage collection leak into the numbers. Keeps setup outside the measured region and places GC deterministically.
Two runs of identical code differ. A "10% win" may be less than what the machine invents on its own. Measures that noise floor by running each candidate against itself, and tells you whether the result clears it.
The machine drifts during the run: thermal throttling, a busy neighbour, a suspended laptop. Tests every run for a trend and for suspension, and warns.
"A is 12% faster" from one run says nothing about how sure you can be. Bootstrap resampling gives an interval and the confidence that A beats B by at least the margin you care about, with the dependence between neighbouring samples taken into account.
Big or pointer-heavy data: where it happens to sit in memory moves the result by several points, and a new process gets a new layout. multiproc runs the comparison in several processes and pools them, so the interval covers that scatter too.
Trees, maps and other structures behave differently under insertions and deletions than under a fixed input. workload generates realistic, reproducible insert/delete streams and compares structures under them.

It is more machinery than testing.B, and that is the point: testing.B gives you a number and leaves the question of whether two numbers really differ to you. rtcompare is for when the answer matters, for example to decide whether a rewrite is worth merging, to gate a pull request in CI, or to defend a claim in a paper. It is not a replacement for profiling, and the standard testing package remains the right tool for a quick look at a single function.

Install

go get github.com/TomTonic/rtcompare

Quickstart

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 ns per operation (median)
B: 1262 ns per operation (median)
A needs 43.5% less time than B: B takes 1.77 times as long as A.
With 95% confidence the difference lies between 42.3% and 44.5% less time (B takes between 1.73 and 1.80 times as long as A).
Noise floor: 1.76%. Identical code measured against itself on this setup can look that different, so smaller differences mean nothing.
Neighbouring measurements are correlated (autocorrelation +0.34), so they were resampled in blocks of 5.

Verdict: RESOLVED. A is faster than B: the difference is real, as its interval excludes zero and it exceeds the noise floor.

Warnings:
  - candidate B drifted during the run: its measurements were 7.12% lower in the second half than in the first, so the machine did not hold still

Confidence that A needs at least 5% less time than B: 100.0%
Confidence that A needs at least 10% less time than B: 100.0%
Confidence that A needs at least 20% less time than B: 100.0%

HOWTO.md explains each line and what to do about a warning.

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. cmd/rtcompare-example shows the one call, and then the same measurements taken apart by hand.

Which call do I need?

What you compare Call Details
Two functions or code paths whose data fits in the CPU caches rtcompare.Compare The five-minute version
Data structures under insertions and deletions workload.Compare Benchmarking insertions and deletions
Anything whose data is larger than the caches, or full of pointers (trees, linked structures, maps of heap objects) multiproc.Main or multiproc.RunTest One process is one observation
Data structures under insertions and deletions, larger than the caches workload.Suite with multiproc.MainSuite or multiproc.RunTestSuite Benchmarking insertions and deletions, then One process is one observation

"Fits in the caches" means, as a rule of thumb, well below 16 MB of live data for both candidates together; Compare warns above that. The reason for the last two rows is explained in One process is one observation.

Where to go next

  • HOWTO.md: what to do, step by step, in plain language: how to write a Batch, what each warning means, and how to fix it.
  • API.md: everything the library exports, and when to reach for each part.
  • BACKGROUND.md: why it works the way it does, with the measurements behind each choice, and what a result cannot tell you (in particular: you measure the loop, not the isolated function).
  • pkg.go.dev: the reference.

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

Examples

Constants

View Source 
const (
	StageCalibrating = "calibrating"
	StageValidating  = "validating"
	StageMeasuring   = "measuring"
	StageResampling  = "resampling"
)

The stages a comparison reports through CompareOptions.Progress.

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; see Ties below.

Ties

Quantization does not only blur a measurement, it also collapses distinct measurements onto the same value, and equal values tie. 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%

One measurement is an integer count of clock ticks divided by the batch size, so its granularity is precision/InnerLoops, and only a longer batch makes ties rarer. 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%

Varying only Repeats at a fixed batch size of 20,000 gave tie rates of 2.2%, 2.3%, 2.8% and 1.8% for 21, 51, 101 and 201 repeats: no trend. HarnessValidation.TieRate reports what a setup actually produces.

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 the median is one of the measured values rather than the mean of the two in the middle.

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 = 11

MinimumDataPoints is the fewest measurements per candidate that CompareSamples, EstimateDifference and Collect accept. Below it a median has too few values to resample from for the bootstrap to say anything.

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 QuantizationGate = 1.5

QuantizationGate is how many clock ticks per batch a difference has to exceed, as a share of the batch, before Compare counts it as resolved.

A measured batch is a whole number of clock ticks, so the ratio of a pair of batches lies on a lattice one tick apart, and so does the median of those ratios. When the batches are short enough for most pairs to tie, the median sits on 0 or on one tick, and the bootstrap interval around a value on a lattice collapses to lattice points: identical code was reported as one tick apart, with an interval excluding zero, in 4 of 30 comparisons on a CI runner. A difference of one tick can be rounding alone; one and a half ticks cannot.

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 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.

Parameters: a and b are the candidates, see Candidate; opt configures the batch size, the order, the warm-up and garbage collection, see CollectOptions. Its zero value is usable.

It returns the two series in the order they were measured, sample i of each taken next to the other, which makes them pairs for EstimateDifference and ConfidencesFor with EstimateOptions.Paired. The errors are listed at the end.

Use it when Compare does more than needed, or to hand the samples to an analysis of your own.

What Collect controls

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.

Attenuation

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.

The noise floor

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.

What ran before

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.

Errors

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 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 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, which takes a few milliseconds, and cached for the lifetime of the process.

Use it to judge how long a batch has to run; CalibrateInnerLoops does, and reports it as Calibration.ClockPrecision.

Background

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 NaN, since an empty set has no median. 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 mean of the two middle elements. Returning either one of them instead, as this function used to, biases the median of an even count towards that side. Time complexity: O(n log n). Space complexity: O(n) due to the copy required for sorting.

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), on the multiples of 2^-24: the 24 random bits of a float32's significand, so no precision is left unused. It never returns 1.0, -0.0, NaN or Inf. For a different range, scale and shift the result. Use CPRNG.Float64 if you need more resolution.

func (*CPRNG) Float64 added in v0.4.0 

func (c *CPRNG) Float64() float64

Float64 returns a uniformly distributed float64 in [0.0, 1.0), on the multiples of 2^-53: the 53 random bits of a float64's significand, so no precision is left unused. It never returns 1.0, -0.0, NaN or Inf. For a different range, scale and shift the result.

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) Shuffle added in v0.8.0 

func (c *CPRNG) Shuffle(n int, swap func(i, j int))

Shuffle puts n elements in a random order by calling swap(i, j) for the pairs a Fisher-Yates shuffle exchanges, like math/rand's Shuffle and DPRNG.Shuffle. n is at most 2^32; zero, one or a negative n does nothing. The order is unpredictable and not reproducible; use a DPRNG for a shuffle that has to repeat.

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.

Parameters: c is the candidate; opt sets the error bound, the largest batch to try and the garbage collection to mirror, see CalibrationOptions.

It returns the Calibration, with the batch size in InnerLoops, or an error for a nil Batch, an invalid bound, or a batch that never grew long enough, which usually means the Batch function ignores its n.

Use it to fix a batch size once and reuse it; Collect, ValidatePair and Compare call it when CollectOptions.InnerLoops is zero.

How it works

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 also decides how often measurements tie, which lifts the confidence
	// at threshold zero. The default suits the magnitude of a difference; for
	// "is A faster at all", tighten it tenfold and pay ten times the batch
	// length. See DefaultMaxQuantizationError for the measurements.
	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

	// Progress, when set, is called as the comparison moves through its
	// stages, and after each A/A validation run, so that a long comparison
	// can show how far it has got. It is called from the comparing goroutine,
	// between batches and never inside a measured one, so a slow callback
	// delays the comparison but does not distort it. See [Progress].
	Progress func(Progress)

	// MaxDuration, when set, bounds the time the validation may take, which
	// is the dominant cost of a comparison: once half of MaxDuration has
	// passed, the validation starts no further A/A runs, provided at least
	// ten have run (or all requested, if fewer). The measurement itself always
	// runs in full, so a comparison can still take longer than MaxDuration;
	// cancel its context through [CompareContext] for a hard limit. A
	// validation cut short says so in Report.Warnings, and its figures rest
	// on fewer runs; see [DefaultValidationRuns] for what that costs.
	MaxDuration time.Duration

	// Seed makes the resampling reproducible: the interval, the confidences
	// and the validations' bootstraps are all drawn from it. Zero draws a
	// random seed. Either way Report.Seed records the seed used, so that a
	// report's figures can be recomputed from its samples; see
	// [EstimateDifference]. It does not make the measurements themselves
	// repeatable, which no seed can.
	Seed uint64
}

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

type Confidences added in v0.8.0 

type Confidences []ThresholdConfidence

Confidences holds one ThresholdConfidence per distinct threshold, in ascending order of threshold, as CompareSamples, BootstrapConfidence, BlockBootstrapConfidence and Report.Confidence return them.

func BlockBootstrapConfidence added in v0.6.0 

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

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.

Parameters are those of BootstrapConfidence, and blockLength is the length of the blocks, zero or negative selecting AutoBlockLength. It returns the same as BootstrapConfidence.

Use it when the lag-1 autocorrelation of the measurements exceeds about AutocorrelationThreshold, as ValidateHarness reports it; Compare switches by itself. Below that, blocks cost variance and repair nothing.

Background

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.

Block length

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) Confidences

BootstrapConfidence is CompareSamples with a seed and without an error channel: for each threshold, the share of bootstrap replicates in which 1 - median(A*)/median(B*) reached it, A and B resampled independently.

Parameters: A and B are the measurements; relativeGains are the thresholds, as for CompareSamples; resamples is the number of replicates; prngSeed makes the replicates reproducible, zero drawing them from cryptographic randomness instead.

It returns one entry per distinct threshold in ascending order. With resamples zero every confidence is NaN, and NaN thresholds are left out, since there is no error to report them with; CompareSamples rejects them.

Use CompareSamples unless the seed matters, and ConfidencesFor for measurements taken in pairs.

Edge cases

A replicate with an empty sample has an undefined difference and meets no threshold. A median(B*) of zero with a non-zero median(A*) gives an infinite difference, the honest answer and a sign that a batch fitted inside one clock tick. Equal medians, zeros and like infinities included, give exactly zero. Infinite thresholds are kept: -Inf always yields 1 and +Inf always 0.

Choosing resamples

The bootstrap literature (Efron & Tibshirani; Davison & Hinkley) recommends at least 1,000 resamples for standard errors and 5,000 to 10,000 for percentile intervals and tail probabilities. The Monte Carlo error of a confidence shrinks as 1/sqrt(resamples), so more resamples make the same answer more precise, not more correct.

func CompareSamples added in v0.3.0 

func CompareSamples(measurementsA, measurementsB []float64, relativeGains []float64, resamples uint64) (Confidences, error)

CompareSamples estimates, for each threshold, the confidence that the measurements in A are smaller than those in B by at least that relative difference, resampling A and B independently of each other.

Parameters: measurementsA and measurementsB are two samples of the same metric, smaller being better, such as runtimes or memory, each with at least MinimumDataPoints values; for a larger-is-better metric such as throughput, pass reciprocals. relativeGains are the thresholds: 0.05 asks "is A at least 5% smaller than B", -0.05 "is A at most 5% larger", and an empty list asks about 0. resamples is the number of bootstrap replicates, zero selecting DefaultResamples.

It returns one entry per distinct threshold, in ascending order, each the share of replicates in which 1 - median(A*)/median(B*) reached it, or an error for too few values or a NaN threshold.

Use it for measurements that were not taken in pairs. For those that were, such as the samples of Collect, use ConfidencesFor with EstimateOptions.Paired, as Compare does. At a threshold of zero, ties count for A; ask for a small positive threshold if you mean strictly faster.

Thresholds of zero and below

Every threshold t is evaluated as delta >= t, so at t = 0 the question is "is A at least as small as B", not "is A smaller", and 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. Shrinking the quantization helps; see CollectOptions.MaxQuantizationError and the tie rate reported by ValidateHarness.

A negative threshold is a tolerated slowdown: t = -0.05 asks whether A is within 5% of B, and a replicate with delta = -0.03 meets it.

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.

Details

Passing the same threshold several times yields one entry for it; the caller's slice is left untouched. NaN is rejected with an error naming its index, since delta >= NaN is false for every delta and the resulting zero would look like a genuine answer; watch for this when passing F2T results, since F2T signals invalid input with NaN. +Inf and -Inf are accepted and consistent: -Inf always yields confidence 1 and +Inf always 0.

func ConfidencesFor added in v0.8.0 

func ConfidencesFor(A, B []float64, thresholds []float64, opt EstimateOptions) (Confidences, error)

ConfidencesFor reports, for each threshold, the confidence that A beats B by at least that relative difference, drawn exactly as EstimateDifference draws its interval under the same options: the share of the very replicates the interval is read from.

Parameters: A and B are the measurements; thresholds are relative differences as for CompareSamples, where an empty list asks about zero; opt is as for EstimateDifference, and Level is not used.

It returns one entry per distinct threshold in ascending order, or an error for too few measurements, pairs of unequal length, or a NaN threshold.

Use it for paired measurements, such as a Report's, where CompareSamples and BlockBootstrapConfidence resample A and B independently. A Report's confidences are recomputed with 

rtcompare.ConfidencesFor(r.SamplesA, r.SamplesB, thresholds, rtcompare.EstimateOptions{
	Resamples: r.Estimate.Resamples, BlockLength: r.BlockLength, Seed: r.Seed, Paired: true})

func (Confidences) At added in v0.8.0 

func (c Confidences) At(threshold float64) (confidence float64, ok bool)

At returns the confidence for the given threshold, and whether it is there. Thresholds match when they differ by no more than a relative 1e-9, so that a threshold computed the way it was passed in, such as F2T(1.1) or 0.1+0.05, finds its entry.

type DPRNG 

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

DPRNG is a deterministic pseudo-random number generator, xorshift64* with Vigna's multiplier (see https://en.wikipedia.org/wiki/Xorshift#xorshift*).

The same seed always gives the same sequence, which is what reproducible benchmark inputs, build orders and bootstrap replicates need. Its period is 2^64-1, every call takes the same time, and it occupies 8 bytes. It is not cryptographically secure, and an instance must not be shared between goroutines without synchronisation; give each goroutine its own.

Create one with NewDPRNG. The zero value is not usable: its state is zero, which xorshift never leaves.

func NewDPRNG added in v0.1.1 

func NewDPRNG(seed uint64) DPRNG

NewDPRNG returns a generator seeded with seed, or with a random seed if seed is zero.

Parameters: seed selects the sequence: the same non-zero seed always gives the same one. Zero asks for a random seed instead, drawn from math/rand/v2, so that NewDPRNG(0) differs from run to run. If you compute the seed and it may come out zero while you need reproducibility, pass seed|1 or another non-zero mapping. The seed is spread over all 64 bits with one round of splitmix64 before use, so that small or consecutive seeds, such as process indices, start unrelated sequences rather than neighbouring states of the same one.

Use it wherever a sequence has to be repeatable, or, with zero, wherever a different sequence per run is wanted without ceremony.

Example

NewDPRNG gives every seed its own fixed sequence, so inputs generated from it are the same in every run. 

package main

import (
	"fmt"

	"github.com/TomTonic/rtcompare"
)

func main() {
	a, b := rtcompare.NewDPRNG(42), rtcompare.NewDPRNG(42)
	same := true
	for range 1000 {
		if a.Uint32N(100) != b.Uint32N(100) {
			same = false
		}
	}
	fmt.Println("same sequence from the same seed:", same)
}

Output:
same sequence from the same seed: true

func (*DPRNG) Float32 added in v0.8.0 

func (thisState *DPRNG) Float32() float32

Float32 returns a pseudo-random float32 in [0.0, 1.0), uniformly distributed on the multiples of 2^-24, the full precision of a float32. It never returns 1.0.

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) Int8 added in v0.8.0 

func (thisState *DPRNG) Int8() int8

Int8 returns a pseudo-random int8; see DPRNG.Uint8.

func (*DPRNG) Int16 added in v0.8.0 

func (thisState *DPRNG) Int16() int16

Int16 returns a pseudo-random int16; see DPRNG.Uint16.

func (*DPRNG) Int32 added in v0.8.0 

func (thisState *DPRNG) Int32() int32

Int32 returns a pseudo-random int32; see DPRNG.Uint32.

func (*DPRNG) Int64 added in v0.8.0 

func (thisState *DPRNG) Int64() int64

Int64 returns a pseudo-random int64, uniformly distributed over its whole range. It advances the sequence by one step, like DPRNG.Uint64.

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 rtcompare.Combine. 

rng := 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.

Example

Shuffle puts fixtures in a seeded order, e.g. the order in which a benchmark builds its data structures in each process. 

package main

import (
	"fmt"

	"github.com/TomTonic/rtcompare"
)

func main() {
	rng := rtcompare.NewDPRNG(7)
	order := []string{"A", "B", "C", "D"}
	rng.Shuffle(len(order), func(i, j int) { order[i], order[j] = order[j], order[i] })
	again := rtcompare.NewDPRNG(7)
	repeat := []string{"A", "B", "C", "D"}
	again.Shuffle(len(repeat), func(i, j int) { repeat[i], repeat[j] = repeat[j], repeat[i] })
	fmt.Println("reproducible:", fmt.Sprint(order) == fmt.Sprint(repeat))
}

Output:
reproducible: true

func (*DPRNG) Uint8 added in v0.8.0 

func (thisState *DPRNG) Uint8() uint8

Uint8 returns a pseudo-random uint8, taken from the high bits of one step of the sequence.

func (*DPRNG) Uint16 added in v0.8.0 

func (thisState *DPRNG) Uint16() uint16

Uint16 returns a pseudo-random uint16, taken from the high bits of one step of the sequence.

func (*DPRNG) Uint32 added in v0.8.0 

func (thisState *DPRNG) Uint32() uint32

Uint32 returns a pseudo-random uint32, taken from the high bits of one step of the sequence, which are the best mixed ones of xorshift64*.

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

Uint64 returns the next pseudo-random number in the sequence. It takes the same time on every call and is small enough to be inlined.

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.

Parameters: samples is the series in the order it was measured, at least four finite values; below about twenty, a real drift easily goes unnoticed.

It returns a DriftReport with the trend's significance and size, which are to be read separately, or an error for fewer than four samples or a non-finite one.

Use it on any series the bootstrap is about to treat as an unordered bag; Compare runs it on both series and on their ratio.

Background

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.

Power is poor below roughly twenty samples, 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), or for paired measurements, as [Compare] takes
	// them, 1 - median(A[i]/B[i]); see EstimateOptions.Paired. 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%".

Delta is 1 - A/B, how much less time A needs relative to B, and that measure is not symmetric: when B takes twice as long as A, Delta is +50%, but with the roles swapped it is -100%. Read it as a share of B's time, or use Estimate.Ratio for the factor between the two, which String prints too.

func EstimateDifference added in v0.6.0 

func EstimateDifference(A, B []float64, opt EstimateOptions) (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.

Parameters: A and B are the measurements, each with at least MinimumDataPoints values and, with opt.Paired, of equal length; opt sets the level, resamples, block length, seed and pairing, see EstimateOptions.

It returns the Estimate, or an error for too few measurements, pairs of unequal length, or a level not strictly between zero and one.

Use it when the question is how large a difference is, rather than whether it clears a given threshold, which ConfidencesFor answers. A Report from Compare can be recomputed exactly from its own samples: 

e, err := rtcompare.EstimateDifference(r.SamplesA, r.SamplesB, rtcompare.EstimateOptions{
	Level: r.Estimate.Level, Resamples: r.Estimate.Resamples, BlockLength: r.BlockLength,
	Seed: r.Seed, Paired: true})

The interval 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.

Coverage

The point estimate is computed on the measurements directly. The interval is a percentile bootstrap: resample, recompute the difference for each replicate, and take the empirical quantiles at (1-level)/2 and (1+level)/2, interpolating between neighbouring replicates.

Coverage was measured rather than assumed, by simulating samples drawn from distributions whose true difference is known and counting how often the unpaired 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. 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. For the paired interval, see EstimateOptions.Paired.

Example

EstimateDifference puts an interval around the difference between two sets of measurements. A seed makes the interval reproducible, and Paired says that A[i] and B[i] were measured together. 

package main

import (
	"fmt"

	"github.com/TomTonic/rtcompare"
)

func main() {
	a := []float64{100, 102, 99, 101, 100, 103, 98, 100, 101, 99, 102}
	b := []float64{125, 128, 124, 126, 125, 129, 122, 125, 127, 124, 127}
	e, err := rtcompare.EstimateDifference(a, b, rtcompare.EstimateOptions{Seed: 1, Paired: true})
	if err != nil {
		fmt.Println(err)
		return
	}
	ratio, _, _ := e.Ratio()
	fmt.Printf("A needs %.0f%% less time than B, B takes %.2f× as long\n", e.Delta*100, ratio)
	fmt.Println("difference established:", e.Excludes(0))
}

Output:
A needs 20% less time than B, B takes 1.25× as long
difference established: true

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) Ratio added in v0.8.0 

func (e Estimate) Ratio() (ratio, low, high float64)

Ratio returns how many times as long B takes as A, median(B)/median(A), with the interval's bounds carried over: 1/(1-Delta), 1/(1-Low) and 1/(1-High). A ratio of 2 means B takes twice as long as A, and 0.5 that it takes half as long.

Use it to report a difference in the form that reads the same whichever candidate is called A: swapping the roles turns 2 into 0.5, where Delta turns +50% into -100%.

func (Estimate) String added in v0.6.0 

func (e Estimate) String() string

String renders the estimate as one line: Delta in percent with its interval, then the ratio B/A with its interval.

type EstimateOptions added in v0.8.0 

type EstimateOptions struct {
	// Level is the interval's coverage level, strictly between zero and one.
	// Zero selects [DefaultConfidenceLevel].
	Level float64

	// Resamples is the number of bootstrap replicates. Zero selects
	// [DefaultResamples].
	Resamples uint64

	// BlockLength resamples contiguous blocks of this many measurements, for
	// measurements correlated with their neighbours; see
	// [BlockBootstrapConfidence]. Zero and one select the ordinary bootstrap.
	BlockLength int

	// Seed makes the resampling reproducible: the same seed and inputs give
	// the same Estimate. Zero selects cryptographic randomness instead.
	// Replicates are drawn exactly as [ConfidencesFor] draws them for the same
	// options, and without Paired as [BlockBootstrapConfidence] does, so they
	// agree replicate for replicate.
	Seed uint64

	// Paired says that A[i] and B[i] were measured together, as the samples
	// [Collect] returns are: in the same round, next to each other. The
	// difference is then 1 - median(A[i]/B[i]) over the pairs, and whole
	// pairs are resampled, so that a disturbance that hit both members of a
	// pair alike, such as a change of clock speed or a busy neighbour,
	// cancels in their ratio instead of widening the interval. A and B must
	// have the same length.
	//
	// Measured on memory-bound candidates, paired intervals were 25 to 38%
	// narrower than unpaired ones; simulated with disturbances common to both
	// members of a pair, the unpaired interval covered at 99 to 100% where
	// 95% was asked for, at up to five times the width, while the paired one
	// held 94 to 95% at a width the common disturbance did not affect, also
	// with one-sided outliers in up to 30% of the batches (issue #122).
	// [Compare] measures in pairs and uses it.
	Paired bool
}

EstimateOptions configures EstimateDifference. The zero value is usable and selects the documented defaults.

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.
	//
	// A replicate whose difference is exactly zero counts half for each side,
	// rather than wholly for A as the plain confidence at threshold zero
	// would, which would centre above 0.5 even on a perfect setup. See
	// TieRate.
	MeanConfidence   float64
	MedianConfidence float64

	// TieRate is the share of bootstrap replicates whose difference came out
	// exactly zero, taken as the median across the runs.
	//
	// Timing measurements are quantized, so identical values are common, and
	// so are pairs of batches that took exactly the same number of ticks.
	// Since the confidence at threshold zero asks whether delta >= 0, every
	// tie counts as "A at least as fast", which lifts it by half the tie rate;
	// MeanConfidence and MedianConfidence split the ties instead.
	//
	// A high tie rate means the measurement is coarse relative to the
	// differences being asked about. The fix is longer batches, through
	// CollectOptions.MaxQuantizationError, and only longer batches: more
	// Repeats draw more values from the same coarse set. See
	// [DefaultMaxQuantizationError] for the measurements.
	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.

Parameters: c is the candidate, measured against itself; opt holds the measurement options the real comparison will use and the number of A/A runs, see ValidationOptions.

It returns the validation, or an error for a nil Batch, invalid options or a failed calibration.

Use it to find the noise floor a result has to clear. When two candidates are about to be compared, validate them together with ValidatePair instead of calling this twice: a candidate validated on its own leaves the caches full of its own data, and the one validated last starts the comparison warm. Compare does all of this; the pieces look like this: 

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)
e, err := rtcompare.EstimateDifference(sa, sb, rtcompare.EstimateOptions{Paired: true})
if math.Abs(e.Delta) <= floor {
    // The difference is within what this machine invents on its own.
}

Background

Any difference an A/A experiment 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. Bootstrap resampling cannot supply it: it quantifies how much the estimate would move if the same measurements were drawn again, cannot see a bias that affected every measurement 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.

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.

Cost

Runs times one Collect plus one calibration, and one bootstrap per run. The resampling dominates: on a candidate calibrated to 48 microsecond batches, the whole validation took 0.76 s at ten runs and 3.03 s at forty when each run still resampled twice, of which the measurement itself was under a tenth. On top of that comes one warm-up of CollectOptions.WarmupDuration before the first run only; the later runs warm up by count alone, since the candidate has been running all along.

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. For a run sized from its first stage, see
	// FirstStage, the interval is Stein's instead.
	Low, High float64

	// FirstStage is zero for [Combine]. For [CombineStaged] it is the number
	// of processes whose scatter decided how many processes the run needed,
	// and the interval is Stein's two-stage interval: the half-width is the t
	// quantile at FirstStage-1 degrees of freedom times the standard deviation
	// of the first stage's deltas, over the square root of Processes.
	FirstStage int

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

	// SpreadBetween is the sample 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

	// Bias is the systematic error the A/A validations found: the mean over the
	// processes of each one's mean signed A/A difference, as a fraction. It is
	// what identical code reported in every process alike, which is the one
	// harness error that pooling cannot average out. Zero when the reports
	// carry no A/A differences.
	Bias float64

	// NoiseFloor is what Delta has to clear for Resolved.
	//
	// When the reports carry their A/A differences (ValidationA.Deltas and
	// ValidationB.Deltas, as Compare and multiproc provide), it is |Bias| plus
	// the t quantile at Level times Bias's standard error across processes: an
	// upper bound on the systematic harness error. That is the right bar for a
	// pooled result, and a lower one than a single process's floor. A single
	// Report's floor is a high quantile of the A/A differences, because its
	// interval covers only the noise within its process; the pooled interval
	// already covers everything that differs between processes, the harness's
	// random error included, so only the part that repeats in every process
	// is left for the floor to catch. Gating the pooled Delta with a single
	// process's floor instead kept small real effects from ever resolving,
	// however many processes ran (issue #121).
	//
	// When any validated report lacks its A/A differences, NoiseFloor falls
	// back to the median of the processes' noise floors, which is
	// conservative. It is zero when no process was validated.
	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)
Example

Combine pools the reports of one comparison run in several processes, each process counting as one observation. Here five processes agree on about 12% but scatter far more than their own intervals claim, which the pooled result reports as inflation. 

package main

import (
	"fmt"

	"github.com/TomTonic/rtcompare"
)

func main() {
	var reports []rtcompare.Report
	for _, d := range []float64{0.10, 0.14, 0.12, 0.11, 0.13} {
		reports = append(reports, rtcompare.Report{
			Estimate: rtcompare.Estimate{Delta: d, Low: d - 0.002, High: d + 0.002, Level: 0.95},
		})
	}
	p, err := rtcompare.Combine(reports, 0)
	if err != nil {
		fmt.Println(err)
		return
	}
	fmt.Printf("pooled %+.1f%% [%+.1f%%, %+.1f%%]\n", p.Delta*100, p.Low*100, p.High*100)
	fmt.Printf("processes scatter %.0f times as widely as one process's interval says\n", p.Inflation)
}

Output:
pooled +12.0% [+10.0%, +14.0%]
processes scatter 15 times as widely as one process's interval says

func CombineStaged added in v0.8.0 

func CombineStaged(reports []Report, firstStage int, level float64) (Pooled, error)

CombineStaged is Combine for a run whose number of processes was fixed from its first stage by Pooled.ProcessesFor, and reports Stein's two-stage interval, which covers at its level even though the run's size depended on its first processes.

Parameters: reports holds one Report per process in the order the processes ran, the first stage first; firstStage is how many of them made up the first stage, at least three and at most len(reports); level is as for Combine.

It returns the same result as Combine, except for Low, High and FirstStage: the half-width is t*s/sqrt(k) with s the standard deviation of the first stage's deltas and t the t quantile at firstStage-1 degrees of freedom, while Delta is still the mean over all k processes. An error is returned for a firstStage out of range and for the reasons Combine gives.

Use it after sizing a run with ProcessesFor; the multiproc package does. Pooling such a run with Combine instead would let the size of the run depend on the scatter that the interval is then built from, which is the optional stopping the two stages exist to avoid. In simulation, with the multiproc defaults, CombineStaged covered at 94.6 to 95.2% at a nominal 95%.

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|.

func (Pooled) ProcessesFor added in v0.8.0 

func (p Pooled) ProcessesFor(abs, rel float64) int

ProcessesFor returns how many processes the comparison needs in all for the pooled interval to have a half-width of at most abs, or at most rel times |Delta|, judged from this result as the first stage of a run.

Parameters: abs and rel are the precision asked for, as for Pooled.Precise. Call it on the result of Combine over the first processes of a run.

It returns at least Processes, and math.MaxInt when neither bound can be met because both are zero.

Use it to size a run once, from its first stage, and then run exactly that many processes and pool them with CombineStaged. That is Stein's two-stage procedure, and it is what keeps the interval honest: a run that instead checks the interval after every process and stops as soon as it is narrow enough stops preferentially when the scatter happened to come out low, and its 95% interval covered only 92 to 94% in simulation (issue #119). The number is ((t*s)/h)², rounded up, with s the scatter between the processes so far, t the t quantile at Level with Processes-1 degrees of freedom, and h the larger of abs and rel*|Delta|. The multiproc package does all of this.

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 Progress added in v0.8.0 

type Progress struct {
	// Stage is the step the comparison is in: [StageCalibrating],
	// [StageValidating], [StageMeasuring] or [StageResampling], in that order.
	Stage string

	// Done and Total count the stage's steps. For StageValidating they are the
	// A/A runs done and requested; the other stages are one step each and are
	// reported once, as they begin, with Done 0 and Total 1.
	Done, Total int
}

Progress tells a CompareOptions.Progress callback how far a comparison has got.

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,
	// from the ratios of the pairs of batches measured next to each other.
	// 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 holds, for each requested threshold in ascending order, the
	// confidence that it is met. It is nil when CompareOptions.Thresholds was
	// empty.
	Confidence Confidences

	// 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

	// Seed is the seed the resampling was drawn from, CompareOptions.Seed or
	// the random one drawn in its place. With SamplesA, SamplesB and
	// BlockLength it reproduces Estimate through [EstimateDifference] and
	// Confidence through [ConfidencesFor] exactly, both with Paired set.
	Seed uint64

	// 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

	// Quantization is the relative size of one clock tick in a batch of the
	// faster candidate: the step by which measured differences move. A
	// difference below [QuantizationGate] such steps does not resolve, since
	// rounding alone can produce it; lengthen the batches through
	// CollectOptions.MaxQuantizationError to see below it.
	Quantization float64

	// Resolved is the short answer: the difference is both statistically
	// distinguishable from zero and larger than what this setup invents on its
	// own, and than the clock can round into it. 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
	// contains filtered or unexported fields
}

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. The difference is taken from the ratios of the pairs of batches measured next to each other, so that a disturbance that hit both members of a pair cancels; see EstimateOptions.Paired.

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.

Example

Compare measures two candidates and says whether one is genuinely faster. Here B does twice A's work. Printing the whole report shows the difference, its interval, the noise floor and any warnings; this example prints only the verdict, which is the same on every machine. 

package main

import (
	"fmt"
	"time"

	"github.com/TomTonic/rtcompare"
)

// exampleSink keeps the candidates' work observable.
var exampleSink uint64

// work returns a candidate that performs cost units of arithmetic per
// operation, with the loop in the batch, as rtcompare expects.
func work(name string, cost uint64) rtcompare.Candidate {
	return rtcompare.Candidate{Name: name, Batch: func(n uint64) {
		var acc uint64
		for i := range n * cost {
			acc = acc*31 + i
		}
		exampleSink ^= acc
	}}
}

func main() {
	report, err := rtcompare.Compare(work("single", 1), work("double", 2), rtcompare.CompareOptions{
		// Shortened for the example; the defaults validate more carefully.
		Collect:        rtcompare.CollectOptions{WarmupDuration: 10 * time.Millisecond},
		ValidationRuns: 10,
	})
	if err != nil {
		fmt.Println(err)
		return
	}
	fmt.Println("resolved:", report.Resolved)
	fmt.Println("A is faster:", report.Estimate.Delta > 0)
}

Output:
resolved: true
A is faster: true

func CompareContext added in v0.8.0 

func CompareContext(ctx context.Context, a, b Candidate, opt CompareOptions) (Report, error)

CompareContext is Compare, stopping as soon as ctx is done.

Parameters: ctx bounds the comparison; a, b and opt are those of Compare.

It checks ctx between batches, never inside a measured one, so it stops within one batch of ctx being done, and returns an error wrapping ctx's error. Use it to give a comparison a hard time limit or to cancel it from elsewhere, e.g. from a signal handler: 

ctx, cancel := context.WithTimeout(context.Background(), time.Minute)
defer cancel()
report, err := rtcompare.CompareContext(ctx, a, b, rtcompare.CompareOptions{})
if errors.Is(err, context.DeadlineExceeded) { ... }

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 ThresholdConfidence added in v0.8.0 

type ThresholdConfidence struct {
	Threshold  float64 `json:"threshold"`
	Confidence float64 `json:"confidence"`
}

ThresholdConfidence is the confidence that A beats B by at least Threshold, a relative difference as in Estimate.Delta: the share of bootstrap replicates in which 1 - median(A)/median(B) >= Threshold.

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

	// Seed makes the bootstraps of the A/A runs reproducible; each run of each
	// candidate draws from its own seed derived from this one. Zero selects
	// cryptographic randomness. [Compare] derives it from its own seed.
	Seed uint64
}

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 ways of sorting a slice, the generic slices.Sort and sort.Slice with a comparison closure, and reports whether the difference between them is one this machine can actually resolve.
 Command rtcompare-example compares two ways of sorting a slice, the generic slices.Sort and sort.Slice with a comparison closure, 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.