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
|
// 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"
)
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 indicies 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
overflow uint64
}
// record adds the given duration to the distribution.
//
// Although the duration is an int64 to facilitate ease-of-use
// with e.g. nanotime, the duration must be non-negative.
func (h *timeHistogram) record(duration int64) {
if duration < 0 {
throw("timeHistogram encountered negative duration")
}
// 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
// add into the special overflow bucket.
atomic.Xadd64(&h.overflow, 1)
return
}
// 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)
}
// 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)
for i := 0; i < timeHistNumSuperBuckets; i++ {
superBucketMin := uint64(0)
// The (inclusive) minimum for the first 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 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] = float64(subBucketMin) / 1e9
}
}
return b
}
|
