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