gc.go

Documentation: internal/trace

     1  // Copyright 2017 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package trace
     6  
     7  import (
     8  	"container/heap"
     9  	"math"
    10  	"sort"
    11  	"strings"
    12  	"time"
    13  )
    14  
    15  // MutatorUtil is a change in mutator utilization at a particular
    16  // time. Mutator utilization functions are represented as a
    17  // time-ordered []MutatorUtil.
    18  type MutatorUtil struct {
    19  	Time int64
    20  	// Util is the mean mutator utilization starting at Time. This
    21  	// is in the range [0, 1].
    22  	Util float64
    23  }
    24  
    25  // UtilFlags controls the behavior of MutatorUtilization.
    26  type UtilFlags int
    27  
    28  const (
    29  	// UtilSTW means utilization should account for STW events.
    30  	// This includes non-GC STW events, which are typically user-requested.
    31  	UtilSTW UtilFlags = 1 << iota
    32  	// UtilBackground means utilization should account for
    33  	// background mark workers.
    34  	UtilBackground
    35  	// UtilAssist means utilization should account for mark
    36  	// assists.
    37  	UtilAssist
    38  	// UtilSweep means utilization should account for sweeping.
    39  	UtilSweep
    40  
    41  	// UtilPerProc means each P should be given a separate
    42  	// utilization function. Otherwise, there is a single function
    43  	// and each P is given a fraction of the utilization.
    44  	UtilPerProc
    45  )
    46  
    47  // MutatorUtilizationV2 returns a set of mutator utilization functions
    48  // for the given v2 trace, passed as an io.Reader. Each function will
    49  // always end with 0 utilization. The bounds of each function are implicit
    50  // in the first and last event; outside of these bounds each function is
    51  // undefined.
    52  //
    53  // If the UtilPerProc flag is not given, this always returns a single
    54  // utilization function. Otherwise, it returns one function per P.
    55  func MutatorUtilizationV2(events []Event, flags UtilFlags) [][]MutatorUtil {
    56  	// Set up a bunch of analysis state.
    57  	type perP struct {
    58  		// gc > 0 indicates that GC is active on this P.
    59  		gc int
    60  		// series the logical series number for this P. This
    61  		// is necessary because Ps may be removed and then
    62  		// re-added, and then the new P needs a new series.
    63  		series int
    64  	}
    65  	type procsCount struct {
    66  		// time at which procs changed.
    67  		time int64
    68  		// n is the number of procs at that point.
    69  		n int
    70  	}
    71  	out := [][]MutatorUtil{}
    72  	stw := 0
    73  	ps := []perP{}
    74  	inGC := make(map[GoID]bool)
    75  	states := make(map[GoID]GoState)
    76  	bgMark := make(map[GoID]bool)
    77  	procs := []procsCount{}
    78  	seenSync := false
    79  
    80  	// Helpers.
    81  	handleSTW := func(r Range) bool {
    82  		return flags&UtilSTW != 0 && isGCSTW(r)
    83  	}
    84  	handleMarkAssist := func(r Range) bool {
    85  		return flags&UtilAssist != 0 && isGCMarkAssist(r)
    86  	}
    87  	handleSweep := func(r Range) bool {
    88  		return flags&UtilSweep != 0 && isGCSweep(r)
    89  	}
    90  
    91  	// Iterate through the trace, tracking mutator utilization.
    92  	var lastEv *Event
    93  	for i := range events {
    94  		ev := &events[i]
    95  		lastEv = ev
    96  
    97  		// Process the event.
    98  		switch ev.Kind() {
    99  		case EventSync:
   100  			seenSync = true
   101  		case EventMetric:
   102  			m := ev.Metric()
   103  			if m.Name != "/sched/gomaxprocs:threads" {
   104  				break
   105  			}
   106  			gomaxprocs := int(m.Value.Uint64())
   107  			if len(ps) > gomaxprocs {
   108  				if flags&UtilPerProc != 0 {
   109  					// End each P's series.
   110  					for _, p := range ps[gomaxprocs:] {
   111  						out[p.series] = addUtil(out[p.series], MutatorUtil{int64(ev.Time()), 0})
   112  					}
   113  				}
   114  				ps = ps[:gomaxprocs]
   115  			}
   116  			for len(ps) < gomaxprocs {
   117  				// Start new P's series.
   118  				series := 0
   119  				if flags&UtilPerProc != 0 || len(out) == 0 {
   120  					series = len(out)
   121  					out = append(out, []MutatorUtil{{int64(ev.Time()), 1}})
   122  				}
   123  				ps = append(ps, perP{series: series})
   124  			}
   125  			if len(procs) == 0 || gomaxprocs != procs[len(procs)-1].n {
   126  				procs = append(procs, procsCount{time: int64(ev.Time()), n: gomaxprocs})
   127  			}
   128  		}
   129  		if len(ps) == 0 {
   130  			// We can't start doing any analysis until we see what GOMAXPROCS is.
   131  			// It will show up very early in the trace, but we need to be robust to
   132  			// something else being emitted beforehand.
   133  			continue
   134  		}
   135  
   136  		switch ev.Kind() {
   137  		case EventRangeActive:
   138  			if seenSync {
   139  				// If we've seen a sync, then we can be sure we're not finding out about
   140  				// something late; we have complete information after that point, and these
   141  				// active events will just be redundant.
   142  				break
   143  			}
   144  			// This range is active back to the start of the trace. We're failing to account
   145  			// for this since we just found out about it now. Fix up the mutator utilization.
   146  			//
   147  			// N.B. A trace can't start during a STW, so we don't handle it here.
   148  			r := ev.Range()
   149  			switch {
   150  			case handleMarkAssist(r):
   151  				if !states[ev.Goroutine()].Executing() {
   152  					// If the goroutine isn't executing, then the fact that it was in mark
   153  					// assist doesn't actually count.
   154  					break
   155  				}
   156  				// This G has been in a mark assist *and running on its P* since the start
   157  				// of the trace.
   158  				fallthrough
   159  			case handleSweep(r):
   160  				// This P has been in sweep (or mark assist, from above) in the start of the trace.
   161  				//
   162  				// We don't need to do anything if UtilPerProc is set. If we get an event like
   163  				// this for a running P, it must show up the first time a P is mentioned. Therefore,
   164  				// this P won't actually have any MutatorUtils on its list yet.
   165  				//
   166  				// However, if UtilPerProc isn't set, then we probably have data from other procs
   167  				// and from previous events. We need to fix that up.
   168  				if flags&UtilPerProc != 0 {
   169  					break
   170  				}
   171  				// Subtract out 1/gomaxprocs mutator utilization for all time periods
   172  				// from the beginning of the trace until now.
   173  				mi, pi := 0, 0
   174  				for mi < len(out[0]) {
   175  					if pi < len(procs)-1 && procs[pi+1].time < out[0][mi].Time {
   176  						pi++
   177  						continue
   178  					}
   179  					out[0][mi].Util -= float64(1) / float64(procs[pi].n)
   180  					if out[0][mi].Util < 0 {
   181  						out[0][mi].Util = 0
   182  					}
   183  					mi++
   184  				}
   185  			}
   186  			// After accounting for the portion we missed, this just acts like the
   187  			// beginning of a new range.
   188  			fallthrough
   189  		case EventRangeBegin:
   190  			r := ev.Range()
   191  			if handleSTW(r) {
   192  				stw++
   193  			} else if handleSweep(r) {
   194  				ps[ev.Proc()].gc++
   195  			} else if handleMarkAssist(r) {
   196  				ps[ev.Proc()].gc++
   197  				if g := r.Scope.Goroutine(); g != NoGoroutine {
   198  					inGC[g] = true
   199  				}
   200  			}
   201  		case EventRangeEnd:
   202  			r := ev.Range()
   203  			if handleSTW(r) {
   204  				stw--
   205  			} else if handleSweep(r) {
   206  				ps[ev.Proc()].gc--
   207  			} else if handleMarkAssist(r) {
   208  				ps[ev.Proc()].gc--
   209  				if g := r.Scope.Goroutine(); g != NoGoroutine {
   210  					delete(inGC, g)
   211  				}
   212  			}
   213  		case EventStateTransition:
   214  			st := ev.StateTransition()
   215  			if st.Resource.Kind != ResourceGoroutine {
   216  				break
   217  			}
   218  			old, new := st.Goroutine()
   219  			g := st.Resource.Goroutine()
   220  			if inGC[g] || bgMark[g] {
   221  				if !old.Executing() && new.Executing() {
   222  					// Started running while doing GC things.
   223  					ps[ev.Proc()].gc++
   224  				} else if old.Executing() && !new.Executing() {
   225  					// Stopped running while doing GC things.
   226  					ps[ev.Proc()].gc--
   227  				}
   228  			}
   229  			states[g] = new
   230  		case EventLabel:
   231  			l := ev.Label()
   232  			if flags&UtilBackground != 0 && strings.HasPrefix(l.Label, "GC ") && l.Label != "GC (idle)" {
   233  				// Background mark worker.
   234  				//
   235  				// If we're in per-proc mode, we don't
   236  				// count dedicated workers because
   237  				// they kick all of the goroutines off
   238  				// that P, so don't directly
   239  				// contribute to goroutine latency.
   240  				if !(flags&UtilPerProc != 0 && l.Label == "GC (dedicated)") {
   241  					bgMark[ev.Goroutine()] = true
   242  					ps[ev.Proc()].gc++
   243  				}
   244  			}
   245  		}
   246  
   247  		if flags&UtilPerProc == 0 {
   248  			// Compute the current average utilization.
   249  			if len(ps) == 0 {
   250  				continue
   251  			}
   252  			gcPs := 0
   253  			if stw > 0 {
   254  				gcPs = len(ps)
   255  			} else {
   256  				for i := range ps {
   257  					if ps[i].gc > 0 {
   258  						gcPs++
   259  					}
   260  				}
   261  			}
   262  			mu := MutatorUtil{int64(ev.Time()), 1 - float64(gcPs)/float64(len(ps))}
   263  
   264  			// Record the utilization change. (Since
   265  			// len(ps) == len(out), we know len(out) > 0.)
   266  			out[0] = addUtil(out[0], mu)
   267  		} else {
   268  			// Check for per-P utilization changes.
   269  			for i := range ps {
   270  				p := &ps[i]
   271  				util := 1.0
   272  				if stw > 0 || p.gc > 0 {
   273  					util = 0.0
   274  				}
   275  				out[p.series] = addUtil(out[p.series], MutatorUtil{int64(ev.Time()), util})
   276  			}
   277  		}
   278  	}
   279  
   280  	// No events in the stream.
   281  	if lastEv == nil {
   282  		return nil
   283  	}
   284  
   285  	// Add final 0 utilization event to any remaining series. This
   286  	// is important to mark the end of the trace. The exact value
   287  	// shouldn't matter since no window should extend beyond this,
   288  	// but using 0 is symmetric with the start of the trace.
   289  	mu := MutatorUtil{int64(lastEv.Time()), 0}
   290  	for i := range ps {
   291  		out[ps[i].series] = addUtil(out[ps[i].series], mu)
   292  	}
   293  	return out
   294  }
   295  
   296  func addUtil(util []MutatorUtil, mu MutatorUtil) []MutatorUtil {
   297  	if len(util) > 0 {
   298  		if mu.Util == util[len(util)-1].Util {
   299  			// No change.
   300  			return util
   301  		}
   302  		if mu.Time == util[len(util)-1].Time {
   303  			// Take the lowest utilization at a time stamp.
   304  			if mu.Util < util[len(util)-1].Util {
   305  				util[len(util)-1] = mu
   306  			}
   307  			return util
   308  		}
   309  	}
   310  	return append(util, mu)
   311  }
   312  
   313  // totalUtil is total utilization, measured in nanoseconds. This is a
   314  // separate type primarily to distinguish it from mean utilization,
   315  // which is also a float64.
   316  type totalUtil float64
   317  
   318  func totalUtilOf(meanUtil float64, dur int64) totalUtil {
   319  	return totalUtil(meanUtil * float64(dur))
   320  }
   321  
   322  // mean returns the mean utilization over dur.
   323  func (u totalUtil) mean(dur time.Duration) float64 {
   324  	return float64(u) / float64(dur)
   325  }
   326  
   327  // An MMUCurve is the minimum mutator utilization curve across
   328  // multiple window sizes.
   329  type MMUCurve struct {
   330  	series []mmuSeries
   331  }
   332  
   333  type mmuSeries struct {
   334  	util []MutatorUtil
   335  	// sums[j] is the cumulative sum of util[:j].
   336  	sums []totalUtil
   337  	// bands summarizes util in non-overlapping bands of duration
   338  	// bandDur.
   339  	bands []mmuBand
   340  	// bandDur is the duration of each band.
   341  	bandDur int64
   342  }
   343  
   344  type mmuBand struct {
   345  	// minUtil is the minimum instantaneous mutator utilization in
   346  	// this band.
   347  	minUtil float64
   348  	// cumUtil is the cumulative total mutator utilization between
   349  	// time 0 and the left edge of this band.
   350  	cumUtil totalUtil
   351  
   352  	// integrator is the integrator for the left edge of this
   353  	// band.
   354  	integrator integrator
   355  }
   356  
   357  // NewMMUCurve returns an MMU curve for the given mutator utilization
   358  // function.
   359  func NewMMUCurve(utils [][]MutatorUtil) *MMUCurve {
   360  	series := make([]mmuSeries, len(utils))
   361  	for i, util := range utils {
   362  		series[i] = newMMUSeries(util)
   363  	}
   364  	return &MMUCurve{series}
   365  }
   366  
   367  // bandsPerSeries is the number of bands to divide each series into.
   368  // This is only changed by tests.
   369  var bandsPerSeries = 1000
   370  
   371  func newMMUSeries(util []MutatorUtil) mmuSeries {
   372  	// Compute cumulative sum.
   373  	sums := make([]totalUtil, len(util))
   374  	var prev MutatorUtil
   375  	var sum totalUtil
   376  	for j, u := range util {
   377  		sum += totalUtilOf(prev.Util, u.Time-prev.Time)
   378  		sums[j] = sum
   379  		prev = u
   380  	}
   381  
   382  	// Divide the utilization curve up into equal size
   383  	// non-overlapping "bands" and compute a summary for each of
   384  	// these bands.
   385  	//
   386  	// Compute the duration of each band.
   387  	numBands := bandsPerSeries
   388  	if numBands > len(util) {
   389  		// There's no point in having lots of bands if there
   390  		// aren't many events.
   391  		numBands = len(util)
   392  	}
   393  	dur := util[len(util)-1].Time - util[0].Time
   394  	bandDur := (dur + int64(numBands) - 1) / int64(numBands)
   395  	if bandDur < 1 {
   396  		bandDur = 1
   397  	}
   398  	// Compute the bands. There are numBands+1 bands in order to
   399  	// record the final cumulative sum.
   400  	bands := make([]mmuBand, numBands+1)
   401  	s := mmuSeries{util, sums, bands, bandDur}
   402  	leftSum := integrator{&s, 0}
   403  	for i := range bands {
   404  		startTime, endTime := s.bandTime(i)
   405  		cumUtil := leftSum.advance(startTime)
   406  		predIdx := leftSum.pos
   407  		minUtil := 1.0
   408  		for i := predIdx; i < len(util) && util[i].Time < endTime; i++ {
   409  			minUtil = math.Min(minUtil, util[i].Util)
   410  		}
   411  		bands[i] = mmuBand{minUtil, cumUtil, leftSum}
   412  	}
   413  
   414  	return s
   415  }
   416  
   417  func (s *mmuSeries) bandTime(i int) (start, end int64) {
   418  	start = int64(i)*s.bandDur + s.util[0].Time
   419  	end = start + s.bandDur
   420  	return
   421  }
   422  
   423  type bandUtil struct {
   424  	// Utilization series index
   425  	series int
   426  	// Band index
   427  	i int
   428  	// Lower bound of mutator utilization for all windows
   429  	// with a left edge in this band.
   430  	utilBound float64
   431  }
   432  
   433  type bandUtilHeap []bandUtil
   434  
   435  func (h bandUtilHeap) Len() int {
   436  	return len(h)
   437  }
   438  
   439  func (h bandUtilHeap) Less(i, j int) bool {
   440  	return h[i].utilBound < h[j].utilBound
   441  }
   442  
   443  func (h bandUtilHeap) Swap(i, j int) {
   444  	h[i], h[j] = h[j], h[i]
   445  }
   446  
   447  func (h *bandUtilHeap) Push(x any) {
   448  	*h = append(*h, x.(bandUtil))
   449  }
   450  
   451  func (h *bandUtilHeap) Pop() any {
   452  	x := (*h)[len(*h)-1]
   453  	*h = (*h)[:len(*h)-1]
   454  	return x
   455  }
   456  
   457  // UtilWindow is a specific window at Time.
   458  type UtilWindow struct {
   459  	Time int64
   460  	// MutatorUtil is the mean mutator utilization in this window.
   461  	MutatorUtil float64
   462  }
   463  
   464  type utilHeap []UtilWindow
   465  
   466  func (h utilHeap) Len() int {
   467  	return len(h)
   468  }
   469  
   470  func (h utilHeap) Less(i, j int) bool {
   471  	if h[i].MutatorUtil != h[j].MutatorUtil {
   472  		return h[i].MutatorUtil > h[j].MutatorUtil
   473  	}
   474  	return h[i].Time > h[j].Time
   475  }
   476  
   477  func (h utilHeap) Swap(i, j int) {
   478  	h[i], h[j] = h[j], h[i]
   479  }
   480  
   481  func (h *utilHeap) Push(x any) {
   482  	*h = append(*h, x.(UtilWindow))
   483  }
   484  
   485  func (h *utilHeap) Pop() any {
   486  	x := (*h)[len(*h)-1]
   487  	*h = (*h)[:len(*h)-1]
   488  	return x
   489  }
   490  
   491  // An accumulator takes a windowed mutator utilization function and
   492  // tracks various statistics for that function.
   493  type accumulator struct {
   494  	mmu float64
   495  
   496  	// bound is the mutator utilization bound where adding any
   497  	// mutator utilization above this bound cannot affect the
   498  	// accumulated statistics.
   499  	bound float64
   500  
   501  	// Worst N window tracking
   502  	nWorst int
   503  	wHeap  utilHeap
   504  
   505  	// Mutator utilization distribution tracking
   506  	mud *mud
   507  	// preciseMass is the distribution mass that must be precise
   508  	// before accumulation is stopped.
   509  	preciseMass float64
   510  	// lastTime and lastMU are the previous point added to the
   511  	// windowed mutator utilization function.
   512  	lastTime int64
   513  	lastMU   float64
   514  }
   515  
   516  // resetTime declares a discontinuity in the windowed mutator
   517  // utilization function by resetting the current time.
   518  func (acc *accumulator) resetTime() {
   519  	// This only matters for distribution collection, since that's
   520  	// the only thing that depends on the progression of the
   521  	// windowed mutator utilization function.
   522  	acc.lastTime = math.MaxInt64
   523  }
   524  
   525  // addMU adds a point to the windowed mutator utilization function at
   526  // (time, mu). This must be called for monotonically increasing values
   527  // of time.
   528  //
   529  // It returns true if further calls to addMU would be pointless.
   530  func (acc *accumulator) addMU(time int64, mu float64, window time.Duration) bool {
   531  	if mu < acc.mmu {
   532  		acc.mmu = mu
   533  	}
   534  	acc.bound = acc.mmu
   535  
   536  	if acc.nWorst == 0 {
   537  		// If the minimum has reached zero, it can't go any
   538  		// lower, so we can stop early.
   539  		return mu == 0
   540  	}
   541  
   542  	// Consider adding this window to the n worst.
   543  	if len(acc.wHeap) < acc.nWorst || mu < acc.wHeap[0].MutatorUtil {
   544  		// This window is lower than the K'th worst window.
   545  		//
   546  		// Check if there's any overlapping window
   547  		// already in the heap and keep whichever is
   548  		// worse.
   549  		for i, ui := range acc.wHeap {
   550  			if time+int64(window) > ui.Time && ui.Time+int64(window) > time {
   551  				if ui.MutatorUtil <= mu {
   552  					// Keep the first window.
   553  					goto keep
   554  				} else {
   555  					// Replace it with this window.
   556  					heap.Remove(&acc.wHeap, i)
   557  					break
   558  				}
   559  			}
   560  		}
   561  
   562  		heap.Push(&acc.wHeap, UtilWindow{time, mu})
   563  		if len(acc.wHeap) > acc.nWorst {
   564  			heap.Pop(&acc.wHeap)
   565  		}
   566  	keep:
   567  	}
   568  
   569  	if len(acc.wHeap) < acc.nWorst {
   570  		// We don't have N windows yet, so keep accumulating.
   571  		acc.bound = 1.0
   572  	} else {
   573  		// Anything above the least worst window has no effect.
   574  		acc.bound = math.Max(acc.bound, acc.wHeap[0].MutatorUtil)
   575  	}
   576  
   577  	if acc.mud != nil {
   578  		if acc.lastTime != math.MaxInt64 {
   579  			// Update distribution.
   580  			acc.mud.add(acc.lastMU, mu, float64(time-acc.lastTime))
   581  		}
   582  		acc.lastTime, acc.lastMU = time, mu
   583  		if _, mudBound, ok := acc.mud.approxInvCumulativeSum(); ok {
   584  			acc.bound = math.Max(acc.bound, mudBound)
   585  		} else {
   586  			// We haven't accumulated enough total precise
   587  			// mass yet to even reach our goal, so keep
   588  			// accumulating.
   589  			acc.bound = 1
   590  		}
   591  		// It's not worth checking percentiles every time, so
   592  		// just keep accumulating this band.
   593  		return false
   594  	}
   595  
   596  	// If we've found enough 0 utilizations, we can stop immediately.
   597  	return len(acc.wHeap) == acc.nWorst && acc.wHeap[0].MutatorUtil == 0
   598  }
   599  
   600  // MMU returns the minimum mutator utilization for the given time
   601  // window. This is the minimum utilization for all windows of this
   602  // duration across the execution. The returned value is in the range
   603  // [0, 1].
   604  func (c *MMUCurve) MMU(window time.Duration) (mmu float64) {
   605  	acc := accumulator{mmu: 1.0, bound: 1.0}
   606  	c.mmu(window, &acc)
   607  	return acc.mmu
   608  }
   609  
   610  // Examples returns n specific examples of the lowest mutator
   611  // utilization for the given window size. The returned windows will be
   612  // disjoint (otherwise there would be a huge number of
   613  // mostly-overlapping windows at the single lowest point). There are
   614  // no guarantees on which set of disjoint windows this returns.
   615  func (c *MMUCurve) Examples(window time.Duration, n int) (worst []UtilWindow) {
   616  	acc := accumulator{mmu: 1.0, bound: 1.0, nWorst: n}
   617  	c.mmu(window, &acc)
   618  	sort.Sort(sort.Reverse(acc.wHeap))
   619  	return ([]UtilWindow)(acc.wHeap)
   620  }
   621  
   622  // MUD returns mutator utilization distribution quantiles for the
   623  // given window size.
   624  //
   625  // The mutator utilization distribution is the distribution of mean
   626  // mutator utilization across all windows of the given window size in
   627  // the trace.
   628  //
   629  // The minimum mutator utilization is the minimum (0th percentile) of
   630  // this distribution. (However, if only the minimum is desired, it's
   631  // more efficient to use the MMU method.)
   632  func (c *MMUCurve) MUD(window time.Duration, quantiles []float64) []float64 {
   633  	if len(quantiles) == 0 {
   634  		return []float64{}
   635  	}
   636  
   637  	// Each unrefined band contributes a known total mass to the
   638  	// distribution (bandDur except at the end), but in an unknown
   639  	// way. However, we know that all the mass it contributes must
   640  	// be at or above its worst-case mean mutator utilization.
   641  	//
   642  	// Hence, we refine bands until the highest desired
   643  	// distribution quantile is less than the next worst-case mean
   644  	// mutator utilization. At this point, all further
   645  	// contributions to the distribution must be beyond the
   646  	// desired quantile and hence cannot affect it.
   647  	//
   648  	// First, find the highest desired distribution quantile.
   649  	maxQ := quantiles[0]
   650  	for _, q := range quantiles {
   651  		if q > maxQ {
   652  			maxQ = q
   653  		}
   654  	}
   655  	// The distribution's mass is in units of time (it's not
   656  	// normalized because this would make it more annoying to
   657  	// account for future contributions of unrefined bands). The
   658  	// total final mass will be the duration of the trace itself
   659  	// minus the window size. Using this, we can compute the mass
   660  	// corresponding to quantile maxQ.
   661  	var duration int64
   662  	for _, s := range c.series {
   663  		duration1 := s.util[len(s.util)-1].Time - s.util[0].Time
   664  		if duration1 >= int64(window) {
   665  			duration += duration1 - int64(window)
   666  		}
   667  	}
   668  	qMass := float64(duration) * maxQ
   669  
   670  	// Accumulate the MUD until we have precise information for
   671  	// everything to the left of qMass.
   672  	acc := accumulator{mmu: 1.0, bound: 1.0, preciseMass: qMass, mud: new(mud)}
   673  	acc.mud.setTrackMass(qMass)
   674  	c.mmu(window, &acc)
   675  
   676  	// Evaluate the quantiles on the accumulated MUD.
   677  	out := make([]float64, len(quantiles))
   678  	for i := range out {
   679  		mu, _ := acc.mud.invCumulativeSum(float64(duration) * quantiles[i])
   680  		if math.IsNaN(mu) {
   681  			// There are a few legitimate ways this can
   682  			// happen:
   683  			//
   684  			// 1. If the window is the full trace
   685  			// duration, then the windowed MU function is
   686  			// only defined at a single point, so the MU
   687  			// distribution is not well-defined.
   688  			//
   689  			// 2. If there are no events, then the MU
   690  			// distribution has no mass.
   691  			//
   692  			// Either way, all of the quantiles will have
   693  			// converged toward the MMU at this point.
   694  			mu = acc.mmu
   695  		}
   696  		out[i] = mu
   697  	}
   698  	return out
   699  }
   700  
   701  func (c *MMUCurve) mmu(window time.Duration, acc *accumulator) {
   702  	if window <= 0 {
   703  		acc.mmu = 0
   704  		return
   705  	}
   706  
   707  	var bandU bandUtilHeap
   708  	windows := make([]time.Duration, len(c.series))
   709  	for i, s := range c.series {
   710  		windows[i] = window
   711  		if max := time.Duration(s.util[len(s.util)-1].Time - s.util[0].Time); window > max {
   712  			windows[i] = max
   713  		}
   714  
   715  		bandU1 := bandUtilHeap(s.mkBandUtil(i, windows[i]))
   716  		if bandU == nil {
   717  			bandU = bandU1
   718  		} else {
   719  			bandU = append(bandU, bandU1...)
   720  		}
   721  	}
   722  
   723  	// Process bands from lowest utilization bound to highest.
   724  	heap.Init(&bandU)
   725  
   726  	// Refine each band into a precise window and MMU until
   727  	// refining the next lowest band can no longer affect the MMU
   728  	// or windows.
   729  	for len(bandU) > 0 && bandU[0].utilBound < acc.bound {
   730  		i := bandU[0].series
   731  		c.series[i].bandMMU(bandU[0].i, windows[i], acc)
   732  		heap.Pop(&bandU)
   733  	}
   734  }
   735  
   736  func (c *mmuSeries) mkBandUtil(series int, window time.Duration) []bandUtil {
   737  	// For each band, compute the worst-possible total mutator
   738  	// utilization for all windows that start in that band.
   739  
   740  	// minBands is the minimum number of bands a window can span
   741  	// and maxBands is the maximum number of bands a window can
   742  	// span in any alignment.
   743  	minBands := int((int64(window) + c.bandDur - 1) / c.bandDur)
   744  	maxBands := int((int64(window) + 2*(c.bandDur-1)) / c.bandDur)
   745  	if window > 1 && maxBands < 2 {
   746  		panic("maxBands < 2")
   747  	}
   748  	tailDur := int64(window) % c.bandDur
   749  	nUtil := len(c.bands) - maxBands + 1
   750  	if nUtil < 0 {
   751  		nUtil = 0
   752  	}
   753  	bandU := make([]bandUtil, nUtil)
   754  	for i := range bandU {
   755  		// To compute the worst-case MU, we assume the minimum
   756  		// for any bands that are only partially overlapped by
   757  		// some window and the mean for any bands that are
   758  		// completely covered by all windows.
   759  		var util totalUtil
   760  
   761  		// Find the lowest and second lowest of the partial
   762  		// bands.
   763  		l := c.bands[i].minUtil
   764  		r1 := c.bands[i+minBands-1].minUtil
   765  		r2 := c.bands[i+maxBands-1].minUtil
   766  		minBand := math.Min(l, math.Min(r1, r2))
   767  		// Assume the worst window maximally overlaps the
   768  		// worst minimum and then the rest overlaps the second
   769  		// worst minimum.
   770  		if minBands == 1 {
   771  			util += totalUtilOf(minBand, int64(window))
   772  		} else {
   773  			util += totalUtilOf(minBand, c.bandDur)
   774  			midBand := 0.0
   775  			switch {
   776  			case minBand == l:
   777  				midBand = math.Min(r1, r2)
   778  			case minBand == r1:
   779  				midBand = math.Min(l, r2)
   780  			case minBand == r2:
   781  				midBand = math.Min(l, r1)
   782  			}
   783  			util += totalUtilOf(midBand, tailDur)
   784  		}
   785  
   786  		// Add the total mean MU of bands that are completely
   787  		// overlapped by all windows.
   788  		if minBands > 2 {
   789  			util += c.bands[i+minBands-1].cumUtil - c.bands[i+1].cumUtil
   790  		}
   791  
   792  		bandU[i] = bandUtil{series, i, util.mean(window)}
   793  	}
   794  
   795  	return bandU
   796  }
   797  
   798  // bandMMU computes the precise minimum mutator utilization for
   799  // windows with a left edge in band bandIdx.
   800  func (c *mmuSeries) bandMMU(bandIdx int, window time.Duration, acc *accumulator) {
   801  	util := c.util
   802  
   803  	// We think of the mutator utilization over time as the
   804  	// box-filtered utilization function, which we call the
   805  	// "windowed mutator utilization function". The resulting
   806  	// function is continuous and piecewise linear (unless
   807  	// window==0, which we handle elsewhere), where the boundaries
   808  	// between segments occur when either edge of the window
   809  	// encounters a change in the instantaneous mutator
   810  	// utilization function. Hence, the minimum of this function
   811  	// will always occur when one of the edges of the window
   812  	// aligns with a utilization change, so these are the only
   813  	// points we need to consider.
   814  	//
   815  	// We compute the mutator utilization function incrementally
   816  	// by tracking the integral from t=0 to the left edge of the
   817  	// window and to the right edge of the window.
   818  	left := c.bands[bandIdx].integrator
   819  	right := left
   820  	time, endTime := c.bandTime(bandIdx)
   821  	if utilEnd := util[len(util)-1].Time - int64(window); utilEnd < endTime {
   822  		endTime = utilEnd
   823  	}
   824  	acc.resetTime()
   825  	for {
   826  		// Advance edges to time and time+window.
   827  		mu := (right.advance(time+int64(window)) - left.advance(time)).mean(window)
   828  		if acc.addMU(time, mu, window) {
   829  			break
   830  		}
   831  		if time == endTime {
   832  			break
   833  		}
   834  
   835  		// The maximum slope of the windowed mutator
   836  		// utilization function is 1/window, so we can always
   837  		// advance the time by at least (mu - mmu) * window
   838  		// without dropping below mmu.
   839  		minTime := time + int64((mu-acc.bound)*float64(window))
   840  
   841  		// Advance the window to the next time where either
   842  		// the left or right edge of the window encounters a
   843  		// change in the utilization curve.
   844  		if t1, t2 := left.next(time), right.next(time+int64(window))-int64(window); t1 < t2 {
   845  			time = t1
   846  		} else {
   847  			time = t2
   848  		}
   849  		if time < minTime {
   850  			time = minTime
   851  		}
   852  		if time >= endTime {
   853  			// For MMUs we could stop here, but for MUDs
   854  			// it's important that we span the entire
   855  			// band.
   856  			time = endTime
   857  		}
   858  	}
   859  }
   860  
   861  // An integrator tracks a position in a utilization function and
   862  // integrates it.
   863  type integrator struct {
   864  	u *mmuSeries
   865  	// pos is the index in u.util of the current time's non-strict
   866  	// predecessor.
   867  	pos int
   868  }
   869  
   870  // advance returns the integral of the utilization function from 0 to
   871  // time. advance must be called on monotonically increasing values of
   872  // times.
   873  func (in *integrator) advance(time int64) totalUtil {
   874  	util, pos := in.u.util, in.pos
   875  	// Advance pos until pos+1 is time's strict successor (making
   876  	// pos time's non-strict predecessor).
   877  	//
   878  	// Very often, this will be nearby, so we optimize that case,
   879  	// but it may be arbitrarily far away, so we handled that
   880  	// efficiently, too.
   881  	const maxSeq = 8
   882  	if pos+maxSeq < len(util) && util[pos+maxSeq].Time > time {
   883  		// Nearby. Use a linear scan.
   884  		for pos+1 < len(util) && util[pos+1].Time <= time {
   885  			pos++
   886  		}
   887  	} else {
   888  		// Far. Binary search for time's strict successor.
   889  		l, r := pos, len(util)
   890  		for l < r {
   891  			h := int(uint(l+r) >> 1)
   892  			if util[h].Time <= time {
   893  				l = h + 1
   894  			} else {
   895  				r = h
   896  			}
   897  		}
   898  		pos = l - 1 // Non-strict predecessor.
   899  	}
   900  	in.pos = pos
   901  	var partial totalUtil
   902  	if time != util[pos].Time {
   903  		partial = totalUtilOf(util[pos].Util, time-util[pos].Time)
   904  	}
   905  	return in.u.sums[pos] + partial
   906  }
   907  
   908  // next returns the smallest time t' > time of a change in the
   909  // utilization function.
   910  func (in *integrator) next(time int64) int64 {
   911  	for _, u := range in.u.util[in.pos:] {
   912  		if u.Time > time {
   913  			return u.Time
   914  		}
   915  	}
   916  	return 1<<63 - 1
   917  }
   918  
   919  func isGCSTW(r Range) bool {
   920  	return strings.HasPrefix(r.Name, "stop-the-world") && strings.Contains(r.Name, "GC")
   921  }
   922  
   923  func isGCMarkAssist(r Range) bool {
   924  	return r.Name == "GC mark assist"
   925  }
   926  
   927  func isGCSweep(r Range) bool {
   928  	return r.Name == "GC incremental sweep"
   929  }
   930
View as plain text