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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
|
// Copyright 2020 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 runtime
import (
"runtime/internal/atomic"
"runtime/internal/sys"
"unsafe"
)
const (
// For the time histogram type, we use an HDR histogram.
// Values are placed in super-buckets based solely on the most
// significant set bit. Thus, super-buckets are power-of-2 sized.
// Values are then placed into sub-buckets based on the value of
// the next timeHistSubBucketBits most significant bits. Thus,
// sub-buckets are linear within a super-bucket.
//
// Therefore, the number of sub-buckets (timeHistNumSubBuckets)
// defines the error. This error may be computed as
// 1/timeHistNumSubBuckets*100%. For example, for 16 sub-buckets
// per super-bucket the error is approximately 6%.
//
// The number of super-buckets (timeHistNumSuperBuckets), on the
// other hand, defines the range. To reserve room for sub-buckets,
// bit timeHistSubBucketBits is the first bit considered for
// super-buckets, so super-bucket indices are adjusted accordingly.
//
// As an example, consider 45 super-buckets with 16 sub-buckets.
//
// 00110
// ^----
// │ ^
// │ └---- Lowest 4 bits -> sub-bucket 6
// └------- Bit 4 unset -> super-bucket 0
//
// 10110
// ^----
// │ ^
// │ └---- Next 4 bits -> sub-bucket 6
// └------- Bit 4 set -> super-bucket 1
// 100010
// ^----^
// │ ^ └-- Lower bits ignored
// │ └---- Next 4 bits -> sub-bucket 1
// └------- Bit 5 set -> super-bucket 2
//
// Following this pattern, bucket 45 will have the bit 48 set. We don't
// have any buckets for higher values, so the highest sub-bucket will
// contain values of 2^48-1 nanoseconds or approx. 3 days. This range is
// more than enough to handle durations produced by the runtime.
timeHistSubBucketBits = 4
timeHistNumSubBuckets = 1 << timeHistSubBucketBits
timeHistNumSuperBuckets = 45
timeHistTotalBuckets = timeHistNumSuperBuckets*timeHistNumSubBuckets + 1
)
// timeHistogram represents a distribution of durations in
// nanoseconds.
//
// The accuracy and range of the histogram is defined by the
// timeHistSubBucketBits and timeHistNumSuperBuckets constants.
//
// It is an HDR histogram with exponentially-distributed
// buckets and linearly distributed sub-buckets.
//
// Counts in the histogram are updated atomically, so it is safe
// for concurrent use. It is also safe to read all the values
// atomically.
type timeHistogram struct {
counts [timeHistNumSuperBuckets * timeHistNumSubBuckets]uint64
// underflow counts all the times we got a negative duration
// sample. Because of how time works on some platforms, it's
// possible to measure negative durations. We could ignore them,
// but we record them anyway because it's better to have some
// signal that it's happening than just missing samples.
underflow uint64
}
// record adds the given duration to the distribution.
func (h *timeHistogram) record(duration int64) {
if duration < 0 {
atomic.Xadd64(&h.underflow, 1)
return
}
// The index of the exponential bucket is just the index
// of the highest set bit adjusted for how many bits we
// use for the subbucket. Note that it's timeHistSubBucketsBits-1
// because we use the 0th bucket to hold values < timeHistNumSubBuckets.
var superBucket, subBucket uint
if duration >= timeHistNumSubBuckets {
// At this point, we know the duration value will always be
// at least timeHistSubBucketsBits long.
superBucket = uint(sys.Len64(uint64(duration))) - timeHistSubBucketBits
if superBucket*timeHistNumSubBuckets >= uint(len(h.counts)) {
// The bucket index we got is larger than what we support, so
// include this count in the highest bucket, which extends to
// infinity.
superBucket = timeHistNumSuperBuckets - 1
subBucket = timeHistNumSubBuckets - 1
} else {
// The linear subbucket index is just the timeHistSubBucketsBits
// bits after the top bit. To extract that value, shift down
// the duration such that we leave the top bit and the next bits
// intact, then extract the index.
subBucket = uint((duration >> (superBucket - 1)) % timeHistNumSubBuckets)
}
} else {
subBucket = uint(duration)
}
atomic.Xadd64(&h.counts[superBucket*timeHistNumSubBuckets+subBucket], 1)
}
const (
fInf = 0x7FF0000000000000
fNegInf = 0xFFF0000000000000
)
func float64Inf() float64 {
inf := uint64(fInf)
return *(*float64)(unsafe.Pointer(&inf))
}
func float64NegInf() float64 {
inf := uint64(fNegInf)
return *(*float64)(unsafe.Pointer(&inf))
}
// timeHistogramMetricsBuckets generates a slice of boundaries for
// the timeHistogram. These boundaries are represented in seconds,
// not nanoseconds like the timeHistogram represents durations.
func timeHistogramMetricsBuckets() []float64 {
b := make([]float64, timeHistTotalBuckets+1)
b[0] = float64NegInf()
for i := 0; i < timeHistNumSuperBuckets; i++ {
superBucketMin := uint64(0)
// The (inclusive) minimum for the first non-negative bucket is 0.
if i > 0 {
// The minimum for the second bucket will be
// 1 << timeHistSubBucketBits, indicating that all
// sub-buckets are represented by the next timeHistSubBucketBits
// bits.
// Thereafter, we shift up by 1 each time, so we can represent
// this pattern as (i-1)+timeHistSubBucketBits.
superBucketMin = uint64(1) << uint(i-1+timeHistSubBucketBits)
}
// subBucketShift is the amount that we need to shift the sub-bucket
// index to combine it with the bucketMin.
subBucketShift := uint(0)
if i > 1 {
// The first two super buckets are exact with respect to integers,
// so we'll never have to shift the sub-bucket index. Thereafter,
// we shift up by 1 with each subsequent bucket.
subBucketShift = uint(i - 2)
}
for j := 0; j < timeHistNumSubBuckets; j++ {
// j is the sub-bucket index. By shifting the index into position to
// combine with the bucket minimum, we obtain the minimum value for that
// sub-bucket.
subBucketMin := superBucketMin + (uint64(j) << subBucketShift)
// Convert the subBucketMin which is in nanoseconds to a float64 seconds value.
// These values will all be exactly representable by a float64.
b[i*timeHistNumSubBuckets+j+1] = float64(subBucketMin) / 1e9
}
}
b[len(b)-1] = float64Inf()
return b
}
|
