From c6c602a92612a855d8eb2f649f3dff75bb5fb9ad Mon Sep 17 00:00:00 2001 From: Austin Clements Date: Mon, 28 Aug 2017 12:29:07 -0400 Subject: [PATCH] internal/trace: use MU slope to optimize MMU This commit speeds up MMU construction by ~10X (and reduces the number of windows considered by ~20X) by using an observation about the maximum slope of the windowed mutator utilization function to advance the window time in jumps if the window's current mean mutator utilization is much larger than the current minimum. Change-Id: If3cba5da0c4adc37b568740f940793e491e96a51 Reviewed-on: https://go-review.googlesource.com/c/60791 Run-TryBot: Austin Clements TryBot-Result: Gobot Gobot Reviewed-by: Hyang-Ah Hana Kim --- src/internal/traceparser/gc.go | 33 +++++++++++++++++++++++++++++++-- 1 file changed, 31 insertions(+), 2 deletions(-) diff --git a/src/internal/traceparser/gc.go b/src/internal/traceparser/gc.go index 7e349308d7..66c68cb450 100644 --- a/src/internal/traceparser/gc.go +++ b/src/internal/traceparser/gc.go @@ -194,6 +194,12 @@ func (c *MMUCurve) MMU(window time.Duration) (mmu float64) { } } + // 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-mmu)*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. @@ -202,6 +208,9 @@ func (c *MMUCurve) MMU(window time.Duration) (mmu float64) { } else { time = t2 } + if time < minTime { + time = minTime + } if time > util[len(util)-1].Time-int64(window) { break } @@ -225,8 +234,28 @@ 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). - for pos+1 < len(util) && util[pos+1].Time <= time { - pos++ + // + // 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 -- 2.50.0