Adding upstream version 1.16.10.upstream/1.16.10upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

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