test/core/util/histogram.cc

   1 /*
   2  *
   3  * Copyright 2015 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 #include "test/core/util/histogram.h"
  20
  21 #include <math.h>
  22 #include <stddef.h>
  23 #include <string.h>
  24
  25 #include <grpc/support/alloc.h>
  26 #include <grpc/support/log.h>
  27 #include <grpc/support/port_platform.h>
  28
  29 #include "src/core/lib/gpr/useful.h"
  30
  31 /* Histograms are stored with exponentially increasing bucket sizes.
  32    The first bucket is [0, m) where m = 1 + resolution
  33    Bucket n (n>=1) contains [m**n, m**(n+1))
  34    There are sufficient buckets to reach max_bucket_start */
  35
  36 struct grpc_histogram {
  37   /* Sum of all values seen so far */
  38   double sum;
  39   /* Sum of squares of all values seen so far */
  40   double sum_of_squares;
  41   /* number of values seen so far */
  42   double count;
  43   /* m in the description */
  44   double multiplier;
  45   double one_on_log_multiplier;
  46   /* minimum value seen */
  47   double min_seen;
  48   /* maximum value seen */
  49   double max_seen;
  50   /* maximum representable value */
  51   double max_possible;
  52   /* number of buckets */
  53   size_t num_buckets;
  54   /* the buckets themselves */
  55   uint32_t* buckets;
  56 };
  57
  58 /* determine a bucket index given a value - does no bounds checking */
  59 static size_t bucket_for_unchecked(grpc_histogram* h, double x) {
  60   return static_cast<size_t>(log(x) * h->one_on_log_multiplier);
  61 }
  62
  63 /* bounds checked version of the above */
  64 static size_t bucket_for(grpc_histogram* h, double x) {
  65   size_t bucket = bucket_for_unchecked(h, GPR_CLAMP(x, 1.0, h->max_possible));
  66   GPR_ASSERT(bucket < h->num_buckets);
  67   return bucket;
  68 }
  69
  70 /* at what value does a bucket start? */
  71 static double bucket_start(grpc_histogram* h, double x) {
  72   return pow(h->multiplier, x);
  73 }
  74
  75 grpc_histogram* grpc_histogram_create(double resolution,
  76                                       double max_bucket_start) {
  77   grpc_histogram* h =
  78       static_cast<grpc_histogram*>(gpr_malloc(sizeof(grpc_histogram)));
  79   GPR_ASSERT(resolution > 0.0);
  80   GPR_ASSERT(max_bucket_start > resolution);
  81   h->sum = 0.0;
  82   h->sum_of_squares = 0.0;
  83   h->multiplier = 1.0 + resolution;
  84   h->one_on_log_multiplier = 1.0 / log(1.0 + resolution);
  85   h->max_possible = max_bucket_start;
  86   h->count = 0.0;
  87   h->min_seen = max_bucket_start;
  88   h->max_seen = 0.0;
  89   h->num_buckets = bucket_for_unchecked(h, max_bucket_start) + 1;
  90   GPR_ASSERT(h->num_buckets > 1);
  91   GPR_ASSERT(h->num_buckets < 100000000);
  92   h->buckets =
  93       static_cast<uint32_t*>(gpr_zalloc(sizeof(uint32_t) * h->num_buckets));
  94   return h;
  95 }
  96
  97 void grpc_histogram_destroy(grpc_histogram* h) {
  98   gpr_free(h->buckets);
  99   gpr_free(h);
 100 }
 101
 102 void grpc_histogram_add(grpc_histogram* h, double x) {
 103   h->sum += x;
 104   h->sum_of_squares += x * x;
 105   h->count++;
 106   if (x < h->min_seen) {
 107     h->min_seen = x;
 108   }
 109   if (x > h->max_seen) {
 110     h->max_seen = x;
 111   }
 112   h->buckets[bucket_for(h, x)]++;
 113 }
 114
 115 int grpc_histogram_merge(grpc_histogram* dst, const grpc_histogram* src) {
 116   if ((dst->num_buckets != src->num_buckets) ||
 117       (dst->multiplier != src->multiplier)) {
 118     /* Fail because these histograms don't match */
 119     return 0;
 120   }
 121   grpc_histogram_merge_contents(dst, src->buckets, src->num_buckets,
 122                                 src->min_seen, src->max_seen, src->sum,
 123                                 src->sum_of_squares, src->count);
 124   return 1;
 125 }
 126
 127 void grpc_histogram_merge_contents(grpc_histogram* histogram,
 128                                    const uint32_t* data, size_t data_count,
 129                                    double min_seen, double max_seen, double sum,
 130                                    double sum_of_squares, double count) {
 131   size_t i;
 132   GPR_ASSERT(histogram->num_buckets == data_count);
 133   histogram->sum += sum;
 134   histogram->sum_of_squares += sum_of_squares;
 135   histogram->count += count;
 136   if (min_seen < histogram->min_seen) {
 137     histogram->min_seen = min_seen;
 138   }
 139   if (max_seen > histogram->max_seen) {
 140     histogram->max_seen = max_seen;
 141   }
 142   for (i = 0; i < histogram->num_buckets; i++) {
 143     histogram->buckets[i] += data[i];
 144   }
 145 }
 146
 147 static double threshold_for_count_below(grpc_histogram* h, double count_below) {
 148   double count_so_far;
 149   double lower_bound;
 150   double upper_bound;
 151   size_t lower_idx;
 152   size_t upper_idx;
 153
 154   if (h->count == 0) {
 155     return 0.0;
 156   }
 157
 158   if (count_below <= 0) {
 159     return h->min_seen;
 160   }
 161   if (count_below >= h->count) {
 162     return h->max_seen;
 163   }
 164
 165   /* find the lowest bucket that gets us above count_below */
 166   count_so_far = 0.0;
 167   for (lower_idx = 0; lower_idx < h->num_buckets; lower_idx++) {
 168     count_so_far += h->buckets[lower_idx];
 169     if (count_so_far >= count_below) {
 170       break;
 171     }
 172   }
 173   if (count_so_far == count_below) {
 174     /* this bucket hits the threshold exactly... we should be midway through
 175        any run of zero values following the bucket */
 176     for (upper_idx = lower_idx + 1; upper_idx < h->num_buckets; upper_idx++) {
 177       if (h->buckets[upper_idx]) {
 178         break;
 179       }
 180     }
 181     return (bucket_start(h, static_cast<double>(lower_idx)) +
 182             bucket_start(h, static_cast<double>(upper_idx))) /
 183            2.0;
 184   } else {
 185     /* treat values as uniform throughout the bucket, and find where this value
 186        should lie */
 187     lower_bound = bucket_start(h, static_cast<double>(lower_idx));
 188     upper_bound = bucket_start(h, static_cast<double>(lower_idx + 1));
 189     return GPR_CLAMP(upper_bound - (upper_bound - lower_bound) *
 190                                        (count_so_far - count_below) /
 191                                        h->buckets[lower_idx],
 192                      h->min_seen, h->max_seen);
 193   }
 194 }
 195
 196 double grpc_histogram_percentile(grpc_histogram* h, double percentile) {
 197   return threshold_for_count_below(h, h->count * percentile / 100.0);
 198 }
 199
 200 double grpc_histogram_mean(grpc_histogram* h) {
 201   GPR_ASSERT(h->count != 0);
 202   return h->sum / h->count;
 203 }
 204
 205 double grpc_histogram_stddev(grpc_histogram* h) {
 206   return sqrt(grpc_histogram_variance(h));
 207 }
 208
 209 double grpc_histogram_variance(grpc_histogram* h) {
 210   if (h->count == 0) return 0.0;
 211   return (h->sum_of_squares * h->count - h->sum * h->sum) /
 212          (h->count * h->count);
 213 }
 214
 215 double grpc_histogram_maximum(grpc_histogram* h) { return h->max_seen; }
 216
 217 double grpc_histogram_minimum(grpc_histogram* h) { return h->min_seen; }
 218
 219 double grpc_histogram_count(grpc_histogram* h) { return h->count; }
 220
 221 double grpc_histogram_sum(grpc_histogram* h) { return h->sum; }
 222
 223 double grpc_histogram_sum_of_squares(grpc_histogram* h) {
 224   return h->sum_of_squares;
 225 }
 226
 227 const uint32_t* grpc_histogram_get_contents(grpc_histogram* histogram,
 228                                             size_t* count) {
 229   *count = histogram->num_buckets;
 230   return histogram->buckets;
 231 }