+++ /dev/null
-// Copyright 2015 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
-
-// This file implements histogramming for RPC statistics collection.
-
-import (
- "bytes"
- "fmt"
- "html/template"
- "log"
- "math"
- "sync"
-
- "golang.org/x/net/internal/timeseries"
-)
-
-const (
- bucketCount = 38
-)
-
-// histogram keeps counts of values in buckets that are spaced
-// out in powers of 2: 0-1, 2-3, 4-7...
-// histogram implements timeseries.Observable
-type histogram struct {
- sum int64 // running total of measurements
- sumOfSquares float64 // square of running total
- buckets []int64 // bucketed values for histogram
- value int // holds a single value as an optimization
- valueCount int64 // number of values recorded for single value
-}
-
-// AddMeasurement records a value measurement observation to the histogram.
-func (h *histogram) addMeasurement(value int64) {
- // TODO: assert invariant
- h.sum += value
- h.sumOfSquares += float64(value) * float64(value)
-
- bucketIndex := getBucket(value)
-
- if h.valueCount == 0 || (h.valueCount > 0 && h.value == bucketIndex) {
- h.value = bucketIndex
- h.valueCount++
- } else {
- h.allocateBuckets()
- h.buckets[bucketIndex]++
- }
-}
-
-func (h *histogram) allocateBuckets() {
- if h.buckets == nil {
- h.buckets = make([]int64, bucketCount)
- h.buckets[h.value] = h.valueCount
- h.value = 0
- h.valueCount = -1
- }
-}
-
-func log2(i int64) int {
- n := 0
- for ; i >= 0x100; i >>= 8 {
- n += 8
- }
- for ; i > 0; i >>= 1 {
- n += 1
- }
- return n
-}
-
-func getBucket(i int64) (index int) {
- index = log2(i) - 1
- if index < 0 {
- index = 0
- }
- if index >= bucketCount {
- index = bucketCount - 1
- }
- return
-}
-
-// Total returns the number of recorded observations.
-func (h *histogram) total() (total int64) {
- if h.valueCount >= 0 {
- total = h.valueCount
- }
- for _, val := range h.buckets {
- total += int64(val)
- }
- return
-}
-
-// Average returns the average value of recorded observations.
-func (h *histogram) average() float64 {
- t := h.total()
- if t == 0 {
- return 0
- }
- return float64(h.sum) / float64(t)
-}
-
-// Variance returns the variance of recorded observations.
-func (h *histogram) variance() float64 {
- t := float64(h.total())
- if t == 0 {
- return 0
- }
- s := float64(h.sum) / t
- return h.sumOfSquares/t - s*s
-}
-
-// StandardDeviation returns the standard deviation of recorded observations.
-func (h *histogram) standardDeviation() float64 {
- return math.Sqrt(h.variance())
-}
-
-// PercentileBoundary estimates the value that the given fraction of recorded
-// observations are less than.
-func (h *histogram) percentileBoundary(percentile float64) int64 {
- total := h.total()
-
- // Corner cases (make sure result is strictly less than Total())
- if total == 0 {
- return 0
- } else if total == 1 {
- return int64(h.average())
- }
-
- percentOfTotal := round(float64(total) * percentile)
- var runningTotal int64
-
- for i := range h.buckets {
- value := h.buckets[i]
- runningTotal += value
- if runningTotal == percentOfTotal {
- // We hit an exact bucket boundary. If the next bucket has data, it is a
- // good estimate of the value. If the bucket is empty, we interpolate the
- // midpoint between the next bucket's boundary and the next non-zero
- // bucket. If the remaining buckets are all empty, then we use the
- // boundary for the next bucket as the estimate.
- j := uint8(i + 1)
- min := bucketBoundary(j)
- if runningTotal < total {
- for h.buckets[j] == 0 {
- j++
- }
- }
- max := bucketBoundary(j)
- return min + round(float64(max-min)/2)
- } else if runningTotal > percentOfTotal {
- // The value is in this bucket. Interpolate the value.
- delta := runningTotal - percentOfTotal
- percentBucket := float64(value-delta) / float64(value)
- bucketMin := bucketBoundary(uint8(i))
- nextBucketMin := bucketBoundary(uint8(i + 1))
- bucketSize := nextBucketMin - bucketMin
- return bucketMin + round(percentBucket*float64(bucketSize))
- }
- }
- return bucketBoundary(bucketCount - 1)
-}
-
-// Median returns the estimated median of the observed values.
-func (h *histogram) median() int64 {
- return h.percentileBoundary(0.5)
-}
-
-// Add adds other to h.
-func (h *histogram) Add(other timeseries.Observable) {
- o := other.(*histogram)
- if o.valueCount == 0 {
- // Other histogram is empty
- } else if h.valueCount >= 0 && o.valueCount > 0 && h.value == o.value {
- // Both have a single bucketed value, aggregate them
- h.valueCount += o.valueCount
- } else {
- // Two different values necessitate buckets in this histogram
- h.allocateBuckets()
- if o.valueCount >= 0 {
- h.buckets[o.value] += o.valueCount
- } else {
- for i := range h.buckets {
- h.buckets[i] += o.buckets[i]
- }
- }
- }
- h.sumOfSquares += o.sumOfSquares
- h.sum += o.sum
-}
-
-// Clear resets the histogram to an empty state, removing all observed values.
-func (h *histogram) Clear() {
- h.buckets = nil
- h.value = 0
- h.valueCount = 0
- h.sum = 0
- h.sumOfSquares = 0
-}
-
-// CopyFrom copies from other, which must be a *histogram, into h.
-func (h *histogram) CopyFrom(other timeseries.Observable) {
- o := other.(*histogram)
- if o.valueCount == -1 {
- h.allocateBuckets()
- copy(h.buckets, o.buckets)
- }
- h.sum = o.sum
- h.sumOfSquares = o.sumOfSquares
- h.value = o.value
- h.valueCount = o.valueCount
-}
-
-// Multiply scales the histogram by the specified ratio.
-func (h *histogram) Multiply(ratio float64) {
- if h.valueCount == -1 {
- for i := range h.buckets {
- h.buckets[i] = int64(float64(h.buckets[i]) * ratio)
- }
- } else {
- h.valueCount = int64(float64(h.valueCount) * ratio)
- }
- h.sum = int64(float64(h.sum) * ratio)
- h.sumOfSquares = h.sumOfSquares * ratio
-}
-
-// New creates a new histogram.
-func (h *histogram) New() timeseries.Observable {
- r := new(histogram)
- r.Clear()
- return r
-}
-
-func (h *histogram) String() string {
- return fmt.Sprintf("%d, %f, %d, %d, %v",
- h.sum, h.sumOfSquares, h.value, h.valueCount, h.buckets)
-}
-
-// round returns the closest int64 to the argument
-func round(in float64) int64 {
- return int64(math.Floor(in + 0.5))
-}
-
-// bucketBoundary returns the first value in the bucket.
-func bucketBoundary(bucket uint8) int64 {
- if bucket == 0 {
- return 0
- }
- return 1 << bucket
-}
-
-// bucketData holds data about a specific bucket for use in distTmpl.
-type bucketData struct {
- Lower, Upper int64
- N int64
- Pct, CumulativePct float64
- GraphWidth int
-}
-
-// data holds data about a Distribution for use in distTmpl.
-type data struct {
- Buckets []*bucketData
- Count, Median int64
- Mean, StandardDeviation float64
-}
-
-// maxHTMLBarWidth is the maximum width of the HTML bar for visualizing buckets.
-const maxHTMLBarWidth = 350.0
-
-// newData returns data representing h for use in distTmpl.
-func (h *histogram) newData() *data {
- // Force the allocation of buckets to simplify the rendering implementation
- h.allocateBuckets()
- // We scale the bars on the right so that the largest bar is
- // maxHTMLBarWidth pixels in width.
- maxBucket := int64(0)
- for _, n := range h.buckets {
- if n > maxBucket {
- maxBucket = n
- }
- }
- total := h.total()
- barsizeMult := maxHTMLBarWidth / float64(maxBucket)
- var pctMult float64
- if total == 0 {
- pctMult = 1.0
- } else {
- pctMult = 100.0 / float64(total)
- }
-
- buckets := make([]*bucketData, len(h.buckets))
- runningTotal := int64(0)
- for i, n := range h.buckets {
- if n == 0 {
- continue
- }
- runningTotal += n
- var upperBound int64
- if i < bucketCount-1 {
- upperBound = bucketBoundary(uint8(i + 1))
- } else {
- upperBound = math.MaxInt64
- }
- buckets[i] = &bucketData{
- Lower: bucketBoundary(uint8(i)),
- Upper: upperBound,
- N: n,
- Pct: float64(n) * pctMult,
- CumulativePct: float64(runningTotal) * pctMult,
- GraphWidth: int(float64(n) * barsizeMult),
- }
- }
- return &data{
- Buckets: buckets,
- Count: total,
- Median: h.median(),
- Mean: h.average(),
- StandardDeviation: h.standardDeviation(),
- }
-}
-
-func (h *histogram) html() template.HTML {
- buf := new(bytes.Buffer)
- if err := distTmpl().Execute(buf, h.newData()); err != nil {
- buf.Reset()
- log.Printf("net/trace: couldn't execute template: %v", err)
- }
- return template.HTML(buf.String())
-}
-
-var distTmplCache *template.Template
-var distTmplOnce sync.Once
-
-func distTmpl() *template.Template {
- distTmplOnce.Do(func() {
- // Input: data
- distTmplCache = template.Must(template.New("distTmpl").Parse(`
-<table>
-<tr>
- <td style="padding:0.25em">Count: {{.Count}}</td>
- <td style="padding:0.25em">Mean: {{printf "%.0f" .Mean}}</td>
- <td style="padding:0.25em">StdDev: {{printf "%.0f" .StandardDeviation}}</td>
- <td style="padding:0.25em">Median: {{.Median}}</td>
-</tr>
-</table>
-<hr>
-<table>
-{{range $b := .Buckets}}
-{{if $b}}
- <tr>
- <td style="padding:0 0 0 0.25em">[</td>
- <td style="text-align:right;padding:0 0.25em">{{.Lower}},</td>
- <td style="text-align:right;padding:0 0.25em">{{.Upper}})</td>
- <td style="text-align:right;padding:0 0.25em">{{.N}}</td>
- <td style="text-align:right;padding:0 0.25em">{{printf "%#.3f" .Pct}}%</td>
- <td style="text-align:right;padding:0 0.25em">{{printf "%#.3f" .CumulativePct}}%</td>
- <td><div style="background-color: blue; height: 1em; width: {{.GraphWidth}};"></div></td>
- </tr>
-{{end}}
-{{end}}
-</table>
-`))
- })
- return distTmplCache
-}
OSDN Git Service
