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