blob: 74f674a0f442b80a9c12b0218e1f0e270bb3eff5 [file] [log] [blame]
// 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 benchseries
import (
"fmt"
"math"
"math/rand"
"os"
"regexp"
"sort"
"time"
"golang.org/x/perf/benchfmt"
"golang.org/x/perf/benchproc"
)
// A Cell is the observations for part of a benchmark comparison.
type Cell struct {
Values []float64 // Actual values observed for this cell (sorted). Typically 1-100.
// Residues is the set of residue Keys mapped to this cell.
// It is used to check for non-unique keys.
Residues map[benchproc.Key]struct{}
}
// A Comparison is a pair of numerator and denominator measurements,
// the date that they were collected (or the latest date if they were accumulated),
// an optional slice of medians of ratios of bootstrapped estimates
// and an optional summary node that contains the spreadsheet/json/database
// summary of this same information.
type Comparison struct {
Numerator, Denominator *Cell
Date string
ratios []float64 // these are from bootstrapping. Typically 1000ish.
Summary *ComparisonSummary
}
// A ComparisonSummary is a summary of the comparison of a particular benchmark measurement
// for two different versions of the toolchain. Low, Center, and High are lower, middle and
// upper estimates of the value, most likely 2.5%ile, 50%ile, and 97.5%ile from a bootstrap
// of the original measurement ratios. Date is the (latest) date at which the measurements
// were taken. Present indicates that Low/Center/High/Date are valid; if comparison is non-nil,
// then there is a bootstrap that can be used or was used to initialize the other fields.
// (otherwise the source was JSON or a database).
type ComparisonSummary struct {
Low float64 `json:"low"`
Center float64 `json:"center"`
High float64 `json:"high"`
Date string `json:"date"`
Present bool `json:"present"` // is this initialized?
comparison *Comparison // backlink for K-S computation, also indicates initialization of L/C/H
}
func (s *ComparisonSummary) Defined() bool {
return s != nil && s.Present
}
// ComparisonHashes contains the git hashes of the two tool chains being compared.
type ComparisonHashes struct {
NumHash, DenHash string
}
type StringAndSlice struct {
S string `json:"s"`
Slice []string `json:"slice"`
}
// A ComparisonSeries describes a table/graph, indexed by paired elements of Benchmarks, Series.
// Summaries contains the points in the graph.
// HashPairs includes annotations for the Series axis.
type ComparisonSeries struct {
Unit string `json:"unit"`
Benchmarks []string `json:"benchmarks"`
Series []string `json:"series"`
Summaries [][]*ComparisonSummary `json:"summaries"`
HashPairs map[string]ComparisonHashes `json:"hashpairs"` // maps a series point to the hashes compared at that point.
Residues []StringAndSlice `json:"residues"`
cells map[SeriesKey]*Comparison
}
// SeriesKey is a map key used to index a single cell in a ComparisonSeries.
// ordering is by benchmark, then "series" (== commit) order
type SeriesKey struct {
Benchmark, Series string
}
// tableKey is a map key used to index a single cell in a lower-t table.
// ordering is by benchmark, then experiment order
type tableKey struct {
Benchmark, Experiment benchproc.Key
}
type unitTableKey struct {
unit, table benchproc.Key
}
type table struct {
cells map[tableKey]*trial
benchmarks map[benchproc.Key]struct{}
exps map[benchproc.Key]struct{}
}
type trial struct {
baseline *Cell
baselineHash benchproc.Key
baselineHashString string
tests map[benchproc.Key]*Cell // map from test hash id to test information
}
// A Builder collects benchmark results into a set of tables, and transforms that into a slice of ComparisonSeries.
type Builder struct {
// one table per unit; each table maps from (benchmark,experiment) to a single trial of baseline vs one or more tests
tables map[unitTableKey]*table
// numHashBy to numerator order.
hashToOrder map[benchproc.Key]benchproc.Key
filter *benchproc.Filter
unitBy, tableBy, pkgBy, experimentBy, benchBy, seriesBy, compareBy, numHashBy, denHashBy *benchproc.Projection
denCompareVal string // the string value of compareBy that indicates the control/baseline in a comparison.
numCompareVal string // the string value of compareBy that indicates the test in a comparison.
residue *benchproc.Projection
unitField *benchproc.Field
Residues map[benchproc.Key]struct{}
warn func(format string, args ...interface{})
}
type BuilderOptions struct {
Filter string // how to filter benchmark results, as a benchproc option (e.g., ".unit:/.*/")
Series string // the name of the benchmark key that contains the time of the last commit to the experiment branch (e.g. "numerator_stamp", "tip-commit-time")
Table string // list of benchmark keys to group ComparisonSeries tables by, in addition to .unit (e.g., "goarch,goos", "" (none))
Experiment string // the name of the benchmark key that contains the time at which the comparative benchmarks were run (e.g., "upload-time", "runstamp")
Compare string // the name of the benchmark key that contains the id/role of the toolchain being compared (e.g., "toolchain", "role")
Numerator string // the value of the Compare key that indicates the numerator in the ratios (i.e., "test", "tip", "experiment")
Denominator string // the value of the Compare key that indicates the denominator in the ratios (i.e., "control", "base", "baseline")
NumeratorHash string // the name of the benchmark key that contains the git hash of the numerator (test) toolchain
DenominatorHash string // the name of the benchmark key that contains the git hash of the denominator (control) toolchain
Ignore string // list of benchmark keys to ignore entirely (e.g. "tip,base,bentstamp,suite")
Warn func(format string, args ...interface{})
}
func BentBuilderOptions() *BuilderOptions {
return &BuilderOptions{
Filter: ".unit:/.*/",
Series: "numerator_stamp",
Table: "goarch,goos,builder_id",
Experiment: "runstamp",
Compare: "toolchain",
Numerator: "Tip",
Denominator: "Base",
NumeratorHash: "numerator_hash",
DenominatorHash: "denominator_hash",
Ignore: "go,tip,base,bentstamp,suite,cpu,denominator_branch,.fullname,shortname",
Warn: func(format string, args ...interface{}) {
fmt.Fprintf(os.Stderr, format, args...)
},
}
}
func DefaultBuilderOptions() *BuilderOptions {
return &BuilderOptions{
Filter: ".unit:/.*/",
Series: "experiment-commit-time",
Table: "", // .unit only
Experiment: "runstamp",
Compare: "toolchain",
Numerator: "experiment",
Denominator: "baseline",
NumeratorHash: "experiment-commit",
DenominatorHash: "baseline-commit",
Ignore: "go,tip,base,bentstamp,shortname,suite",
Warn: func(format string, args ...interface{}) {
fmt.Fprintf(os.Stderr, format, args...)
},
}
}
var noPuncDate = regexp.MustCompile("^[0-9]{8}T[0-9]{6}$")
// RFC3339NanoNoZ has the property that formatted date&time.000000000 < date&time.000000001,
// unlike RFC3339Nano where date&timeZ > date&timeZ.000000001Z
// i.e., "Z" > "."" but "+" < "." so if ".000000000" is elided must use "+00:00"
// to express the Z time zone to get the sort right.
const RFC3339NanoNoZ = "2006-01-02T15:04:05.999999999-07:00"
// NormalizeDateString converts dates in two formats used in bent/benchmarking
// into UTC, so that all sort properly into a single order with no confusion.
func NormalizeDateString(in string) (string, error) {
if noPuncDate.MatchString(in) {
//20211229T213212
//2021-12-29T21:32:12
in = in[0:4] + "-" + in[4:6] + "-" + in[6:11] + ":" + in[11:13] + ":" + in[13:15] + "+00:00"
}
t, err := time.Parse(time.RFC3339Nano, in)
if err != nil {
return "", err
}
return t.UTC().Format(RFC3339NanoNoZ), nil
}
// ParseNormalizedDateString parses a time in the format returned by
// NormalizeDateString.
func ParseNormalizedDateString(in string) (time.Time, error) {
return time.Parse(RFC3339NanoNoZ, in)
}
// NewBuilder creates a new Builder for collecting benchmark results
// into tables. Each result will be mapped to a Table by seriesBy.
// Within each table, the results are mapped to cells by benchBy and
// seriesBy. Any results within a single cell that vary by residue will
// be reported as warnings.
func NewBuilder(bo *BuilderOptions) (*Builder, error) {
filter, err := benchproc.NewFilter(bo.Filter)
if err != nil {
return nil, fmt.Errorf("parsing -filter: %s", err)
}
var parserErr error
var parser benchproc.ProjectionParser
mustParse := func(name, val string) *benchproc.Projection {
schema, err := parser.Parse(val, filter)
if err != nil {
parserErr = fmt.Errorf("parsing %s: %s", name, err)
}
return schema
}
unitBy, unitField, err := parser.ParseWithUnit("", nil)
if err != nil {
panic("Couldn't parse the unit schema")
}
tableBy, err := parser.Parse(bo.Table, nil)
if err != nil {
panic("Couldn't parse the table schema")
}
benchBy, err := parser.Parse(".fullname", nil)
if err != nil {
panic("Couldn't parse the .name schema")
}
pkgBy, err := parser.Parse("pkg", nil)
if err != nil {
panic("Couldn't parse 'pkg' schema")
}
seriesBy := mustParse("-series", bo.Series)
experimentBy := mustParse("-experiment", bo.Experiment)
compareBy := mustParse("-compare", bo.Compare)
numHashBy := mustParse("-numerator-hash", bo.NumeratorHash)
denHashBy := mustParse("-denominator-hash", bo.DenominatorHash)
mustParse("-ignore", bo.Ignore)
if parserErr != nil {
return nil, parserErr
}
residue := parser.Residue()
return &Builder{
filter: filter,
unitBy: unitBy,
tableBy: tableBy,
pkgBy: pkgBy,
experimentBy: experimentBy,
benchBy: benchBy,
seriesBy: seriesBy,
compareBy: compareBy,
numHashBy: numHashBy,
denHashBy: denHashBy,
denCompareVal: bo.Denominator,
numCompareVal: bo.Numerator,
residue: residue,
unitField: unitField,
hashToOrder: make(map[benchproc.Key]benchproc.Key),
tables: make(map[unitTableKey]*table),
Residues: make(map[benchproc.Key]struct{}),
warn: bo.Warn,
}, nil
}
func (b *Builder) AddFiles(files benchfmt.Files) error {
for files.Scan() {
rec := files.Result()
if err, ok := rec.(*benchfmt.SyntaxError); ok {
// Non-fatal result parse error. Warn
// but keep going.
b.warn("%v\n", err)
continue
}
res := rec.(*benchfmt.Result)
b.Add(res)
}
if err := files.Err(); err != nil {
return err
}
return nil
}
// Add adds all of the values in result to the tables in the Builder.
func (b *Builder) Add(result *benchfmt.Result) {
if ok, _ := b.filter.Apply(result); !ok {
return
}
// Project the result.
unitCfgs := b.unitBy.ProjectValues(result)
tableCfg := b.tableBy.Project(result)
_ = b.pkgBy.Project(result) // for now we are dropping pkg on the floor
expCfg := b.experimentBy.Project(result)
benchCfg := b.benchBy.Project(result)
serCfg := b.seriesBy.Project(result)
cmpCfg := b.compareBy.Project(result)
numHashCfg := b.numHashBy.Project(result)
denHashCfg := b.denHashBy.Project(result)
// tableBy, experimentBy, benchBy, seriesBy, compareBy, numHashBy, denHashBy
residueCfg := b.residue.Project(result)
cellCfg := tableKey{Benchmark: benchCfg, Experiment: expCfg}
// Map to tables.
for unitI, unitCfg := range unitCfgs {
tuk := unitTableKey{unitCfg, tableCfg}
table := b.tables[tuk]
if table == nil {
table = b.newTable()
b.tables[tuk] = table
}
// Map to a trial.
t := table.cells[cellCfg]
if t == nil {
t = new(trial)
table.cells[cellCfg] = t
t.tests = make(map[benchproc.Key]*Cell)
table.exps[expCfg] = struct{}{}
table.benchmarks[benchCfg] = struct{}{}
}
var c *Cell
newCell := func() *Cell {
return &Cell{Residues: make(map[benchproc.Key]struct{})}
}
switch cmpCfg.StringValues() {
case b.denCompareVal:
c = t.baseline
if c == nil {
c = newCell()
t.baseline = c
t.baselineHash = denHashCfg
t.baselineHashString = denHashCfg.StringValues()
}
case b.numCompareVal:
c = t.tests[numHashCfg]
if c == nil {
c = newCell()
t.tests[numHashCfg] = c
b.hashToOrder[numHashCfg] = serCfg
}
default:
// Compare field is set to an unknown value or
// completely unset. Don't add cell.
}
// Add to the cell.
if c != nil {
c.Values = append(c.Values, result.Values[unitI].Value)
c.Residues[residueCfg] = struct{}{}
b.Residues[residueCfg] = struct{}{}
}
}
}
func (b *Builder) newTable() *table {
return &table{
benchmarks: make(map[benchproc.Key]struct{}),
exps: make(map[benchproc.Key]struct{}),
cells: make(map[tableKey]*trial),
}
}
// union combines two sets of benchproc.Key into one.
func union(a, b map[benchproc.Key]struct{}) map[benchproc.Key]struct{} {
if len(b) < len(a) {
a, b = b, a
}
for k := range a {
if _, ok := b[k]; !ok {
// a member of the not-larger set was not present in the larger set
c := make(map[benchproc.Key]struct{})
for k := range a {
c[k] = struct{}{}
}
for k := range b {
c[k] = struct{}{}
}
return c
}
}
return b
}
func concat(a, b []float64) []float64 {
return append(append([]float64{}, a...), b...)
}
const (
DUPE_REPLACE = iota
DUPE_COMBINE
// TODO DUPE_REPEAT
)
// AllComparisonSeries converts the accumulated "experiments" into a slice of series of comparisons,
// with one slice element per goos-goarch-unit. The experiments need not have occurred in any
// sensible order; this deals with that, including overlaps (depend on flag, either replaces old with
// younger or combines, REPLACE IS PREFERRED and works properly with combining old summary data with
// fresh benchmarking data) and possibly also with previously processed summaries.
func (b *Builder) AllComparisonSeries(existing []*ComparisonSeries, dupeHow int) ([]*ComparisonSeries, error) {
old := make(map[string]*ComparisonSeries)
for _, cs := range existing {
old[cs.Unit] = cs
}
var css []*ComparisonSeries
// Iterate over units.
for _, u := range sortTableKeys(b.tables) {
t := b.tables[u]
uString := u.unit.StringValues()
if ts := u.table.StringValues(); ts != "" {
uString += " " + u.table.StringValues()
}
var cs *ComparisonSeries
sers := make(map[string]struct{})
benches := make(map[string]struct{})
if o := old[uString]; o != nil {
cs = o
delete(old, uString)
cs.cells = make(map[SeriesKey]*Comparison)
for i, s := range cs.Series {
for j, b := range cs.Benchmarks {
if cs.Summaries[i][j].Defined() {
sk := SeriesKey{
Benchmark: b,
Series: s,
}
benches[b] = struct{}{}
sers[s] = struct{}{}
sum := cs.Summaries[i][j]
cc := &Comparison{Summary: sum, Date: sum.Date}
sum.comparison = cc
cs.cells[sk] = cc
}
}
}
} else {
cs = &ComparisonSeries{Unit: uString,
HashPairs: make(map[string]ComparisonHashes),
cells: make(map[SeriesKey]*Comparison),
}
}
// TODO not handling overlapping samples between "existing" and "newly read" yet.
// Rearrange into paired comparisons, gathering repeats of same comparison from multiple experiments.
for tk, tr := range t.cells {
// tk == bench, experiment, tr == baseline, tests, tests == map hash -> cell.
bench := tk.Benchmark
dateString, err := NormalizeDateString(tk.Experiment.StringValues())
if err != nil {
return nil, fmt.Errorf("error parsing experiment date %q: %w", tk.Experiment.StringValues(), err)
}
benchString := bench.StringValues()
benches[benchString] = struct{}{}
for hash, cell := range tr.tests {
hashString := hash.StringValues()
ser := b.hashToOrder[hash]
serString, err := NormalizeDateString(ser.StringValues())
if err != nil {
return nil, fmt.Errorf("error parsing series date %q: %w", ser.StringValues(), err)
}
sers[serString] = struct{}{}
sk := SeriesKey{
Benchmark: benchString,
Series: serString,
}
cc := cs.cells[sk]
if cc == nil || dupeHow == DUPE_REPLACE {
if cc == nil || cc.Date < dateString {
cc = &Comparison{
Numerator: cell,
Denominator: tr.baseline,
Date: dateString,
}
cs.cells[sk] = cc
}
hp, ok := cs.HashPairs[serString]
if !ok {
cs.HashPairs[serString] = ComparisonHashes{NumHash: hashString, DenHash: tr.baselineHashString}
} else {
if hp.NumHash != hashString || hp.DenHash != tr.baselineHashString {
fmt.Fprintf(os.Stderr, "numerator/denominator mismatch, expected %s/%s got %s/%s\n",
hp.NumHash, hp.DenHash, hashString, tr.baselineHashString)
}
}
} else { // Current augments, but this will do the wrong thing if one is an old summary; also need to think about "repeat"
// augment an existing measurement (i.e., a second experiment on this same datapoint)
// fmt.Printf("Augment u:%s,b:%s,ch:%s,cd:%s; cc=%v[n(%d+%d)d(%d+%d)]\n",
// u.StringValues(), bench.StringValues(), hash.StringValues(), ser.StringValues(),
// cc, len(cc.Numerator.Values), len(cell.Values), len(cc.Denominator.Values), len(tr.baseline.Values))
cc.Numerator = &Cell{
Values: concat(cc.Numerator.Values, cell.Values),
Residues: union(cc.Numerator.Residues, cell.Residues),
}
cc.Denominator = &Cell{
Values: concat(cc.Denominator.Values, tr.baseline.Values),
Residues: union(cc.Denominator.Residues, tr.baseline.Residues),
}
if cc.Date < dateString {
cc.Date = dateString
}
}
}
}
cs.Benchmarks = sortStringSet(benches)
cs.Series = sortStringSet(sers)
for _, b := range cs.Benchmarks {
for _, s := range cs.Series {
cc := cs.cells[SeriesKey{Benchmark: b, Series: s}]
if cc != nil && cc.Numerator != nil && cc.Denominator != nil {
sort.Float64s(cc.Numerator.Values)
sort.Float64s(cc.Denominator.Values)
}
}
}
// Accumulate residues for this unit's table
type seenKey struct {
f *benchproc.Field
s string
}
seen := make(map[seenKey]bool)
rmap := make(map[string][]string)
for _, c := range cs.cells {
for _, f := range b.residue.FlattenedFields() {
if c.Numerator == nil {
continue
}
for k, _ := range c.Numerator.Residues {
s := k.Get(f)
if !seen[seenKey{f, s}] {
seen[seenKey{f, s}] = true
rmap[f.Name] = append(rmap[f.Name], s)
}
}
for k, _ := range c.Denominator.Residues {
s := k.Get(f)
if !seen[seenKey{f, s}] {
seen[seenKey{f, s}] = true
rmap[f.Name] = append(rmap[f.Name], s)
}
}
}
}
sas := []StringAndSlice{}
for k, v := range rmap {
sort.Strings(v)
sas = append(sas, StringAndSlice{k, v})
}
sort.Slice(sas, func(i, j int) bool { return sas[i].S < sas[j].S })
if len(cs.Residues) > 0 {
// Need to merge old and new
osas, nsas := cs.Residues, []StringAndSlice{}
for i, j := 0, 0; i < len(sas) || j < len(osas); {
if i == len(sas) || j < len(osas) && osas[j].S < sas[i].S {
nsas = append(nsas, osas[j])
j++
continue
}
if j == len(osas) || osas[j].S > sas[i].S {
nsas = append(nsas, sas[i])
i++
continue
}
// S (keys) are equal, merge value slices
sl, osl, nsl := sas[i].Slice, osas[j].Slice, []string{}
for ii, jj := 0, 0; ii < len(sl) || jj < len(osl); {
if ii == len(sl) || jj < len(osl) && osl[jj] < sl[ii] {
nsl = append(nsl, osl[jj])
jj++
continue
}
if jj == len(osl) || osl[jj] > sl[ii] {
nsl = append(nsl, sl[ii])
ii++
continue
}
nsl = append(nsl, sl[ii])
ii++
jj++
}
nsas = append(nsas, StringAndSlice{sas[i].S, nsl})
i++
j++
}
sas = nsas
}
cs.Residues = sas
css = append(css, cs)
}
for _, cs := range existing {
if o := old[cs.Unit]; o != nil {
css = append(css, cs)
}
}
return css, nil
}
func sortStringSet(m map[string]struct{}) []string {
var s []string
for k := range m {
s = append(s, k)
}
sort.Strings(s)
return s
}
func sortTableKeys(m map[unitTableKey]*table) []unitTableKey {
var s []unitTableKey
for k := range m {
s = append(s, k)
}
sort.Slice(s, func(i, j int) bool {
if s[i].unit != s[j].unit {
return s[i].unit.StringValues() < s[j].unit.StringValues()
}
if s[i].table == s[j].table {
return false
}
return s[i].table.StringValues() < s[j].table.StringValues()
})
return s
}
func absSortedPermFor(a []float64) []int {
p := make([]int, len(a), len(a))
for i := range p {
p[i] = i
}
sort.Slice(p, func(i, j int) bool {
return math.Abs(a[p[i]]) < math.Abs(a[p[j]])
})
return p
}
func permute(a []float64, p []int) []float64 {
b := make([]float64, len(a), len(a))
for i, j := range p {
b[i] = a[j]
}
return b
}
// TODO Does this need to export the individual cells? What's the expected/intended use?
func (cs *ComparisonSeries) ComparisonAt(benchmark, series string) (*Comparison, bool) {
if cc := cs.cells[SeriesKey{Benchmark: benchmark, Series: series}]; cc != nil {
return cc, true
}
return nil, false
}
func (cs *ComparisonSeries) SummaryAt(benchmark, series string) (*ComparisonSummary, bool) {
if cc := cs.cells[SeriesKey{Benchmark: benchmark, Series: series}]; cc != nil {
return cc.Summary, true
}
return nil, false
}
func (c *Cell) resampleInto(r *rand.Rand, x []float64) {
l := len(x)
for i := range x {
x[i] = c.Values[r.Intn(l)]
}
sort.Float64s(x)
}
const rot = 23
func (c *Cell) hash() int64 {
var x int64
for _, v := range c.Values {
xlow := (x >> (64 - rot)) & (1<<rot - 1)
x = (x << rot) ^ xlow ^ int64(math.Float64bits(v))
}
return x
}
// ratio computes a bootstrapped estimate of the confidence interval for
// the ratio of measurements in nu divided by measurements in de.
func ratio(nu, de *Cell, confidence float64, r *rand.Rand, ratios []float64) (center, low, high float64) {
N := len(ratios)
rnu := make([]float64, len(nu.Values), len(nu.Values))
rde := make([]float64, len(de.Values), len(de.Values))
for i := 0; i < N; i++ {
nu.resampleInto(r, rnu)
de.resampleInto(r, rde)
den := median(rde)
if den == 0 {
num := median(rnu)
if num >= 0 {
ratios[i] = (num + 1)
} else {
ratios[i] = (num - 1)
}
} else {
ratios[i] = median(rnu) / den
}
}
sort.Float64s(ratios)
p := (1 - confidence) / 2
low = percentile(ratios, p)
high = percentile(ratios, 1-p)
center = median(ratios)
return
}
func percentile(a []float64, p float64) float64 {
if len(a) == 0 {
return math.NaN()
}
if p == 0 {
return a[0]
}
n := len(a)
if p == 1 {
return a[n-1]
}
f := float64(float64(n) * p) // Suppress fused-multiply-add
i := int(f)
x := f - float64(i)
r := a[i]
if x > 0 && i+1 < len(a) {
r = float64(r*(1-x)) + float64(a[i+1]*x) // Suppress fused-multiply-add
}
return r
}
func median(a []float64) float64 {
l := len(a)
if l&1 == 1 {
return a[l/2]
}
return (a[l/2] + a[l/2-1]) / 2
}
func norm(a []float64, l float64) float64 {
if len(a) == 0 {
return math.NaN()
}
n := 0.0
sum := 0.0
for _, x := range a {
if math.IsInf(x, 0) || math.IsNaN(x) {
continue
}
sum += math.Pow(math.Abs(x), l)
n++
}
return math.Pow(sum/n, 1/l)
}
// ChangeScore returns an indicator of the change and direction.
// This is a heuristic measure of the lack of overlap between
// two confidence intervals; minimum lack of overlap (i.e., same
// confidence intervals) is zero. Exact non-overlap, meaning
// the high end of one interval is equal to the low end of the
// other, is one. A gap of size G between the two intervals
// yields a score of 1 + G/M where M is the size of the smaller
// interval (this penalizes a ChangeScore in noise, which is also a
// ChangeScore). A partial overlap of size G yields a score of
// 1 - G/M.
//
// Empty confidence intervals are problematic and produces infinities
// or NaNs.
func ChangeScore(l1, c1, h1, l2, c2, h2 float64) float64 {
sign := 1.0
if c1 > c2 {
l1, c1, h1, l2, c2, h2 = l2, c2, h2, l1, c1, h1
sign = -sign
}
r := math.Min(h1-l1, h2-l2)
// we know l1 < c1 < h1, c1 < c2, l2 < c2 < h2
// therefore l1 < c1 < c2 < h2
if h1 > l2 { // overlap
if h1 > h2 {
h1 = h2
}
if l2 < l1 {
l2 = l1
}
return sign * (1 - (h1-l2)/r) // perfect overlap == 0
} else { // no overlap
return sign * (1 + (l2-h1)/r) //
}
}
type compareFn func(c *Comparison) (center, low, high float64)
func withBootstrap(confidence float64, N int) compareFn {
return func(c *Comparison) (center, low, high float64) {
c.ratios = make([]float64, N, N)
r := rand.New(rand.NewSource(c.Numerator.hash() * c.Denominator.hash()))
center, low, high = ratio(c.Numerator, c.Denominator, confidence, r, c.ratios)
return
}
}
// KSov returns the size-adjusted Kolmogorov-Smirnov statistic,
// equal to D_{n,m} / sqrt((n+m)/n*m). The result can be compared
// to c(α) where α is the level at which the null hypothesis is rejected.
//
// α: 0.2 0.15 0.10 0.05 0.025 0.01 0.005 0.001
// c(α): 1.073 1.138 1.224 1.358 1.48 1.628 1.731 1.949
//
// see
// https://en.wikipedia.org/wiki/Kolmogorov%E2%80%93Smirnov_test#Two-sample_Kolmogorov%E2%80%93Smirnov_test
func (a *ComparisonSummary) KSov(b *ComparisonSummary) float64 {
// TODO Kolmogorov-Smirnov hasn't worked that well
ra, rb := a.comparison.ratios, b.comparison.ratios
ia, ib := 0, 0
la, lb := len(ra), len(rb)
fla, flb := float64(la), float64(lb)
gap := 0.0
for ia < la && ib < lb {
if ra[ia] < rb[ib] {
ia++
} else if ra[ia] > rb[ib] {
ib++
} else {
ia++
ib++
}
g := math.Abs(float64(ia)/fla - float64(ib)/flb)
if g > gap {
gap = g
}
}
return gap * math.Sqrt(fla*flb/(fla+flb))
}
// HeurOverlap computes a heuristic overlap between two confidence intervals
func (a *ComparisonSummary) HeurOverlap(b *ComparisonSummary, threshold float64) float64 {
if a.Low == a.High && b.Low == b.High {
ca, cb, sign := a.Center, b.Center, 100.0
if cb < ca {
ca, cb, sign = cb, ca, -100.0
}
if ca == 0 {
if cb > threshold {
return sign
}
} else if (cb-ca)/ca > threshold {
return sign
}
return 0
}
return ChangeScore(a.Low, a.Center, a.High, b.Low, b.Center, b.High)
}
// AddSummaries computes the summary data (bootstrapped estimated of the specified
// confidence interval) for the comparison series cs. The 3rd parameter N specifies
// the number of sampled bootstraps to use; 1000 is recommended, but 500 is good enough
// for testing.
func (cs *ComparisonSeries) AddSummaries(confidence float64, N int) {
fn := withBootstrap(confidence, N)
var tab [][]*ComparisonSummary
for _, s := range cs.Series {
row := []*ComparisonSummary{}
for _, b := range cs.Benchmarks {
if c, ok := cs.ComparisonAt(b, s); ok {
sum := c.Summary
if sum == nil || (!sum.Present && sum.comparison == nil) {
sum = &ComparisonSummary{comparison: c, Date: c.Date}
sum.Center, sum.Low, sum.High = fn(c)
sum.Present = true
c.Summary = sum
}
row = append(row, sum)
} else {
row = append(row, &ComparisonSummary{})
}
}
tab = append(tab, row)
}
cs.Summaries = tab
}