[release-branch.go1.16] runtime: simplify histogram buckets considerably
There was an off-by-one error in the time histogram buckets calculation
that caused the linear sub-buckets distances to be off by 2x.
The fix was trivial, but in writing tests I realized there was a much
simpler way to express the calculation for the histogram buckets, and
took the opportunity to do that here. The new bucket calculation also
fixes the bug.
For #50732.
Fixes #50733.
Change-Id: Idae89986de1c415ee4e148f778e0e101ca003ade
Reviewed-on: https://go-review.googlesource.com/c/go/+/380094
Reviewed-by: Michael Pratt <mpratt@google.com>
Reviewed-by: Emmanuel Odeke <emmanuel@orijtech.com>
Trust: Michael Knyszek <mknyszek@google.com>
Run-TryBot: Michael Knyszek <mknyszek@google.com>
(cherry picked from commit 2e9dcb508647dc473a37ecfa244d2bc4a1843ab4)
Reviewed-on: https://go-review.googlesource.com/c/go/+/384620
diff --git a/src/runtime/export_test.go b/src/runtime/export_test.go
index 59f72ae..79f13d1 100644
--- a/src/runtime/export_test.go
+++ b/src/runtime/export_test.go
@@ -1226,3 +1226,5 @@
func (th *TimeHistogram) Record(duration int64) {
(*timeHistogram)(th).record(duration)
}
+
+var TimeHistogramMetricsBuckets = timeHistogramMetricsBuckets
diff --git a/src/runtime/histogram.go b/src/runtime/histogram.go
index da4910d..1b45ad9 100644
--- a/src/runtime/histogram.go
+++ b/src/runtime/histogram.go
@@ -47,7 +47,7 @@
// │ └---- 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
+ // Following this pattern, super-bucket 44 will have the bit 47 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.
@@ -135,36 +135,30 @@
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)
- }
+ // Super-bucket 0 has no bits above timeHistSubBucketBits
+ // set, so just iterate over each bucket and assign the
+ // incrementing bucket.
+ for i := 0; i < timeHistNumSubBuckets; i++ {
+ bucketNanos := uint64(i)
+ b[i+1] = float64(bucketNanos) / 1e9
+ }
+ // Generate the rest of the super-buckets. It's easier to reason
+ // about if we cut out the 0'th bucket, so subtract one since
+ // we just handled that bucket.
+ for i := 0; i < timeHistNumSuperBuckets-1; i++ {
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.
+ // Set the super-bucket bit.
+ bucketNanos := uint64(1) << (i + timeHistSubBucketBits)
+ // Set the sub-bucket bits.
+ bucketNanos |= uint64(j) << i
+ // The index for this bucket is going to be the (i+1)'th super bucket
+ // (note that we're starting from zero, but handled the first super-bucket
+ // earlier, so we need to compensate), and the j'th sub bucket.
+ // Add 1 because we left space for -Inf.
+ bucketIndex := (i+1)*timeHistNumSubBuckets + j + 1
+ // Convert nanoseconds to seconds via a division.
// These values will all be exactly representable by a float64.
- b[i*timeHistNumSubBuckets+j+1] = float64(subBucketMin) / 1e9
+ b[bucketIndex] = float64(bucketNanos) / 1e9
}
}
b[len(b)-1] = float64Inf()
diff --git a/src/runtime/histogram_test.go b/src/runtime/histogram_test.go
index dbc64fa..b12b65a 100644
--- a/src/runtime/histogram_test.go
+++ b/src/runtime/histogram_test.go
@@ -68,3 +68,43 @@
dummyTimeHistogram = TimeHistogram{}
}
+
+func TestTimeHistogramMetricsBuckets(t *testing.T) {
+ buckets := TimeHistogramMetricsBuckets()
+
+ nonInfBucketsLen := TimeHistNumSubBuckets * TimeHistNumSuperBuckets
+ expBucketsLen := nonInfBucketsLen + 2 // Count -Inf and +Inf.
+ if len(buckets) != expBucketsLen {
+ t.Fatalf("unexpected length of buckets: got %d, want %d", len(buckets), expBucketsLen)
+ }
+ // Check the first non-Inf 2*TimeHistNumSubBuckets buckets in order, skipping the
+ // first bucket which should be -Inf (checked later).
+ //
+ // Because of the way this scheme works, the bottom TimeHistNumSubBuckets
+ // buckets are fully populated, and then the next TimeHistNumSubBuckets
+ // have the TimeHistSubBucketBits'th bit set, while the bottom are once
+ // again fully populated.
+ for i := 1; i <= 2*TimeHistNumSubBuckets+1; i++ {
+ if got, want := buckets[i], float64(i-1)/1e9; got != want {
+ t.Errorf("expected bucket %d to have value %e, got %e", i, want, got)
+ }
+ }
+ // Check some values.
+ idxToBucket := map[int]float64{
+ 0: math.Inf(-1),
+ 33: float64(0x10<<1) / 1e9,
+ 34: float64(0x11<<1) / 1e9,
+ 49: float64(0x10<<2) / 1e9,
+ 58: float64(0x19<<2) / 1e9,
+ 65: float64(0x10<<3) / 1e9,
+ 513: float64(0x10<<31) / 1e9,
+ 519: float64(0x16<<31) / 1e9,
+ expBucketsLen - 2: float64(0x1f<<43) / 1e9,
+ expBucketsLen - 1: math.Inf(1),
+ }
+ for idx, bucket := range idxToBucket {
+ if got, want := buckets[idx], bucket; got != want {
+ t.Errorf("expected bucket %d to have value %e, got %e", idx, want, got)
+ }
+ }
+}
