Black Lives Matter. Support the Equal Justice Initiative.

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  //
    85  // Disallow preemptions and stack growths because this function
    86  // may run in sensitive locations.
    87  //go:nosplit
    88  func (h *timeHistogram) record(duration int64) {
    89  	if duration < 0 {
    90  		atomic.Xadd64(&h.underflow, 1)
    91  		return
    92  	}
    93  	// The index of the exponential bucket is just the index
    94  	// of the highest set bit adjusted for how many bits we
    95  	// use for the subbucket. Note that it's timeHistSubBucketsBits-1
    96  	// because we use the 0th bucket to hold values < timeHistNumSubBuckets.
    97  	var superBucket, subBucket uint
    98  	if duration >= timeHistNumSubBuckets {
    99  		// At this point, we know the duration value will always be
   100  		// at least timeHistSubBucketsBits long.
   101  		superBucket = uint(sys.Len64(uint64(duration))) - timeHistSubBucketBits
   102  		if superBucket*timeHistNumSubBuckets >= uint(len(h.counts)) {
   103  			// The bucket index we got is larger than what we support, so
   104  			// include this count in the highest bucket, which extends to
   105  			// infinity.
   106  			superBucket = timeHistNumSuperBuckets - 1
   107  			subBucket = timeHistNumSubBuckets - 1
   108  		} else {
   109  			// The linear subbucket index is just the timeHistSubBucketsBits
   110  			// bits after the top bit. To extract that value, shift down
   111  			// the duration such that we leave the top bit and the next bits
   112  			// intact, then extract the index.
   113  			subBucket = uint((duration >> (superBucket - 1)) % timeHistNumSubBuckets)
   114  		}
   115  	} else {
   116  		subBucket = uint(duration)
   117  	}
   118  	atomic.Xadd64(&h.counts[superBucket*timeHistNumSubBuckets+subBucket], 1)
   119  }
   120  
   121  const (
   122  	fInf    = 0x7FF0000000000000
   123  	fNegInf = 0xFFF0000000000000
   124  )
   125  
   126  func float64Inf() float64 {
   127  	inf := uint64(fInf)
   128  	return *(*float64)(unsafe.Pointer(&inf))
   129  }
   130  
   131  func float64NegInf() float64 {
   132  	inf := uint64(fNegInf)
   133  	return *(*float64)(unsafe.Pointer(&inf))
   134  }
   135  
   136  // timeHistogramMetricsBuckets generates a slice of boundaries for
   137  // the timeHistogram. These boundaries are represented in seconds,
   138  // not nanoseconds like the timeHistogram represents durations.
   139  func timeHistogramMetricsBuckets() []float64 {
   140  	b := make([]float64, timeHistTotalBuckets+1)
   141  	b[0] = float64NegInf()
   142  	for i := 0; i < timeHistNumSuperBuckets; i++ {
   143  		superBucketMin := uint64(0)
   144  		// The (inclusive) minimum for the first non-negative bucket is 0.
   145  		if i > 0 {
   146  			// The minimum for the second bucket will be
   147  			// 1 << timeHistSubBucketBits, indicating that all
   148  			// sub-buckets are represented by the next timeHistSubBucketBits
   149  			// bits.
   150  			// Thereafter, we shift up by 1 each time, so we can represent
   151  			// this pattern as (i-1)+timeHistSubBucketBits.
   152  			superBucketMin = uint64(1) << uint(i-1+timeHistSubBucketBits)
   153  		}
   154  		// subBucketShift is the amount that we need to shift the sub-bucket
   155  		// index to combine it with the bucketMin.
   156  		subBucketShift := uint(0)
   157  		if i > 1 {
   158  			// The first two super buckets are exact with respect to integers,
   159  			// so we'll never have to shift the sub-bucket index. Thereafter,
   160  			// we shift up by 1 with each subsequent bucket.
   161  			subBucketShift = uint(i - 2)
   162  		}
   163  		for j := 0; j < timeHistNumSubBuckets; j++ {
   164  			// j is the sub-bucket index. By shifting the index into position to
   165  			// combine with the bucket minimum, we obtain the minimum value for that
   166  			// sub-bucket.
   167  			subBucketMin := superBucketMin + (uint64(j) << subBucketShift)
   168  
   169  			// Convert the subBucketMin which is in nanoseconds to a float64 seconds value.
   170  			// These values will all be exactly representable by a float64.
   171  			b[i*timeHistNumSubBuckets+j+1] = float64(subBucketMin) / 1e9
   172  		}
   173  	}
   174  	b[len(b)-1] = float64Inf()
   175  	return b
   176  }
   177  

View as plain text