benchproc: new package for high-level benchmark processing
This provides a transform/filter/projection processing model for
working with benchmark results, and mini-languages for constructing
filters and projections. This model is the result of quite a bit of
experimentation, and at this point I've built three tools on top of
this package, so I consider it reasonably well validated.
This also introduces a benchproc/syntax package, akin to the
regexp/syntax package. The syntax package documents the syntax and
provides low-level parsers for filter and projection expressions. If
we ever port the web UI over to this, this will make it easy to
transform these expressions into database filters.
This requires updating the language version in go.mod to 1.13 because
benchproc uses binary literals and signed shifts.
Change-Id: If9da95ec1e583594644c123f3bc3fc377a0e97e5
Reviewed-on: https://go-review.googlesource.com/c/perf/+/283617
Trust: Austin Clements <austin@google.com>
Run-TryBot: Austin Clements <austin@google.com>
Reviewed-by: Michael Knyszek <mknyszek@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
diff --git a/benchfmt/result.go b/benchfmt/result.go
index 65a5f11..8903c2e 100644
--- a/benchfmt/result.go
+++ b/benchfmt/result.go
@@ -244,7 +244,7 @@
// 2. "/<string>" indicates a positional configuration pair.
//
// 3. "-<gomaxprocs>" indicates the GOMAXPROCS of this benchmark. This
-// component can only appear last.
+// part can only appear last.
//
// Concatenating the base name and the configuration parts
// reconstructs the full name.
diff --git a/benchproc/doc.go b/benchproc/doc.go
new file mode 100644
index 0000000..7c3a035
--- /dev/null
+++ b/benchproc/doc.go
@@ -0,0 +1,50 @@
+// 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 benchproc provides tools for filtering, grouping, and
+// sorting benchmark results.
+//
+// This package supports a pipeline processing model based around
+// domain-specific languages for filtering and projecting benchmark
+// results. These languages are described in "go doc
+// golang.org/x/perf/benchproc/syntax".
+//
+// The typical steps for processing a stream of benchmark
+// results are:
+//
+// 1. Read a stream of benchfmt.Results from one or more input sources.
+// Command-line tools will often do this using benchfmt.Files.
+//
+// 2. For each benchfmt.Result:
+//
+// 2a. Optionally transform the benchfmt.Result to add or modify keys
+// according to a particular tool's needs. Custom keys often start with
+// "." to distinguish them from file or sub-name keys. For example,
+// benchfmt.Files adds a ".file" key.
+//
+// 2b. Optionally filter the benchfmt.Result according to a user-provided
+// predicate parsed by NewFilter. Filters can keep or discard entire
+// Results, or just particular measurements from a Result.
+//
+// 2c. Project the benchfmt.Result using one or more Projections.
+// Projecting a Result extracts a subset of the information from a
+// Result into a Key. Projections are produced by a ProjectionParser,
+// typically from user-provided projection expressions. An application
+// should have a Projection for each "dimension" of its output. For
+// example, an application that emits a table may have two Projections:
+// one for rows and one for columns. An application that produces a
+// scatterplot could have Projections for X and Y as well as other
+// visual properties like point color and size.
+//
+// 2d. Group the benchfmt.Result according to the projected Keys.
+// Usually this is done by storing the measurements from the Result in a
+// Go map indexed by Key. Because identical Keys compare ==, they can be
+// used as map keys. Applications that use two or more Projections may
+// use a map of maps, or a map keyed by a struct of two Keys, or some
+// combination.
+//
+// 3. At the end of the Results stream, once all Results have been
+// grouped by their Keys, sort the Keys of each dimension using SortKeys
+// and present the data in the resulting order.
+package benchproc
diff --git a/benchproc/extract.go b/benchproc/extract.go
new file mode 100644
index 0000000..1722258
--- /dev/null
+++ b/benchproc/extract.go
@@ -0,0 +1,187 @@
+// 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 benchproc
+
+import (
+ "bytes"
+ "fmt"
+ "strings"
+
+ "golang.org/x/perf/benchfmt"
+)
+
+// An extractor returns some field of a benchmark result. The
+// result may be a view into a mutable []byte in *benchfmt.Result, so
+// it may change if the Result is modified.
+type extractor func(*benchfmt.Result) []byte
+
+// newExtractor returns a function that extracts some field of a
+// benchmark result.
+//
+// The key must be one of the following:
+//
+// - ".name" for the benchmark name (excluding per-benchmark
+// configuration).
+//
+// - ".fullname" for the full benchmark name (including per-benchmark
+// configuration).
+//
+// - "/{key}" for a benchmark sub-name key. This may be "/gomaxprocs"
+// and the extractor will normalize the name as needed.
+//
+// - Any other string is a file configuration key.
+func newExtractor(key string) (extractor, error) {
+ if len(key) == 0 {
+ return nil, fmt.Errorf("key must not be empty")
+ }
+
+ switch {
+ case key == ".config", key == ".unit":
+ // The caller should already have handled this more gracefully.
+ panic(key + " is not an extractor")
+
+ case key == ".name":
+ return extractName, nil
+
+ case key == ".fullname":
+ return extractFull, nil
+
+ case strings.HasPrefix(key, "/"):
+ // Construct the byte prefix to search for.
+ prefix := make([]byte, len(key)+1)
+ copy(prefix, key)
+ prefix[len(prefix)-1] = '='
+ isGomaxprocs := key == "/gomaxprocs"
+ return func(res *benchfmt.Result) []byte {
+ return extractNamePart(res, prefix, isGomaxprocs)
+ }, nil
+ }
+
+ return func(res *benchfmt.Result) []byte {
+ return extractConfig(res, key)
+ }, nil
+}
+
+// newExtractorFullName returns an extractor for the full name of a
+// benchmark, but optionally with the base name or sub-name
+// configuration keys excluded. Any excluded sub-name keys will be
+// deleted from the name. If ".name" is excluded, the name will be
+// normalized to "*". This will ignore anything in the exclude list that
+// isn't in the form of a /-prefixed sub-name key or ".name".
+func newExtractorFullName(exclude []string) extractor {
+ // Extract the sub-name keys, turn them into substrings and
+ // construct their normalized replacement.
+ //
+ // It's important that we fully delete excluded sub-name keys rather
+ // than, say, normalizing them to "*". Simply normalizing them will
+ // leak whether or not they are present into the result, resulting
+ // in different strings. This is most noticeable when excluding
+ // /gomaxprocs: since this is already omitted if it's 1, benchmarks
+ // running at /gomaxprocs of 1 won't merge with benchmarks at higher
+ // /gomaxprocs.
+ var delete [][]byte
+ excName := false
+ excGomaxprocs := false
+ for _, k := range exclude {
+ if k == ".name" {
+ excName = true
+ }
+ if !strings.HasPrefix(k, "/") {
+ continue
+ }
+ delete = append(delete, append([]byte(k), '='))
+ if k == "/gomaxprocs" {
+ excGomaxprocs = true
+ }
+ }
+ if len(delete) == 0 && !excName && !excGomaxprocs {
+ return extractFull
+ }
+ return func(res *benchfmt.Result) []byte {
+ return extractFullExcluded(res, delete, excName, excGomaxprocs)
+ }
+}
+
+func extractName(res *benchfmt.Result) []byte {
+ return res.Name.Base()
+}
+
+func extractFull(res *benchfmt.Result) []byte {
+ return res.Name.Full()
+}
+
+func extractFullExcluded(res *benchfmt.Result, delete [][]byte, excName, excGomaxprocs bool) []byte {
+ name := res.Name.Full()
+ found := false
+ if excName {
+ found = true
+ }
+ if !found {
+ for _, k := range delete {
+ if bytes.Contains(name, k) {
+ found = true
+ break
+ }
+ }
+ }
+ if !found && excGomaxprocs && bytes.IndexByte(name, '-') >= 0 {
+ found = true
+ }
+ if !found {
+ // No need to transform name.
+ return name
+ }
+
+ // Delete excluded keys from the name.
+ base, parts := res.Name.Parts()
+ var newName []byte
+ if excName {
+ newName = append(newName, '*')
+ } else {
+ newName = append(newName, base...)
+ }
+outer:
+ for _, part := range parts {
+ for _, k := range delete {
+ if bytes.HasPrefix(part, k) {
+ // Skip this part.
+ continue outer
+ }
+ }
+ if excGomaxprocs && part[0] == '-' {
+ // Skip gomaxprocs.
+ continue outer
+ }
+ newName = append(newName, part...)
+ }
+ return newName
+}
+
+func extractNamePart(res *benchfmt.Result, prefix []byte, isGomaxprocs bool) []byte {
+ _, parts := res.Name.Parts()
+ if isGomaxprocs && len(parts) > 0 {
+ last := parts[len(parts)-1]
+ if last[0] == '-' {
+ // GOMAXPROCS specified as "-N" suffix.
+ return last[1:]
+ }
+ }
+ // Search for the prefix.
+ for _, part := range parts {
+ if bytes.HasPrefix(part, prefix) {
+ return part[len(prefix):]
+ }
+ }
+ // Not found.
+ return nil
+}
+
+func extractConfig(res *benchfmt.Result, key string) []byte {
+ pos, ok := res.ConfigIndex(key)
+ if !ok {
+ return nil
+ }
+ return res.Config[pos].Value
+}
diff --git a/benchproc/extract_test.go b/benchproc/extract_test.go
new file mode 100644
index 0000000..8b3fbc3
--- /dev/null
+++ b/benchproc/extract_test.go
@@ -0,0 +1,135 @@
+// 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 benchproc
+
+import (
+ "testing"
+
+ "golang.org/x/perf/benchfmt"
+)
+
+func checkNameExtractor(t *testing.T, x extractor, fullName string, want string) {
+ t.Helper()
+ res := &benchfmt.Result{Name: benchfmt.Name(fullName)}
+ got := string(x(res))
+ if got != want {
+ t.Errorf("got %s, want %s", got, want)
+ }
+}
+
+func TestExtractName(t *testing.T) {
+ check := checkNameExtractor
+
+ x, err := newExtractor(".name")
+ if err != nil {
+ t.Fatal(err)
+ }
+ check(t, x, "Test", "Test")
+ check(t, x, "Test/a", "Test")
+ check(t, x, "Test-4", "Test")
+ check(t, x, "Test/a-4", "Test")
+}
+
+func TestExtractFullName(t *testing.T) {
+ check := checkNameExtractor
+
+ t.Run("basic", func(t *testing.T) {
+ x, err := newExtractor(".fullname")
+ if err != nil {
+ t.Fatal(err)
+ }
+ check(t, x, "Test", "Test")
+ check(t, x, "Test/a=123", "Test/a=123")
+ check(t, x, "Test-2", "Test-2")
+ })
+
+ t.Run("excludeA", func(t *testing.T) {
+ x := newExtractorFullName([]string{"/a"})
+ check(t, x, "Test", "Test")
+ check(t, x, "Test/a=123", "Test")
+ check(t, x, "Test/b=123/a=123", "Test/b=123")
+ check(t, x, "Test/a=123/b=123", "Test/b=123")
+ check(t, x, "Test/a=123/a=123", "Test")
+ check(t, x, "Test/a=123-2", "Test-2")
+ })
+
+ t.Run("excludeName", func(t *testing.T) {
+ x := newExtractorFullName([]string{".name"})
+ check(t, x, "Test", "*")
+ check(t, x, "Test/a=123", "*/a=123")
+ x = newExtractorFullName([]string{".name", "/a"})
+ check(t, x, "Test", "*")
+ check(t, x, "Test/a=123", "*")
+ check(t, x, "Test/a=123/b=123", "*/b=123")
+ })
+
+ t.Run("excludeGomaxprocs", func(t *testing.T) {
+ x := newExtractorFullName([]string{"/gomaxprocs"})
+ check(t, x, "Test", "Test")
+ check(t, x, "Test/a=123", "Test/a=123")
+ check(t, x, "Test/a=123-2", "Test/a=123")
+ check(t, x, "Test/gomaxprocs=123", "Test")
+ })
+}
+
+func TestExtractNameKey(t *testing.T) {
+ check := checkNameExtractor
+
+ t.Run("basic", func(t *testing.T) {
+ x, err := newExtractor("/a")
+ if err != nil {
+ t.Fatal(err)
+ }
+ check(t, x, "Test", "")
+ check(t, x, "Test/a=1", "1")
+ check(t, x, "Test/aa=1", "")
+ check(t, x, "Test/a=1/b=2", "1")
+ check(t, x, "Test/b=1/a=2", "2")
+ check(t, x, "Test/b=1/a=2-4", "2")
+ })
+
+ t.Run("gomaxprocs", func(t *testing.T) {
+ x, err := newExtractor("/gomaxprocs")
+ if err != nil {
+ t.Fatal(err)
+ }
+ check(t, x, "Test", "")
+ check(t, x, "Test/gomaxprocs=4", "4")
+ check(t, x, "Test-4", "4")
+ check(t, x, "Test/a-4", "4")
+ })
+}
+
+func TestExtractFileKey(t *testing.T) {
+ x, err := newExtractor("file-key")
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ res := r(t, "Name", "file-key", "123", "other-key", "456")
+ got := string(x(res))
+ want := "123"
+ if got != want {
+ t.Errorf("got %s, want %s", got, want)
+ }
+
+ res = r(t, "Name", "other-key", "456")
+ got = string(x(res))
+ want = ""
+ if got != want {
+ t.Errorf("got %s, want %s", got, want)
+ }
+}
+
+func TestExtractBadKey(t *testing.T) {
+ check := func(t *testing.T, got error, want string) {
+ t.Helper()
+ if got == nil || got.Error() != want {
+ t.Errorf("got error %s, want error %s", got, want)
+ }
+ }
+ _, err := newExtractor("")
+ check(t, err, "key must not be empty")
+}
diff --git a/benchproc/filter.go b/benchproc/filter.go
new file mode 100644
index 0000000..7277b2b
--- /dev/null
+++ b/benchproc/filter.go
@@ -0,0 +1,282 @@
+// 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 benchproc
+
+import (
+ "fmt"
+
+ "golang.org/x/perf/benchfmt"
+ "golang.org/x/perf/benchproc/internal/parse"
+)
+
+// A Filter filters benchmarks and benchmark observations.
+type Filter struct {
+ // match is the filter function that implements this filter.
+ match filterFn
+}
+
+// filterFn is a filter function. If it matches individual measurements,
+// it returns a non-nil mask (and the bool result is ignored). If it
+// matches whole results, it returns a nil mask and a single boolean
+// match result.
+type filterFn func(res *benchfmt.Result) (mask, bool)
+
+// NewFilter constructs a result filter from a boolean filter
+// expression, such as ".name:Copy /size:4k". See "go doc
+// golang.org/x/perf/benchproc/syntax" for a description of filter
+// syntax.
+//
+// To create a filter that matches everything, pass "*" for query.
+func NewFilter(query string) (*Filter, error) {
+ q, err := parse.ParseFilter(query)
+ if err != nil {
+ return nil, err
+ }
+
+ // Recursively walk the filter expression, "compiling" it into
+ // a filterFn.
+ //
+ // We cache extractor functions since it's common to see the
+ // same key multiple times.
+ extractors := make(map[string]extractor)
+ var walk func(q parse.Filter) (filterFn, error)
+ walk = func(q parse.Filter) (filterFn, error) {
+ var err error
+ switch q := q.(type) {
+ case *parse.FilterOp:
+ subs := make([]filterFn, len(q.Exprs))
+ for i, sub := range q.Exprs {
+ subs[i], err = walk(sub)
+ if err != nil {
+ return nil, err
+ }
+ }
+ return filterOp(q.Op, subs), nil
+
+ case *parse.FilterMatch:
+ if q.Key == ".unit" {
+ return func(res *benchfmt.Result) (mask, bool) {
+ // Find the units this matches.
+ m := newMask(len(res.Values))
+ for i := range res.Values {
+ if q.MatchString(res.Values[i].Unit) || (res.Values[i].OrigUnit != "" && q.MatchString(res.Values[i].OrigUnit)) {
+ m.set(i)
+ }
+ }
+ return m, false
+ }, nil
+ }
+
+ if q.Key == ".config" {
+ return nil, &parse.SyntaxError{query, q.Off, ".config is only allowed in projections"}
+ }
+
+ // Construct the extractor.
+ ext := extractors[q.Key]
+ if ext == nil {
+ ext, err = newExtractor(q.Key)
+ if err != nil {
+ return nil, &parse.SyntaxError{query, q.Off, err.Error()}
+ }
+ extractors[q.Key] = ext
+ }
+
+ // Make the filter function.
+ return func(res *benchfmt.Result) (mask, bool) {
+ return nil, q.Match(ext(res))
+ }, nil
+ }
+ panic(fmt.Sprintf("unknown query node type %T", q))
+ }
+ f, err := walk(q)
+ if err != nil {
+ return nil, err
+ }
+ return &Filter{f}, nil
+}
+
+func filterOp(op parse.Op, subs []filterFn) filterFn {
+ switch op {
+ case parse.OpNot:
+ sub := subs[0]
+ return func(res *benchfmt.Result) (mask, bool) {
+ m, x := sub(res)
+ if m == nil {
+ return nil, !x
+ }
+ m.not()
+ return m, false
+ }
+
+ case parse.OpAnd:
+ return func(res *benchfmt.Result) (mask, bool) {
+ var m mask
+ for _, sub := range subs {
+ m2, x := sub(res)
+ if m2 == nil {
+ if !x {
+ // Short-circuit
+ return nil, false
+ }
+ } else if m == nil {
+ m = m2
+ } else {
+ m.and(m2)
+ }
+ }
+ return m, true
+ }
+
+ case parse.OpOr:
+ return func(res *benchfmt.Result) (mask, bool) {
+ var m mask
+ for _, sub := range subs {
+ m2, x := sub(res)
+ if m2 == nil {
+ if x {
+ // Short-circuit
+ return nil, true
+ }
+ } else if m == nil {
+ m = m2
+ } else {
+ m.or(m2)
+ }
+ }
+ return m, false
+ }
+ }
+ panic(fmt.Sprintf("unknown query op %v", op))
+}
+
+// Note: Right now the two methods below always return a nil error, but
+// the intent is to add more complicated types to projection expressions
+// (such as "commit") that may filter out results they can't parse with
+// an error (e.g., "unknown commit hash").
+
+// Apply rewrites res.Values to keep only the measurements that match
+// the Filter f and reports whether any measurements remain.
+//
+// Apply returns true if all or part of res.Values is kept by the filter.
+// Otherwise, it sets res.Values to an empty slice and returns false
+// to indicate res was completely filtered out.
+//
+// If Apply returns false, it may return a non-nil error
+// indicating why the result was filtered out.
+func (f *Filter) Apply(res *benchfmt.Result) (bool, error) {
+ m, err := f.Match(res)
+ return m.Apply(res), err
+}
+
+// Match returns the set of res.Values that match f.
+//
+// In contrast with the Apply method, this does not modify the Result.
+//
+// If the Match is empty, it may return a non-nil error
+// indicating why the result was filtered out.
+func (f *Filter) Match(res *benchfmt.Result) (Match, error) {
+ m, x := f.match(res)
+ return Match{len(res.Values), m, x}, nil
+}
+
+type mask []uint32
+
+func newMask(n int) mask {
+ return mask(make([]uint32, (n+31)/32))
+}
+
+func (m mask) set(i int) {
+ m[i/32] |= 1 << (i % 32)
+}
+
+func (m mask) and(n mask) {
+ for i := range m {
+ m[i] &= n[i]
+ }
+}
+
+func (m mask) or(n mask) {
+ for i := range m {
+ m[i] |= n[i]
+ }
+}
+
+func (m mask) not() {
+ for i := range m {
+ m[i] = ^m[i]
+ }
+}
+
+// A Match records the set of result measurements that matched a filter
+// query.
+type Match struct {
+ // n is the number of bits in this match.
+ n int
+
+ // m and x record the result of a filterFn. See filterFn for
+ // their meaning.
+ m mask
+ x bool
+}
+
+// All reports whether all measurements in a result matched the query.
+func (m *Match) All() bool {
+ if m.m == nil {
+ return m.x
+ }
+ for i, x := range m.m {
+ // Set all bits above m.n.
+ if x|(0xffffffff<<(m.n-i*32)) != 0xffffffff {
+ return false
+ }
+ }
+ return true
+}
+
+// Any reports whether any measurements in a result matched the query.
+func (m *Match) Any() bool {
+ if m.m == nil {
+ return m.x
+ }
+ for i, x := range m.m {
+ // Zero all bits above m.n.
+ if x&^(0xffffffff<<(m.n-i*32)) != 0 {
+ return true
+ }
+ }
+ return false
+}
+
+// Test reports whether measurement i of a result matched the query.
+func (m *Match) Test(i int) bool {
+ if i < 0 || i >= m.n {
+ return false
+ } else if m.m == nil {
+ return m.x
+ }
+ return m.m[i/32]&(1<<(i%32)) != 0
+}
+
+// Apply rewrites res.Values to keep only the measurements that match m.
+// It reports whether any Values remain.
+func (m *Match) Apply(res *benchfmt.Result) bool {
+ if m.All() {
+ return true
+ }
+ if !m.Any() {
+ res.Values = res.Values[:0]
+ return false
+ }
+
+ j := 0
+ for i, val := range res.Values {
+ if m.Test(i) {
+ res.Values[j] = val
+ j++
+ }
+ }
+ res.Values = res.Values[:j]
+ return j > 0
+}
diff --git a/benchproc/filter_test.go b/benchproc/filter_test.go
new file mode 100644
index 0000000..9fce3cf
--- /dev/null
+++ b/benchproc/filter_test.go
@@ -0,0 +1,132 @@
+// 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 benchproc
+
+import (
+ "fmt"
+ "testing"
+
+ "golang.org/x/perf/benchfmt"
+)
+
+func TestFilter(t *testing.T) {
+ res := r(t, "Name/n1=v3", "f1", "v1", "f2", "v2")
+ res.Values = []benchfmt.Value{
+ {100, "ns/op", 100e-9, "sec/op"},
+ {100, "B/op", 0, ""},
+ }
+ const ALL = 0b11
+ const NONE = 0
+
+ check := func(t *testing.T, query string, want uint) {
+ t.Helper()
+ f, err := NewFilter(query)
+ if err != nil {
+ t.Fatal(err)
+ }
+ m, _ := f.Match(res)
+ var got uint
+ for i := 0; i < 2; i++ {
+ if m.Test(i) {
+ got |= 1 << i
+ }
+ }
+ if got != want {
+ t.Errorf("%s: got %02b, want %02b", query, got, want)
+ } else if want == ALL && !m.All() {
+ t.Errorf("%s: want All", query)
+ } else if want == 0 && m.Any() {
+ t.Errorf("%s: want !Any", query)
+ }
+ }
+
+ t.Run("basic", func(t *testing.T) {
+ // File keys
+ check(t, "f1:v1", ALL)
+ check(t, "f1:v2", NONE)
+ // Name keys
+ check(t, "/n1:v3", ALL)
+ // Special keys
+ check(t, ".name:Name", ALL)
+ check(t, ".fullname:Name/n1=v3", ALL)
+ })
+
+ t.Run("units", func(t *testing.T) {
+ check(t, ".unit:ns/op", 0b01) // Base unit
+ check(t, ".unit:sec/op", 0b01) // Tidied unit
+ check(t, ".unit:B/op", 0b10)
+ check(t, ".unit:foo", 0b00)
+ })
+
+ t.Run("boolean", func(t *testing.T) {
+ check(t, "*", ALL)
+ check(t, "f1:v1 OR f1:v2", ALL)
+ check(t, "f1:v1 AND f1:v2", NONE)
+ check(t, "f1:v1 f1:v2", NONE)
+ check(t, "f1:v1 f2:v2", ALL)
+ check(t, "-f1:v1", NONE)
+ check(t, "--f1:v1", ALL)
+ check(t, ".unit:(ns/op OR B/op)", 0b11)
+ })
+
+ t.Run("manyUnits", func(t *testing.T) {
+ res := res.Clone()
+ res.Values = make([]benchfmt.Value, 100)
+ for i := range res.Values {
+ res.Values[i].Unit = fmt.Sprintf("u%d", i)
+ }
+ // Test large unit matches through all operators.
+ f, err := NewFilter("f1:v1 AND --(f1:v2 OR .unit:(u0 OR u99))")
+ if err != nil {
+ t.Fatal(err)
+ }
+ m, _ := f.Match(res)
+ for i := 0; i < 100; i++ {
+ got := m.Test(i)
+ want := i == 0 || i == 99
+ if got != want {
+ t.Errorf("for unit u%d, got %v, want %v", i, got, want)
+ }
+ }
+ })
+}
+
+func TestMatch(t *testing.T) {
+ check := func(m Match, all, any bool) {
+ t.Helper()
+ if m.All() != all {
+ t.Errorf("match %+v: All should be %v, got %v", m, all, !all)
+ }
+ if m.Any() != any {
+ t.Errorf("match %+v: Any should be %v, got %v", m, any, !any)
+ }
+ if m.Test(-1) {
+ t.Errorf("match %+v: Test(-1) should be false, got true", m)
+ }
+ if m.Test(m.n + 1) {
+ t.Errorf("match %+v: Test(%v) should be false, got true", m, m.n+1)
+ }
+ }
+
+ // Check nil mask.
+ m := Match{n: 4, x: false}
+ check(m, false, false)
+ m = Match{n: 4, x: true}
+ check(m, true, true)
+
+ // Check mask with some bits set.
+ m = Match{n: 4, m: []uint32{0x1}}
+ check(m, false, true)
+ m = Match{n: 1, m: []uint32{0x1}}
+ check(m, true, true)
+
+ // Check that we ignore zeroed bits above n.
+ m = Match{n: 4, m: []uint32{0xf}}
+ check(m, true, true)
+
+ // Check that we ignore set bits above n.
+ m = Match{n: 4, m: []uint32{0xfffffff0}}
+ check(m, false, false)
+}
diff --git a/benchproc/internal/parse/doc.go b/benchproc/internal/parse/doc.go
new file mode 100644
index 0000000..c995e34
--- /dev/null
+++ b/benchproc/internal/parse/doc.go
@@ -0,0 +1,10 @@
+// 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 parse implements parsers for golang.org/x/perf/benchproc/syntax.
+//
+// Currently this package is internal to benchproc, but if we ever
+// migrate perf.golang.org to this expression syntax, it will be
+// valuable to construct database queries from the same grammar.
+package parse
diff --git a/benchproc/internal/parse/filter.go b/benchproc/internal/parse/filter.go
new file mode 100644
index 0000000..d402111
--- /dev/null
+++ b/benchproc/internal/parse/filter.go
@@ -0,0 +1,146 @@
+// 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 parse
+
+import "strconv"
+
+// ParseFilter parses a filter expression into a Filter tree.
+func ParseFilter(q string) (Filter, error) {
+ toks := newTokenizer(q)
+ p := parser{}
+ query, toks := p.expr(toks)
+ toks.end()
+ if toks.errt.err != nil {
+ return nil, toks.errt.err
+ }
+ return query, nil
+}
+
+type parser struct{}
+
+func (p *parser) error(toks tokenizer, msg string) tokenizer {
+ _, toks = toks.error(msg)
+ return toks
+}
+
+func (p *parser) expr(toks tokenizer) (Filter, tokenizer) {
+ var terms []Filter
+ for {
+ var q Filter
+ q, toks = p.andExpr(toks)
+ terms = append(terms, q)
+ op, toks2 := toks.keyOrOp()
+ if op.Kind != 'O' {
+ break
+ }
+ toks = toks2
+ }
+ if len(terms) == 1 {
+ return terms[0], toks
+ }
+ return &FilterOp{OpOr, terms}, toks
+}
+
+func (p *parser) andExpr(toks tokenizer) (Filter, tokenizer) {
+ var q Filter
+ q, toks = p.match(toks)
+ terms := []Filter{q}
+loop:
+ for {
+ op, toks2 := toks.keyOrOp()
+ switch op.Kind {
+ case 'A':
+ // "AND" between matches is the same as no
+ // operator. Skip.
+ toks = toks2
+ continue
+ case '(', '-', '*', 'w', 'q':
+ q, toks = p.match(toks)
+ terms = append(terms, q)
+ case ')', 'O', 0:
+ break loop
+ default:
+ return nil, p.error(toks, "unexpected "+strconv.Quote(op.Tok))
+ }
+ }
+ if len(terms) == 1 {
+ return terms[0], toks
+ }
+ return &FilterOp{OpAnd, terms}, toks
+}
+
+func (p *parser) match(start tokenizer) (Filter, tokenizer) {
+ tok, rest := start.keyOrOp()
+ switch tok.Kind {
+ case '(':
+ q, rest := p.expr(rest)
+ op, toks2 := rest.keyOrOp()
+ if op.Kind != ')' {
+ return nil, p.error(rest, "missing \")\"")
+ }
+ return q, toks2
+ case '-':
+ q, rest := p.match(rest)
+ q = &FilterOp{OpNot, []Filter{q}}
+ return q, rest
+ case '*':
+ q := &FilterOp{OpAnd, nil}
+ return q, rest
+ case 'w', 'q':
+ off := tok.Off
+ key := tok.Tok
+ op, toks2 := rest.keyOrOp()
+ if op.Kind != ':' {
+ // TODO: Support other operators
+ return nil, p.error(start, "expected key:value")
+ }
+ rest = toks2
+ val, rest := rest.valueOrOp()
+ switch val.Kind {
+ default:
+ return nil, p.error(start, "expected key:value")
+ case 'w', 'q', 'r':
+ return p.mkMatch(off, key, val), rest
+ case '(':
+ var terms []Filter
+ for {
+ val, toks2 := rest.valueOrOp()
+ switch val.Kind {
+ default:
+ return nil, p.error(rest, "expected value")
+ case 'w', 'q', 'r':
+ terms = append(terms, p.mkMatch(off, key, val))
+ }
+ rest = toks2
+
+ // Consume "OR" or ")"
+ val, toks2 = rest.valueOrOp()
+ switch val.Kind {
+ default:
+ return nil, p.error(rest, "value list must be separated by OR")
+ case ')':
+ return &FilterOp{OpOr, terms}, toks2
+ case 'O':
+ // Do nothing
+ }
+ rest = toks2
+ }
+ }
+ }
+ return nil, p.error(start, "expected key:value or subexpression")
+}
+
+func (p *parser) mkMatch(off int, key string, val tok) Filter {
+ switch val.Kind {
+ case 'w', 'q':
+ // Literal match.
+ return &FilterMatch{key, nil, val.Tok, off}
+ case 'r':
+ // Regexp match.
+ return &FilterMatch{key, val.Regexp, "", off}
+ default:
+ panic("non-word token")
+ }
+}
diff --git a/benchproc/internal/parse/filter_test.go b/benchproc/internal/parse/filter_test.go
new file mode 100644
index 0000000..bf35aec
--- /dev/null
+++ b/benchproc/internal/parse/filter_test.go
@@ -0,0 +1,74 @@
+// 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 parse
+
+import "testing"
+
+func TestParseFilter(t *testing.T) {
+ check := func(query string, want string) {
+ t.Helper()
+ q, err := ParseFilter(query)
+ if err != nil {
+ t.Errorf("%s: unexpected error %s", query, err)
+ } else if got := q.String(); got != want {
+ t.Errorf("%s: got %s, want %s", query, got, want)
+ }
+ }
+ checkErr := func(query, error string, pos int) {
+ t.Helper()
+ _, err := ParseFilter(query)
+ if se, _ := err.(*SyntaxError); se == nil || se.Msg != error || se.Off != pos {
+ t.Errorf("%s: want error %s at %d; got %s", query, error, pos, err)
+ }
+ }
+ check(`*`, `*`)
+ check(`a:b`, `a:b`)
+ checkErr(`a`, "expected key:value", 0)
+ checkErr(`a :`, "expected key:value", 0)
+ check(`a :b`, `a:b`)
+ check(`a : b`, `a:b`)
+ checkErr(`a:`, "expected key:value", 0)
+ checkErr(``, "expected key:value or subexpression", 0)
+ checkErr(`()`, "expected key:value or subexpression", 1)
+ checkErr(`AND`, "expected key:value or subexpression", 0)
+ check(`"a":"b c"`, `a:"b c"`)
+ check(`"a\"":"b c"`, `"a\"":"b c"`)
+ check(`"a\u2603":"b c"`, `a☃:"b c"`)
+ checkErr(`"a\z":"b c"`, "bad escape sequence", 0)
+ checkErr(`a "b`, "missing end quote", 2)
+ check("a-b:c", `a-b:c`) // "-" inside bare word
+ check("a*b:c", `a*b:c`) // "*" inside bare word
+
+ // Parens
+ check(`(a:b)`, `a:b`)
+ checkErr(`(a:b`, "missing \")\"", 4)
+ checkErr(`(a:b))`, "unexpected \")\"", 5)
+
+ // Operators
+ check(`a:b c:d e:f`, `(a:b AND c:d AND e:f)`)
+ check(`-a:b`, `-a:b`)
+ check(`-*`, `-*`)
+ check(`a:b AND c:d`, `(a:b AND c:d)`)
+ check(`-a:b AND c:d`, `(-a:b AND c:d)`)
+ check(`-(a:b AND c:d)`, `-(a:b AND c:d)`)
+ check(`a:b AND * AND c:d`, `(a:b AND * AND c:d)`)
+ check(`a:b OR c:d`, `(a:b OR c:d)`)
+ check(`a:b AND c:d OR e:f AND g:h`, `((a:b AND c:d) OR (e:f AND g:h))`)
+ check(`a:b AND (c:d OR e:f) AND g:h`, `(a:b AND (c:d OR e:f) AND g:h)`)
+
+ // Regexp match
+ checkErr("a:/b", "missing close \"/\"", 2)
+ checkErr("a:/[[:foo:]]/", "error parsing regexp: invalid character class range: `[:foo:]`", 2)
+ checkErr("a:/b/c", "regexp must be followed by space or an operator (unescaped \"/\"?)", 5)
+ check("a:/b[/](/)\\/c/", "a:/b[/](/)\\/c/")
+
+ // Multi-match
+ check(`a:(b OR c OR d)`, `(a:b OR a:c OR a:d)`)
+ check(`a:(b OR "c " OR /d/)`, `(a:b OR a:"c " OR a:/d/)`)
+ checkErr(`a:(b c)`, "value list must be separated by OR", 5)
+ checkErr(`a:(b AND c)`, "value list must be separated by OR", 5)
+ checkErr(`a:(b OR AND)`, "expected value", 8)
+ checkErr(`a:()`, "expected value", 3)
+}
diff --git a/benchproc/internal/parse/projection.go b/benchproc/internal/parse/projection.go
new file mode 100644
index 0000000..f9192d8
--- /dev/null
+++ b/benchproc/internal/parse/projection.go
@@ -0,0 +1,134 @@
+// 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 parse
+
+import (
+ "fmt"
+ "strings"
+)
+
+// A Field is one element in a projection expression. It represents
+// extracting a single dimension of a benchmark result and applying an
+// order to it.
+type Field struct {
+ Key string
+
+ // Order is the sort order for this field. This can be
+ // "first", meaning to sort by order of first appearance;
+ // "fixed", meaning to use the explicit value order in Fixed;
+ // or a named sort order.
+ Order string
+
+ // Fixed gives the explicit value order for "fixed" ordering.
+ // If a record's value is not in this list, the record should
+ // be filtered out. Otherwise, values should be sorted
+ // according to their order in this list.
+ Fixed []string
+
+ // KeyOff and OrderOff give the byte offsets of the key and
+ // order, for error reporting.
+ KeyOff, OrderOff int
+}
+
+// String returns Projection as a valid projection expression.
+func (p Field) String() string {
+ switch p.Order {
+ case "first":
+ return quoteWord(p.Key)
+ case "fixed":
+ words := make([]string, 0, len(p.Fixed))
+ for _, word := range p.Fixed {
+ words = append(words, quoteWord(word))
+ }
+ return fmt.Sprintf("%s@(%s)", quoteWord(p.Key), strings.Join(words, " "))
+ }
+ return fmt.Sprintf("%s@%s", quoteWord(p.Key), quoteWord(p.Order))
+}
+
+// ParseProjection parses a projection expression into a tuple of
+// Fields.
+func ParseProjection(q string) ([]Field, error) {
+ // Parse each projection field.
+ var fields []Field
+ toks := newTokenizer(q)
+ for {
+ // Peek at the next token.
+ tok, toks2 := toks.keyOrOp()
+ if tok.Kind == 0 {
+ // No more fields.
+ break
+ } else if tok.Kind == ',' && len(fields) > 0 {
+ // Consume optional separating comma.
+ toks = toks2
+ }
+
+ var f Field
+ f, toks = parseField(toks)
+ fields = append(fields, f)
+ }
+ toks.end()
+ if toks.errt.err != nil {
+ return nil, toks.errt.err
+ }
+ return fields, nil
+}
+
+func parseField(toks tokenizer) (Field, tokenizer) {
+ var f Field
+
+ // Consume key.
+ key, toks2 := toks.keyOrOp()
+ if !(key.Kind == 'w' || key.Kind == 'q') {
+ _, toks = toks.error("expected key")
+ return f, toks
+ }
+ toks = toks2
+ f.Key = key.Tok
+ f.KeyOff = key.Off
+
+ // Consume optional sort order.
+ f.Order = "first"
+ f.OrderOff = key.Off + len(key.Tok)
+ sep, toks2 := toks.keyOrOp()
+ if sep.Kind != '@' {
+ // No sort order.
+ return f, toks
+ }
+ toks = toks2
+
+ // Is it a named sort order?
+ order, toks2 := toks.keyOrOp()
+ f.OrderOff = order.Off
+ if order.Kind == 'w' || order.Kind == 'q' {
+ f.Order = order.Tok
+ return f, toks2
+ }
+ // Or a fixed sort order?
+ if order.Kind == '(' {
+ f.Order = "fixed"
+ toks = toks2
+ for {
+ t, toks2 := toks.keyOrOp()
+ if t.Kind == 'w' || t.Kind == 'q' {
+ toks = toks2
+ f.Fixed = append(f.Fixed, t.Tok)
+ } else if t.Kind == ')' {
+ if len(f.Fixed) == 0 {
+ _, toks = toks.error("nothing to match")
+ } else {
+ toks = toks2
+ }
+ break
+ } else {
+ _, toks = toks.error("missing )")
+ break
+ }
+ }
+ return f, toks
+ }
+ // Bad sort order syntax.
+ _, toks = toks.error("expected named sort order or parenthesized list")
+ return f, toks
+}
diff --git a/benchproc/internal/parse/projection_test.go b/benchproc/internal/parse/projection_test.go
new file mode 100644
index 0000000..36ee716
--- /dev/null
+++ b/benchproc/internal/parse/projection_test.go
@@ -0,0 +1,52 @@
+// 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 parse
+
+import (
+ "reflect"
+ "testing"
+)
+
+func TestParseProjection(t *testing.T) {
+ check := func(proj string, want ...string) {
+ t.Helper()
+ p, err := ParseProjection(proj)
+ if err != nil {
+ t.Errorf("%s: unexpected error %s", proj, err)
+ return
+ }
+ var got []string
+ for _, part := range p {
+ got = append(got, part.String())
+ }
+ if !reflect.DeepEqual(got, want) {
+ t.Errorf("%s: got %v, want %v", proj, got, want)
+ }
+ }
+ checkErr := func(proj, error string, pos int) {
+ t.Helper()
+ _, err := ParseProjection(proj)
+ if se, _ := err.(*SyntaxError); se == nil || se.Msg != error || se.Off != pos {
+ t.Errorf("%s: want error %s at %d; got %s", proj, error, pos, err)
+ }
+ }
+
+ check("")
+ check("a,b", "a", "b")
+ check("a, b", "a", "b")
+ check("a b", "a", "b")
+ checkErr("a,,b", "expected key", 2)
+ check("a,.name", "a", ".name")
+ check("a,/b", "a", "/b")
+
+ check("a@alpha, b@num", "a@alpha", "b@num")
+ checkErr("a@", "expected named sort order or parenthesized list", 2)
+ checkErr("a@,b", "expected named sort order or parenthesized list", 2)
+
+ check("a@(1 2), b@(3 4)", "a@(1 2)", "b@(3 4)")
+ checkErr("a@(", "missing )", 3)
+ checkErr("a@(,", "missing )", 3)
+ checkErr("a@()", "nothing to match", 3)
+}
diff --git a/benchproc/internal/parse/tok.go b/benchproc/internal/parse/tok.go
new file mode 100644
index 0000000..01c2b27
--- /dev/null
+++ b/benchproc/internal/parse/tok.go
@@ -0,0 +1,263 @@
+// 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 parse
+
+import (
+ "errors"
+ "fmt"
+ "regexp"
+ "strconv"
+ "strings"
+ "unicode"
+ "unicode/utf8"
+)
+
+// A SyntaxError is an error produced by parsing a malformed expression.
+type SyntaxError struct {
+ Query string // The original query string
+ Off int // Byte offset of the error in Query
+ Msg string // Error message
+}
+
+func (e *SyntaxError) Error() string {
+ // Translate byte offset to a rune offset.
+ pos := 0
+ for i, r := range e.Query {
+ if i >= e.Off {
+ break
+ }
+ if unicode.IsGraphic(r) {
+ pos++
+ }
+ }
+ return fmt.Sprintf("syntax error: %s\n\t%s\n\t%*s^", e.Msg, e.Query, pos, "")
+}
+
+type errorTracker struct {
+ qOrig string
+ err *SyntaxError
+}
+
+func (t *errorTracker) error(q string, msg string) {
+ off := len(t.qOrig) - len(q)
+ if t.err == nil {
+ t.err = &SyntaxError{t.qOrig, off, msg}
+ }
+}
+
+// A tok is a single token in the filter/projection lexical syntax.
+type tok struct {
+ // Kind specifies the category of this token. It is either 'w'
+ // or 'q' for an unquoted or quoted word, respectively, 'r'
+ // for a regexp, an operator character, or 0 for the
+ // end-of-string token.
+ Kind byte
+ Off int // Byte offset of the beginning of this token
+ Tok string // Literal token contents; quoted words are unescaped
+ Regexp *regexp.Regexp
+}
+
+type tokenizer struct {
+ q string
+ errt *errorTracker
+}
+
+func newTokenizer(q string) tokenizer {
+ return tokenizer{q, &errorTracker{q, nil}}
+}
+
+func isOp(ch rune) bool {
+ return ch == '(' || ch == ')' || ch == ':' || ch == '@' || ch == ','
+}
+
+// At the beginning of a word, we accept "-" and "*" as operators,
+// but in the middle of words we treat them as part of the word.
+func isStartOp(ch rune) bool {
+ return isOp(ch) || ch == '-' || ch == '*'
+}
+
+func isSpace(q string) int {
+ if q[0] == ' ' {
+ return 1
+ }
+ r, size := utf8.DecodeRuneInString(q)
+ if unicode.IsSpace(r) {
+ return size
+ }
+ return 0
+}
+
+// keyOrOp returns the next key or operator token.
+// A key may be a bare word or a quoted word.
+func (t *tokenizer) keyOrOp() (tok, tokenizer) {
+ return t.next(false)
+}
+
+// valueOrOp returns the next value or operator token.
+// A value may be a bare word, a quoted word, or a regexp.
+func (t *tokenizer) valueOrOp() (tok, tokenizer) {
+ return t.next(true)
+}
+
+// end asserts that t has reached the end of the token stream. If it
+// has not, it returns a tokenizer the reports an error.
+func (t *tokenizer) end() tokenizer {
+ if tok, _ := t.keyOrOp(); tok.Kind != 0 {
+ _, t2 := t.error("unexpected " + strconv.Quote(tok.Tok))
+ return t2
+ }
+ return *t
+}
+
+func (t *tokenizer) next(allowRegexp bool) (tok, tokenizer) {
+ for len(t.q) > 0 {
+ if isStartOp(rune(t.q[0])) {
+ return t.tok(t.q[0], t.q[:1], t.q[1:])
+ } else if n := isSpace(t.q); n > 0 {
+ t.q = t.q[n:]
+ } else if allowRegexp && t.q[0] == '/' {
+ return t.regexp()
+ } else if t.q[0] == '"' {
+ return t.quotedWord()
+ } else {
+ return t.bareWord()
+ }
+ }
+ // Add an EOF token. This eliminates the need for lots of
+ // bounds checks in the parser and gives the EOF a position.
+ return t.tok(0, "", "")
+}
+
+func (t *tokenizer) tok(kind byte, token string, rest string) (tok, tokenizer) {
+ off := len(t.errt.qOrig) - len(t.q)
+ return tok{kind, off, token, nil}, tokenizer{rest, t.errt}
+}
+
+func (t *tokenizer) error(msg string) (tok, tokenizer) {
+ t.errt.error(t.q, msg)
+ // Move to the end.
+ return t.tok(0, "", "")
+}
+
+func (t *tokenizer) quotedWord() (tok, tokenizer) {
+ pos := 1 // Skip initial "
+ for pos < len(t.q) && (t.q[pos] != '"' || t.q[pos-1] == '\\') {
+ pos++
+ }
+ if pos == len(t.q) {
+ return t.error("missing end quote")
+ }
+ // Parse the quoted string.
+ word, err := strconv.Unquote(t.q[:pos+1])
+ if err != nil {
+ return t.error("bad escape sequence")
+ }
+ return t.tok('q', word, t.q[pos+1:])
+}
+
+func (t *tokenizer) bareWord() (tok, tokenizer) {
+ // Consume until a space or operator. We only take "-"
+ // as an operator immediately following another space
+ // or operator so things like "foo-bar" work as
+ // expected.
+ end := len(t.q)
+ for i, r := range t.q {
+ if unicode.IsSpace(r) || isOp(r) {
+ end = i
+ break
+ }
+ }
+ word := t.q[:end]
+ if word == "AND" {
+ return t.tok('A', word, t.q[end:])
+ } else if word == "OR" {
+ return t.tok('O', word, t.q[end:])
+ }
+ return t.tok('w', word, t.q[end:])
+}
+
+// quoteWord returns a string that tokenizes as the word s.
+func quoteWord(s string) string {
+ if len(s) == 0 {
+ return `""`
+ }
+ for i, r := range s {
+ switch r {
+ case '"', ' ', '\a', '\b':
+ return strconv.Quote(s)
+ }
+ if isOp(r) || unicode.IsSpace(r) || (i == 0 && (r == '-' || r == '*')) {
+ return strconv.Quote(s)
+ }
+ }
+ // No quoting necessary.
+ return s
+}
+
+func (t *tokenizer) regexp() (tok, tokenizer) {
+ expr, rest, err := regexpParseUntil(t.q[1:], "/")
+ if err == errNoDelim {
+ return t.error("missing close \"/\"")
+ } else if err != nil {
+ return t.error(err.Error())
+ }
+
+ r, err := regexp.Compile(expr)
+ if err != nil {
+ return t.error(err.Error())
+ }
+
+ // To avoid confusion when "/" appears in the regexp itself,
+ // we require space or an operator after the close "/".
+ q2 := rest[1:]
+ if !(q2 == "" || unicode.IsSpace(rune(q2[0])) || isStartOp(rune(q2[0]))) {
+ t.q = q2
+ return t.error("regexp must be followed by space or an operator (unescaped \"/\"?)")
+ }
+
+ tok, next := t.tok('r', expr, q2)
+ tok.Regexp = r
+ return tok, next
+}
+
+var errNoDelim = errors.New("unterminated regexp")
+
+// regexpParseUntil parses a regular expression from the beginning of str
+// until the string delim appears at the top level of the expression.
+// It returns the regular expression prefix of str and the remainder of str.
+// If successful, rest will always begin with delim.
+// If delim does not appear at the top level of str, it returns str, "", errNoDelim.
+//
+// TODO: There are corner cases this doesn't get right. Replace it
+// with a standard library call if #44254 is implemented.
+func regexpParseUntil(str, delim string) (expr, rest string, err error) {
+ cs := 0
+ cp := 0
+ for i := 0; i < len(str); {
+ if cs == 0 && cp == 0 && strings.HasPrefix(str[i:], delim) {
+ return str[:i], str[i:], nil
+ }
+ switch str[i] {
+ case '[':
+ cs++
+ case ']':
+ if cs--; cs < 0 { // An unmatched ']' is legal.
+ cs = 0
+ }
+ case '(':
+ if cs == 0 {
+ cp++
+ }
+ case ')':
+ if cs == 0 {
+ cp--
+ }
+ case '\\':
+ i++
+ }
+ i++
+ }
+ return str, "", errNoDelim
+}
diff --git a/benchproc/internal/parse/tree.go b/benchproc/internal/parse/tree.go
new file mode 100644
index 0000000..d71467e
--- /dev/null
+++ b/benchproc/internal/parse/tree.go
@@ -0,0 +1,105 @@
+// 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 parse
+
+import (
+ "fmt"
+ "regexp"
+ "strings"
+)
+
+// A Filter is a node in the boolean filter. It can either be a
+// FilterOp or a FilterMatch.
+type Filter interface {
+ isFilter()
+ String() string
+}
+
+// A FilterMatch is a leaf in a Filter tree that tests a specific key
+// for a match.
+type FilterMatch struct {
+ Key string
+
+ // Regexp is the regular expression to match against the
+ // value. This may be nil, in which case this is a literal
+ // match against Lit.
+ Regexp *regexp.Regexp
+ // Lit is the literal value to match against the value if Regexp
+ // is nil.
+ Lit string
+
+ // Off is the byte offset of the key in the original query,
+ // for error reporting.
+ Off int
+}
+
+func (q *FilterMatch) isFilter() {}
+func (q *FilterMatch) String() string {
+ if q.Regexp != nil {
+ return quoteWord(q.Key) + ":/" + q.Regexp.String() + "/"
+ }
+ return quoteWord(q.Key) + ":" + quoteWord(q.Lit)
+}
+
+// Match returns whether q matches the given value of q.Key.
+func (q *FilterMatch) Match(value []byte) bool {
+ if q.Regexp != nil {
+ return q.Regexp.Match(value)
+ }
+ return q.Lit == string(value)
+}
+
+// MatchString returns whether q matches the given value of q.Key.
+func (q *FilterMatch) MatchString(value string) bool {
+ if q.Regexp != nil {
+ return q.Regexp.MatchString(value)
+ }
+ return q.Lit == value
+}
+
+// A FilterOp is a boolean operator in the Filter tree. OpNot must have
+// exactly one child node. OpAnd and OpOr may have zero or more child nodes.
+type FilterOp struct {
+ Op Op
+ Exprs []Filter
+}
+
+func (q *FilterOp) isFilter() {}
+func (q *FilterOp) String() string {
+ var op string
+ switch q.Op {
+ case OpNot:
+ return fmt.Sprintf("-%s", q.Exprs[0])
+ case OpAnd:
+ if len(q.Exprs) == 0 {
+ return "*"
+ }
+ op = " AND "
+ case OpOr:
+ if len(q.Exprs) == 0 {
+ return "-*"
+ }
+ op = " OR "
+ }
+ var buf strings.Builder
+ buf.WriteByte('(')
+ for i, e := range q.Exprs {
+ if i > 0 {
+ buf.WriteString(op)
+ }
+ buf.WriteString(e.String())
+ }
+ buf.WriteByte(')')
+ return buf.String()
+}
+
+// Op specifies a type of boolean operator.
+type Op int
+
+const (
+ OpAnd Op = 1 + iota
+ OpOr
+ OpNot
+)
diff --git a/benchproc/key.go b/benchproc/key.go
new file mode 100644
index 0000000..32f47cc
--- /dev/null
+++ b/benchproc/key.go
@@ -0,0 +1,126 @@
+// 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 benchproc
+
+import "strings"
+
+// A Key is an immutable tuple mapping from Fields to strings whose
+// structure is given by a Projection. Two Keys are == if they come
+// from the same Projection and have identical values.
+type Key struct {
+ k *keyNode
+}
+
+// IsZero reports whether k is a zeroed Key with no projection and no fields.
+func (k Key) IsZero() bool {
+ return k.k == nil
+}
+
+// Get returns the value of Field f in this Key.
+//
+// It panics if Field f does not come from the same Projection as the
+// Key or if f is a tuple Field.
+func (k Key) Get(f *Field) string {
+ if k.IsZero() {
+ panic("zero Key has no fields")
+ }
+ if k.k.proj != f.proj {
+ panic("Key and Field have different Projections")
+ }
+ if f.IsTuple {
+ panic(f.Name + " is a tuple field")
+ }
+ idx := f.idx
+ if idx >= len(k.k.vals) {
+ return ""
+ }
+ return k.k.vals[idx]
+}
+
+// Projection returns the Projection describing Key k.
+func (k Key) Projection() *Projection {
+ if k.IsZero() {
+ return nil
+ }
+ return k.k.proj
+}
+
+// String returns Key as a space-separated sequence of key:value
+// pairs in field order.
+func (k Key) String() string {
+ return k.string(true)
+}
+
+// StringValues returns Key as a space-separated sequences of
+// values in field order.
+func (k Key) StringValues() string {
+ return k.string(false)
+}
+
+func (k Key) string(keys bool) string {
+ if k.IsZero() {
+ return "<zero>"
+ }
+ buf := new(strings.Builder)
+ for _, field := range k.k.proj.FlattenedFields() {
+ if field.idx >= len(k.k.vals) {
+ continue
+ }
+ val := k.k.vals[field.idx]
+ if val == "" {
+ continue
+ }
+ if buf.Len() > 0 {
+ buf.WriteByte(' ')
+ }
+ if keys {
+ buf.WriteString(field.Name)
+ buf.WriteByte(':')
+ }
+ buf.WriteString(val)
+ }
+ return buf.String()
+}
+
+// commonProjection returns the Projection that all Keys have, or panics if any
+// Key has a different Projection. It returns nil if len(keys) == 0.
+func commonProjection(keys []Key) *Projection {
+ if len(keys) == 0 {
+ return nil
+ }
+ s := keys[0].Projection()
+ for _, k := range keys[1:] {
+ if k.Projection() != s {
+ panic("Keys must all have the same Projection")
+ }
+ }
+ return s
+}
+
+// keyNode is the internal heap-allocated object backing a Key.
+// This allows Key itself to be a value type whose equality is
+// determined by the pointer equality of the underlying keyNode.
+type keyNode struct {
+ proj *Projection
+ // vals are the values in this Key, indexed by fieldInternal.idx. Trailing
+ // ""s are always trimmed.
+ //
+ // Notably, this is *not* in the order of the flattened schema. This is
+ // because fields can be added in the middle of a schema on-the-fly, and we
+ // need to not invalidate existing Keys.
+ vals []string
+}
+
+func (n *keyNode) equalRow(row []string) bool {
+ if len(n.vals) != len(row) {
+ return false
+ }
+ for i, v := range n.vals {
+ if row[i] != v {
+ return false
+ }
+ }
+ return true
+}
diff --git a/benchproc/keyheader.go b/benchproc/keyheader.go
new file mode 100644
index 0000000..42ee375
--- /dev/null
+++ b/benchproc/keyheader.go
@@ -0,0 +1,102 @@
+// 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 benchproc
+
+// A KeyHeader represents a slice of Keys, combined into a forest of
+// trees by common Field values. This is intended to visually present a
+// sequence of Keys in a compact form; primarily, as a header on a
+// table.
+//
+// All Keys must have the same Projection. The levels of the tree
+// correspond to the Fields of the Projection, and the depth of the tree
+// is exactly the number of Fields. A node at level i represents a
+// subslice of the Keys that all have the same values as each other for
+// fields 0 through i.
+//
+// For example, given four keys:
+//
+// K[0] = a:1 b:1 c:1
+// K[1] = a:1 b:1 c:2
+// K[2] = a:2 b:2 c:2
+// K[3] = a:2 b:3 c:3
+//
+// the KeyHeader is as follows:
+//
+// Level 0 a:1 a:2
+// | / \
+// Level 1 b:1 b:2 b:3
+// / \ | |
+// Level 2 c:1 c:2 c:2 c:3
+// K[0] K[1] K[2] K[3]
+type KeyHeader struct {
+ // Keys is the sequence of keys at the leaf level of this tree.
+ // Each level subdivides this sequence.
+ Keys []Key
+
+ // Levels are the labels for each level of the tree. Level i of the
+ // tree corresponds to the i'th field of all Keys.
+ Levels []*Field
+
+ // Top is the list of tree roots. These nodes are all at level 0.
+ Top []*KeyHeaderNode
+}
+
+// KeyHeaderNode is a node in a KeyHeader.
+type KeyHeaderNode struct {
+ // Field is the index into KeyHeader.Levels of the Field represented
+ // by this node. This is also the level of this node in the tree,
+ // starting with 0 at the top.
+ Field int
+
+ // Value is the value that all Keys have in common for Field.
+ Value string
+
+ // Start is the index of the first Key covered by this node.
+ Start int
+ // Len is the number of Keys in the sequence represented by this node.
+ // This is also the number of leaf nodes in the subtree at this node.
+ Len int
+
+ // Children are the children of this node. These are all at level Field+1.
+ // Child i+1 differs from child i in the value of field Field+1.
+ Children []*KeyHeaderNode
+}
+
+// NewKeyHeader computes the KeyHeader of a slice of Keys by combining
+// common prefixes of fields.
+func NewKeyHeader(keys []Key) *KeyHeader {
+ if len(keys) == 0 {
+ return &KeyHeader{}
+ }
+
+ fields := commonProjection(keys).FlattenedFields()
+
+ var walk func(parent *KeyHeaderNode)
+ walk = func(parent *KeyHeaderNode) {
+ level := parent.Field + 1
+ if level == len(fields) {
+ return
+ }
+ field := fields[level]
+ var node *KeyHeaderNode
+ for j, key := range keys[parent.Start : parent.Start+parent.Len] {
+ val := key.Get(field)
+ if node != nil && val == node.Value {
+ // Add this key to the current node.
+ node.Len++
+ } else {
+ // Start a new node.
+ node = &KeyHeaderNode{level, val, parent.Start + j, 1, nil}
+ parent.Children = append(parent.Children, node)
+ }
+ }
+ for _, child := range parent.Children {
+ walk(child)
+ }
+ }
+ root := &KeyHeaderNode{-1, "", 0, len(keys), nil}
+ walk(root)
+ return &KeyHeader{keys, fields, root.Children}
+}
diff --git a/benchproc/keyheader_test.go b/benchproc/keyheader_test.go
new file mode 100644
index 0000000..ed4e3e5
--- /dev/null
+++ b/benchproc/keyheader_test.go
@@ -0,0 +1,118 @@
+// 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 benchproc
+
+import (
+ "fmt"
+ "strings"
+ "testing"
+)
+
+func checkKeyHeader(t *testing.T, tree *KeyHeader, want string) {
+ t.Helper()
+ got := renderKeyHeader(tree)
+ if got != want {
+ t.Errorf("want %s\ngot %s", want, got)
+ }
+
+ // Check the structure of the tree.
+ prevEnd := make([]int, len(tree.Levels))
+ var walk func(int, *KeyHeaderNode)
+ walk = func(level int, n *KeyHeaderNode) {
+ if n.Field != level {
+ t.Errorf("want level %d, got %d", level, n.Field)
+ }
+ if n.Start != prevEnd[level] {
+ t.Errorf("want start %d, got %d", prevEnd[level], n.Start)
+ }
+ prevEnd[level] = n.Start + n.Len
+ for _, sub := range n.Children {
+ walk(level+1, sub)
+ }
+ }
+ for _, n := range tree.Top {
+ walk(0, n)
+ }
+ // Check that we walked the full span of keys on each level.
+ for level, width := range prevEnd {
+ if width != len(tree.Keys) {
+ t.Errorf("want width %d, got %d at level %d", len(tree.Keys), width, level)
+ }
+ }
+}
+
+func renderKeyHeader(t *KeyHeader) string {
+ buf := new(strings.Builder)
+ var walk func([]*KeyHeaderNode)
+ walk = func(ns []*KeyHeaderNode) {
+ for _, n := range ns {
+ fmt.Fprintf(buf, "\n%s%s:%s", strings.Repeat("\t", n.Field), t.Levels[n.Field], n.Value)
+ walk(n.Children)
+ }
+ }
+ walk(t.Top)
+ return buf.String()
+}
+
+func TestKeyHeader(t *testing.T) {
+ // Test basic merging.
+ t.Run("basic", func(t *testing.T) {
+ s, _ := mustParse(t, ".config")
+ c1 := p(t, s, "", "a", "a1", "b", "b1")
+ c2 := p(t, s, "", "a", "a1", "b", "b2")
+ tree := NewKeyHeader([]Key{c1, c2})
+ checkKeyHeader(t, tree, `
+a:a1
+ b:b1
+ b:b2`)
+ })
+
+ // Test that higher level differences prevent lower levels
+ // from being merged, even if the lower levels match.
+ t.Run("noMerge", func(t *testing.T) {
+ s, _ := mustParse(t, ".config")
+ c1 := p(t, s, "", "a", "a1", "b", "b1")
+ c2 := p(t, s, "", "a", "a2", "b", "b1")
+ tree := NewKeyHeader([]Key{c1, c2})
+ checkKeyHeader(t, tree, `
+a:a1
+ b:b1
+a:a2
+ b:b1`)
+ })
+
+ // Test mismatched tuple lengths.
+ t.Run("missingValues", func(t *testing.T) {
+ s, _ := mustParse(t, ".config")
+ c1 := p(t, s, "", "a", "a1")
+ c2 := p(t, s, "", "a", "a1", "b", "b1")
+ c3 := p(t, s, "", "a", "a1", "b", "b1", "c", "c1")
+ tree := NewKeyHeader([]Key{c1, c2, c3})
+ checkKeyHeader(t, tree, `
+a:a1
+ b:
+ c:
+ b:b1
+ c:
+ c:c1`)
+ })
+
+ // Test no Keys.
+ t.Run("none", func(t *testing.T) {
+ tree := NewKeyHeader([]Key{})
+ if len(tree.Top) != 0 {
+ t.Fatalf("wanted empty tree, got %v", tree)
+ }
+ })
+
+ // Test empty Keys.
+ t.Run("empty", func(t *testing.T) {
+ s, _ := mustParse(t, ".config")
+ c1 := p(t, s, "")
+ c2 := p(t, s, "")
+ tree := NewKeyHeader([]Key{c1, c2})
+ checkKeyHeader(t, tree, "")
+ })
+}
diff --git a/benchproc/nonsingular.go b/benchproc/nonsingular.go
new file mode 100644
index 0000000..4f7bf52
--- /dev/null
+++ b/benchproc/nonsingular.go
@@ -0,0 +1,38 @@
+// 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 benchproc
+
+// NonSingularFields returns the subset of Fields for which at least two of keys
+// have different values.
+//
+// This is useful for warning the user if aggregating a set of results has
+// resulted in potentially hiding important configuration differences. Typically
+// these keys are "residue" keys produced by ProjectionParser.Residue.
+func NonSingularFields(keys []Key) []*Field {
+ // TODO: This is generally used on residue keys, but those might
+ // just have ".fullname" (generally with implicit exclusions).
+ // Telling the user that a set of benchmarks varies in ".fullname"
+ // isn't nearly as useful as listing out the specific subfields. We
+ // should synthesize "/N" subfields for ".fullname" for this (this
+ // makes even more sense if we make .fullname a group field that
+ // already has these subfields).
+
+ if len(keys) <= 1 {
+ // There can't be any differences.
+ return nil
+ }
+ var out []*Field
+ fields := commonProjection(keys).FlattenedFields()
+ for _, f := range fields {
+ base := keys[0].Get(f)
+ for _, k := range keys[1:] {
+ if k.Get(f) != base {
+ out = append(out, f)
+ break
+ }
+ }
+ }
+ return out
+}
diff --git a/benchproc/nonsingular_test.go b/benchproc/nonsingular_test.go
new file mode 100644
index 0000000..2d09835
--- /dev/null
+++ b/benchproc/nonsingular_test.go
@@ -0,0 +1,55 @@
+// 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 benchproc
+
+import (
+ "reflect"
+ "testing"
+)
+
+func TestNonSingularFields(t *testing.T) {
+ s, _ := mustParse(t, ".config")
+
+ var keys []Key
+ check := func(want ...string) {
+ t.Helper()
+ got := NonSingularFields(keys)
+ var gots []string
+ for _, f := range got {
+ gots = append(gots, f.Name)
+ }
+ if !reflect.DeepEqual(want, gots) {
+ t.Errorf("want %v, got %v", want, gots)
+ }
+ }
+
+ keys = []Key{}
+ check()
+
+ keys = []Key{
+ p(t, s, "", "a", "1", "b", "1"),
+ }
+ check()
+
+ keys = []Key{
+ p(t, s, "", "a", "1", "b", "1"),
+ p(t, s, "", "a", "1", "b", "1"),
+ p(t, s, "", "a", "1", "b", "1"),
+ }
+ check()
+
+ keys = []Key{
+ p(t, s, "", "a", "1", "b", "1"),
+ p(t, s, "", "a", "2", "b", "1"),
+ }
+ check("a")
+
+ keys = []Key{
+ p(t, s, "", "a", "1", "b", "1"),
+ p(t, s, "", "a", "2", "b", "1"),
+ p(t, s, "", "a", "1", "b", "2"),
+ }
+ check("a", "b")
+}
diff --git a/benchproc/projection.go b/benchproc/projection.go
new file mode 100644
index 0000000..26d934b
--- /dev/null
+++ b/benchproc/projection.go
@@ -0,0 +1,536 @@
+// 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 benchproc
+
+import (
+ "fmt"
+ "hash/maphash"
+ "strings"
+ "sync"
+
+ "golang.org/x/perf/benchfmt"
+ "golang.org/x/perf/benchproc/internal/parse"
+)
+
+// TODO: If we support comparison operators in filter expressions,
+// does it make sense to unify the orders understood by projections
+// with the comparison orders supported in filters? One danger is that
+// the default order for projections is observation order, but if you
+// filter on key<val, you probably want that to be numeric by default
+// (it's not clear you ever want a comparison on observation order).
+
+// A ProjectionParser parses one or more related projection expressions.
+type ProjectionParser struct {
+ configKeys map[string]bool // Specific .config keys (excluded from .config)
+ fullnameKeys []string // Specific sub-name keys (excluded from .fullname)
+ haveConfig bool // .config was projected
+ haveFullname bool // .fullname was projected
+
+ // Fields below here are constructed when the first Result is
+ // processed.
+
+ fullExtractor extractor
+}
+
+// Parse parses a single projection expression, such as ".name,/size".
+// A projection expression describes how to extract fields of a
+// benchfmt.Result into a Key and how to order the resulting Keys. See
+// "go doc golang.org/x/perf/benchproc/syntax" for a description of
+// projection syntax.
+//
+// A projection expression may also imply a filter, for example if
+// there's a fixed order like "/size@(1MiB)". Parse will add any filters
+// to "filter".
+//
+// If an application calls Parse multiple times on the same
+// ProjectionParser, these form a mutually-exclusive group of
+// projections in which specific keys in any projection are excluded
+// from group keys in any other projection. The group keys are
+// ".config" and ".fullname". For example, given two projections
+// ".config" and "commit,date", the specific file configuration keys
+// "commit" and "date" are excluded from the group key ".config".
+// The result is the same regardless of the order these expressions
+// are parsed in.
+func (p *ProjectionParser) Parse(projection string, filter *Filter) (*Projection, error) {
+ if p.configKeys == nil {
+ p.configKeys = make(map[string]bool)
+ }
+
+ proj := newProjection()
+
+ // Parse the projection.
+ parts, err := parse.ParseProjection(projection)
+ if err != nil {
+ return nil, err
+ }
+ var filterParts []filterFn
+ for _, part := range parts {
+ f, err := p.makeProjection(proj, projection, part)
+ if err != nil {
+ return nil, err
+ }
+ if f != nil {
+ filterParts = append(filterParts, f)
+ }
+ }
+ // Now that we've ensured the projection is valid, add any
+ // filter parts to the filter.
+ if len(filterParts) > 0 {
+ if filter == nil {
+ panic(fmt.Sprintf("projection expression %s contains a filter, but Parse was passed a nil *Filter", projection))
+ }
+ filterParts = append(filterParts, filter.match)
+ filter.match = filterOp(parse.OpAnd, filterParts)
+ }
+
+ return proj, nil
+}
+
+// ParseWithUnit is like Parse, but the returned Projection has an
+// additional field called ".unit" that extracts the unit of each
+// individual benchfmt.Value in a benchfmt.Result. It returns the
+// Projection and the ".unit" Field.
+//
+// Typically, callers need to break out individual benchmark values on
+// some dimension of a set of Projections. Adding a .unit field makes
+// this easy.
+//
+// Callers should use the ProjectValues method of the returned
+// Projection rather than the Project method to project each value
+// rather than the whole benchfmt.Result.
+func (p *ProjectionParser) ParseWithUnit(projection string, filter *Filter) (*Projection, *Field, error) {
+ proj, err := p.Parse(projection, filter)
+ if err != nil {
+ return nil, nil, err
+ }
+ field := proj.addField(proj.root, ".unit")
+ field.order = make(map[string]int)
+ field.cmp = func(a, b string) int {
+ return field.order[a] - field.order[b]
+ }
+ proj.unitField = field
+ return proj, field, nil
+}
+
+// Residue returns a projection for any field not yet projected by any
+// projection parsed by p. The resulting Projection does not have a
+// meaningful order.
+//
+// For example, following calls to p.Parse("goos") and
+// p.Parse(".fullname"), Reside would return a Projection with fields
+// for all file configuration fields except goos.
+//
+// The intended use of this is to report when a user may have
+// over-aggregated results. Specifically, track the residues of all of
+// the benchfmt.Results that are aggregated together (e.g., into a
+// single table cell). If there's more than one distinct residue, report
+// that those results differed in some field. Typically this is used
+// with NonSingularFields to report exactly which fields differ.
+func (p *ProjectionParser) Residue() *Projection {
+ s := newProjection()
+
+ // The .config and .fullname groups together cover the
+ // projection space. If they haven't already been specified,
+ // then these groups (with any specific keys excluded) exactly
+ // form the remainder.
+ if !p.haveConfig {
+ p.makeProjection(s, "", parse.Field{Key: ".config", Order: "first"})
+ }
+ if !p.haveFullname {
+ p.makeProjection(s, "", parse.Field{Key: ".fullname", Order: "first"})
+ }
+
+ return s
+}
+
+func (p *ProjectionParser) makeProjection(s *Projection, q string, proj parse.Field) (filterFn, error) {
+ // Construct the order function.
+ var initField func(field *Field)
+ var filter filterFn
+ makeFilter := func(ext extractor) {}
+ if proj.Order == "fixed" {
+ fixedMap := make(map[string]int, len(proj.Fixed))
+ for i, s := range proj.Fixed {
+ fixedMap[s] = i
+ }
+ initField = func(field *Field) {
+ field.cmp = func(a, b string) int {
+ return fixedMap[a] - fixedMap[b]
+ }
+ }
+ makeFilter = func(ext extractor) {
+ filter = func(res *benchfmt.Result) (mask, bool) {
+ _, ok := fixedMap[string(ext(res))]
+ return nil, ok
+ }
+ }
+ } else if proj.Order == "first" {
+ initField = func(field *Field) {
+ field.order = make(map[string]int)
+ field.cmp = func(a, b string) int {
+ return field.order[a] - field.order[b]
+ }
+ }
+ } else if cmp, ok := builtinOrders[proj.Order]; ok {
+ initField = func(field *Field) {
+ field.cmp = cmp
+ }
+ } else {
+ return nil, &parse.SyntaxError{q, proj.OrderOff, fmt.Sprintf("unknown order %q", proj.Order)}
+ }
+
+ var project func(*benchfmt.Result, *[]string)
+ switch proj.Key {
+ case ".config":
+ // File configuration, excluding any more
+ // specific file keys.
+ if proj.Order == "fixed" {
+ // Fixed orders don't make sense for a whole tuple.
+ return nil, &parse.SyntaxError{q, proj.OrderOff, fmt.Sprintf("fixed order not allowed for .config")}
+ }
+
+ p.haveConfig = true
+ group := s.addGroup(s.root, ".config")
+ seen := make(map[string]*Field)
+ project = func(r *benchfmt.Result, row *[]string) {
+ for _, cfg := range r.Config {
+ if !cfg.File {
+ continue
+ }
+
+ // Have we already seen this key? If so, use its already
+ // assigned field index.
+ field, ok := seen[cfg.Key]
+ if !ok {
+ // This closure doesn't get called until we've
+ // parsed all projections, so p.configKeys is fully
+ // populated from all parsed projections.
+ if p.configKeys[cfg.Key] {
+ // This key was explicitly specified in another
+ // projection, so omit it from .config.
+ continue
+ }
+ // Create a new field for this new key.
+ field = s.addField(group, cfg.Key)
+ initField(field)
+ seen[cfg.Key] = field
+ }
+
+ (*row)[field.idx] = s.intern(cfg.Value)
+ }
+ }
+
+ case ".fullname":
+ // Full benchmark name, including name config.
+ // We want to exclude any more specific keys,
+ // including keys from later projections, so
+ // we delay constructing the extractor until
+ // we process the first Result.
+ p.haveFullname = true
+ field := s.addField(s.root, ".fullname")
+ initField(field)
+ makeFilter(extractFull)
+
+ project = func(r *benchfmt.Result, row *[]string) {
+ if p.fullExtractor == nil {
+ p.fullExtractor = newExtractorFullName(p.fullnameKeys)
+ }
+ val := p.fullExtractor(r)
+ (*row)[field.idx] = s.intern(val)
+ }
+
+ case ".unit":
+ return nil, &parse.SyntaxError{q, proj.KeyOff, ".unit is only allowed in filters"}
+
+ default:
+ // This is a specific sub-name or file key. Add it
+ // to the excludes.
+ if proj.Key == ".name" || strings.HasPrefix(proj.Key, "/") {
+ p.fullnameKeys = append(p.fullnameKeys, proj.Key)
+ } else {
+ p.configKeys[proj.Key] = true
+ }
+ ext, err := newExtractor(proj.Key)
+ if err != nil {
+ return nil, &parse.SyntaxError{q, proj.KeyOff, err.Error()}
+ }
+ field := s.addField(s.root, proj.Key)
+ initField(field)
+ makeFilter(ext)
+ project = func(r *benchfmt.Result, row *[]string) {
+ val := ext(r)
+ (*row)[field.idx] = s.intern(val)
+ }
+ }
+ s.project = append(s.project, project)
+ return filter, nil
+}
+
+// A Projection extracts some subset of the fields of a benchfmt.Result
+// into a Key.
+//
+// A Projection also implies a sort order over Keys that is
+// lexicographic over the fields of the Projection. The sort order of
+// each individual field is specified by the projection expression and
+// defaults to the order in which values of that field were first
+// observed.
+type Projection struct {
+ root *Field
+ nFields int
+
+ // unitField, if non-nil, is the ".unit" field used to project
+ // the values of a benchmark result.
+ unitField *Field
+
+ // project is a set of functions that project a Result into
+ // row.
+ //
+ // These take a pointer to row because these functions may
+ // grow the set of fields, so the row slice may grow.
+ project []func(r *benchfmt.Result, row *[]string)
+
+ // row is the buffer used to construct a projection.
+ row []string
+
+ // flatCache is a cache of the flattened sort fields in tuple
+ // comparison order.
+ flatCache []*Field
+ flatCacheOnce *sync.Once
+
+ // interns is used to intern the []byte to string conversion. It's
+ // keyed by string because we can't key a map on []byte, but the
+ // compiler elides the string allocation in interns[string(x)], so
+ // lookups are still cheap. These strings are always referenced in
+ // keys, so this doesn't cause any over-retention.
+ interns map[string]string
+
+ // keys are the interned Keys of this Projection.
+ keys map[uint64][]*keyNode
+}
+
+func newProjection() *Projection {
+ var p Projection
+ p.root = &Field{idx: -1}
+ p.flatCacheOnce = new(sync.Once)
+ p.interns = make(map[string]string)
+ p.keys = make(map[uint64][]*keyNode)
+ return &p
+}
+
+func (p *Projection) addField(group *Field, name string) *Field {
+ if group.idx != -1 {
+ panic("field's parent is not a group")
+ }
+
+ // Assign this field an index.
+ field := &Field{Name: name, proj: p, idx: p.nFields}
+ p.nFields++
+ group.Sub = append(group.Sub, field)
+ // Clear the flat cache.
+ if p.flatCache != nil {
+ p.flatCache = nil
+ p.flatCacheOnce = new(sync.Once)
+ }
+ // Add to the row buffer.
+ p.row = append(p.row, "")
+ return field
+}
+
+func (p *Projection) addGroup(group *Field, name string) *Field {
+ field := &Field{Name: name, IsTuple: true, proj: p, idx: -1}
+ group.Sub = append(group.Sub, field)
+ return field
+}
+
+// Fields returns the fields of p. These correspond exactly to the
+// fields in the Projection's projection expression.
+//
+// The caller must not modify the returned slice.
+func (p *Projection) Fields() []*Field {
+ return p.root.Sub
+}
+
+// FlattenedFields is like Fields, but expands tuple Fields
+// (specifically, ".config") into their sub-Fields. This is also the
+// sequence of Fields used for sorting Keys returned from this
+// Projection.
+//
+// The caller must not modify the returned slice.
+func (p *Projection) FlattenedFields() []*Field {
+ // This can reasonably be called in parallel after all results have
+ // been projected, so we make sure it's thread-safe.
+ p.flatCacheOnce.Do(func() {
+ p.flatCache = []*Field{}
+ var walk func(f *Field)
+ walk = func(f *Field) {
+ if f.idx != -1 {
+ p.flatCache = append(p.flatCache, f)
+ return
+ }
+ for _, sub := range f.Sub {
+ walk(sub)
+ }
+ }
+ walk(p.root)
+ })
+ return p.flatCache
+}
+
+// A Field is a single field of a Projection.
+//
+// For example, in the projection ".name,/gomaxprocs", ".name" and
+// "/gomaxprocs" are both Fields.
+//
+// A Field may be a group field with sub-Fields.
+type Field struct {
+ Name string
+
+ // IsTuple indicates that this Field is a tuple that does not itself
+ // have a string value.
+ IsTuple bool
+
+ // Sub is the sequence of sub-Fields for a group field.
+ Sub []*Field
+
+ proj *Projection
+
+ // idx gives the index of this field's values in a keyNode.
+ //
+ // Indexes are assigned sequentially as new sub-Fields are added to
+ // group Fields. This allows the set of Fields to grow without
+ // invalidating existing Keys.
+ //
+ // idx is -1 for Fields that are not directly stored in a keyNode,
+ // such as the root Field and ".config".
+ idx int
+
+ // cmp is the comparison function for values of this field. It
+ // returns <0 if a < b, >0 if a > b, or 0 if a == b or a and b
+ // are unorderable.
+ cmp func(a, b string) int
+
+ // order, if non-nil, records the observation order of this
+ // field.
+ order map[string]int
+}
+
+// String returns the name of Field f.
+func (f Field) String() string {
+ return f.Name
+}
+
+var keySeed = maphash.MakeSeed()
+
+// Project extracts fields from benchmark Result r according to
+// Projection s and returns them as a Key.
+//
+// Two Keys produced by Project will be == if and only if their
+// projected fields have the same values. Notably, this means Keys can
+// be used as Go map keys, which is useful for grouping benchmark
+// results.
+//
+// Calling Project may add new sub-Fields to group Fields in this
+// Projection. For example, if the Projection has a ".config" field and
+// r has a never-before-seen file configuration key, this will add a new
+// sub-Field to the ".config" Field.
+//
+// If this Projection includes a .units field, it will be left as "" in
+// the resulting Key. The caller should use ProjectValues instead.
+func (p *Projection) Project(r *benchfmt.Result) Key {
+ p.populateRow(r)
+ return p.internRow()
+}
+
+// ProjectValues is like Project, but for each benchmark value of
+// r.Values individually. The returned slice corresponds to the
+// r.Values slice.
+//
+// If this Projection includes a .unit field, it will differ between
+// these Keys. If not, then all of the Keys will be identical
+// because the benchmark values vary only on .unit.
+func (p *Projection) ProjectValues(r *benchfmt.Result) []Key {
+ p.populateRow(r)
+ out := make([]Key, len(r.Values))
+ if p.unitField == nil {
+ // There's no .unit, so the Keys will all be the same.
+ key := p.internRow()
+ for i := range out {
+ out[i] = key
+ }
+ return out
+ }
+ // Vary the .unit field.
+ for i, val := range r.Values {
+ p.row[p.unitField.idx] = val.Unit
+ out[i] = p.internRow()
+ }
+ return out
+}
+
+func (p *Projection) populateRow(r *benchfmt.Result) {
+ // Clear the row buffer.
+ for i := range p.row {
+ p.row[i] = ""
+ }
+
+ // Run the projection functions to fill in row.
+ for _, proj := range p.project {
+ // proj may add fields and grow row.
+ proj(r, &p.row)
+ }
+}
+
+func (p *Projection) internRow() Key {
+ // Hash the row. This must be invariant to unused trailing fields: the
+ // field set can grow, and if those new fields are later cleared,
+ // we want Keys from before the growth to equal Keys from after the growth.
+ row := p.row
+ for len(row) > 0 && row[len(row)-1] == "" {
+ row = row[:len(row)-1]
+ }
+ var h maphash.Hash
+ h.SetSeed(keySeed)
+ for _, val := range row {
+ h.WriteString(val)
+ }
+ hash := h.Sum64()
+
+ // Check if we already have this key.
+ keys := p.keys[hash]
+ for _, key := range keys {
+ if key.equalRow(row) {
+ return Key{key}
+ }
+ }
+
+ // Update observation orders.
+ for _, field := range p.Fields() {
+ if field.order == nil {
+ // Not tracking observation order for this field.
+ continue
+ }
+ var val string
+ if field.idx < len(row) {
+ val = row[field.idx]
+ }
+ if _, ok := field.order[val]; !ok {
+ field.order[val] = len(field.order)
+ }
+ }
+
+ // Save the key.
+ key := &keyNode{p, append([]string(nil), row...)}
+ p.keys[hash] = append(p.keys[hash], key)
+ return Key{key}
+}
+
+func (p *Projection) intern(b []byte) string {
+ if str, ok := p.interns[string(b)]; ok {
+ return str
+ }
+ str := string(b)
+ p.interns[str] = str
+ return str
+}
diff --git a/benchproc/projection_test.go b/benchproc/projection_test.go
new file mode 100644
index 0000000..846ca61
--- /dev/null
+++ b/benchproc/projection_test.go
@@ -0,0 +1,354 @@
+// 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 benchproc
+
+import (
+ "fmt"
+ "strings"
+ "testing"
+
+ "golang.org/x/perf/benchfmt"
+ "golang.org/x/perf/benchproc/internal/parse"
+)
+
+// mustParse parses a single projection.
+func mustParse(t *testing.T, proj string) (*Projection, *Filter) {
+ f, err := NewFilter("*")
+ if err != nil {
+ t.Fatalf("unexpected error: %v", err)
+ }
+ s, err := (&ProjectionParser{}).Parse(proj, f)
+ if err != nil {
+ t.Fatalf("unexpected error parsing %q: %v", proj, err)
+ }
+ return s, f
+}
+
+// r constructs a benchfmt.Result with the given full name and file
+// config, which is specified as alternating key/value pairs. The
+// result has 1 iteration and no values.
+func r(t *testing.T, fullName string, fileConfig ...string) *benchfmt.Result {
+ res := &benchfmt.Result{
+ Name: benchfmt.Name(fullName),
+ Iters: 1,
+ }
+
+ if len(fileConfig)%2 != 0 {
+ t.Fatal("fileConfig must be alternating key/value pairs")
+ }
+ for i := 0; i < len(fileConfig); i += 2 {
+ cfg := benchfmt.Config{Key: fileConfig[i], Value: []byte(fileConfig[i+1]), File: true}
+ res.Config = append(res.Config, cfg)
+ }
+
+ return res
+}
+
+// p constructs a benchfmt.Result like r, then projects it using p.
+func p(t *testing.T, p *Projection, fullName string, fileConfig ...string) Key {
+ res := r(t, fullName, fileConfig...)
+ return p.Project(res)
+}
+
+func TestProjectionBasic(t *testing.T) {
+ check := func(key Key, want string) {
+ t.Helper()
+ got := key.String()
+ if got != want {
+ t.Errorf("got %s, want %s", got, want)
+ }
+ }
+
+ var s *Projection
+
+ // Sub-name config.
+ s, _ = mustParse(t, ".fullname")
+ check(p(t, s, "Name/a=1"), ".fullname:Name/a=1")
+ s, _ = mustParse(t, "/a")
+ check(p(t, s, "Name/a=1"), "/a:1")
+ s, _ = mustParse(t, ".name")
+ check(p(t, s, "Name/a=1"), ".name:Name")
+
+ // Fixed file config.
+ s, _ = mustParse(t, "a")
+ check(p(t, s, "", "a", "1", "b", "2"), "a:1")
+ check(p(t, s, "", "b", "2"), "") // Missing values are omitted
+ check(p(t, s, "", "a", "", "b", "2"), "")
+
+ // Variable file config.
+ s, _ = mustParse(t, ".config")
+ check(p(t, s, "", "a", "1", "b", "2"), "a:1 b:2")
+ check(p(t, s, "", "c", "3"), "c:3")
+ check(p(t, s, "", "c", "3", "a", "2"), "a:2 c:3")
+}
+
+func TestProjectionIntern(t *testing.T) {
+ s, _ := mustParse(t, "a,b")
+
+ c12 := p(t, s, "", "a", "1", "b", "2")
+
+ if c12 != p(t, s, "", "a", "1", "b", "2") {
+ t.Errorf("Keys should be equal")
+ }
+
+ if c12 == p(t, s, "", "a", "1", "b", "3") {
+ t.Errorf("Keys should not be equal")
+ }
+
+ if c12 != p(t, s, "", "a", "1", "b", "2", "c", "3") {
+ t.Errorf("Keys should be equal")
+ }
+}
+
+func fieldNames(fields []*Field) string {
+ names := new(strings.Builder)
+ for i, f := range fields {
+ if i > 0 {
+ names.WriteByte(' ')
+ }
+ names.WriteString(f.Name)
+ }
+ return names.String()
+}
+
+func TestProjectionParsing(t *testing.T) {
+ // Basic parsing is tested by the syntax package. Here we test
+ // additional processing done by this package.
+
+ check := func(proj string, want, wantFlat string) {
+ t.Helper()
+ s, _ := mustParse(t, proj)
+ got := fieldNames(s.Fields())
+ if got != want {
+ t.Errorf("%s: got fields %v, want %v", proj, got, want)
+ }
+ gotFlat := fieldNames(s.FlattenedFields())
+ if gotFlat != wantFlat {
+ t.Errorf("%s: got flat fields %v, want %v", proj, gotFlat, wantFlat)
+ }
+ }
+ checkErr := func(proj, error string, pos int) {
+ t.Helper()
+ f, _ := NewFilter("*")
+ _, err := (&ProjectionParser{}).Parse(proj, f)
+ if se, _ := err.(*parse.SyntaxError); se == nil || se.Msg != error || se.Off != pos {
+ t.Errorf("%s: want error %s at %d; got %s", proj, error, pos, err)
+ }
+ }
+
+ check("a,b,c", "a b c", "a b c")
+ check("a,.config,c", "a .config c", "a c") // .config hasn't been populated with anything yet
+ check("a,.fullname,c", "a .fullname c", "a .fullname c")
+ check("a,.name,c", "a .name c", "a .name c")
+ check("a,/b,c", "a /b c", "a /b c")
+
+ checkErr("a@foo", "unknown order \"foo\"", 2)
+
+ checkErr(".config@(1 2)", "fixed order not allowed for .config", 8)
+}
+
+func TestProjectionFiltering(t *testing.T) {
+ _, f := mustParse(t, "a@(a b c)")
+ check := func(val string, want bool) {
+ t.Helper()
+ res := r(t, "", "a", val)
+ got, _ := f.Apply(res)
+ if want != got {
+ t.Errorf("%s: want %v, got %v", val, want, got)
+ }
+ }
+ check("a", true)
+ check("b", true)
+ check("aa", false)
+ check("z", false)
+}
+
+func TestProjectionExclusion(t *testing.T) {
+ // The underlying name normalization has already been tested
+ // thoroughly in benchfmt/extract_test.go, so here we just
+ // have to test that it's being plumbed right.
+
+ check := func(key Key, want string) {
+ t.Helper()
+ got := key.String()
+ if got != want {
+ t.Errorf("got %s, want %s", got, want)
+ }
+ }
+
+ // Create the main projection.
+ var pp ProjectionParser
+ f, _ := NewFilter("*")
+ s, err := pp.Parse(".fullname,.config", f)
+ if err != nil {
+ t.Fatalf("unexpected error %v", err)
+ }
+ // Parse specific keys that should be excluded from fullname
+ // and config.
+ _, err = pp.Parse(".name,/a,exc", f)
+ if err != nil {
+ t.Fatalf("unexpected error %v", err)
+ }
+
+ check(p(t, s, "Name"), ".fullname:*")
+ check(p(t, s, "Name/a=1"), ".fullname:*")
+ check(p(t, s, "Name/a=1/b=2"), ".fullname:*/b=2")
+
+ check(p(t, s, "Name", "exc", "1"), ".fullname:*")
+ check(p(t, s, "Name", "exc", "1", "abc", "2"), ".fullname:* abc:2")
+ check(p(t, s, "Name", "abc", "2"), ".fullname:* abc:2")
+}
+
+func TestProjectionResidue(t *testing.T) {
+ check := func(mainProj string, want string) {
+ t.Helper()
+
+ // Get the residue of mainProj.
+ var pp ProjectionParser
+ f, _ := NewFilter("*")
+ _, err := pp.Parse(mainProj, f)
+ if err != nil {
+ t.Fatalf("unexpected error %v", err)
+ }
+ s := pp.Residue()
+
+ // Project a test result.
+ key := p(t, s, "Name/a=1/b=2", "x", "3", "y", "4")
+ got := key.String()
+ if got != want {
+ t.Errorf("got %s, want %s", got, want)
+ }
+ }
+
+ // Full residue.
+ check("", "x:3 y:4 .fullname:Name/a=1/b=2")
+ // Empty residue.
+ check(".config,.fullname", "")
+ // Partial residues.
+ check("x,/a", "y:4 .fullname:Name/b=2")
+ check(".config", ".fullname:Name/a=1/b=2")
+ check(".fullname", "x:3 y:4")
+ check(".name", "x:3 y:4 .fullname:*/a=1/b=2")
+}
+
+// ExampleProjectionParser_Residue demonstrates residue projections.
+//
+// This example groups a set of results by .fullname and goos, but the
+// two results for goos:linux have two different goarch values,
+// indicating the user probably unintentionally grouped uncomparable
+// results together. The example uses ProjectionParser.Residue and
+// NonSingularFields to warn the user about this.
+func ExampleProjectionParser_Residue() {
+ var pp ProjectionParser
+ p, _ := pp.Parse(".fullname,goos", nil)
+ residue := pp.Residue()
+
+ // Aggregate each result by p and track the residue of each group.
+ type group struct {
+ values []float64
+ residues []Key
+ }
+ groups := make(map[Key]*group)
+ var keys []Key
+
+ for _, result := range results(`
+goos: linux
+goarch: amd64
+BenchmarkAlloc 1 128 ns/op
+
+goos: linux
+goarch: arm64
+BenchmarkAlloc 1 137 ns/op
+
+goos: darwin
+goarch: amd64
+BenchmarkAlloc 1 130 ns/op`) {
+ // Map result to a group.
+ key := p.Project(result)
+ g, ok := groups[key]
+ if !ok {
+ g = new(group)
+ groups[key] = g
+ keys = append(keys, key)
+ }
+
+ // Add value to the group.
+ speed, _ := result.Value("sec/op")
+ g.values = append(g.values, speed)
+
+ // Add residue to the group.
+ g.residues = append(g.residues, residue.Project(result))
+ }
+
+ // Report aggregated results.
+ SortKeys(keys)
+ for _, k := range keys {
+ g := groups[k]
+ // Report the result.
+ fmt.Println(k, mean(g.values), "sec/op")
+ // Check if the grouped results vary in some unexpected way.
+ nonsingular := NonSingularFields(g.residues)
+ if len(nonsingular) > 0 {
+ // Report a potential issue.
+ fmt.Printf("warning: results vary in %s and may be uncomparable\n", nonsingular)
+ }
+ }
+
+ // Output:
+ // .fullname:Alloc goos:linux 1.325e-07 sec/op
+ // warning: results vary in [goarch] and may be uncomparable
+ // .fullname:Alloc goos:darwin 1.3e-07 sec/op
+}
+
+func results(data string) []*benchfmt.Result {
+ var out []*benchfmt.Result
+ r := benchfmt.NewReader(strings.NewReader(data), "<string>")
+ for r.Scan() {
+ switch rec := r.Result(); rec := rec.(type) {
+ case *benchfmt.Result:
+ out = append(out, rec.Clone())
+ case *benchfmt.SyntaxError:
+ panic("unexpected error in test data: " + rec.Error())
+ }
+ }
+ return out
+}
+
+func mean(xs []float64) float64 {
+ var sum float64
+ for _, x := range xs {
+ sum += x
+ }
+ return sum / float64(len(xs))
+}
+
+func TestProjectionValues(t *testing.T) {
+ s, unit, err := (&ProjectionParser{}).ParseWithUnit("x", nil)
+ if err != nil {
+ t.Fatalf("unexpected error parsing %q: %v", "x", err)
+ }
+
+ check := func(key Key, want, wantUnit string) {
+ t.Helper()
+ got := key.String()
+ if got != want {
+ t.Errorf("got %s, want %s", got, want)
+ }
+ gotUnit := key.Get(unit)
+ if gotUnit != wantUnit {
+ t.Errorf("got unit %s, want %s", gotUnit, wantUnit)
+ }
+ }
+
+ res := r(t, "Name", "x", "1")
+ res.Values = []benchfmt.Value{{Value: 100, Unit: "ns/op"}, {Value: 1.21, Unit: "gigawatts"}}
+ keys := s.ProjectValues(res)
+ if len(keys) != len(res.Values) {
+ t.Fatalf("got %d Keys, want %d", len(keys), len(res.Values))
+ }
+
+ check(keys[0], "x:1 .unit:ns/op", "ns/op")
+ check(keys[1], "x:1 .unit:gigawatts", "gigawatts")
+}
diff --git a/benchproc/sort.go b/benchproc/sort.go
new file mode 100644
index 0000000..69c85fd
--- /dev/null
+++ b/benchproc/sort.go
@@ -0,0 +1,140 @@
+// 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 benchproc
+
+import (
+ "math"
+ "regexp"
+ "sort"
+ "strconv"
+ "strings"
+)
+
+// Less reports whether k comes before o in the sort order implied by
+// their projection. It panics if k and o have different Projections.
+func (k Key) Less(o Key) bool {
+ if k.k.proj != o.k.proj {
+ panic("cannot compare Keys from different Projections")
+ }
+ return less(k.k.proj.FlattenedFields(), k.k.vals, o.k.vals)
+}
+
+func less(flat []*Field, a, b []string) bool {
+ // Walk the tuples in flattened order.
+ for _, node := range flat {
+ var aa, bb string
+ if node.idx < len(a) {
+ aa = a[node.idx]
+ }
+ if node.idx < len(b) {
+ bb = b[node.idx]
+ }
+ if aa != bb {
+ cmp := node.cmp(aa, bb)
+ if cmp != 0 {
+ return cmp < 0
+ }
+ // The values are equal/unordered according to
+ // the comparison function, but the strings
+ // differ. Because Keys are only == if
+ // their string representations are ==, this
+ // means we have to fall back to a secondary
+ // comparison that is only == if the strings
+ // are ==.
+ return aa < bb
+ }
+ }
+
+ // Tuples are equal.
+ return false
+}
+
+// SortKeys sorts a slice of Keys using Key.Less.
+// All Keys must have the same Projection.
+//
+// This is equivalent to using Key.Less with the sort package but
+// more efficient.
+func SortKeys(keys []Key) {
+ // Check all the Projections so we don't have to do this on every
+ // comparison.
+ if len(keys) == 0 {
+ return
+ }
+ s := commonProjection(keys)
+ flat := s.FlattenedFields()
+
+ sort.Slice(keys, func(i, j int) bool {
+ return less(flat, keys[i].k.vals, keys[j].k.vals)
+ })
+}
+
+// builtinOrders is the built-in comparison functions.
+var builtinOrders = map[string]func(a, b string) int{
+ "alpha": func(a, b string) int {
+ return strings.Compare(a, b)
+ },
+ "num": func(a, b string) int {
+ aa, erra := parseNum(a)
+ bb, errb := parseNum(b)
+ if erra == nil && errb == nil {
+ // Sort numerically, and put NaNs after other
+ // values.
+ if aa < bb || (!math.IsNaN(aa) && math.IsNaN(bb)) {
+ return -1
+ }
+ if aa > bb || (math.IsNaN(aa) && !math.IsNaN(bb)) {
+ return 1
+ }
+ // The values are unordered.
+ return 0
+ }
+ if erra != nil && errb != nil {
+ // The values are unordered.
+ return 0
+ }
+ // Put floats before non-floats.
+ if erra == nil {
+ return -1
+ }
+ return 1
+ },
+}
+
+const numPrefixes = `KMGTPEZY`
+
+var numRe = regexp.MustCompile(`([0-9.]+)([k` + numPrefixes + `]i?)?[bB]?`)
+
+// parseNum is a fuzzy number parser. It supports common patterns,
+// such as SI prefixes.
+func parseNum(x string) (float64, error) {
+ // Try parsing as a regular float.
+ v, err := strconv.ParseFloat(x, 64)
+ if err == nil {
+ return v, nil
+ }
+
+ // Try a suffixed number.
+ subs := numRe.FindStringSubmatch(x)
+ if subs != nil {
+ v, err := strconv.ParseFloat(subs[1], 64)
+ if err == nil {
+ exp := 0
+ if len(subs[2]) > 0 {
+ pre := subs[2][0]
+ if pre == 'k' {
+ pre = 'K'
+ }
+ exp = 1 + strings.IndexByte(numPrefixes, pre)
+ }
+ iec := strings.HasSuffix(subs[2], "i")
+ if iec {
+ return v * math.Pow(1024, float64(exp)), nil
+ }
+ return v * math.Pow(1000, float64(exp)), nil
+ }
+ }
+
+ return 0, strconv.ErrSyntax
+}
diff --git a/benchproc/sort_test.go b/benchproc/sort_test.go
new file mode 100644
index 0000000..a0f1886
--- /dev/null
+++ b/benchproc/sort_test.go
@@ -0,0 +1,133 @@
+// 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 benchproc
+
+import (
+ "math/rand"
+ "reflect"
+ "testing"
+)
+
+func TestSort(t *testing.T) {
+ check := func(keys []Key, want ...string) {
+ SortKeys(keys)
+ var got []string
+ for _, key := range keys {
+ got = append(got, key.String())
+ }
+ if !reflect.DeepEqual(got, want) {
+ t.Errorf("got %v, want %v", got, want)
+ }
+ }
+
+ // Observation order.
+ s, _ := mustParse(t, "a")
+ k := []Key{
+ p(t, s, "", "a", "1"),
+ p(t, s, "", "a", "3"),
+ p(t, s, "", "a", "2"),
+ }
+ check(k, "a:1", "a:3", "a:2")
+
+ // Tuple observation order.
+ s, _ = mustParse(t, "a,b")
+ // Prepare order.
+ p(t, s, "", "a", "1")
+ p(t, s, "", "a", "2")
+ p(t, s, "", "b", "1")
+ p(t, s, "", "b", "2")
+ k = []Key{
+ p(t, s, "", "a", "2", "b", "1"),
+ p(t, s, "", "a", "1", "b", "2"),
+ }
+ check(k, "a:1 b:2", "a:2 b:1")
+
+ // Alphabetic
+ s, _ = mustParse(t, "a@alpha")
+ k = []Key{
+ p(t, s, "", "a", "c"),
+ p(t, s, "", "a", "b"),
+ p(t, s, "", "a", "a"),
+ }
+ check(k, "a:a", "a:b", "a:c")
+
+ // Numeric.
+ s, _ = mustParse(t, "a@num")
+ k = []Key{
+ p(t, s, "", "a", "100"),
+ p(t, s, "", "a", "20"),
+ p(t, s, "", "a", "3"),
+ }
+ check(k, "a:3", "a:20", "a:100")
+
+ // Numeric with strings.
+ s, _ = mustParse(t, "a@num")
+ k = []Key{
+ p(t, s, "", "a", "b"),
+ p(t, s, "", "a", "a"),
+ p(t, s, "", "a", "100"),
+ p(t, s, "", "a", "20"),
+ }
+ check(k, "a:20", "a:100", "a:a", "a:b")
+
+ // Numeric with weird cases.
+ s, _ = mustParse(t, "a@num")
+ k = []Key{
+ p(t, s, "", "a", "1"),
+ p(t, s, "", "a", "-inf"),
+ p(t, s, "", "a", "-infinity"),
+ p(t, s, "", "a", "inf"),
+ p(t, s, "", "a", "infinity"),
+ p(t, s, "", "a", "1.0"),
+ p(t, s, "", "a", "NaN"),
+ p(t, s, "", "a", "nan"),
+ }
+ // Shuffle the slice to exercise any instabilities.
+ for try := 0; try < 10; try++ {
+ for i := 1; i < len(k); i++ {
+ p := rand.Intn(i)
+ k[p], k[i] = k[i], k[p]
+ }
+ check(k, "a:-inf", "a:-infinity", "a:1", "a:1.0", "a:inf", "a:infinity", "a:NaN", "a:nan")
+ }
+
+ // Fixed.
+ s, _ = mustParse(t, "a@(c b a)")
+ k = []Key{
+ p(t, s, "", "a", "a"),
+ p(t, s, "", "a", "b"),
+ p(t, s, "", "a", "c"),
+ }
+ check(k, "a:c", "a:b", "a:a")
+}
+
+func TestParseNum(t *testing.T) {
+ check := func(x string, want float64) {
+ t.Helper()
+ got, err := parseNum(x)
+ if err != nil {
+ t.Errorf("%s: want %v, got error %s", x, want, err)
+ } else if want != got {
+ t.Errorf("%s: want %v, got %v", x, want, got)
+ }
+ }
+
+ check("1", 1)
+ check("1B", 1)
+ check("1b", 1)
+ check("100.5", 100.5)
+ check("1k", 1000)
+ check("1K", 1000)
+ check("1ki", 1024)
+ check("1kiB", 1024)
+ check("1M", 1000000)
+ check("1Mi", 1<<20)
+ check("1G", 1000000000)
+ check("1T", 1000000000000)
+ check("1P", 1000000000000000)
+ check("1E", 1000000000000000000)
+ check("1Z", 1000000000000000000000)
+ check("1Y", 1000000000000000000000000)
+}
diff --git a/benchproc/syntax/doc.go b/benchproc/syntax/doc.go
new file mode 100644
index 0000000..160e5f0
--- /dev/null
+++ b/benchproc/syntax/doc.go
@@ -0,0 +1,132 @@
+// 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 syntax documents the syntax used by benchmark filter and
+// projection expressions.
+//
+// These expressions work with benchmark data in the Go benchmark
+// format (https://golang.org/design/14313-benchmark-format). Each
+// benchmark result (a line beginning with "Benchmark") consists of
+// several field, including a name, name-based configuration, and
+// file configuration pairs ("key: value" lines).
+//
+// Keys
+//
+// Filters and projections share a common set of keys for referring to
+// these fields of a benchmark result:
+//
+// - ".name" refers to the benchmark name, excluding per-benchmark
+// configuration. For example, the ".name" of the
+// "BenchmarkCopy/size=4k-16" benchmark is "Copy".
+//
+// - ".fullname" refers to the full benchmark name, including
+// per-benchmark configuration, but excluding the "Benchmark" prefix.
+// For example, the ".fullname" of "BenchmarkCopy/size=4k-16" is
+// "Copy/size=4k-16".
+//
+// - "/{key}" refers to value of {key} from the benchmark name
+// configuration. For example, the "/size" of
+// "BenchmarkCopy/size=4k-16", is "4k". As a special case,
+// "/gomaxprocs" recognizes both a literal "/gomaxprocs=" in the name,
+// and the "-N" convention. For the above example, "/gomaxprocs" is
+// "16".
+//
+// - Any name NOT prefixed with "/" or "." refers to the value of a
+// file configuration key. For example, the "testing" package
+// automatically emits a few file configuration keys, including "pkg",
+// "goos", and "goarch", so the projection "pkg" extracts the package
+// path of a benchmark.
+//
+// - ".config" (only in projections) refers to the all file
+// configuration keys of a benchmark. The value of .config isn't a
+// string like the other fields, but rather a tuple. .config is useful
+// for grouping results by all file configuration keys to avoid grouping
+// together incomparable results. For example, benchstat separates
+// results with different .config into different tables.
+//
+// - ".unit" (only in filters) refers to individual measurements in a
+// result, such as the "ns/op" measurement. The filter ".unit:ns/op"
+// extracts just the ns/op measurement of a result. This will match
+// both original units (e.g., "ns/op") and tidied units (e.g.,
+// "sec/op").
+//
+// - ".file" refers to the input file provided on the command line
+// (for command-line tools that use benchfmt.Files).
+//
+// Filters
+//
+// Filters are boolean expressions that match or exclude benchmark
+// results or individual measurements.
+//
+// Filters are built from key-value terms:
+//
+// key:value - Match if key's value is exactly "value".
+// key:"value" - Same, but value is a double-quoted Go string that
+// may contain spaces or other special characters.
+// "key":value - Keys may also be double-quoted.
+// key:/regexp/ - Match if key's value matches a regular expression.
+// key:(val1 OR val2 OR ...)
+// - Short-hand for key:val1 OR key:val2. Values may be
+// double-quoted strings or regexps.
+// * - Match everything.
+//
+// These terms can be combined into larger expressions as follows:
+//
+// x y ... - Match if x, y, etc. all match.
+// x AND y - Same as x y.
+// x OR y - Match if x or y match.
+// -x - Match if x does not match.
+// (...) - Subexpression.
+//
+// Precise syntax:
+//
+// expr = andExpr {"OR" andExpr}
+// andExpr = match {"AND"? match}
+// match = "(" expr ")"
+// | "-" match
+// | "*"
+// | key ":" value
+// | key ":" "(" value {"OR" value} ")"
+// key = word
+// value = word
+// | "/" regexp "/"
+//
+// Projections
+//
+// A projection expresses how to extract a tuple of data from a
+// benchmark result, as well as a sort order for projected tuples.
+//
+// A projection is a comma- or space-separated list of fields.
+// Each field specifies a key and optionally a sort order and a
+// filter as follows:
+//
+// - "key" extracts the named field and orders it using the order
+// values of this key are first observed in the data.
+//
+// - "key@order" specifies one of the built-in named sort orders. This
+// can be "alpha" or "num" for alphabetic or numeric sorting. "num"
+// understands basic use of metric and IEC prefixes like "2k" and
+// "1Mi".
+//
+// - "key@(value value ...)" specifies a fixed value order for key.
+// It also specifies a filter: if key has a value that isn't any of
+// the specified values, the result is filtered out.
+//
+// Precise syntax:
+//
+// expr = part {","? part}
+// part = key
+// | key "@" order
+// | key "@" "(" word {word} ")"
+// key = word
+// order = word
+//
+// Common syntax
+//
+// Filters and projections share the following common base syntax:
+//
+// word = bareWord
+// | double-quoted Go string
+// bareWord = [^-*"():@,][^ ():@,]*
+package syntax
diff --git a/go.mod b/go.mod
index 842359f..a330a8a 100644
--- a/go.mod
+++ b/go.mod
@@ -1,6 +1,6 @@
module golang.org/x/perf
-go 1.11
+go 1.13
require (
cloud.google.com/go v0.0.0-20170206221025-ce650573d812
