folly/stats/Histogram.h

   1 /*
   2  * Copyright 2013-present 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/stats/detail/Bucket.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(
  57       ValueType bucketSize,
  58       ValueType min,
  59       ValueType max,
  60       const BucketType& defaultBucket);
  61
  62   /* Returns the bucket size of each bucket in the histogram. */
  63   ValueType getBucketSize() const {
  64     return bucketSize_;
  65   }
  66
  67   /* Returns the min value at which bucketing begins. */
  68   ValueType getMin() const {
  69     return min_;
  70   }
  71
  72   /* Returns the max value at which bucketing ends. */
  73   ValueType getMax() const {
  74     return max_;
  75   }
  76
  77   /*
  78    * Returns the number of buckets.
  79    *
  80    * This includes the total number of buckets for the [min, max) range,
  81    * plus 2 extra buckets, one for handling values less than min, and one for
  82    * values greater than max.
  83    */
  84   size_t getNumBuckets() const {
  85     return buckets_.size();
  86   }
  87
  88   /* Returns the bucket index into which the given value would fall. */
  89   size_t getBucketIdx(ValueType value) const;
  90
  91   /* Returns the bucket for the specified value */
  92   BucketType& getByValue(ValueType value) {
  93     return buckets_[getBucketIdx(value)];
  94   }
  95
  96   /* Returns the bucket for the specified value */
  97   const BucketType& getByValue(ValueType value) const {
  98     return buckets_[getBucketIdx(value)];
  99   }
 100
 101   /*
 102    * Returns the bucket at the specified index.
 103    *
 104    * Note that index 0 is the bucket for all values less than the specified
 105    * minimum.  Index 1 is the first bucket in the specified bucket range.
 106    */
 107   BucketType& getByIndex(size_t idx) {
 108     return buckets_[idx];
 109   }
 110
 111   /* Returns the bucket at the specified index. */
 112   const BucketType& getByIndex(size_t idx) const {
 113     return buckets_[idx];
 114   }
 115
 116   /*
 117    * Returns the minimum threshold for the bucket at the given index.
 118    *
 119    * The bucket at the specified index will store values in the range
 120    * [bucketMin, bucketMin + bucketSize), or [bucketMin, max), if the overall
 121    * max is smaller than bucketMin + bucketSize.
 122    */
 123   ValueType getBucketMin(size_t idx) const {
 124     if (idx == 0) {
 125       return std::numeric_limits<ValueType>::min();
 126     }
 127     if (idx == buckets_.size() - 1) {
 128       return max_;
 129     }
 130
 131     return ValueType(min_ + ((idx - 1) * bucketSize_));
 132   }
 133
 134   /*
 135    * Returns the maximum threshold for the bucket at the given index.
 136    *
 137    * The bucket at the specified index will store values in the range
 138    * [bucketMin, bucketMin + bucketSize), or [bucketMin, max), if the overall
 139    * max is smaller than bucketMin + bucketSize.
 140    */
 141   ValueType getBucketMax(size_t idx) const {
 142     if (idx == buckets_.size() - 1) {
 143       return std::numeric_limits<ValueType>::max();
 144     }
 145
 146     return ValueType(min_ + (idx * bucketSize_));
 147   }
 148
 149   /**
 150    * Computes the total number of values stored across all buckets.
 151    *
 152    * Runs in O(numBuckets)
 153    *
 154    * @param countFn A function that takes a const BucketType&, and returns the
 155    *                number of values in that bucket
 156    * @return Returns the total number of values stored across all buckets
 157    */
 158   template <typename CountFn>
 159   uint64_t computeTotalCount(CountFn countFromBucket) const;
 160
 161   /**
 162    * Determine which bucket the specified percentile falls into.
 163    *
 164    * Looks for the bucket that contains the Nth percentile data point.
 165    *
 166    * @param pct     The desired percentile to find, as a value from 0.0 to 1.0.
 167    * @param countFn A function that takes a const BucketType&, and returns the
 168    *                number of values in that bucket.
 169    * @param lowPct  The lowest percentile stored in the selected bucket will be
 170    *                returned via this parameter.
 171    * @param highPct The highest percentile stored in the selected bucket will
 172    *                be returned via this parameter.
 173    *
 174    * @return Returns the index of the bucket that contains the Nth percentile
 175    *         data point.
 176    */
 177   template <typename CountFn>
 178   size_t getPercentileBucketIdx(
 179       double pct,
 180       CountFn countFromBucket,
 181       double* lowPct = nullptr,
 182       double* highPct = nullptr) const;
 183
 184   /**
 185    * Estimate the value at the specified percentile.
 186    *
 187    * @param pct     The desired percentile to find, as a value from 0.0 to 1.0.
 188    * @param countFn A function that takes a const BucketType&, and returns the
 189    *                number of values in that bucket.
 190    * @param avgFn   A function that takes a const BucketType&, and returns the
 191    *                average of all the values in that bucket.
 192    *
 193    * @return Returns an estimate for N, where N is the number where exactly pct
 194    *         percentage of the data points in the histogram are less than N.
 195    */
 196   template <typename CountFn, typename AvgFn>
 197   ValueType getPercentileEstimate(
 198       double pct,
 199       CountFn countFromBucket,
 200       AvgFn avgFromBucket) const;
 201
 202   /*
 203    * Iterator access to the buckets.
 204    *
 205    * Note that the first bucket is for all values less than min, and the last
 206    * bucket is for all values greater than max.  The buckets tracking values in
 207    * the [min, max) actually start at the second bucket.
 208    */
 209   typename std::vector<BucketType>::const_iterator begin() const {
 210     return buckets_.begin();
 211   }
 212   typename std::vector<BucketType>::iterator begin() {
 213     return buckets_.begin();
 214   }
 215   typename std::vector<BucketType>::const_iterator end() const {
 216     return buckets_.end();
 217   }
 218   typename std::vector<BucketType>::iterator end() {
 219     return buckets_.end();
 220   }
 221
 222  private:
 223   ValueType bucketSize_;
 224   ValueType min_;
 225   ValueType max_;
 226   std::vector<BucketType> buckets_;
 227 };
 228
 229 } // namespace detail
 230
 231 /*
 232  * A basic histogram class.
 233  *
 234  * Groups data points into equally-sized buckets, and stores the overall sum of
 235  * the data points in each bucket, as well as the number of data points in the
 236  * bucket.
 237  *
 238  * The caller must specify the minimum and maximum data points to expect ahead
 239  * of time, as well as the bucket width.
 240  */
 241 template <typename T>
 242 class Histogram {
 243  public:
 244   typedef T ValueType;
 245   typedef detail::Bucket<T> Bucket;
 246
 247   Histogram(ValueType bucketSize, ValueType min, ValueType max)
 248       : buckets_(bucketSize, min, max, Bucket()) {}
 249
 250   /* Add a data point to the histogram */
 251   void addValue(ValueType value) FOLLY_DISABLE_UNDEFINED_BEHAVIOR_SANITIZER(
 252       "signed-integer-overflow",
 253       "unsigned-integer-overflow") {
 254     Bucket& bucket = buckets_.getByValue(value);
 255     // NOTE: Overflow is handled elsewhere and tests check this
 256     // behavior (see HistogramTest.cpp TestOverflow* tests).
 257     // TODO: It would be nice to handle overflow here and redesign this class.
 258     bucket.sum += value;
 259     bucket.count += 1;
 260   }
 261
 262   /* Add multiple same data points to the histogram */
 263   void addRepeatedValue(ValueType value, uint64_t nSamples)
 264       FOLLY_DISABLE_UNDEFINED_BEHAVIOR_SANITIZER(
 265           "signed-integer-overflow",
 266           "unsigned-integer-overflow") {
 267     Bucket& bucket = buckets_.getByValue(value);
 268     // NOTE: Overflow is handled elsewhere and tests check this
 269     // behavior (see HistogramTest.cpp TestOverflow* tests).
 270     // TODO: It would be nice to handle overflow here and redesign this class.
 271     bucket.sum += value * nSamples;
 272     bucket.count += nSamples;
 273   }
 274
 275   /*
 276    * Remove a data point to the histogram
 277    *
 278    * Note that this method does not actually verify that this exact data point
 279    * had previously been added to the histogram; it merely subtracts the
 280    * requested value from the appropriate bucket's sum.
 281    */
 282   void removeValue(ValueType value) FOLLY_DISABLE_UNDEFINED_BEHAVIOR_SANITIZER(
 283       "signed-integer-overflow",
 284       "unsigned-integer-overflow") {
 285     Bucket& bucket = buckets_.getByValue(value);
 286     // NOTE: Overflow is handled elsewhere and tests check this
 287     // behavior (see HistogramTest.cpp TestOverflow* tests).
 288     // TODO: It would be nice to handle overflow here and redesign this class.
 289     if (bucket.count > 0) {
 290       bucket.sum -= value;
 291       bucket.count -= 1;
 292     } else {
 293       bucket.sum = ValueType();
 294       bucket.count = 0;
 295     }
 296   }
 297
 298   /* Remove multiple same data points from the histogram */
 299   void removeRepeatedValue(ValueType value, uint64_t nSamples) {
 300     Bucket& bucket = buckets_.getByValue(value);
 301     // TODO: It would be nice to handle overflow here.
 302     if (bucket.count >= nSamples) {
 303       bucket.sum -= value * nSamples;
 304       bucket.count -= nSamples;
 305     } else {
 306       bucket.sum = ValueType();
 307       bucket.count = 0;
 308     }
 309   }
 310
 311   /* Remove all data points from the histogram */
 312   void clear() {
 313     for (size_t i = 0; i < buckets_.getNumBuckets(); i++) {
 314       buckets_.getByIndex(i).clear();
 315     }
 316   }
 317
 318   /* Subtract another histogram data from the histogram */
 319   void subtract(const Histogram& hist) {
 320     // the two histogram bucket definitions must match to support
 321     // subtract.
 322     if (getBucketSize() != hist.getBucketSize() || getMin() != hist.getMin() ||
 323         getMax() != hist.getMax() || getNumBuckets() != hist.getNumBuckets()) {
 324       throw std::invalid_argument("Cannot subtract input histogram.");
 325     }
 326
 327     for (size_t i = 0; i < buckets_.getNumBuckets(); i++) {
 328       buckets_.getByIndex(i) -= hist.buckets_.getByIndex(i);
 329     }
 330   }
 331
 332   /* Merge two histogram data together */
 333   void merge(const Histogram& hist) {
 334     // the two histogram bucket definitions must match to support
 335     // a merge.
 336     if (getBucketSize() != hist.getBucketSize() || getMin() != hist.getMin() ||
 337         getMax() != hist.getMax() || 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() || getMin() != hist.getMin() ||
 350         getMax() != hist.getMax() || getNumBuckets() != hist.getNumBuckets()) {
 351       throw std::invalid_argument("Cannot copy from input histogram.");
 352     }
 353
 354     for (size_t i = 0; i < buckets_.getNumBuckets(); i++) {
 355       buckets_.getByIndex(i) = hist.buckets_.getByIndex(i);
 356     }
 357   }
 358
 359   /* Returns the bucket size of each bucket in the histogram. */
 360   ValueType getBucketSize() const {
 361     return buckets_.getBucketSize();
 362   }
 363   /* Returns the min value at which bucketing begins. */
 364   ValueType getMin() const {
 365     return buckets_.getMin();
 366   }
 367   /* Returns the max value at which bucketing ends. */
 368   ValueType getMax() const {
 369     return buckets_.getMax();
 370   }
 371   /* Returns the number of buckets */
 372   size_t getNumBuckets() const {
 373     return buckets_.getNumBuckets();
 374   }
 375
 376   /* Returns the specified bucket (for reading only!) */
 377   const Bucket& getBucketByIndex(size_t idx) const {
 378     return buckets_.getByIndex(idx);
 379   }
 380
 381   /*
 382    * Returns the minimum threshold for the bucket at the given index.
 383    *
 384    * The bucket at the specified index will store values in the range
 385    * [bucketMin, bucketMin + bucketSize), or [bucketMin, max), if the overall
 386    * max is smaller than bucketMin + bucketSize.
 387    */
 388   ValueType getBucketMin(size_t idx) const {
 389     return buckets_.getBucketMin(idx);
 390   }
 391
 392   /*
 393    * Returns the maximum threshold for the bucket at the given index.
 394    *
 395    * The bucket at the specified index will store values in the range
 396    * [bucketMin, bucketMin + bucketSize), or [bucketMin, max), if the overall
 397    * max is smaller than bucketMin + bucketSize.
 398    */
 399   ValueType getBucketMax(size_t idx) const {
 400     return buckets_.getBucketMax(idx);
 401   }
 402
 403   /**
 404    * Computes the total number of values stored across all buckets.
 405    *
 406    * Runs in O(numBuckets)
 407    */
 408   uint64_t computeTotalCount() const {
 409     CountFromBucket countFn;
 410     return buckets_.computeTotalCount(countFn);
 411   }
 412
 413   /*
 414    * Get the bucket that the specified percentile falls into
 415    *
 416    * The lowest and highest percentile data points in returned bucket will be
 417    * returned in the lowPct and highPct arguments, if they are not nullptr.
 418    */
 419   size_t getPercentileBucketIdx(
 420       double pct,
 421       double* lowPct = nullptr,
 422       double* highPct = nullptr) const {
 423     // We unfortunately can't use lambdas here yet;
 424     // Some users of this code are still built with gcc-4.4.
 425     CountFromBucket countFn;
 426     return buckets_.getPercentileBucketIdx(pct, countFn, lowPct, highPct);
 427   }
 428
 429   /**
 430    * Estimate the value at the specified percentile.
 431    *
 432    * @param pct     The desired percentile to find, as a value from 0.0 to 1.0.
 433    *
 434    * @return Returns an estimate for N, where N is the number where exactly pct
 435    *         percentage of the data points in the histogram are less than N.
 436    */
 437   ValueType getPercentileEstimate(double pct) const {
 438     CountFromBucket countFn;
 439     AvgFromBucket avgFn;
 440     return buckets_.getPercentileEstimate(pct, countFn, avgFn);
 441   }
 442
 443   /*
 444    * Get a human-readable string describing the histogram contents
 445    */
 446   std::string debugString() const;
 447
 448   /*
 449    * Write the histogram contents in tab-separated values (TSV) format.
 450    * Format is "min max count sum".
 451    */
 452   void toTSV(std::ostream& out, bool skipEmptyBuckets = true) const;
 453
 454   struct CountFromBucket {
 455     uint64_t operator()(const Bucket& bucket) const {
 456       return bucket.count;
 457     }
 458   };
 459   struct AvgFromBucket {
 460     ValueType operator()(const Bucket& bucket) const {
 461       if (bucket.count == 0) {
 462         return ValueType(0);
 463       }
 464       // Cast bucket.count to a signed integer type.  This ensures that we
 465       // perform division properly here: If bucket.sum is a signed integer
 466       // type but we divide by an unsigned number, unsigned division will be
 467       // performed and bucket.sum will be converted to unsigned first.
 468       // If bucket.sum is unsigned, the code will still do unsigned division
 469       // correctly.
 470       //
 471       // The only downside is if bucket.count is large enough to be negative
 472       // when treated as signed.  That should be extremely unlikely, though.
 473       return bucket.sum / static_cast<int64_t>(bucket.count);
 474     }
 475   };
 476
 477  private:
 478   detail::HistogramBuckets<ValueType, Bucket> buckets_;
 479 };
 480
 481 } // namespace folly
 482
 483 // MSVC 2017 Update 3/4 has an issue with explicitly instantiating templated
 484 // functions with default arguments inside templated classes when compiled
 485 // with /permissive- (the default for the CMake build), so we directly include
 486 // the -defs as if it were -inl, and don't provide the explicit instantiations.
 487 // https://developercommunity.visualstudio.com/content/problem/81223/incorrect-error-c5037-with-permissive.html
 488 #if defined(_MSC_VER) && _MSC_FULL_VER >= 191125506 && \
 489     _MSC_FULL_VER <= 191125547
 490 #define FOLLY_MSVC_USE_WORKAROUND_FOR_C5037 1
 491 #else
 492 #define FOLLY_MSVC_USE_WORKAROUND_FOR_C5037 0
 493 #endif
 494
 495 #if FOLLY_MSVC_USE_WORKAROUND_FOR_C5037
 496 #include <folly/stats/Histogram-defs.h>
 497 #endif