Source file src/runtime/histogram.go
Documentation: runtime
1 // Copyright 2020 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 package runtime 6 7 import ( 8 "runtime/internal/atomic" 9 "runtime/internal/sys" 10 "unsafe" 11 ) 12 13 const ( 14 // For the time histogram type, we use an HDR histogram. 15 // Values are placed in super-buckets based solely on the most 16 // significant set bit. Thus, super-buckets are power-of-2 sized. 17 // Values are then placed into sub-buckets based on the value of 18 // the next timeHistSubBucketBits most significant bits. Thus, 19 // sub-buckets are linear within a super-bucket. 20 // 21 // Therefore, the number of sub-buckets (timeHistNumSubBuckets) 22 // defines the error. This error may be computed as 23 // 1/timeHistNumSubBuckets*100%. For example, for 16 sub-buckets 24 // per super-bucket the error is approximately 6%. 25 // 26 // The number of super-buckets (timeHistNumSuperBuckets), on the 27 // other hand, defines the range. To reserve room for sub-buckets, 28 // bit timeHistSubBucketBits is the first bit considered for 29 // super-buckets, so super-bucket indices are adjusted accordingly. 30 // 31 // As an example, consider 45 super-buckets with 16 sub-buckets. 32 // 33 // 00110 34 // ^---- 35 // │ ^ 36 // │ └---- Lowest 4 bits -> sub-bucket 6 37 // └------- Bit 4 unset -> super-bucket 0 38 // 39 // 10110 40 // ^---- 41 // │ ^ 42 // │ └---- Next 4 bits -> sub-bucket 6 43 // └------- Bit 4 set -> super-bucket 1 44 // 100010 45 // ^----^ 46 // │ ^ └-- Lower bits ignored 47 // │ └---- Next 4 bits -> sub-bucket 1 48 // └------- Bit 5 set -> super-bucket 2 49 // 50 // Following this pattern, bucket 45 will have the bit 48 set. We don't 51 // have any buckets for higher values, so the highest sub-bucket will 52 // contain values of 2^48-1 nanoseconds or approx. 3 days. This range is 53 // more than enough to handle durations produced by the runtime. 54 timeHistSubBucketBits = 4 55 timeHistNumSubBuckets = 1 << timeHistSubBucketBits 56 timeHistNumSuperBuckets = 45 57 timeHistTotalBuckets = timeHistNumSuperBuckets*timeHistNumSubBuckets + 1 58 ) 59 60 // timeHistogram represents a distribution of durations in 61 // nanoseconds. 62 // 63 // The accuracy and range of the histogram is defined by the 64 // timeHistSubBucketBits and timeHistNumSuperBuckets constants. 65 // 66 // It is an HDR histogram with exponentially-distributed 67 // buckets and linearly distributed sub-buckets. 68 // 69 // Counts in the histogram are updated atomically, so it is safe 70 // for concurrent use. It is also safe to read all the values 71 // atomically. 72 type timeHistogram struct { 73 counts [timeHistNumSuperBuckets * timeHistNumSubBuckets]uint64 74 75 // underflow counts all the times we got a negative duration 76 // sample. Because of how time works on some platforms, it's 77 // possible to measure negative durations. We could ignore them, 78 // but we record them anyway because it's better to have some 79 // signal that it's happening than just missing samples. 80 underflow uint64 81 } 82 83 // record adds the given duration to the distribution. 84 func (h *timeHistogram) record(duration int64) { 85 if duration < 0 { 86 atomic.Xadd64(&h.underflow, 1) 87 return 88 } 89 // The index of the exponential bucket is just the index 90 // of the highest set bit adjusted for how many bits we 91 // use for the subbucket. Note that it's timeHistSubBucketsBits-1 92 // because we use the 0th bucket to hold values < timeHistNumSubBuckets. 93 var superBucket, subBucket uint 94 if duration >= timeHistNumSubBuckets { 95 // At this point, we know the duration value will always be 96 // at least timeHistSubBucketsBits long. 97 superBucket = uint(sys.Len64(uint64(duration))) - timeHistSubBucketBits 98 if superBucket*timeHistNumSubBuckets >= uint(len(h.counts)) { 99 // The bucket index we got is larger than what we support, so 100 // include this count in the highest bucket, which extends to 101 // infinity. 102 superBucket = timeHistNumSuperBuckets - 1 103 subBucket = timeHistNumSubBuckets - 1 104 } else { 105 // The linear subbucket index is just the timeHistSubBucketsBits 106 // bits after the top bit. To extract that value, shift down 107 // the duration such that we leave the top bit and the next bits 108 // intact, then extract the index. 109 subBucket = uint((duration >> (superBucket - 1)) % timeHistNumSubBuckets) 110 } 111 } else { 112 subBucket = uint(duration) 113 } 114 atomic.Xadd64(&h.counts[superBucket*timeHistNumSubBuckets+subBucket], 1) 115 } 116 117 const ( 118 fInf = 0x7FF0000000000000 119 fNegInf = 0xFFF0000000000000 120 ) 121 122 func float64Inf() float64 { 123 inf := uint64(fInf) 124 return *(*float64)(unsafe.Pointer(&inf)) 125 } 126 127 func float64NegInf() float64 { 128 inf := uint64(fNegInf) 129 return *(*float64)(unsafe.Pointer(&inf)) 130 } 131 132 // timeHistogramMetricsBuckets generates a slice of boundaries for 133 // the timeHistogram. These boundaries are represented in seconds, 134 // not nanoseconds like the timeHistogram represents durations. 135 func timeHistogramMetricsBuckets() []float64 { 136 b := make([]float64, timeHistTotalBuckets+1) 137 b[0] = float64NegInf() 138 for i := 0; i < timeHistNumSuperBuckets; i++ { 139 superBucketMin := uint64(0) 140 // The (inclusive) minimum for the first non-negative bucket is 0. 141 if i > 0 { 142 // The minimum for the second bucket will be 143 // 1 << timeHistSubBucketBits, indicating that all 144 // sub-buckets are represented by the next timeHistSubBucketBits 145 // bits. 146 // Thereafter, we shift up by 1 each time, so we can represent 147 // this pattern as (i-1)+timeHistSubBucketBits. 148 superBucketMin = uint64(1) << uint(i-1+timeHistSubBucketBits) 149 } 150 // subBucketShift is the amount that we need to shift the sub-bucket 151 // index to combine it with the bucketMin. 152 subBucketShift := uint(0) 153 if i > 1 { 154 // The first two super buckets are exact with respect to integers, 155 // so we'll never have to shift the sub-bucket index. Thereafter, 156 // we shift up by 1 with each subsequent bucket. 157 subBucketShift = uint(i - 2) 158 } 159 for j := 0; j < timeHistNumSubBuckets; j++ { 160 // j is the sub-bucket index. By shifting the index into position to 161 // combine with the bucket minimum, we obtain the minimum value for that 162 // sub-bucket. 163 subBucketMin := superBucketMin + (uint64(j) << subBucketShift) 164 165 // Convert the subBucketMin which is in nanoseconds to a float64 seconds value. 166 // These values will all be exactly representable by a float64. 167 b[i*timeHistNumSubBuckets+j+1] = float64(subBucketMin) / 1e9 168 } 169 } 170 b[len(b)-1] = float64Inf() 171 return b 172 } 173