benchmath/sample.go

// Copyright 2022 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package benchmath provides tools for computing statistics over
// distributions of benchmark measurements.
//
// This package is opinionated. For example, it doesn't provide
// specific statistical tests. Instead, callers state distributional
// assumptions and this package chooses appropriate tests.
//
// All analysis results contain a list of warnings, captured as an
// []error value. These aren't errors that prevent analysis, but
// should be presented to the user along with analysis results.
package benchmath

import (
	"fmt"
	"math"
	"sort"

	"github.com/aclements/go-moremath/mathx"
	"github.com/aclements/go-moremath/stats"
)

// A Sample is a set of repeated measurements of a given benchmark.
type Sample struct {
	// Values are the measured values, in ascending order.
	Values []float64

	// Thresholds stores the statistical thresholds used by tests
	// on this sample.
	Thresholds *Thresholds

	// Warnings is a list of warnings about this sample that
	// should be reported to the user.
	Warnings []error
}

// NewSample constructs a Sample from a set of measurements.
func NewSample(values []float64, t *Thresholds) *Sample {
	// TODO: Analyze stationarity and put results in Warnings.
	// Consider Augmented Dickey–Fuller (based on Maricq et al.)

	// Sort values for fast order statistics.
	sort.Float64s(values)
	return &Sample{values, t, nil}
}

func (s *Sample) sample() stats.Sample {
	return stats.Sample{Xs: s.Values, Sorted: true}
}

// A Thresholds configures various thresholds used by statistical tests.
//
// This should be initialized to DefaultThresholds because it may be
// extended with other fields in the future.
type Thresholds struct {
	// CompareAlpha is the alpha level below which
	// Assumption.Compare rejects the null hypothesis that two
	// samples come from the same distribution.
	//
	// This is typically 0.05.
	CompareAlpha float64
}

// Note: Thresholds exists so we can extend it in the future with
// things like the stationarity and normality test thresholds without
// having to add function arguments in the future.

// DefaultThresholds contains a reasonable set of defaults for Thresholds.
var DefaultThresholds = Thresholds{
	CompareAlpha: 0.05,
}

// An Assumption indicates a distributional assumption about a sample.
type Assumption interface {
	// SummaryLabel returns the string name for the summary
	// statistic under this assumption. For example, "median" or
	// "mean".
	SummaryLabel() string

	// Summary returns a summary statistic and its confidence
	// interval at the given confidence level for Sample s.
	//
	// Confidence is given in the range [0,1], e.g., 0.95 for 95%
	// confidence.
	Summary(s *Sample, confidence float64) Summary

	// Compare tests whether s1 and s2 come from the same
	// distribution.
	Compare(s1, s2 *Sample) Comparison
}

// A Summary summarizes a Sample.
type Summary struct {
	// Center is some measure of the central tendency of a sample.
	Center float64

	// Lo and Hi give the bounds of the confidence interval around
	// Center.
	Lo, Hi float64

	// Confidence is the actual confidence level of the confidence
	// interval given by Lo, Hi. It will be >= the requested
	// confidence level.
	Confidence float64

	// Warnings is a list of warnings about this summary or its
	// confidence interval.
	Warnings []error
}

// PctRangeString returns a string representation of the range of this
// Summary's confidence interval as a percentage.
func (s Summary) PctRangeString() string {
	if math.IsInf(s.Lo, 0) || math.IsInf(s.Hi, 0) {
		return "∞"
	}

	// If the signs of the bounds differ from the center, we can't
	// render it as a percent.
	var csign = mathx.Sign(s.Center)
	if csign != mathx.Sign(s.Lo) || csign != mathx.Sign(s.Hi) {
		return "?"
	}

	// If center is 0, avoid dividing by zero. But we can only get
	// here if lo and hi are also 0, in which case is seems
	// reasonable to call this 0%.
	if s.Center == 0 {
		return "0%"
	}

	// Phew. Compute the range percent.
	v := math.Max(s.Hi/s.Center-1, 1-s.Lo/s.Center)
	return fmt.Sprintf("%.0f%%", 100*v)
}

// A Comparison is the result of comparing two samples to test if they
// come from the same distribution.
type Comparison struct {
	// P is the p-value of the null hypothesis that two samples
	// come from the same distribution. If P is less than a
	// threshold alpha (typically 0.05), then we reject the null
	// hypothesis.
	//
	// P can be 0, which indicates this is an exact result.
	P float64

	// N1 and N2 are the sizes of the two samples.
	N1, N2 int

	// Alpha is the alpha threshold for this test. If P < Alpha,
	// we reject the null hypothesis that the two samples come
	// from the same distribution.
	Alpha float64

	// Warnings is a list of warnings about this comparison
	// result.
	Warnings []error
}

// String summarizes the comparison. The general form of this string
// is "p=0.PPP n=N1+N2" but can be shortened.
func (c Comparison) String() string {
	var s string
	if c.P != 0 {
		s = fmt.Sprintf("p=%0.3f ", c.P)
	}
	if c.N1 == c.N2 {
		// Slightly shorter form for a common case.
		return s + fmt.Sprintf("n=%d", c.N1)
	}
	return s + fmt.Sprintf("n=%d+%d", c.N1, c.N2)
}

// FormatDelta formats the difference in the centers of two distributions.
// The old and new values must be the center summaries of the two
// compared samples. If the Comparison accepts the null hypothesis
// that the samples come from the same distribution, FormatDelta
// returns "~" to indicate there's no meaningful difference.
// Otherwise, it returns the percent difference between the centers.
func (c Comparison) FormatDelta(old, new float64) string {
	if c.P > c.Alpha {
		return "~"
	}
	if old == new {
		return "0.00%"
	}
	if old == 0 {
		return "?"
	}
	pct := ((new / old) - 1.0) * 100.0
	return fmt.Sprintf("%+.2f%%", pct)
}