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