Source file src/pkg/internal/trace/mud.go

     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		"math"
     9		"sort"
    10	)
    11	
    12	// mud is an updatable mutator utilization distribution.
    13	//
    14	// This is a continuous distribution of duration over mutator
    15	// utilization. For example, the integral from mutator utilization a
    16	// to b is the total duration during which the mutator utilization was
    17	// in the range [a, b].
    18	//
    19	// This distribution is *not* normalized (it is not a probability
    20	// distribution). This makes it easier to work with as it's being
    21	// updated.
    22	//
    23	// It is represented as the sum of scaled uniform distribution
    24	// functions and Dirac delta functions (which are treated as
    25	// degenerate uniform distributions).
    26	type mud struct {
    27		sorted, unsorted []edge
    28	
    29		// trackMass is the inverse cumulative sum to track as the
    30		// distribution is updated.
    31		trackMass float64
    32		// trackBucket is the bucket in which trackMass falls. If the
    33		// total mass of the distribution is < trackMass, this is
    34		// len(hist).
    35		trackBucket int
    36		// trackSum is the cumulative sum of hist[:trackBucket]. Once
    37		// trackSum >= trackMass, trackBucket must be recomputed.
    38		trackSum float64
    39	
    40		// hist is a hierarchical histogram of distribution mass.
    41		hist [mudDegree]float64
    42	}
    43	
    44	const (
    45		// mudDegree is the number of buckets in the MUD summary
    46		// histogram.
    47		mudDegree = 1024
    48	)
    49	
    50	type edge struct {
    51		// At x, the function increases by y.
    52		x, delta float64
    53		// Additionally at x is a Dirac delta function with area dirac.
    54		dirac float64
    55	}
    56	
    57	// add adds a uniform function over [l, r] scaled so the total weight
    58	// of the uniform is area. If l==r, this adds a Dirac delta function.
    59	func (d *mud) add(l, r, area float64) {
    60		if area == 0 {
    61			return
    62		}
    63	
    64		if r < l {
    65			l, r = r, l
    66		}
    67	
    68		// Add the edges.
    69		if l == r {
    70			d.unsorted = append(d.unsorted, edge{l, 0, area})
    71		} else {
    72			delta := area / (r - l)
    73			d.unsorted = append(d.unsorted, edge{l, delta, 0}, edge{r, -delta, 0})
    74		}
    75	
    76		// Update the histogram.
    77		h := &d.hist
    78		lbFloat, lf := math.Modf(l * mudDegree)
    79		lb := int(lbFloat)
    80		if lb >= mudDegree {
    81			lb, lf = mudDegree-1, 1
    82		}
    83		if l == r {
    84			h[lb] += area
    85		} else {
    86			rbFloat, rf := math.Modf(r * mudDegree)
    87			rb := int(rbFloat)
    88			if rb >= mudDegree {
    89				rb, rf = mudDegree-1, 1
    90			}
    91			if lb == rb {
    92				h[lb] += area
    93			} else {
    94				perBucket := area / (r - l) / mudDegree
    95				h[lb] += perBucket * (1 - lf)
    96				h[rb] += perBucket * rf
    97				for i := lb + 1; i < rb; i++ {
    98					h[i] += perBucket
    99				}
   100			}
   101		}
   102	
   103		// Update mass tracking.
   104		if thresh := float64(d.trackBucket) / mudDegree; l < thresh {
   105			if r < thresh {
   106				d.trackSum += area
   107			} else {
   108				d.trackSum += area * (thresh - l) / (r - l)
   109			}
   110			if d.trackSum >= d.trackMass {
   111				// The tracked mass now falls in a different
   112				// bucket. Recompute the inverse cumulative sum.
   113				d.setTrackMass(d.trackMass)
   114			}
   115		}
   116	}
   117	
   118	// setTrackMass sets the mass to track the inverse cumulative sum for.
   119	//
   120	// Specifically, mass is a cumulative duration, and the mutator
   121	// utilization bounds for this duration can be queried using
   122	// approxInvCumulativeSum.
   123	func (d *mud) setTrackMass(mass float64) {
   124		d.trackMass = mass
   125	
   126		// Find the bucket currently containing trackMass by computing
   127		// the cumulative sum.
   128		sum := 0.0
   129		for i, val := range d.hist[:] {
   130			newSum := sum + val
   131			if newSum > mass {
   132				// mass falls in bucket i.
   133				d.trackBucket = i
   134				d.trackSum = sum
   135				return
   136			}
   137			sum = newSum
   138		}
   139		d.trackBucket = len(d.hist)
   140		d.trackSum = sum
   141	}
   142	
   143	// approxInvCumulativeSum is like invCumulativeSum, but specifically
   144	// operates on the tracked mass and returns an upper and lower bound
   145	// approximation of the inverse cumulative sum.
   146	//
   147	// The true inverse cumulative sum will be in the range [lower, upper).
   148	func (d *mud) approxInvCumulativeSum() (float64, float64, bool) {
   149		if d.trackBucket == len(d.hist) {
   150			return math.NaN(), math.NaN(), false
   151		}
   152		return float64(d.trackBucket) / mudDegree, float64(d.trackBucket+1) / mudDegree, true
   153	}
   154	
   155	// invCumulativeSum returns x such that the integral of d from -∞ to x
   156	// is y. If the total weight of d is less than y, it returns the
   157	// maximum of the distribution and false.
   158	//
   159	// Specifically, y is a cumulative duration, and invCumulativeSum
   160	// returns the mutator utilization x such that at least y time has
   161	// been spent with mutator utilization <= x.
   162	func (d *mud) invCumulativeSum(y float64) (float64, bool) {
   163		if len(d.sorted) == 0 && len(d.unsorted) == 0 {
   164			return math.NaN(), false
   165		}
   166	
   167		// Sort edges.
   168		edges := d.unsorted
   169		sort.Slice(edges, func(i, j int) bool {
   170			return edges[i].x < edges[j].x
   171		})
   172		// Merge with sorted edges.
   173		d.unsorted = nil
   174		if d.sorted == nil {
   175			d.sorted = edges
   176		} else {
   177			oldSorted := d.sorted
   178			newSorted := make([]edge, len(oldSorted)+len(edges))
   179			i, j := 0, 0
   180			for o := range newSorted {
   181				if i >= len(oldSorted) {
   182					copy(newSorted[o:], edges[j:])
   183					break
   184				} else if j >= len(edges) {
   185					copy(newSorted[o:], oldSorted[i:])
   186					break
   187				} else if oldSorted[i].x < edges[j].x {
   188					newSorted[o] = oldSorted[i]
   189					i++
   190				} else {
   191					newSorted[o] = edges[j]
   192					j++
   193				}
   194			}
   195			d.sorted = newSorted
   196		}
   197	
   198		// Traverse edges in order computing a cumulative sum.
   199		csum, rate, prevX := 0.0, 0.0, 0.0
   200		for _, e := range d.sorted {
   201			newCsum := csum + (e.x-prevX)*rate
   202			if newCsum >= y {
   203				// y was exceeded between the previous edge
   204				// and this one.
   205				if rate == 0 {
   206					// Anywhere between prevX and
   207					// e.x will do. We return e.x
   208					// because that takes care of
   209					// the y==0 case naturally.
   210					return e.x, true
   211				}
   212				return (y-csum)/rate + prevX, true
   213			}
   214			newCsum += e.dirac
   215			if newCsum >= y {
   216				// y was exceeded by the Dirac delta at e.x.
   217				return e.x, true
   218			}
   219			csum, prevX = newCsum, e.x
   220			rate += e.delta
   221		}
   222		return prevX, false
   223	}
   224	

View as plain text