-
Notifications
You must be signed in to change notification settings - Fork 30
/
buckets.go
115 lines (100 loc) · 2.88 KB
/
buckets.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
package histogram
import (
"math"
"math/bits"
"github.com/Netflix/spectator-go"
)
var (
bucketValues []int64
powerOf4Index []int
)
func init() {
const DIGITS uint8 = 2
bucketValues = append(bucketValues, 1, 2, 3)
powerOf4Index = append(powerOf4Index, 0)
for exp := DIGITS; exp < 64; exp += DIGITS {
var current int64 = 1 << exp
delta := current / 3
next := (current << DIGITS) - delta
powerOf4Index = append(powerOf4Index, len(bucketValues))
for ; current < next; current += delta {
bucketValues = append(bucketValues, current)
}
}
bucketValues = append(bucketValues, math.MaxInt64)
}
func counterFor(registry *spectator.Registry, id *spectator.Id, i int, tagValues []string) *spectator.Counter {
tags := map[string]string{"statistic": "percentile"}
tags["percentile"] = tagValues[i]
return registry.CounterWithId(id.WithTags(tags))
}
// PercentileBucketsLength returns the lengths of the package local bucketValues
// variable, to give an idea of how many buckets exist.
func PercentileBucketsLength() int {
return len(bucketValues)
}
// PercentileBucketsIndex calculates which bucket handles that specific value.
func PercentileBucketsIndex(v int64) int {
if v <= 0 {
return 0
} else if v <= 15 {
return int(v)
} else {
lz := bits.LeadingZeros64(uint64(v))
shift := uint(64 - lz - 1)
prevPowerOf2 := (v >> shift) << shift
prevPowerOf4 := prevPowerOf2
if shift%2 != 0 {
shift--
prevPowerOf4 = prevPowerOf2 >> 1
}
base := prevPowerOf4
delta := base / 3
offset := int((v - base) / delta)
pos := offset + powerOf4Index[shift/2]
if pos >= len(bucketValues)-1 {
return len(bucketValues) - 1
}
return pos + 1
}
}
// PercentileBucketsBucket returns the bucketValue for the specific value.
func PercentileBucketsBucket(v int64) int64 {
return bucketValues[PercentileBucketsIndex(v)]
}
// PercentileBucketsPercentiles takes the counts, and desired percentiles, and
// generates the proper results.
func PercentileBucketsPercentiles(counts []int64, pcts []float64) []float64 {
results := make([]float64, len(pcts))
total := float64(0)
for _, c := range counts {
total += float64(c)
}
pctIndex := 0
prev := int64(0)
prevP := 0.0
prevB := int64(0)
for i, nextB := range bucketValues {
next := prev + counts[i]
nextP := 100 * float64(next) / total
for ; pctIndex < len(pcts) && nextP >= pcts[pctIndex]; pctIndex++ {
f := (pcts[pctIndex] - prevP) / (nextP - prevP)
results[pctIndex] = f*float64(nextB-prevB) + float64(prevB)
}
if pctIndex >= len(pcts) {
break
}
prev = next
prevP = nextP
prevB = nextB
}
return results
}
// PercentileBucketsPercentile takes the counts, and returns the requested
// percentile value based on the counts.
func PercentileBucketsPercentile(counts []int64, pct float64) float64 {
pcts := make([]float64, 1)
pcts[0] = pct
results := PercentileBucketsPercentiles(counts, pcts)
return results[0]
}