rtcompare

README

rtcompare

Statistically significant runtime comparison for codepaths in golang

rtcompare is a small, focused Go library for robust runtime comparisons and lightweight benchmarking. It provides utilities to collect timing samples, compare runtime distributions using bootstrap techniques, and helper primitives (deterministic PRNG, sample timing helpers, small statistics utilities). The project is intended as a practical alternative to the standard testing benchmarking harness when you want reproducible, distribution-aware comparisons and confidence estimates for relative speedups.

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

Features

• Collect per-run timing samples for two implementations and compare their runtime distributions.
• Compute confidence that implementation A is faster than B by at least a given relative speedup using bootstrap resampling.
• Deterministic DPRNG for reproducible input generation.
• Timing helpers (SampleTime, DiffTimeStamps) and small statistics utilities (mean, median, stddev).
• Small, dependency-light API suitable for integration into CI and micro-benchmarks.

Install

Use as a normal Go module dependency:

go get github.com/TomTonic/rtcompare

Import:

import "github.com/TomTonic/rtcompare"

Quickstart example

This example demonstrates how to collect timing samples for two median implementations and compare them (see cmd/rtcompare-example/main.go for a full runnable example).

import (
    "fmt"
    "math/rand"

    "github.com/TomTonic/rtcompare"
)

func example() {
    // generate some timing samples for two functions
    var timesA, timesB []float64
    for i := 0; i < 50; i++ {
        // set up inputs deterministically using DPRNG
        dprng := rtcompare.NewDPRNG()
        // measure repeatedly to reduce quantization noise
        t1 := rtcompare.SampleTime()
        for j := 0; j < 2000; j++ {
            // call candidate A
            // use dprng with constant runtime if necessary
        }
        t2 := rtcompare.SampleTime()
        timesA = append(timesA, float64(rtcompare.DiffTimeStamps(t1, t2))/2000.0)

        // ... same for candidate B ...
    }

    // Compare distributions using bootstrap (precision controls bootstrap repetitions)
    speedups := []float64{0.1, 0.2, 0.5, 1.0} // relative speedups to test
    results, err := rtcompare.CompareRuntimes(timesA, timesB, speedups, 10000)
    if err != nil {
        panic(err)
    }
    for _, r := range results {
        fmt.Printf("Speedup ≥ %.0f%% → Confidence %.2f%%\n", r.RelativeSpeedupSampleAvsSampleB*100, r.Confidence*100)
    }
}

Technical background

• Bootstrap-based inference: Instead of reporting a single sample mean or relying on the testing harness, rtcompare collects timing samples across independent runs and uses bootstrap resampling to estimate the confidence that one implementation is faster than another by at least a given relative margin. This yields more informative, distribution-aware results (confidence intervals and probability estimates).
• Deterministic input generation: DPRNG is provided to seed and generate reproducible inputs across runs, helping reduce input variance when comparing implementations.
• Noise reduction: The example shows how to warm up, use multiple inner iterations per timing sample to reduce quantization noise, and manually trigger GC cycles to reduce interference from allocations.

When to use rtcompare instead of testing.B

Use rtcompare when you want:

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

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

API highlights

• DPRNG — deterministic PRNG with Uint64 and Float64 helpers.
• SampleTime() / DiffTimeStamps() — helpers for high-resolution timing.
• CompareRuntimes(timesA, timesB, speedups, precision) — returns confidence estimates per requested relative speedup.
• QuickMedian — returns the median of a Float64 slice in expected O(n) time.

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

Contributing

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

License

MIT — see LICENSE file.

Documentation

Index

• Constants
• func DiffTimeStamps(t_earlier, t_later TimeStamp) int64
• func FloatsEqualWithTolerance(f1, f2, tolerancePercentage float64) bool
• func GetSampleTimePrecision() int64
• func Median(data []float64) float64
• func QuickMedian(xs []float64) float64
• func Statistics(data []float64) (mean, variance, stddev float64)
• type DPRNG
  • func NewDPRNG(seed ...uint64) DPRNG
  • func (thisState *DPRNG) Float64() float64
  • func (thisState *DPRNG) Uint64() uint64
• type RTcomparisonResult
  • func CompareRuntimes(sampleA, sampleB []float64, relativeSpeedupsToTest []float64, ...) (result []RTcomparisonResult, err error)
• type TimeStamp
  • func SampleTime() TimeStamp

Constants

const MinimumDataPoints uint64 = 11

Functions

func DiffTimeStamps

func DiffTimeStamps(t_earlier, t_later TimeStamp) int64

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

func FloatsEqualWithTolerance

func FloatsEqualWithTolerance(f1, f2, tolerancePercentage float64) bool

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

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

absTol = |v * tolerancePercentage / 100|

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

Important notes:

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

func GetSampleTimePrecision

func GetSampleTimePrecision() int64

Returns the precision of time measurements obtained via SampleTime() on the runtime system in nanoseconds. Should return 100ns on Windows systems, and typically between 20ns and 100ns on Linux and MacOS systems.

func Median

func Median(data []float64) float64

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

func QuickMedian

func QuickMedian(xs []float64) float64

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

func Statistics

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

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

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

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

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

Types

type DPRNG

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

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

func NewDPRNG

func NewDPRNG(seed ...uint64) DPRNG

NewDPRNG creates a new DPRNG instance. If no seed is provided, it initializes the state with a random non-zero value. If the provided seed is zero, it initializes the state with a random non-zero value. Otherwise, it uses the provided seed value.

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

func (thisState *DPRNG) Uint64() uint64

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

type RTcomparisonResult

type RTcomparisonResult struct {
	RelativeSpeedupSampleAvsSampleB float64
	Confidence                      float64
}

func CompareRuntimes

func CompareRuntimes(sampleA, sampleB []float64, relativeSpeedupsToTest []float64, precisionLevel uint64) (result []RTcomparisonResult, err error)

CompareRuntimes compares two samples of runtimes (in float64, e.g., milliseconds) and computes the confidence that sample A is faster than sample B by at least the specified relative speedups. The precisionLevel parameter controls the number of bootstrap repetitions (higher values yield more precise results of the statistical tests but take longer to compute). It returns a slice of RTcomparisonResult, each containing one of the given relative speedup and the corresponding confidence level calculated by the statistical test. If there are not enough data points in either sample, an error is returned.

type TimeStamp

type TimeStamp = time.Time

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

func SampleTime

func SampleTime() TimeStamp

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