Source file src/runtime/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  //
    88  //go:nosplit
    89  func (h *timeHistogram) record(duration int64) {
    90  	if duration < 0 {
    91  		atomic.Xadd64(&h.underflow, 1)
    92  		return
    93  	}
    94  	// The index of the exponential bucket is just the index
    95  	// of the highest set bit adjusted for how many bits we
    96  	// use for the subbucket. Note that it's timeHistSubBucketsBits-1
    97  	// because we use the 0th bucket to hold values < timeHistNumSubBuckets.
    98  	var superBucket, subBucket uint
    99  	if duration >= timeHistNumSubBuckets {
   100  		// At this point, we know the duration value will always be
   101  		// at least timeHistSubBucketsBits long.
   102  		superBucket = uint(sys.Len64(uint64(duration))) - timeHistSubBucketBits
   103  		if superBucket*timeHistNumSubBuckets >= uint(len(h.counts)) {
   104  			// The bucket index we got is larger than what we support, so
   105  			// include this count in the highest bucket, which extends to
   106  			// infinity.
   107  			superBucket = timeHistNumSuperBuckets - 1
   108  			subBucket = timeHistNumSubBuckets - 1
   109  		} else {
   110  			// The linear subbucket index is just the timeHistSubBucketsBits
   111  			// bits after the top bit. To extract that value, shift down
   112  			// the duration such that we leave the top bit and the next bits
   113  			// intact, then extract the index.
   114  			subBucket = uint((duration >> (superBucket - 1)) % timeHistNumSubBuckets)
   115  		}
   116  	} else {
   117  		subBucket = uint(duration)
   118  	}
   119  	atomic.Xadd64(&h.counts[superBucket*timeHistNumSubBuckets+subBucket], 1)
   120  }
   121  
   122  const (
   123  	fInf    = 0x7FF0000000000000
   124  	fNegInf = 0xFFF0000000000000
   125  )
   126  
   127  func float64Inf() float64 {
   128  	inf := uint64(fInf)
   129  	return *(*float64)(unsafe.Pointer(&inf))
   130  }
   131  
   132  func float64NegInf() float64 {
   133  	inf := uint64(fNegInf)
   134  	return *(*float64)(unsafe.Pointer(&inf))
   135  }
   136  
   137  // timeHistogramMetricsBuckets generates a slice of boundaries for
   138  // the timeHistogram. These boundaries are represented in seconds,
   139  // not nanoseconds like the timeHistogram represents durations.
   140  func timeHistogramMetricsBuckets() []float64 {
   141  	b := make([]float64, timeHistTotalBuckets+1)
   142  	b[0] = float64NegInf()
   143  	// Super-bucket 0 has no bits above timeHistSubBucketBits
   144  	// set, so just iterate over each bucket and assign the
   145  	// incrementing bucket.
   146  	for i := 0; i < timeHistNumSubBuckets; i++ {
   147  		bucketNanos := uint64(i)
   148  		b[i+1] = float64(bucketNanos) / 1e9
   149  	}
   150  	// Generate the rest of the super-buckets. It's easier to reason
   151  	// about if we cut out the 0'th bucket, so subtract one since
   152  	// we just handled that bucket.
   153  	for i := 0; i < timeHistNumSuperBuckets-1; i++ {
   154  		for j := 0; j < timeHistNumSubBuckets; j++ {
   155  			// Set the super-bucket bit.
   156  			bucketNanos := uint64(1) << (i + timeHistSubBucketBits)
   157  			// Set the sub-bucket bits.
   158  			bucketNanos |= uint64(j) << i
   159  			// The index for this bucket is going to be the (i+1)'th super bucket
   160  			// (note that we're starting from zero, but handled the first super-bucket
   161  			// earlier, so we need to compensate), and the j'th sub bucket.
   162  			// Add 1 because we left space for -Inf.
   163  			bucketIndex := (i+1)*timeHistNumSubBuckets + j + 1
   164  			// Convert nanoseconds to seconds via a division.
   165  			// These values will all be exactly representable by a float64.
   166  			b[bucketIndex] = float64(bucketNanos) / 1e9
   167  		}
   168  	}
   169  	b[len(b)-1] = float64Inf()
   170  	return b
   171  }
   172  

View as plain text