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 (
	
	
	
	
	
	

	
)

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.
TODO: assert invariant
	.sum += 
	.sumOfSquares += float64() * float64()

	 := getBucket()

	if .valueCount == 0 || (.valueCount > 0 && .value == ) {
		.value = 
		.valueCount++
	} else {
		.allocateBuckets()
		.buckets[]++
	}
}

func ( *histogram) () {
	if .buckets == nil {
		.buckets = make([]int64, bucketCount)
		.buckets[.value] = .valueCount
		.value = 0
		.valueCount = -1
	}
}

func ( int64) int {
	 := 0
	for ;  >= 0x100;  >>= 8 {
		 += 8
	}
	for ;  > 0;  >>= 1 {
		 += 1
	}
	return 
}

func ( int64) ( int) {
	 = log2() - 1
	if  < 0 {
		 = 0
	}
	if  >= bucketCount {
		 = bucketCount - 1
	}
	return
}
Total returns the number of recorded observations.
func ( *histogram) () ( int64) {
	if .valueCount >= 0 {
		 = .valueCount
	}
	for ,  := range .buckets {
		 += int64()
	}
	return
}
Average returns the average value of recorded observations.
func ( *histogram) () float64 {
	 := .total()
	if  == 0 {
		return 0
	}
	return float64(.sum) / float64()
}
Variance returns the variance of recorded observations.
func ( *histogram) () float64 {
	 := float64(.total())
	if  == 0 {
		return 0
	}
	 := float64(.sum) / 
	return .sumOfSquares/ - *
}
StandardDeviation returns the standard deviation of recorded observations.
func ( *histogram) () float64 {
	return math.Sqrt(.variance())
}
PercentileBoundary estimates the value that the given fraction of recorded observations are less than.
func ( *histogram) ( float64) int64 {
	 := .total()
Corner cases (make sure result is strictly less than Total())
	if  == 0 {
		return 0
	} else if  == 1 {
		return int64(.average())
	}

	 := round(float64() * )
	var  int64

	for  := range .buckets {
		 := .buckets[]
		 += 
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.
			 := uint8( + 1)
			 := bucketBoundary()
			if  <  {
				for .buckets[] == 0 {
					++
				}
			}
			 := bucketBoundary()
			return  + round(float64(-)/2)
The value is in this bucket. Interpolate the value.
			 :=  - 
			 := float64(-) / float64()
			 := bucketBoundary(uint8())
			 := bucketBoundary(uint8( + 1))
			 :=  - 
			return  + round(*float64())
		}
	}
	return bucketBoundary(bucketCount - 1)
}
Median returns the estimated median of the observed values.
func ( *histogram) () int64 {
	return .percentileBoundary(0.5)
}
Add adds other to h.
func ( *histogram) ( timeseries.Observable) {
	 := .(*histogram)
Other histogram is empty
Both have a single bucketed value, aggregate them
Two different values necessitate buckets in this histogram
		.allocateBuckets()
		if .valueCount >= 0 {
			.buckets[.value] += .valueCount
		} else {
			for  := range .buckets {
				.buckets[] += .buckets[]
			}
		}
	}
	.sumOfSquares += .sumOfSquares
	.sum += .sum
}
Clear resets the histogram to an empty state, removing all observed values.
func ( *histogram) () {
	.buckets = nil
	.value = 0
	.valueCount = 0
	.sum = 0
	.sumOfSquares = 0
}
CopyFrom copies from other, which must be a *histogram, into h.
func ( *histogram) ( timeseries.Observable) {
	 := .(*histogram)
	if .valueCount == -1 {
		.allocateBuckets()
		copy(.buckets, .buckets)
	}
	.sum = .sum
	.sumOfSquares = .sumOfSquares
	.value = .value
	.valueCount = .valueCount
}
Multiply scales the histogram by the specified ratio.
func ( *histogram) ( float64) {
	if .valueCount == -1 {
		for  := range .buckets {
			.buckets[] = int64(float64(.buckets[]) * )
		}
	} else {
		.valueCount = int64(float64(.valueCount) * )
	}
	.sum = int64(float64(.sum) * )
	.sumOfSquares = .sumOfSquares * 
}
New creates a new histogram.
func ( *histogram) () timeseries.Observable {
	 := new(histogram)
	.Clear()
	return 
}

func ( *histogram) () string {
	return fmt.Sprintf("%d, %f, %d, %d, %v",
		.sum, .sumOfSquares, .value, .valueCount, .buckets)
}
round returns the closest int64 to the argument
func ( float64) int64 {
	return int64(math.Floor( + 0.5))
}
bucketBoundary returns the first value in the bucket.
func ( uint8) int64 {
	if  == 0 {
		return 0
	}
	return 1 << 
}
bucketData holds data about a specific bucket for use in distTmpl.
data holds data about a Distribution for use in distTmpl.
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.
Force the allocation of buckets to simplify the rendering implementation
We scale the bars on the right so that the largest bar is maxHTMLBarWidth pixels in width.
	 := int64(0)
	for ,  := range .buckets {
		if  >  {
			 = 
		}
	}
	 := .total()
	 := maxHTMLBarWidth / float64()
	var  float64
	if  == 0 {
		 = 1.0
	} else {
		 = 100.0 / float64()
	}

	 := make([]*bucketData, len(.buckets))
	 := int64(0)
	for ,  := range .buckets {
		if  == 0 {
			continue
		}
		 += 
		var  int64
		if  < bucketCount-1 {
			 = bucketBoundary(uint8( + 1))
		} else {
			 = math.MaxInt64
		}
		[] = &bucketData{
			Lower:         bucketBoundary(uint8()),
			Upper:         ,
			N:             ,
			Pct:           float64() * ,
			CumulativePct: float64() * ,
			GraphWidth:    int(float64() * ),
		}
	}
	return &data{
		Buckets:           ,
		Count:             ,
		Median:            .median(),
		Mean:              .average(),
		StandardDeviation: .standardDeviation(),
	}
}

func ( *histogram) () template.HTML {
	 := new(bytes.Buffer)
	if  := distTmpl().Execute(, .newData());  != nil {
		.Reset()
		log.Printf("net/trace: couldn't execute template: %v", )
	}
	return template.HTML(.String())
}

var distTmplCache *template.Template
var distTmplOnce sync.Once

func () *template.Template {
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