vendor/golang.org/x/net/trace/histogram.go

   1 // Copyright 2015 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 // This file implements histogramming for RPC statistics collection.
   8
   9 import (
  10         "bytes"
  11         "fmt"
  12         "html/template"
  13         "log"
  14         "math"
  15         "sync"
  16
  17         "golang.org/x/net/internal/timeseries"
  18 )
  19
  20 const (
  21         bucketCount = 38
  22 )
  23
  24 // histogram keeps counts of values in buckets that are spaced
  25 // out in powers of 2: 0-1, 2-3, 4-7...
  26 // histogram implements timeseries.Observable
  27 type histogram struct {
  28         sum          int64   // running total of measurements
  29         sumOfSquares float64 // square of running total
  30         buckets      []int64 // bucketed values for histogram
  31         value        int     // holds a single value as an optimization
  32         valueCount   int64   // number of values recorded for single value
  33 }
  34
  35 // AddMeasurement records a value measurement observation to the histogram.
  36 func (h *histogram) addMeasurement(value int64) {
  37         // TODO: assert invariant
  38         h.sum += value
  39         h.sumOfSquares += float64(value) * float64(value)
  40
  41         bucketIndex := getBucket(value)
  42
  43         if h.valueCount == 0 || (h.valueCount > 0 && h.value == bucketIndex) {
  44                 h.value = bucketIndex
  45                 h.valueCount++
  46         } else {
  47                 h.allocateBuckets()
  48                 h.buckets[bucketIndex]++
  49         }
  50 }
  51
  52 func (h *histogram) allocateBuckets() {
  53         if h.buckets == nil {
  54                 h.buckets = make([]int64, bucketCount)
  55                 h.buckets[h.value] = h.valueCount
  56                 h.value = 0
  57                 h.valueCount = -1
  58         }
  59 }
  60
  61 func log2(i int64) int {
  62         n := 0
  63         for ; i >= 0x100; i >>= 8 {
  64                 n += 8
  65         }
  66         for ; i > 0; i >>= 1 {
  67                 n += 1
  68         }
  69         return n
  70 }
  71
  72 func getBucket(i int64) (index int) {
  73         index = log2(i) - 1
  74         if index < 0 {
  75                 index = 0
  76         }
  77         if index >= bucketCount {
  78                 index = bucketCount - 1
  79         }
  80         return
  81 }
  82
  83 // Total returns the number of recorded observations.
  84 func (h *histogram) total() (total int64) {
  85         if h.valueCount >= 0 {
  86                 total = h.valueCount
  87         }
  88         for _, val := range h.buckets {
  89                 total += int64(val)
  90         }
  91         return
  92 }
  93
  94 // Average returns the average value of recorded observations.
  95 func (h *histogram) average() float64 {
  96         t := h.total()
  97         if t == 0 {
  98                 return 0
  99         }
 100         return float64(h.sum) / float64(t)
 101 }
 102
 103 // Variance returns the variance of recorded observations.
 104 func (h *histogram) variance() float64 {
 105         t := float64(h.total())
 106         if t == 0 {
 107                 return 0
 108         }
 109         s := float64(h.sum) / t
 110         return h.sumOfSquares/t - s*s
 111 }
 112
 113 // StandardDeviation returns the standard deviation of recorded observations.
 114 func (h *histogram) standardDeviation() float64 {
 115         return math.Sqrt(h.variance())
 116 }
 117
 118 // PercentileBoundary estimates the value that the given fraction of recorded
 119 // observations are less than.
 120 func (h *histogram) percentileBoundary(percentile float64) int64 {
 121         total := h.total()
 122
 123         // Corner cases (make sure result is strictly less than Total())
 124         if total == 0 {
 125                 return 0
 126         } else if total == 1 {
 127                 return int64(h.average())
 128         }
 129
 130         percentOfTotal := round(float64(total) * percentile)
 131         var runningTotal int64
 132
 133         for i := range h.buckets {
 134                 value := h.buckets[i]
 135                 runningTotal += value
 136                 if runningTotal == percentOfTotal {
 137                         // We hit an exact bucket boundary. If the next bucket has data, it is a
 138                         // good estimate of the value. If the bucket is empty, we interpolate the
 139                         // midpoint between the next bucket's boundary and the next non-zero
 140                         // bucket. If the remaining buckets are all empty, then we use the
 141                         // boundary for the next bucket as the estimate.
 142                         j := uint8(i + 1)
 143                         min := bucketBoundary(j)
 144                         if runningTotal < total {
 145                                 for h.buckets[j] == 0 {
 146                                         j++
 147                                 }
 148                         }
 149                         max := bucketBoundary(j)
 150                         return min + round(float64(max-min)/2)
 151                 } else if runningTotal > percentOfTotal {
 152                         // The value is in this bucket. Interpolate the value.
 153                         delta := runningTotal - percentOfTotal
 154                         percentBucket := float64(value-delta) / float64(value)
 155                         bucketMin := bucketBoundary(uint8(i))
 156                         nextBucketMin := bucketBoundary(uint8(i + 1))
 157                         bucketSize := nextBucketMin - bucketMin
 158                         return bucketMin + round(percentBucket*float64(bucketSize))
 159                 }
 160         }
 161         return bucketBoundary(bucketCount - 1)
 162 }
 163
 164 // Median returns the estimated median of the observed values.
 165 func (h *histogram) median() int64 {
 166         return h.percentileBoundary(0.5)
 167 }
 168
 169 // Add adds other to h.
 170 func (h *histogram) Add(other timeseries.Observable) {
 171         o := other.(*histogram)
 172         if o.valueCount == 0 {
 173                 // Other histogram is empty
 174         } else if h.valueCount >= 0 && o.valueCount > 0 && h.value == o.value {
 175                 // Both have a single bucketed value, aggregate them
 176                 h.valueCount += o.valueCount
 177         } else {
 178                 // Two different values necessitate buckets in this histogram
 179                 h.allocateBuckets()
 180                 if o.valueCount >= 0 {
 181                         h.buckets[o.value] += o.valueCount
 182                 } else {
 183                         for i := range h.buckets {
 184                                 h.buckets[i] += o.buckets[i]
 185                         }
 186                 }
 187         }
 188         h.sumOfSquares += o.sumOfSquares
 189         h.sum += o.sum
 190 }
 191
 192 // Clear resets the histogram to an empty state, removing all observed values.
 193 func (h *histogram) Clear() {
 194         h.buckets = nil
 195         h.value = 0
 196         h.valueCount = 0
 197         h.sum = 0
 198         h.sumOfSquares = 0
 199 }
 200
 201 // CopyFrom copies from other, which must be a *histogram, into h.
 202 func (h *histogram) CopyFrom(other timeseries.Observable) {
 203         o := other.(*histogram)
 204         if o.valueCount == -1 {
 205                 h.allocateBuckets()
 206                 copy(h.buckets, o.buckets)
 207         }
 208         h.sum = o.sum
 209         h.sumOfSquares = o.sumOfSquares
 210         h.value = o.value
 211         h.valueCount = o.valueCount
 212 }
 213
 214 // Multiply scales the histogram by the specified ratio.
 215 func (h *histogram) Multiply(ratio float64) {
 216         if h.valueCount == -1 {
 217                 for i := range h.buckets {
 218                         h.buckets[i] = int64(float64(h.buckets[i]) * ratio)
 219                 }
 220         } else {
 221                 h.valueCount = int64(float64(h.valueCount) * ratio)
 222         }
 223         h.sum = int64(float64(h.sum) * ratio)
 224         h.sumOfSquares = h.sumOfSquares * ratio
 225 }
 226
 227 // New creates a new histogram.
 228 func (h *histogram) New() timeseries.Observable {
 229         r := new(histogram)
 230         r.Clear()
 231         return r
 232 }
 233
 234 func (h *histogram) String() string {
 235         return fmt.Sprintf("%d, %f, %d, %d, %v",
 236                 h.sum, h.sumOfSquares, h.value, h.valueCount, h.buckets)
 237 }
 238
 239 // round returns the closest int64 to the argument
 240 func round(in float64) int64 {
 241         return int64(math.Floor(in + 0.5))
 242 }
 243
 244 // bucketBoundary returns the first value in the bucket.
 245 func bucketBoundary(bucket uint8) int64 {
 246         if bucket == 0 {
 247                 return 0
 248         }
 249         return 1 << bucket
 250 }
 251
 252 // bucketData holds data about a specific bucket for use in distTmpl.
 253 type bucketData struct {
 254         Lower, Upper       int64
 255         N                  int64
 256         Pct, CumulativePct float64
 257         GraphWidth         int
 258 }
 259
 260 // data holds data about a Distribution for use in distTmpl.
 261 type data struct {
 262         Buckets                 []*bucketData
 263         Count, Median           int64
 264         Mean, StandardDeviation float64
 265 }
 266
 267 // maxHTMLBarWidth is the maximum width of the HTML bar for visualizing buckets.
 268 const maxHTMLBarWidth = 350.0
 269
 270 // newData returns data representing h for use in distTmpl.
 271 func (h *histogram) newData() *data {
 272         // Force the allocation of buckets to simplify the rendering implementation
 273         h.allocateBuckets()
 274         // We scale the bars on the right so that the largest bar is
 275         // maxHTMLBarWidth pixels in width.
 276         maxBucket := int64(0)
 277         for _, n := range h.buckets {
 278                 if n > maxBucket {
 279                         maxBucket = n
 280                 }
 281         }
 282         total := h.total()
 283         barsizeMult := maxHTMLBarWidth / float64(maxBucket)
 284         var pctMult float64
 285         if total == 0 {
 286                 pctMult = 1.0
 287         } else {
 288                 pctMult = 100.0 / float64(total)
 289         }
 290
 291         buckets := make([]*bucketData, len(h.buckets))
 292         runningTotal := int64(0)
 293         for i, n := range h.buckets {
 294                 if n == 0 {
 295                         continue
 296                 }
 297                 runningTotal += n
 298                 var upperBound int64
 299                 if i < bucketCount-1 {
 300                         upperBound = bucketBoundary(uint8(i + 1))
 301                 } else {
 302                         upperBound = math.MaxInt64
 303                 }
 304                 buckets[i] = &bucketData{
 305                         Lower:         bucketBoundary(uint8(i)),
 306                         Upper:         upperBound,
 307                         N:             n,
 308                         Pct:           float64(n) * pctMult,
 309                         CumulativePct: float64(runningTotal) * pctMult,
 310                         GraphWidth:    int(float64(n) * barsizeMult),
 311                 }
 312         }
 313         return &data{
 314                 Buckets:           buckets,
 315                 Count:             total,
 316                 Median:            h.median(),
 317                 Mean:              h.average(),
 318                 StandardDeviation: h.standardDeviation(),
 319         }
 320 }
 321
 322 func (h *histogram) html() template.HTML {
 323         buf := new(bytes.Buffer)
 324         if err := distTmpl().Execute(buf, h.newData()); err != nil {
 325                 buf.Reset()
 326                 log.Printf("net/trace: couldn't execute template: %v", err)
 327         }
 328         return template.HTML(buf.String())
 329 }
 330
 331 var distTmplCache *template.Template
 332 var distTmplOnce sync.Once
 333
 334 func distTmpl() *template.Template {
 335         distTmplOnce.Do(func() {
 336                 // Input: data
 337                 distTmplCache = template.Must(template.New("distTmpl").Parse(`
 338 <table>
 339 <tr>
 340     <td style="padding:0.25em">Count: {{.Count}}</td>
 341     <td style="padding:0.25em">Mean: {{printf "%.0f" .Mean}}</td>
 342     <td style="padding:0.25em">StdDev: {{printf "%.0f" .StandardDeviation}}</td>
 343     <td style="padding:0.25em">Median: {{.Median}}</td>
 344 </tr>
 345 </table>
 346 <hr>
 347 <table>
 348 {{range $b := .Buckets}}
 349 {{if $b}}
 350   <tr>
 351     <td style="padding:0 0 0 0.25em">[</td>
 352     <td style="text-align:right;padding:0 0.25em">{{.Lower}},</td>
 353     <td style="text-align:right;padding:0 0.25em">{{.Upper}})</td>
 354     <td style="text-align:right;padding:0 0.25em">{{.N}}</td>
 355     <td style="text-align:right;padding:0 0.25em">{{printf "%#.3f" .Pct}}%</td>
 356     <td style="text-align:right;padding:0 0.25em">{{printf "%#.3f" .CumulativePct}}%</td>
 357     <td><div style="background-color: blue; height: 1em; width: {{.GraphWidth}};"></div></td>
 358   </tr>
 359 {{end}}
 360 {{end}}
 361 </table>
 362 `))
 363         })
 364         return distTmplCache
 365 }