Skip to main content

internal/benchtab/builder.go

1// Note(alexwlchan, 2026-11-04): This file was retrieved from
2// https://cs.opensource.google/go/x/perf/+/be2c69fb:cmd/benchstat/internal/benchtab/builder.go
4// Copyright 2020 The Go Authors. All rights reserved.
5// Use of this source code is governed by a BSD-style
6// license that can be found in the LICENSE file.
8// Package benchtab presents benchmark results as comparison tables.
9package benchtab
11import (
12 "encoding/csv"
13 "errors"
14 "fmt"
15 "io"
16 "math"
17 "runtime"
18 "strings"
19 "sync"
21 "github.com/aclements/go-moremath/stats"
22 "golang.org/x/perf/benchfmt"
23 "golang.org/x/perf/benchmath"
24 "golang.org/x/perf/benchproc"
27// TODO: Color by good/bad (or nothing for unknown units)
29// A Builder collects benchmark results into a Tables set.
30type Builder struct {
31 tableBy, rowBy, colBy *benchproc.Projection
32 residue *benchproc.Projection
34 unitField *benchproc.Field
36 // tables maps from tableBy to table.
37 tables map[benchproc.Key]*builderTable
40type builderTable struct {
41 // Observed row and col Keys within this group. Within the
42 // group, we show only the row and col labels for the data in
43 // the group, but we sort them according to the global
44 // observation order for consistency across groups.
45 rows map[benchproc.Key]struct{}
46 cols map[benchproc.Key]struct{}
48 // cells maps from (row, col) to each cell.
49 cells map[TableKey]*builderCell
52type builderCell struct {
53 // values are the observed values in this cell.
54 values []float64
55 // residue is the set of residue keys mapped to this cell.
56 // It is used to check for non-unique keys.
57 residue map[benchproc.Key]struct{}
60// NewBuilder creates a new Builder for collecting benchmark results
61// into tables. Each result will be mapped to a Table by tableBy.
62// Within each table, the results are mapped to cells by rowBy and
63// colBy. Any results within a single cell that vary by residue will
64// be reported as warnings. tableBy must have a ".unit" field.
65func NewBuilder(tableBy, rowBy, colBy, residue *benchproc.Projection) *Builder {
66 tableFields := tableBy.Fields()
67 unitField := tableFields[len(tableFields)-1]
68 if unitField.Name != ".unit" {
69 panic("tableBy projection missing .unit field")
70 }
71 return &Builder{
72 tableBy: tableBy, rowBy: rowBy, colBy: colBy, residue: residue,
73 unitField: unitField,
74 tables: make(map[benchproc.Key]*builderTable),
75 }
78// Add adds all of the values in result to the tables in the Builder.
79func (b *Builder) Add(result *benchfmt.Result) {
80 // Project the result.
81 tableKeys := b.tableBy.ProjectValues(result)
82 rowKey := b.rowBy.Project(result)
83 colKey := b.colBy.Project(result)
84 residueKey := b.residue.Project(result)
85 cellKey := TableKey{rowKey, colKey}
87 // Map to tables.
88 for unitI, tableKey := range tableKeys {
89 table := b.tables[tableKey]
90 if table == nil {
91 table = b.newTable()
92 b.tables[tableKey] = table
93 }
95 // Map to a cell.
96 c := table.cells[cellKey]
97 if c == nil {
98 c = new(builderCell)
99 c.residue = make(map[benchproc.Key]struct{})
100 table.cells[cellKey] = c
101 table.rows[rowKey] = struct{}{}
102 table.cols[colKey] = struct{}{}
103 }
105 // Add to the cell.
106 c.values = append(c.values, result.Values[unitI].Value)
107 c.residue[residueKey] = struct{}{}
108 }
111func (b *Builder) newTable() *builderTable {
112 return &builderTable{
113 rows: make(map[benchproc.Key]struct{}),
114 cols: make(map[benchproc.Key]struct{}),
115 cells: make(map[TableKey]*builderCell),
116 }
119// TableOpts provides options for constructing the final analysis
120// tables from a Builder.
121type TableOpts struct {
122 // Confidence is the desired confidence level in summary
123 // intervals; e.g., 0.95 for 95%.
124 Confidence float64
126 // Thresholds are the thresholds to use for statistical tests.
127 Thresholds *benchmath.Thresholds
129 // Units is the unit metadata. This gives distributional
130 // assumptions for units, among other properties.
131 Units benchfmt.UnitMetadataMap
134// Tables is a sequence of benchmark statistic tables.
135type Tables struct {
136 // Tables is a slice of statistic tables. Within a Table, all
137 // results have the same table Key (including unit).
138 Tables []*Table
139 // Keys is a slice of table keys, corresponding 1:1 to
140 // the Tables slice. These always end with a ".unit"
141 // field giving the unit.
142 Keys []benchproc.Key
145// ToTables finalizes a Builder into a sequence of statistic tables.
146func (b *Builder) ToTables(opts TableOpts) *Tables {
147 // Sort tables.
148 var keys []benchproc.Key
149 for k := range b.tables {
150 keys = append(keys, k)
151 }
152 benchproc.SortKeys(keys)
154 // We're going to compute table cells in parallel because the
155 // statistics are somewhat expensive. This is entirely
156 // CPU-bound, so we put a simple concurrency limit on it.
157 limit := make(chan struct{}, 2*runtime.GOMAXPROCS(-1))
158 var wg sync.WaitGroup
160 // Process each table.
161 var tables []*Table
162 for _, k := range keys {
163 cTable := b.tables[k]
165 // Get the configured assumption for this unit.
166 unit := k.Get(b.unitField)
167 assumption := opts.Units.GetAssumption(unit)
169 // Sort the rows and columns.
170 rowKeys, colKeys := mapKeys(cTable.rows), mapKeys(cTable.cols)
171 table := &Table{
172 Unit: unit,
173 Opts: opts,
174 Assumption: assumption,
175 Rows: rowKeys,
176 Cols: colKeys,
177 Cells: make(map[TableKey]*TableCell),
178 }
179 tables = append(tables, table)
181 // Create all TableCells and fill their Samples. This
182 // is fast enough it's not worth parallelizing. This
183 // enables the second pass to look up baselines and
184 // their samples.
185 for k, cCell := range cTable.cells {
186 table.Cells[k] = &TableCell{
187 Sample: benchmath.NewSample(cCell.values, opts.Thresholds),
188 }
189 }
191 // Populate cells.
192 baselineCfg := colKeys[0]
193 wg.Add(len(cTable.cells))
194 for k, cCell := range cTable.cells {
195 cell := table.Cells[k]
197 // Look up the baseline.
198 if k.Col != baselineCfg {
199 base, ok := table.Cells[TableKey{k.Row, baselineCfg}]
200 if ok {
201 cell.Baseline = base
202 }
203 }
205 limit <- struct{}{}
206 cCell := cCell
207 go func() {
208 summarizeCell(cCell, cell, assumption, opts.Confidence)
209 <-limit
210 wg.Done()
211 }()
212 }
213 }
214 wg.Wait()
216 // Add summary rows to each table.
217 for _, table := range tables {
218 table.SummaryLabel = "geomean"
219 table.Summary = make(map[benchproc.Key]*TableSummary)
221 // Count the number of baseline benchmarks. If later
222 // columns don't have the same number of baseline
223 // pairings, we know the benchmark sets don't match.
224 nBase := 0
225 baseCol := table.Cols[0]
226 for _, row := range table.Rows {
227 if _, ok := table.Cells[TableKey{row, baseCol}]; ok {
228 nBase++
229 }
230 }
232 for i, col := range table.Cols {
233 var s TableSummary
234 table.Summary[col] = &s
235 isBase := i == 0
237 limit <- struct{}{}
238 table, col := table, col
239 wg.Add(1)
240 go func() {
241 summarizeCol(table, col, &s, nBase, isBase)
242 <-limit
243 wg.Done()
244 }()
245 }
246 }
247 wg.Wait()
249 return &Tables{tables, keys}
252func mapKeys(m map[benchproc.Key]struct{}) []benchproc.Key {
253 var keys []benchproc.Key
254 for k := range m {
255 keys = append(keys, k)
256 }
257 benchproc.SortKeys(keys)
258 return keys
261func summarizeCell(cCell *builderCell, cell *TableCell, assumption benchmath.Assumption, confidence float64) {
262 cell.Summary = assumption.Summary(cell.Sample, confidence)
264 // If there's a baseline, compute comparison.
265 if cell.Baseline != nil {
266 cell.Comparison = assumption.Compare(cell.Baseline.Sample, cell.Sample)
267 }
269 // Warn for non-singular keys in this cell.
270 nsk := benchproc.NonSingularFields(mapKeys(cCell.residue))
271 if len(nsk) > 0 {
272 // Emit a warning.
273 var warn strings.Builder
274 warn.WriteString("benchmarks vary in ")
275 for i, field := range nsk {
276 if i > 0 {
277 warn.WriteString(", ")
278 }
279 warn.WriteString(field.Name)
280 }
282 cell.Sample.Warnings = append(cell.Sample.Warnings, errors.New(warn.String()))
283 }
286func summarizeCol(table *Table, col benchproc.Key, s *TableSummary, nBase int, isBase bool) {
287 // Collect cells.
288 //
289 // This computes the geomean of the summary ratios rather than
290 // ratio of the summary geomeans. These are identical *if* the
291 // benchmark sets are the same. But if the benchmark sets
292 // differ, this leads to more sensible ratios because it's
293 // still the geomean of the column, rather than being a
294 // comparison of two incomparable numbers. It's still easy to
295 // misinterpret, but at least it's not meaningless.
296 var summaries, ratios []float64
297 badRatio := false
298 for _, row := range table.Rows {
299 cell, ok := table.Cells[TableKey{row, col}]
300 if !ok {
301 continue
302 }
303 summaries = append(summaries, cell.Summary.Center)
304 if cell.Baseline != nil {
305 var ratio float64
306 a, b := cell.Summary.Center, cell.Baseline.Summary.Center
307 if a == b {
308 // Treat 0/0 as 1.
309 ratio = 1
310 } else if b == 0 {
311 badRatio = true
312 // Keep nBase check working.
313 ratios = append(ratios, 0)
314 continue
315 } else {
316 ratio = a / b
317 }
318 ratios = append(ratios, ratio)
319 }
320 }
322 // If the number of cells in this column that had a baseline
323 // is the same as the total number of baselines, then we know
324 // the benchmark sets match. Otherwise, they don't and these
325 // numbers are probably misleading.
326 if !isBase && nBase != len(ratios) {
327 s.Warnings = append(s.Warnings, fmt.Errorf("benchmark set differs from baseline; geomeans may not be comparable"))
328 }
330 // Summarize centers.
331 gm := stats.GeoMean(summaries)
332 if math.IsNaN(gm) {
333 s.Warnings = append(s.Warnings, fmt.Errorf("summaries must be >0 to compute geomean"))
334 } else {
335 s.HasSummary = true
336 s.Summary = gm
337 }
339 // Summarize ratios.
340 if !isBase && !badRatio {
341 gm := stats.GeoMean(ratios)
342 if math.IsNaN(gm) {
343 s.Warnings = append(s.Warnings, fmt.Errorf("ratios must be >0 to compute geomean"))
344 } else {
345 s.HasRatio = true
346 s.Ratio = gm
347 }
348 }
351// ToText renders t to a textual representation, assuming a
352// fixed-width font.
353func (t *Tables) ToText(w io.Writer, color bool) error {
354 return t.printTables(func(hdr string) error {
355 _, err := fmt.Fprintf(w, "%s\n", hdr)
356 return err
357 }, func(table *Table) error {
358 return table.ToText(w, color)
359 })
362// ToCSV renders t in CSV (comma-separated values) format.
363//
364// Warnings are written to a separate stream so as not to interrupt
365// the regular format of the CSV table.
366func (t *Tables) ToCSV(w, warnings io.Writer) error {
367 o := csv.NewWriter(w)
368 row := 1
370 err := t.printTables(func(hdr string) error {
371 o.Write([]string{hdr})
372 row++
373 return nil
374 }, func(table *Table) error {
375 nRows := table.ToCSV(o, row, warnings)
376 row += nRows
377 return nil
378 })
379 if err != nil {
380 return err
381 }
382 o.Flush()
383 return o.Error()
386func (t *Tables) printTables(hdr func(string) error, cb func(*Table) error) error {
387 if len(t.Tables) == 0 {
388 return nil
389 }
391 var prevKey benchproc.Key
392 fields := t.Keys[0].Projection().FlattenedFields()
394 for i, table := range t.Tables {
395 if i > 0 {
396 // Blank line between tables.
397 if err := hdr(""); err != nil {
398 return err
399 }
400 }
402 // Print table key changes.
403 key := t.Keys[i]
404 for _, f := range fields {
405 if f.Name == ".unit" {
406 // Skip .unit because it's shown in the table itself.
407 continue
408 }
409 val := key.Get(f)
410 if prevKey.IsZero() || val != prevKey.Get(f) {
411 if err := hdr(fmt.Sprintf("%s: %s", f.Name, val)); err != nil {
412 return err
413 }
414 }
415 }
416 prevKey = key
418 // Print table.
419 if err := cb(table); err != nil {
420 return err
421 }
422 }
424 return nil