diff options
Diffstat (limited to 'src/internal/trace/gc.go')
| -rw-r--r-- | src/internal/trace/gc.go | 825 |
1 files changed, 825 insertions, 0 deletions
diff --git a/src/internal/trace/gc.go b/src/internal/trace/gc.go new file mode 100644 index 0000000..cc19fdf --- /dev/null +++ b/src/internal/trace/gc.go @@ -0,0 +1,825 @@ +// Copyright 2017 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 trace + +import ( + "container/heap" + "math" + "sort" + "strings" + "time" +) + +// MutatorUtil is a change in mutator utilization at a particular +// time. Mutator utilization functions are represented as a +// time-ordered []MutatorUtil. +type MutatorUtil struct { + Time int64 + // Util is the mean mutator utilization starting at Time. This + // is in the range [0, 1]. + Util float64 +} + +// UtilFlags controls the behavior of MutatorUtilization. +type UtilFlags int + +const ( + // UtilSTW means utilization should account for STW events. + UtilSTW UtilFlags = 1 << iota + // UtilBackground means utilization should account for + // background mark workers. + UtilBackground + // UtilAssist means utilization should account for mark + // assists. + UtilAssist + // UtilSweep means utilization should account for sweeping. + UtilSweep + + // UtilPerProc means each P should be given a separate + // utilization function. Otherwise, there is a single function + // and each P is given a fraction of the utilization. + UtilPerProc +) + +// MutatorUtilization returns a set of mutator utilization functions +// for the given trace. Each function will always end with 0 +// utilization. The bounds of each function are implicit in the first +// and last event; outside of these bounds each function is undefined. +// +// If the UtilPerProc flag is not given, this always returns a single +// utilization function. Otherwise, it returns one function per P. +func MutatorUtilization(events []*Event, flags UtilFlags) [][]MutatorUtil { + if len(events) == 0 { + return nil + } + + type perP struct { + // gc > 0 indicates that GC is active on this P. + gc int + // series the logical series number for this P. This + // is necessary because Ps may be removed and then + // re-added, and then the new P needs a new series. + series int + } + ps := []perP{} + stw := 0 + + out := [][]MutatorUtil{} + assists := map[uint64]bool{} + block := map[uint64]*Event{} + bgMark := map[uint64]bool{} + + for _, ev := range events { + switch ev.Type { + case EvGomaxprocs: + gomaxprocs := int(ev.Args[0]) + if len(ps) > gomaxprocs { + if flags&UtilPerProc != 0 { + // End each P's series. + for _, p := range ps[gomaxprocs:] { + out[p.series] = addUtil(out[p.series], MutatorUtil{ev.Ts, 0}) + } + } + ps = ps[:gomaxprocs] + } + for len(ps) < gomaxprocs { + // Start new P's series. + series := 0 + if flags&UtilPerProc != 0 || len(out) == 0 { + series = len(out) + out = append(out, []MutatorUtil{{ev.Ts, 1}}) + } + ps = append(ps, perP{series: series}) + } + case EvGCSTWStart: + if flags&UtilSTW != 0 { + stw++ + } + case EvGCSTWDone: + if flags&UtilSTW != 0 { + stw-- + } + case EvGCMarkAssistStart: + if flags&UtilAssist != 0 { + ps[ev.P].gc++ + assists[ev.G] = true + } + case EvGCMarkAssistDone: + if flags&UtilAssist != 0 { + ps[ev.P].gc-- + delete(assists, ev.G) + } + case EvGCSweepStart: + if flags&UtilSweep != 0 { + ps[ev.P].gc++ + } + case EvGCSweepDone: + if flags&UtilSweep != 0 { + ps[ev.P].gc-- + } + case EvGoStartLabel: + if flags&UtilBackground != 0 && strings.HasPrefix(ev.SArgs[0], "GC ") && ev.SArgs[0] != "GC (idle)" { + // Background mark worker. + // + // If we're in per-proc mode, we don't + // count dedicated workers because + // they kick all of the goroutines off + // that P, so don't directly + // contribute to goroutine latency. + if !(flags&UtilPerProc != 0 && ev.SArgs[0] == "GC (dedicated)") { + bgMark[ev.G] = true + ps[ev.P].gc++ + } + } + fallthrough + case EvGoStart: + if assists[ev.G] { + // Unblocked during assist. + ps[ev.P].gc++ + } + block[ev.G] = ev.Link + default: + if ev != block[ev.G] { + continue + } + + if assists[ev.G] { + // Blocked during assist. + ps[ev.P].gc-- + } + if bgMark[ev.G] { + // Background mark worker done. + ps[ev.P].gc-- + delete(bgMark, ev.G) + } + delete(block, ev.G) + } + + if flags&UtilPerProc == 0 { + // Compute the current average utilization. + if len(ps) == 0 { + continue + } + gcPs := 0 + if stw > 0 { + gcPs = len(ps) + } else { + for i := range ps { + if ps[i].gc > 0 { + gcPs++ + } + } + } + mu := MutatorUtil{ev.Ts, 1 - float64(gcPs)/float64(len(ps))} + + // Record the utilization change. (Since + // len(ps) == len(out), we know len(out) > 0.) + out[0] = addUtil(out[0], mu) + } else { + // Check for per-P utilization changes. + for i := range ps { + p := &ps[i] + util := 1.0 + if stw > 0 || p.gc > 0 { + util = 0.0 + } + out[p.series] = addUtil(out[p.series], MutatorUtil{ev.Ts, util}) + } + } + } + + // Add final 0 utilization event to any remaining series. This + // is important to mark the end of the trace. The exact value + // shouldn't matter since no window should extend beyond this, + // but using 0 is symmetric with the start of the trace. + mu := MutatorUtil{events[len(events)-1].Ts, 0} + for i := range ps { + out[ps[i].series] = addUtil(out[ps[i].series], mu) + } + return out +} + +func addUtil(util []MutatorUtil, mu MutatorUtil) []MutatorUtil { + if len(util) > 0 { + if mu.Util == util[len(util)-1].Util { + // No change. + return util + } + if mu.Time == util[len(util)-1].Time { + // Take the lowest utilization at a time stamp. + if mu.Util < util[len(util)-1].Util { + util[len(util)-1] = mu + } + return util + } + } + return append(util, mu) +} + +// totalUtil is total utilization, measured in nanoseconds. This is a +// separate type primarily to distinguish it from mean utilization, +// which is also a float64. +type totalUtil float64 + +func totalUtilOf(meanUtil float64, dur int64) totalUtil { + return totalUtil(meanUtil * float64(dur)) +} + +// mean returns the mean utilization over dur. +func (u totalUtil) mean(dur time.Duration) float64 { + return float64(u) / float64(dur) +} + +// An MMUCurve is the minimum mutator utilization curve across +// multiple window sizes. +type MMUCurve struct { + series []mmuSeries +} + +type mmuSeries struct { + util []MutatorUtil + // sums[j] is the cumulative sum of util[:j]. + sums []totalUtil + // bands summarizes util in non-overlapping bands of duration + // bandDur. + bands []mmuBand + // bandDur is the duration of each band. + bandDur int64 +} + +type mmuBand struct { + // minUtil is the minimum instantaneous mutator utilization in + // this band. + minUtil float64 + // cumUtil is the cumulative total mutator utilization between + // time 0 and the left edge of this band. + cumUtil totalUtil + + // integrator is the integrator for the left edge of this + // band. + integrator integrator +} + +// NewMMUCurve returns an MMU curve for the given mutator utilization +// function. +func NewMMUCurve(utils [][]MutatorUtil) *MMUCurve { + series := make([]mmuSeries, len(utils)) + for i, util := range utils { + series[i] = newMMUSeries(util) + } + return &MMUCurve{series} +} + +// bandsPerSeries is the number of bands to divide each series into. +// This is only changed by tests. +var bandsPerSeries = 1000 + +func newMMUSeries(util []MutatorUtil) mmuSeries { + // Compute cumulative sum. + sums := make([]totalUtil, len(util)) + var prev MutatorUtil + var sum totalUtil + for j, u := range util { + sum += totalUtilOf(prev.Util, u.Time-prev.Time) + sums[j] = sum + prev = u + } + + // Divide the utilization curve up into equal size + // non-overlapping "bands" and compute a summary for each of + // these bands. + // + // Compute the duration of each band. + numBands := bandsPerSeries + if numBands > len(util) { + // There's no point in having lots of bands if there + // aren't many events. + numBands = len(util) + } + dur := util[len(util)-1].Time - util[0].Time + bandDur := (dur + int64(numBands) - 1) / int64(numBands) + if bandDur < 1 { + bandDur = 1 + } + // Compute the bands. There are numBands+1 bands in order to + // record the final cumulative sum. + bands := make([]mmuBand, numBands+1) + s := mmuSeries{util, sums, bands, bandDur} + leftSum := integrator{&s, 0} + for i := range bands { + startTime, endTime := s.bandTime(i) + cumUtil := leftSum.advance(startTime) + predIdx := leftSum.pos + minUtil := 1.0 + for i := predIdx; i < len(util) && util[i].Time < endTime; i++ { + minUtil = math.Min(minUtil, util[i].Util) + } + bands[i] = mmuBand{minUtil, cumUtil, leftSum} + } + + return s +} + +func (s *mmuSeries) bandTime(i int) (start, end int64) { + start = int64(i)*s.bandDur + s.util[0].Time + end = start + s.bandDur + return +} + +type bandUtil struct { + // Utilization series index + series int + // Band index + i int + // Lower bound of mutator utilization for all windows + // with a left edge in this band. + utilBound float64 +} + +type bandUtilHeap []bandUtil + +func (h bandUtilHeap) Len() int { + return len(h) +} + +func (h bandUtilHeap) Less(i, j int) bool { + return h[i].utilBound < h[j].utilBound +} + +func (h bandUtilHeap) Swap(i, j int) { + h[i], h[j] = h[j], h[i] +} + +func (h *bandUtilHeap) Push(x interface{}) { + *h = append(*h, x.(bandUtil)) +} + +func (h *bandUtilHeap) Pop() interface{} { + x := (*h)[len(*h)-1] + *h = (*h)[:len(*h)-1] + return x +} + +// UtilWindow is a specific window at Time. +type UtilWindow struct { + Time int64 + // MutatorUtil is the mean mutator utilization in this window. + MutatorUtil float64 +} + +type utilHeap []UtilWindow + +func (h utilHeap) Len() int { + return len(h) +} + +func (h utilHeap) Less(i, j int) bool { + if h[i].MutatorUtil != h[j].MutatorUtil { + return h[i].MutatorUtil > h[j].MutatorUtil + } + return h[i].Time > h[j].Time +} + +func (h utilHeap) Swap(i, j int) { + h[i], h[j] = h[j], h[i] +} + +func (h *utilHeap) Push(x interface{}) { + *h = append(*h, x.(UtilWindow)) +} + +func (h *utilHeap) Pop() interface{} { + x := (*h)[len(*h)-1] + *h = (*h)[:len(*h)-1] + return x +} + +// An accumulator takes a windowed mutator utilization function and +// tracks various statistics for that function. +type accumulator struct { + mmu float64 + + // bound is the mutator utilization bound where adding any + // mutator utilization above this bound cannot affect the + // accumulated statistics. + bound float64 + + // Worst N window tracking + nWorst int + wHeap utilHeap + + // Mutator utilization distribution tracking + mud *mud + // preciseMass is the distribution mass that must be precise + // before accumulation is stopped. + preciseMass float64 + // lastTime and lastMU are the previous point added to the + // windowed mutator utilization function. + lastTime int64 + lastMU float64 +} + +// resetTime declares a discontinuity in the windowed mutator +// utilization function by resetting the current time. +func (acc *accumulator) resetTime() { + // This only matters for distribution collection, since that's + // the only thing that depends on the progression of the + // windowed mutator utilization function. + acc.lastTime = math.MaxInt64 +} + +// addMU adds a point to the windowed mutator utilization function at +// (time, mu). This must be called for monotonically increasing values +// of time. +// +// It returns true if further calls to addMU would be pointless. +func (acc *accumulator) addMU(time int64, mu float64, window time.Duration) bool { + if mu < acc.mmu { + acc.mmu = mu + } + acc.bound = acc.mmu + + if acc.nWorst == 0 { + // If the minimum has reached zero, it can't go any + // lower, so we can stop early. + return mu == 0 + } + + // Consider adding this window to the n worst. + if len(acc.wHeap) < acc.nWorst || mu < acc.wHeap[0].MutatorUtil { + // This window is lower than the K'th worst window. + // + // Check if there's any overlapping window + // already in the heap and keep whichever is + // worse. + for i, ui := range acc.wHeap { + if time+int64(window) > ui.Time && ui.Time+int64(window) > time { + if ui.MutatorUtil <= mu { + // Keep the first window. + goto keep + } else { + // Replace it with this window. + heap.Remove(&acc.wHeap, i) + break + } + } + } + + heap.Push(&acc.wHeap, UtilWindow{time, mu}) + if len(acc.wHeap) > acc.nWorst { + heap.Pop(&acc.wHeap) + } + keep: + } + + if len(acc.wHeap) < acc.nWorst { + // We don't have N windows yet, so keep accumulating. + acc.bound = 1.0 + } else { + // Anything above the least worst window has no effect. + acc.bound = math.Max(acc.bound, acc.wHeap[0].MutatorUtil) + } + + if acc.mud != nil { + if acc.lastTime != math.MaxInt64 { + // Update distribution. + acc.mud.add(acc.lastMU, mu, float64(time-acc.lastTime)) + } + acc.lastTime, acc.lastMU = time, mu + if _, mudBound, ok := acc.mud.approxInvCumulativeSum(); ok { + acc.bound = math.Max(acc.bound, mudBound) + } else { + // We haven't accumulated enough total precise + // mass yet to even reach our goal, so keep + // accumulating. + acc.bound = 1 + } + // It's not worth checking percentiles every time, so + // just keep accumulating this band. + return false + } + + // If we've found enough 0 utilizations, we can stop immediately. + return len(acc.wHeap) == acc.nWorst && acc.wHeap[0].MutatorUtil == 0 +} + +// MMU returns the minimum mutator utilization for the given time +// window. This is the minimum utilization for all windows of this +// duration across the execution. The returned value is in the range +// [0, 1]. +func (c *MMUCurve) MMU(window time.Duration) (mmu float64) { + acc := accumulator{mmu: 1.0, bound: 1.0} + c.mmu(window, &acc) + return acc.mmu +} + +// Examples returns n specific examples of the lowest mutator +// utilization for the given window size. The returned windows will be +// disjoint (otherwise there would be a huge number of +// mostly-overlapping windows at the single lowest point). There are +// no guarantees on which set of disjoint windows this returns. +func (c *MMUCurve) Examples(window time.Duration, n int) (worst []UtilWindow) { + acc := accumulator{mmu: 1.0, bound: 1.0, nWorst: n} + c.mmu(window, &acc) + sort.Sort(sort.Reverse(acc.wHeap)) + return ([]UtilWindow)(acc.wHeap) +} + +// MUD returns mutator utilization distribution quantiles for the +// given window size. +// +// The mutator utilization distribution is the distribution of mean +// mutator utilization across all windows of the given window size in +// the trace. +// +// The minimum mutator utilization is the minimum (0th percentile) of +// this distribution. (However, if only the minimum is desired, it's +// more efficient to use the MMU method.) +func (c *MMUCurve) MUD(window time.Duration, quantiles []float64) []float64 { + if len(quantiles) == 0 { + return []float64{} + } + + // Each unrefined band contributes a known total mass to the + // distribution (bandDur except at the end), but in an unknown + // way. However, we know that all the mass it contributes must + // be at or above its worst-case mean mutator utilization. + // + // Hence, we refine bands until the highest desired + // distribution quantile is less than the next worst-case mean + // mutator utilization. At this point, all further + // contributions to the distribution must be beyond the + // desired quantile and hence cannot affect it. + // + // First, find the highest desired distribution quantile. + maxQ := quantiles[0] + for _, q := range quantiles { + if q > maxQ { + maxQ = q + } + } + // The distribution's mass is in units of time (it's not + // normalized because this would make it more annoying to + // account for future contributions of unrefined bands). The + // total final mass will be the duration of the trace itself + // minus the window size. Using this, we can compute the mass + // corresponding to quantile maxQ. + var duration int64 + for _, s := range c.series { + duration1 := s.util[len(s.util)-1].Time - s.util[0].Time + if duration1 >= int64(window) { + duration += duration1 - int64(window) + } + } + qMass := float64(duration) * maxQ + + // Accumulate the MUD until we have precise information for + // everything to the left of qMass. + acc := accumulator{mmu: 1.0, bound: 1.0, preciseMass: qMass, mud: new(mud)} + acc.mud.setTrackMass(qMass) + c.mmu(window, &acc) + + // Evaluate the quantiles on the accumulated MUD. + out := make([]float64, len(quantiles)) + for i := range out { + mu, _ := acc.mud.invCumulativeSum(float64(duration) * quantiles[i]) + if math.IsNaN(mu) { + // There are a few legitimate ways this can + // happen: + // + // 1. If the window is the full trace + // duration, then the windowed MU function is + // only defined at a single point, so the MU + // distribution is not well-defined. + // + // 2. If there are no events, then the MU + // distribution has no mass. + // + // Either way, all of the quantiles will have + // converged toward the MMU at this point. + mu = acc.mmu + } + out[i] = mu + } + return out +} + +func (c *MMUCurve) mmu(window time.Duration, acc *accumulator) { + if window <= 0 { + acc.mmu = 0 + return + } + + var bandU bandUtilHeap + windows := make([]time.Duration, len(c.series)) + for i, s := range c.series { + windows[i] = window + if max := time.Duration(s.util[len(s.util)-1].Time - s.util[0].Time); window > max { + windows[i] = max + } + + bandU1 := bandUtilHeap(s.mkBandUtil(i, windows[i])) + if bandU == nil { + bandU = bandU1 + } else { + bandU = append(bandU, bandU1...) + } + } + + // Process bands from lowest utilization bound to highest. + heap.Init(&bandU) + + // Refine each band into a precise window and MMU until + // refining the next lowest band can no longer affect the MMU + // or windows. + for len(bandU) > 0 && bandU[0].utilBound < acc.bound { + i := bandU[0].series + c.series[i].bandMMU(bandU[0].i, windows[i], acc) + heap.Pop(&bandU) + } +} + +func (c *mmuSeries) mkBandUtil(series int, window time.Duration) []bandUtil { + // For each band, compute the worst-possible total mutator + // utilization for all windows that start in that band. + + // minBands is the minimum number of bands a window can span + // and maxBands is the maximum number of bands a window can + // span in any alignment. + minBands := int((int64(window) + c.bandDur - 1) / c.bandDur) + maxBands := int((int64(window) + 2*(c.bandDur-1)) / c.bandDur) + if window > 1 && maxBands < 2 { + panic("maxBands < 2") + } + tailDur := int64(window) % c.bandDur + nUtil := len(c.bands) - maxBands + 1 + if nUtil < 0 { + nUtil = 0 + } + bandU := make([]bandUtil, nUtil) + for i := range bandU { + // To compute the worst-case MU, we assume the minimum + // for any bands that are only partially overlapped by + // some window and the mean for any bands that are + // completely covered by all windows. + var util totalUtil + + // Find the lowest and second lowest of the partial + // bands. + l := c.bands[i].minUtil + r1 := c.bands[i+minBands-1].minUtil + r2 := c.bands[i+maxBands-1].minUtil + minBand := math.Min(l, math.Min(r1, r2)) + // Assume the worst window maximally overlaps the + // worst minimum and then the rest overlaps the second + // worst minimum. + if minBands == 1 { + util += totalUtilOf(minBand, int64(window)) + } else { + util += totalUtilOf(minBand, c.bandDur) + midBand := 0.0 + switch { + case minBand == l: + midBand = math.Min(r1, r2) + case minBand == r1: + midBand = math.Min(l, r2) + case minBand == r2: + midBand = math.Min(l, r1) + } + util += totalUtilOf(midBand, tailDur) + } + + // Add the total mean MU of bands that are completely + // overlapped by all windows. + if minBands > 2 { + util += c.bands[i+minBands-1].cumUtil - c.bands[i+1].cumUtil + } + + bandU[i] = bandUtil{series, i, util.mean(window)} + } + + return bandU +} + +// bandMMU computes the precise minimum mutator utilization for +// windows with a left edge in band bandIdx. +func (c *mmuSeries) bandMMU(bandIdx int, window time.Duration, acc *accumulator) { + util := c.util + + // We think of the mutator utilization over time as the + // box-filtered utilization function, which we call the + // "windowed mutator utilization function". The resulting + // function is continuous and piecewise linear (unless + // window==0, which we handle elsewhere), where the boundaries + // between segments occur when either edge of the window + // encounters a change in the instantaneous mutator + // utilization function. Hence, the minimum of this function + // will always occur when one of the edges of the window + // aligns with a utilization change, so these are the only + // points we need to consider. + // + // We compute the mutator utilization function incrementally + // by tracking the integral from t=0 to the left edge of the + // window and to the right edge of the window. + left := c.bands[bandIdx].integrator + right := left + time, endTime := c.bandTime(bandIdx) + if utilEnd := util[len(util)-1].Time - int64(window); utilEnd < endTime { + endTime = utilEnd + } + acc.resetTime() + for { + // Advance edges to time and time+window. + mu := (right.advance(time+int64(window)) - left.advance(time)).mean(window) + if acc.addMU(time, mu, window) { + break + } + if time == endTime { + break + } + + // The maximum slope of the windowed mutator + // utilization function is 1/window, so we can always + // advance the time by at least (mu - mmu) * window + // without dropping below mmu. + minTime := time + int64((mu-acc.bound)*float64(window)) + + // Advance the window to the next time where either + // the left or right edge of the window encounters a + // change in the utilization curve. + if t1, t2 := left.next(time), right.next(time+int64(window))-int64(window); t1 < t2 { + time = t1 + } else { + time = t2 + } + if time < minTime { + time = minTime + } + if time >= endTime { + // For MMUs we could stop here, but for MUDs + // it's important that we span the entire + // band. + time = endTime + } + } +} + +// An integrator tracks a position in a utilization function and +// integrates it. +type integrator struct { + u *mmuSeries + // pos is the index in u.util of the current time's non-strict + // predecessor. + pos int +} + +// advance returns the integral of the utilization function from 0 to +// time. advance must be called on monotonically increasing values of +// times. +func (in *integrator) advance(time int64) totalUtil { + util, pos := in.u.util, in.pos + // Advance pos until pos+1 is time's strict successor (making + // pos time's non-strict predecessor). + // + // Very often, this will be nearby, so we optimize that case, + // but it may be arbitrarily far away, so we handled that + // efficiently, too. + const maxSeq = 8 + if pos+maxSeq < len(util) && util[pos+maxSeq].Time > time { + // Nearby. Use a linear scan. + for pos+1 < len(util) && util[pos+1].Time <= time { + pos++ + } + } else { + // Far. Binary search for time's strict successor. + l, r := pos, len(util) + for l < r { + h := int(uint(l+r) >> 1) + if util[h].Time <= time { + l = h + 1 + } else { + r = h + } + } + pos = l - 1 // Non-strict predecessor. + } + in.pos = pos + var partial totalUtil + if time != util[pos].Time { + partial = totalUtilOf(util[pos].Util, time-util[pos].Time) + } + return in.u.sums[pos] + partial +} + +// next returns the smallest time t' > time of a change in the +// utilization function. +func (in *integrator) next(time int64) int64 { + for _, u := range in.u.util[in.pos:] { + if u.Time > time { + return u.Time + } + } + return 1<<63 - 1 +} |