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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
// Package histogram provides building blocks for fast histograms.
package histogram
import (
"math"
"sort"
"sync"
"github.com/valyala/fastrand"
)
var (
infNeg = math.Inf(-1)
infPos = math.Inf(1)
nan = math.NaN()
)
// Fast is a fast histogram.
//
// It cannot be used from concurrently running goroutines without
// external synchronization.
type Fast struct {
max float64
min float64
count uint64
a []float64
tmp []float64
rng fastrand.RNG
}
// NewFast returns new fast histogram.
func NewFast() *Fast {
f := &Fast{}
f.Reset()
return f
}
// Reset resets the histogram.
func (f *Fast) Reset() {
f.max = infNeg
f.min = infPos
f.count = 0
if len(f.a) > 0 {
f.a = f.a[:0]
f.tmp = f.tmp[:0]
} else {
// Free up memory occupied by unused histogram.
f.a = nil
f.tmp = nil
}
// Reset rng state in order to get repeatable results
// for the same sequence of values passed to Fast.Update.
// See https://github.com/VictoriaMetrics/VictoriaMetrics/issues/1612
f.rng.Seed(1)
}
// Update updates the f with v.
func (f *Fast) Update(v float64) {
if v > f.max {
f.max = v
}
if v < f.min {
f.min = v
}
f.count++
if len(f.a) < maxSamples {
f.a = append(f.a, v)
return
}
if n := int(f.rng.Uint32n(uint32(f.count))); n < len(f.a) {
f.a[n] = v
}
}
const maxSamples = 1000
// Quantile returns the quantile value for the given phi.
func (f *Fast) Quantile(phi float64) float64 {
f.tmp = append(f.tmp[:0], f.a...)
sort.Float64s(f.tmp)
return f.quantile(phi)
}
// Quantiles appends quantile values to dst for the given phis.
func (f *Fast) Quantiles(dst, phis []float64) []float64 {
f.tmp = append(f.tmp[:0], f.a...)
sort.Float64s(f.tmp)
for _, phi := range phis {
q := f.quantile(phi)
dst = append(dst, q)
}
return dst
}
func (f *Fast) quantile(phi float64) float64 {
if len(f.tmp) == 0 || math.IsNaN(phi) {
return nan
}
if phi <= 0 {
return f.min
}
if phi >= 1 {
return f.max
}
idx := uint(phi*float64(len(f.tmp)-1) + 0.5)
if idx >= uint(len(f.tmp)) {
idx = uint(len(f.tmp) - 1)
}
return f.tmp[idx]
}
// GetFast returns a histogram from a pool.
func GetFast() *Fast {
v := fastPool.Get()
if v == nil {
return NewFast()
}
return v.(*Fast)
}
// PutFast puts hf to the pool.
//
// hf cannot be used after this call.
func PutFast(f *Fast) {
f.Reset()
fastPool.Put(f)
}
var fastPool sync.Pool
|
