[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

3 files changed, 65 insertions, 29 deletions

diff --git a/src/runtime/export_test.go b/src/runtime/export_test.go
index 59f72ae709..79f13d1b4b 100644
--- a/src/runtime/export_test.go
+++ b/src/runtime/export_test.go
@@ -1226,3 +1226,5 @@ func (th *TimeHistogram) Count(bucket, subBucket uint) (uint64, bool) {
 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 da4910d341..1b45ad97df 100644
--- a/src/runtime/histogram.go
+++ b/src/runtime/histogram.go
@@ -47,7 +47,7 @@ const (
 	//    │  └---- 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 float64NegInf() float64 {
 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 dbc64fa559..b12b65a41e 100644
--- a/src/runtime/histogram_test.go
+++ b/src/runtime/histogram_test.go
@@ -68,3 +68,43 @@ func TestTimeHistogram(t *testing.T) {
 
 	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)
+		}
+	}
+}