folly/stats/Histogram.h

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #pragma once
  18
  19 #include <cstddef>
  20 #include <cstdint>
  21 #include <limits>
  22 #include <ostream>
  23 #include <stdexcept>
  24 #include <string>
  25 #include <vector>
  26
  27 #include <folly/CPortability.h>
  28 #include <folly/detail/Stats.h>
  29
  30 namespace folly {
  31
  32 namespace detail {
  33
  34 /*
  35  * A helper class to manage a set of histogram buckets.
  36  */
  37 template <typename T, typename BucketT>
  38 class HistogramBuckets {
  39  public:
  40   typedef T ValueType;
  41   typedef BucketT BucketType;
  42
  43   /*
  44    * Create a set of histogram buckets.
  45    *
  46    * One bucket will be created for each bucketSize interval of values within
  47    * the specified range.  Additionally, one bucket will be created to track
  48    * all values that fall below the specified minimum, and one bucket will be
  49    * created for all values above the specified maximum.
  50    *
  51    * If (max - min) is not a multiple of bucketSize, the last bucket will cover
  52    * a smaller range of values than the other buckets.
  53    *
  54    * (max - min) must be larger than or equal to bucketSize.
  55    */
  56   HistogramBuckets(ValueType bucketSize, ValueType min, ValueType max,
  57                    const BucketType& defaultBucket);
  58
  59   /* Returns the bucket size of each bucket in the histogram. */
  60   ValueType getBucketSize() const {
  61     return bucketSize_;
  62   }
  63
  64   /* Returns the min value at which bucketing begins. */
  65   ValueType getMin() const {
  66     return min_;
  67   }
  68
  69   /* Returns the max value at which bucketing ends. */
  70   ValueType getMax() const {
  71     return max_;
  72   }
  73
  74   /*
  75    * Returns the number of buckets.
  76    *
  77    * This includes the total number of buckets for the [min, max) range,
  78    * plus 2 extra buckets, one for handling values less than min, and one for
  79    * values greater than max.
  80    */
  81   size_t getNumBuckets() const {
  82     return buckets_.size();
  83   }
  84
  85   /* Returns the bucket index into which the given value would fall. */
  86   size_t getBucketIdx(ValueType value) const;
  87
  88   /* Returns the bucket for the specified value */
  89   BucketType& getByValue(ValueType value) {
  90     return buckets_[getBucketIdx(value)];
  91   }
  92
  93   /* Returns the bucket for the specified value */
  94   const BucketType& getByValue(ValueType value) const {
  95     return buckets_[getBucketIdx(value)];
  96   }
  97
  98   /*
  99    * Returns the bucket at the specified index.
 100    *
 101    * Note that index 0 is the bucket for all values less than the specified
 102    * minimum.  Index 1 is the first bucket in the specified bucket range.
 103    */
 104   BucketType& getByIndex(size_t idx) {
 105     return buckets_[idx];
 106   }
 107
 108   /* Returns the bucket at the specified index. */
 109   const BucketType& getByIndex(size_t idx) const {
 110     return buckets_[idx];
 111   }
 112
 113   /*
 114    * Returns the minimum threshold for the bucket at the given index.
 115    *
 116    * The bucket at the specified index will store values in the range
 117    * [bucketMin, bucketMin + bucketSize), or [bucketMin, max), if the overall
 118    * max is smaller than bucketMin + bucketSize.
 119    */
 120   ValueType getBucketMin(size_t idx) const {
 121     if (idx == 0) {
 122       return std::numeric_limits<ValueType>::min();
 123     }
 124     if (idx == buckets_.size() - 1) {
 125       return max_;
 126     }
 127
 128     return ValueType(min_ + ((idx - 1) * bucketSize_));
 129   }
 130
 131   /*
 132    * Returns the maximum threshold for the bucket at the given index.
 133    *
 134    * The bucket at the specified index will store values in the range
 135    * [bucketMin, bucketMin + bucketSize), or [bucketMin, max), if the overall
 136    * max is smaller than bucketMin + bucketSize.
 137    */
 138   ValueType getBucketMax(size_t idx) const {
 139     if (idx == buckets_.size() - 1) {
 140       return std::numeric_limits<ValueType>::max();
 141     }
 142
 143     return ValueType(min_ + (idx * bucketSize_));
 144   }
 145
 146   /**
 147    * Computes the total number of values stored across all buckets.
 148    *
 149    * Runs in O(numBuckets)
 150    *
 151    * @param countFn A function that takes a const BucketType&, and returns the
 152    *                number of values in that bucket
 153    * @return Returns the total number of values stored across all buckets
 154    */
 155   template <typename CountFn>
 156   uint64_t computeTotalCount(CountFn countFromBucket) const;
 157
 158   /**
 159    * Determine which bucket the specified percentile falls into.
 160    *
 161    * Looks for the bucket that contains the Nth percentile data point.
 162    *
 163    * @param pct     The desired percentile to find, as a value from 0.0 to 1.0.
 164    * @param countFn A function that takes a const BucketType&, and returns the
 165    *                number of values in that bucket.
 166    * @param lowPct  The lowest percentile stored in the selected bucket will be
 167    *                returned via this parameter.
 168    * @param highPct The highest percentile stored in the selected bucket will
 169    *                be returned via this parameter.
 170    *
 171    * @return Returns the index of the bucket that contains the Nth percentile
 172    *         data point.
 173    */
 174   template <typename CountFn>
 175   size_t getPercentileBucketIdx(
 176       double pct,
 177       CountFn countFromBucket,
 178       double* lowPct = nullptr,
 179       double* highPct = nullptr) const;
 180
 181   /**
 182    * Estimate the value at the specified percentile.
 183    *
 184    * @param pct     The desired percentile to find, as a value from 0.0 to 1.0.
 185    * @param countFn A function that takes a const BucketType&, and returns the
 186    *                number of values in that bucket.
 187    * @param avgFn   A function that takes a const BucketType&, and returns the
 188    *                average of all the values in that bucket.
 189    *
 190    * @return Returns an estimate for N, where N is the number where exactly pct
 191    *         percentage of the data points in the histogram are less than N.
 192    */
 193   template <typename CountFn, typename AvgFn>
 194   ValueType getPercentileEstimate(double pct,
 195                                   CountFn countFromBucket,
 196                                   AvgFn avgFromBucket) const;
 197
 198   /*
 199    * Iterator access to the buckets.
 200    *
 201    * Note that the first bucket is for all values less than min, and the last
 202    * bucket is for all values greater than max.  The buckets tracking values in
 203    * the [min, max) actually start at the second bucket.
 204    */
 205   typename std::vector<BucketType>::const_iterator begin() const {
 206     return buckets_.begin();
 207   }
 208   typename std::vector<BucketType>::iterator begin() {
 209     return buckets_.begin();
 210   }
 211   typename std::vector<BucketType>::const_iterator end() const {
 212     return buckets_.end();
 213   }
 214   typename std::vector<BucketType>::iterator end() {
 215     return buckets_.end();
 216   }
 217
 218  private:
 219   ValueType bucketSize_;
 220   ValueType min_;
 221   ValueType max_;
 222   std::vector<BucketType> buckets_;
 223 };
 224
 225 } // detail
 226
 227
 228 /*
 229  * A basic histogram class.
 230  *
 231  * Groups data points into equally-sized buckets, and stores the overall sum of
 232  * the data points in each bucket, as well as the number of data points in the
 233  * bucket.
 234  *
 235  * The caller must specify the minimum and maximum data points to expect ahead
 236  * of time, as well as the bucket width.
 237  */
 238 template <typename T>
 239 class Histogram {
 240  public:
 241   typedef T ValueType;
 242   typedef detail::Bucket<T> Bucket;
 243
 244   Histogram(ValueType bucketSize, ValueType min, ValueType max)
 245     : buckets_(bucketSize, min, max, Bucket()) {}
 246
 247   /* Add a data point to the histogram */
 248   void addValue(ValueType value)
 249       FOLLY_DISABLE_UNDEFINED_BEHAVIOR_SANITIZER("signed-integer-overflow")
 250       FOLLY_DISABLE_UNDEFINED_BEHAVIOR_SANITIZER("unsigned-integer-overflow") {
 251     Bucket& bucket = buckets_.getByValue(value);
 252     // NOTE: Overflow is handled elsewhere and tests check this
 253     // behavior (see HistogramTest.cpp TestOverflow* tests).
 254     // TODO: It would be nice to handle overflow here and redesign this class.
 255     bucket.sum += value;
 256     bucket.count += 1;
 257   }
 258
 259   /* Add multiple same data points to the histogram */
 260   void addRepeatedValue(ValueType value, uint64_t nSamples)
 261       FOLLY_DISABLE_UNDEFINED_BEHAVIOR_SANITIZER("signed-integer-overflow")
 262       FOLLY_DISABLE_UNDEFINED_BEHAVIOR_SANITIZER("unsigned-integer-overflow") {
 263     Bucket& bucket = buckets_.getByValue(value);
 264     // NOTE: Overflow is handled elsewhere and tests check this
 265     // behavior (see HistogramTest.cpp TestOverflow* tests).
 266     // TODO: It would be nice to handle overflow here and redesign this class.
 267     bucket.sum += value * nSamples;
 268     bucket.count += nSamples;
 269   }
 270
 271   /*
 272    * Remove a data point to the histogram
 273    *
 274    * Note that this method does not actually verify that this exact data point
 275    * had previously been added to the histogram; it merely subtracts the
 276    * requested value from the appropriate bucket's sum.
 277    */
 278   void removeValue(ValueType value) FOLLY_DISABLE_UNDEFINED_BEHAVIOR_SANITIZER(
 279       "signed-integer-overflow")
 280       FOLLY_DISABLE_UNDEFINED_BEHAVIOR_SANITIZER("unsigned-integer-overflow") {
 281     Bucket& bucket = buckets_.getByValue(value);
 282     // NOTE: Overflow is handled elsewhere and tests check this
 283     // behavior (see HistogramTest.cpp TestOverflow* tests).
 284     // TODO: It would be nice to handle overflow here and redesign this class.
 285     if (bucket.count > 0) {
 286       bucket.sum -= value;
 287       bucket.count -= 1;
 288     } else {
 289       bucket.sum = ValueType();
 290       bucket.count = 0;
 291     }
 292   }
 293
 294   /* Remove multiple same data points from the histogram */
 295   void removeRepeatedValue(ValueType value, uint64_t nSamples) {
 296     Bucket& bucket = buckets_.getByValue(value);
 297     // TODO: It would be nice to handle overflow here.
 298     if (bucket.count >= nSamples) {
 299       bucket.sum -= value * nSamples;
 300       bucket.count -= nSamples;
 301     } else {
 302       bucket.sum = ValueType();
 303       bucket.count = 0;
 304     }
 305   }
 306
 307   /* Remove all data points from the histogram */
 308   void clear() {
 309     for (size_t i = 0; i < buckets_.getNumBuckets(); i++) {
 310       buckets_.getByIndex(i).clear();
 311     }
 312   }
 313
 314   /* Subtract another histogram data from the histogram */
 315   void subtract(const Histogram &hist) {
 316     // the two histogram bucket definitions must match to support
 317     // subtract.
 318     if (getBucketSize() != hist.getBucketSize() ||
 319         getMin() != hist.getMin() ||
 320         getMax() != hist.getMax() ||
 321         getNumBuckets() != hist.getNumBuckets() ) {
 322       throw std::invalid_argument("Cannot subtract input histogram.");
 323     }
 324
 325     for (size_t i = 0; i < buckets_.getNumBuckets(); i++) {
 326       buckets_.getByIndex(i) -= hist.buckets_.getByIndex(i);
 327     }
 328   }
 329
 330   /* Merge two histogram data together */
 331   void merge(const Histogram &hist) {
 332     // the two histogram bucket definitions must match to support
 333     // a merge.
 334     if (getBucketSize() != hist.getBucketSize() ||
 335         getMin() != hist.getMin() ||
 336         getMax() != hist.getMax() ||
 337         getNumBuckets() != hist.getNumBuckets() ) {
 338       throw std::invalid_argument("Cannot merge from input histogram.");
 339     }
 340
 341     for (size_t i = 0; i < buckets_.getNumBuckets(); i++) {
 342       buckets_.getByIndex(i) += hist.buckets_.getByIndex(i);
 343     }
 344   }
 345
 346   /* Copy bucket values from another histogram */
 347   void copy(const Histogram &hist) {
 348     // the two histogram bucket definition must match
 349     if (getBucketSize() != hist.getBucketSize() ||
 350         getMin() != hist.getMin() ||
 351         getMax() != hist.getMax() ||
 352         getNumBuckets() != hist.getNumBuckets() ) {
 353       throw std::invalid_argument("Cannot copy from input histogram.");
 354     }
 355
 356     for (size_t i = 0; i < buckets_.getNumBuckets(); i++) {
 357       buckets_.getByIndex(i) = hist.buckets_.getByIndex(i);
 358     }
 359   }
 360
 361   /* Returns the bucket size of each bucket in the histogram. */
 362   ValueType getBucketSize() const {
 363     return buckets_.getBucketSize();
 364   }
 365   /* Returns the min value at which bucketing begins. */
 366   ValueType getMin() const {
 367     return buckets_.getMin();
 368   }
 369   /* Returns the max value at which bucketing ends. */
 370   ValueType getMax() const {
 371     return buckets_.getMax();
 372   }
 373   /* Returns the number of buckets */
 374   size_t getNumBuckets() const {
 375     return buckets_.getNumBuckets();
 376   }
 377
 378   /* Returns the specified bucket (for reading only!) */
 379   const Bucket& getBucketByIndex(size_t idx) const {
 380     return buckets_.getByIndex(idx);
 381   }
 382
 383   /*
 384    * Returns the minimum threshold for the bucket at the given index.
 385    *
 386    * The bucket at the specified index will store values in the range
 387    * [bucketMin, bucketMin + bucketSize), or [bucketMin, max), if the overall
 388    * max is smaller than bucketMin + bucketSize.
 389    */
 390   ValueType getBucketMin(size_t idx) const {
 391     return buckets_.getBucketMin(idx);
 392   }
 393
 394   /*
 395    * Returns the maximum threshold for the bucket at the given index.
 396    *
 397    * The bucket at the specified index will store values in the range
 398    * [bucketMin, bucketMin + bucketSize), or [bucketMin, max), if the overall
 399    * max is smaller than bucketMin + bucketSize.
 400    */
 401   ValueType getBucketMax(size_t idx) const {
 402     return buckets_.getBucketMax(idx);
 403   }
 404
 405   /**
 406    * Computes the total number of values stored across all buckets.
 407    *
 408    * Runs in O(numBuckets)
 409    */
 410   uint64_t computeTotalCount() const {
 411     CountFromBucket countFn;
 412     return buckets_.computeTotalCount(countFn);
 413   }
 414
 415   /*
 416    * Get the bucket that the specified percentile falls into
 417    *
 418    * The lowest and highest percentile data points in returned bucket will be
 419    * returned in the lowPct and highPct arguments, if they are non-NULL.
 420    */
 421   size_t getPercentileBucketIdx(
 422       double pct,
 423       double* lowPct = nullptr,
 424       double* highPct = nullptr) const {
 425     // We unfortunately can't use lambdas here yet;
 426     // Some users of this code are still built with gcc-4.4.
 427     CountFromBucket countFn;
 428     return buckets_.getPercentileBucketIdx(pct, countFn, lowPct, highPct);
 429   }
 430
 431   /**
 432    * Estimate the value at the specified percentile.
 433    *
 434    * @param pct     The desired percentile to find, as a value from 0.0 to 1.0.
 435    *
 436    * @return Returns an estimate for N, where N is the number where exactly pct
 437    *         percentage of the data points in the histogram are less than N.
 438    */
 439   ValueType getPercentileEstimate(double pct) const {
 440     CountFromBucket countFn;
 441     AvgFromBucket avgFn;
 442     return buckets_.getPercentileEstimate(pct, countFn, avgFn);
 443   }
 444
 445   /*
 446    * Get a human-readable string describing the histogram contents
 447    */
 448   std::string debugString() const;
 449
 450   /*
 451    * Write the histogram contents in tab-separated values (TSV) format.
 452    * Format is "min max count sum".
 453    */
 454   void toTSV(std::ostream& out, bool skipEmptyBuckets = true) const;
 455
 456   struct CountFromBucket {
 457     uint64_t operator()(const Bucket& bucket) const {
 458       return bucket.count;
 459     }
 460   };
 461   struct AvgFromBucket {
 462     ValueType operator()(const Bucket& bucket) const {
 463       if (bucket.count == 0) {
 464         return ValueType(0);
 465       }
 466       // Cast bucket.count to a signed integer type.  This ensures that we
 467       // perform division properly here: If bucket.sum is a signed integer
 468       // type but we divide by an unsigned number, unsigned division will be
 469       // performed and bucket.sum will be converted to unsigned first.
 470       // If bucket.sum is unsigned, the code will still do unsigned division
 471       // correctly.
 472       //
 473       // The only downside is if bucket.count is large enough to be negative
 474       // when treated as signed.  That should be extremely unlikely, though.
 475       return bucket.sum / static_cast<int64_t>(bucket.count);
 476     }
 477   };
 478
 479  private:
 480   detail::HistogramBuckets<ValueType, Bucket> buckets_;
 481 };
 482
 483 } // folly