histogram.go

     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, super-bucket 44 will have the bit 47 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  	// Super-bucket 0 has no bits above timeHistSubBucketBits
   143  	// set, so just iterate over each bucket and assign the
   144  	// incrementing bucket.
   145  	for i := 0; i < timeHistNumSubBuckets; i++ {
   146  		bucketNanos := uint64(i)
   147  		b[i+1] = float64(bucketNanos) / 1e9
   148  	}
   149  	// Generate the rest of the super-buckets. It's easier to reason
   150  	// about if we cut out the 0'th bucket, so subtract one since
   151  	// we just handled that bucket.
   152  	for i := 0; i < timeHistNumSuperBuckets-1; i++ {
   153  		for j := 0; j < timeHistNumSubBuckets; j++ {
   154  			// Set the super-bucket bit.
   155  			bucketNanos := uint64(1) << (i + timeHistSubBucketBits)
   156  			// Set the sub-bucket bits.
   157  			bucketNanos |= uint64(j) << i
   158  			// The index for this bucket is going to be the (i+1)'th super bucket
   159  			// (note that we're starting from zero, but handled the first super-bucket
   160  			// earlier, so we need to compensate), and the j'th sub bucket.
   161  			// Add 1 because we left space for -Inf.
   162  			bucketIndex := (i+1)*timeHistNumSubBuckets + j + 1
   163  			// Convert nanoseconds to seconds via a division.
   164  			// These values will all be exactly representable by a float64.
   165  			b[bucketIndex] = float64(bucketNanos) / 1e9
   166  		}
   167  	}
   168  	b[len(b)-1] = float64Inf()
   169  	return b
   170  }
   171
View as plain text