histogram.go

Documentation: google.golang.org/grpc/benchmark/stats

     1  /*
     2   *
     3   * Copyright 2017 gRPC authors.
     4   *
     5   * Licensed under the Apache License, Version 2.0 (the "License");
     6   * you may not use this file except in compliance with the License.
     7   * You may obtain a copy of the License at
     8   *
     9   *     http://www.apache.org/licenses/LICENSE-2.0
    10   *
    11   * Unless required by applicable law or agreed to in writing, software
    12   * distributed under the License is distributed on an "AS IS" BASIS,
    13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    14   * See the License for the specific language governing permissions and
    15   * limitations under the License.
    16   *
    17   */
    18  
    19  package stats
    20  
    21  import (
    22  	"bytes"
    23  	"fmt"
    24  	"io"
    25  	"log"
    26  	"math"
    27  	"strconv"
    28  	"strings"
    29  )
    30  
    31  // Histogram accumulates values in the form of a histogram with
    32  // exponentially increased bucket sizes.
    33  type Histogram struct {
    34  	// Count is the total number of values added to the histogram.
    35  	Count int64
    36  	// Sum is the sum of all the values added to the histogram.
    37  	Sum int64
    38  	// SumOfSquares is the sum of squares of all values.
    39  	SumOfSquares int64
    40  	// Min is the minimum of all the values added to the histogram.
    41  	Min int64
    42  	// Max is the maximum of all the values added to the histogram.
    43  	Max int64
    44  	// Buckets contains all the buckets of the histogram.
    45  	Buckets []HistogramBucket
    46  
    47  	opts                          HistogramOptions
    48  	logBaseBucketSize             float64
    49  	oneOverLogOnePlusGrowthFactor float64
    50  }
    51  
    52  // HistogramOptions contains the parameters that define the histogram's buckets.
    53  // The first bucket of the created histogram (with index 0) contains [min, min+n)
    54  // where n = BaseBucketSize, min = MinValue.
    55  // Bucket i (i>=1) contains [min + n * m^(i-1), min + n * m^i), where m = 1+GrowthFactor.
    56  // The type of the values is int64.
    57  type HistogramOptions struct {
    58  	// NumBuckets is the number of buckets.
    59  	NumBuckets int
    60  	// GrowthFactor is the growth factor of the buckets. A value of 0.1
    61  	// indicates that bucket N+1 will be 10% larger than bucket N.
    62  	GrowthFactor float64
    63  	// BaseBucketSize is the size of the first bucket.
    64  	BaseBucketSize float64
    65  	// MinValue is the lower bound of the first bucket.
    66  	MinValue int64
    67  }
    68  
    69  // HistogramBucket represents one histogram bucket.
    70  type HistogramBucket struct {
    71  	// LowBound is the lower bound of the bucket.
    72  	LowBound float64
    73  	// Count is the number of values in the bucket.
    74  	Count int64
    75  }
    76  
    77  // NewHistogram returns a pointer to a new Histogram object that was created
    78  // with the provided options.
    79  func NewHistogram(opts HistogramOptions) *Histogram {
    80  	if opts.NumBuckets == 0 {
    81  		opts.NumBuckets = 32
    82  	}
    83  	if opts.BaseBucketSize == 0.0 {
    84  		opts.BaseBucketSize = 1.0
    85  	}
    86  	h := Histogram{
    87  		Buckets: make([]HistogramBucket, opts.NumBuckets),
    88  		Min:     math.MaxInt64,
    89  		Max:     math.MinInt64,
    90  
    91  		opts:                          opts,
    92  		logBaseBucketSize:             math.Log(opts.BaseBucketSize),
    93  		oneOverLogOnePlusGrowthFactor: 1 / math.Log(1+opts.GrowthFactor),
    94  	}
    95  	m := 1.0 + opts.GrowthFactor
    96  	delta := opts.BaseBucketSize
    97  	h.Buckets[0].LowBound = float64(opts.MinValue)
    98  	for i := 1; i < opts.NumBuckets; i++ {
    99  		h.Buckets[i].LowBound = float64(opts.MinValue) + delta
   100  		delta = delta * m
   101  	}
   102  	return &h
   103  }
   104  
   105  // Print writes textual output of the histogram values.
   106  func (h *Histogram) Print(w io.Writer) {
   107  	h.PrintWithUnit(w, 1)
   108  }
   109  
   110  // PrintWithUnit writes textual output of the histogram values	.
   111  // Data in histogram is divided by a Unit before print.
   112  func (h *Histogram) PrintWithUnit(w io.Writer, unit float64) {
   113  	avg := float64(h.Sum) / float64(h.Count)
   114  	fmt.Fprintf(w, "Count: %d  Min: %5.1f  Max: %5.1f  Avg: %.2f\n", h.Count, float64(h.Min)/unit, float64(h.Max)/unit, avg/unit)
   115  	fmt.Fprintf(w, "%s\n", strings.Repeat("-", 60))
   116  	if h.Count <= 0 {
   117  		return
   118  	}
   119  
   120  	maxBucketDigitLen := len(strconv.FormatFloat(h.Buckets[len(h.Buckets)-1].LowBound, 'f', 6, 64))
   121  	maxCountDigitLen := len(strconv.FormatInt(h.Count, 10))
   122  	percentMulti := 100 / float64(h.Count)
   123  
   124  	accCount := int64(0)
   125  	for i, b := range h.Buckets {
   126  		fmt.Fprintf(w, "[%*f, ", maxBucketDigitLen, b.LowBound/unit)
   127  		if i+1 < len(h.Buckets) {
   128  			fmt.Fprintf(w, "%*f)", maxBucketDigitLen, h.Buckets[i+1].LowBound/unit)
   129  		} else {
   130  			upperBound := float64(h.opts.MinValue) + (b.LowBound-float64(h.opts.MinValue))*(1.0+h.opts.GrowthFactor)
   131  			fmt.Fprintf(w, "%*f)", maxBucketDigitLen, upperBound/unit)
   132  		}
   133  		accCount += b.Count
   134  		fmt.Fprintf(w, "  %*d  %5.1f%%  %5.1f%%", maxCountDigitLen, b.Count, float64(b.Count)*percentMulti, float64(accCount)*percentMulti)
   135  
   136  		const barScale = 0.1
   137  		barLength := int(float64(b.Count)*percentMulti*barScale + 0.5)
   138  		fmt.Fprintf(w, "  %s\n", strings.Repeat("#", barLength))
   139  	}
   140  }
   141  
   142  // String returns the textual output of the histogram values as string.
   143  func (h *Histogram) String() string {
   144  	var b bytes.Buffer
   145  	h.Print(&b)
   146  	return b.String()
   147  }
   148  
   149  // Clear resets all the content of histogram.
   150  func (h *Histogram) Clear() {
   151  	h.Count = 0
   152  	h.Sum = 0
   153  	h.SumOfSquares = 0
   154  	h.Min = math.MaxInt64
   155  	h.Max = math.MinInt64
   156  	for i := range h.Buckets {
   157  		h.Buckets[i].Count = 0
   158  	}
   159  }
   160  
   161  // Opts returns a copy of the options used to create the Histogram.
   162  func (h *Histogram) Opts() HistogramOptions {
   163  	return h.opts
   164  }
   165  
   166  // Add adds a value to the histogram.
   167  func (h *Histogram) Add(value int64) error {
   168  	bucket, err := h.findBucket(value)
   169  	if err != nil {
   170  		return err
   171  	}
   172  	h.Buckets[bucket].Count++
   173  	h.Count++
   174  	h.Sum += value
   175  	h.SumOfSquares += value * value
   176  	if value < h.Min {
   177  		h.Min = value
   178  	}
   179  	if value > h.Max {
   180  		h.Max = value
   181  	}
   182  	return nil
   183  }
   184  
   185  func (h *Histogram) findBucket(value int64) (int, error) {
   186  	delta := float64(value - h.opts.MinValue)
   187  	if delta < 0 {
   188  		return 0, fmt.Errorf("no bucket for value: %d", value)
   189  	}
   190  	var b int
   191  	if delta >= h.opts.BaseBucketSize {
   192  		// b = log_{1+growthFactor} (delta / baseBucketSize) + 1
   193  		//   = log(delta / baseBucketSize) / log(1+growthFactor) + 1
   194  		//   = (log(delta) - log(baseBucketSize)) * (1 / log(1+growthFactor)) + 1
   195  		b = int((math.Log(delta)-h.logBaseBucketSize)*h.oneOverLogOnePlusGrowthFactor + 1)
   196  	}
   197  	if b >= len(h.Buckets) {
   198  		return 0, fmt.Errorf("no bucket for value: %d", value)
   199  	}
   200  	return b, nil
   201  }
   202  
   203  // Merge takes another histogram h2, and merges its content into h.
   204  // The two histograms must be created by equivalent HistogramOptions.
   205  func (h *Histogram) Merge(h2 *Histogram) {
   206  	if h.opts != h2.opts {
   207  		log.Fatalf("failed to merge histograms, created by inequivalent options")
   208  	}
   209  	h.Count += h2.Count
   210  	h.Sum += h2.Sum
   211  	h.SumOfSquares += h2.SumOfSquares
   212  	if h2.Min < h.Min {
   213  		h.Min = h2.Min
   214  	}
   215  	if h2.Max > h.Max {
   216  		h.Max = h2.Max
   217  	}
   218  	for i, b := range h2.Buckets {
   219  		h.Buckets[i].Count += b.Count
   220  	}
   221  }
   222
View as plain text