folly/Histogram.h

   1 /*
   2  * Copyright 2012 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 #ifndef FOLLY_HISTOGRAM_H_
  18 #define FOLLY_HISTOGRAM_H_
  19
  20 #include <cstddef>
  21 #include <cstdint>
  22 #include <limits>
  23 #include <string>
  24 #include <vector>
  25
  26 namespace folly {
  27
  28 namespace detail {
  29
  30 /*
  31  * A helper class to manage a set of histogram buckets.
  32  */
  33 template <typename T, typename BucketT>
  34 class HistogramBuckets {
  35  public:
  36   typedef T ValueType;
  37   typedef BucketT BucketType;
  38
  39   /*
  40    * Create a set of histogram buckets.
  41    *
  42    * One bucket will be created for each bucketSize interval of values within
  43    * the specified range.  Additionally, one bucket will be created to track
  44    * all values that fall below the specified minimum, and one bucket will be
  45    * created for all values above the specified maximum.
  46    *
  47    * If (max - min) is not a multiple of bucketSize, the last bucket will cover
  48    * a smaller range of values than the other buckets.
  49    *
  50    * (max - min) must be larger than or equal to bucketSize.
  51    */
  52   HistogramBuckets(ValueType bucketSize, ValueType min, ValueType max,
  53                    const BucketType& defaultBucket);
  54
  55   /* Returns the bucket size of each bucket in the histogram. */
  56   ValueType getBucketSize() const {
  57     return bucketSize_;
  58   }
  59
  60   /* Returns the min value at which bucketing begins. */
  61   ValueType getMin() const {
  62     return min_;
  63   }
  64
  65   /* Returns the max value at which bucketing ends. */
  66   ValueType getMax() const {
  67     return max_;
  68   }
  69
  70   /*
  71    * Returns the number of buckets.
  72    *
  73    * This includes the total number of buckets for the [min, max) range,
  74    * plus 2 extra buckets, one for handling values less than min, and one for
  75    * values greater than max.
  76    */
  77   unsigned int getNumBuckets() const {
  78     return buckets_.size();
  79   }
  80
  81   /* Returns the bucket index into which the given value would fall. */
  82   unsigned int getBucketIdx(ValueType value) const;
  83
  84   /* Returns the bucket for the specified value */
  85   BucketType& getByValue(ValueType value) {
  86     return buckets_[getBucketIdx(value)];
  87   }
  88
  89   /* Returns the bucket for the specified value */
  90   const BucketType& getByValue(ValueType value) const {
  91     return buckets_[getBucketIdx(value)];
  92   }
  93
  94   /*
  95    * Returns the bucket at the specified index.
  96    *
  97    * Note that index 0 is the bucket for all values less than the specified
  98    * minimum.  Index 1 is the first bucket in the specified bucket range.
  99    */
 100   BucketType& getByIndex(unsigned int idx) {
 101     return buckets_[idx];
 102   }
 103
 104   /* Returns the bucket at the specified index. */
 105   const BucketType& getByIndex(unsigned int idx) const {
 106     return buckets_[idx];
 107   }
 108
 109   /*
 110    * Returns the minimum threshold for the bucket at the given index.
 111    *
 112    * The bucket at the specified index will store values in the range
 113    * [bucketMin, bucketMin + bucketSize), or [bucketMin, max), if the overall
 114    * max is smaller than bucketMin + bucketSize.
 115    */
 116   ValueType getBucketMin(unsigned int idx) const {
 117     if (idx == 0) {
 118       return std::numeric_limits<ValueType>::min();
 119     }
 120     if (idx == buckets_.size() - 1) {
 121       return max_;
 122     }
 123
 124     return min_ + ((idx - 1) * bucketSize_);
 125   }
 126
 127   /*
 128    * Returns the maximum threshold for the bucket at the given index.
 129    *
 130    * The bucket at the specified index will store values in the range
 131    * [bucketMin, bucketMin + bucketSize), or [bucketMin, max), if the overall
 132    * max is smaller than bucketMin + bucketSize.
 133    */
 134   ValueType getBucketMax(unsigned int idx) const {
 135     if (idx == buckets_.size() - 1) {
 136       return std::numeric_limits<ValueType>::max();
 137     }
 138
 139     return min_ + (idx * bucketSize_);
 140   }
 141
 142   /**
 143    * Determine which bucket the specified percentile falls into.
 144    *
 145    * Looks for the bucket that contains the Nth percentile data point.
 146    *
 147    * @param pct     The desired percentile to find, as a value from 0.0 to 1.0.
 148    * @param countFn A function that takes a const BucketType&, and returns the
 149    *                number of values in that bucket.
 150    * @param lowPct  The lowest percentile stored in the selected bucket will be
 151    *                returned via this parameter.
 152    * @param highPct The highest percentile stored in the selected bucket will
 153    *                be returned via this parameter.
 154    *
 155    * @return Returns the index of the bucket that contains the Nth percentile
 156    *         data point.
 157    */
 158   template <typename CountFn>
 159   unsigned int getPercentileBucketIdx(double pct,
 160                                       CountFn countFromBucket,
 161                                       double* lowPct = NULL,
 162                                       double* highPct = NULL) const;
 163
 164   /**
 165    * Estimate the value at the specified percentile.
 166    *
 167    * @param pct     The desired percentile to find, as a value from 0.0 to 1.0.
 168    * @param countFn A function that takes a const BucketType&, and returns the
 169    *                number of values in that bucket.
 170    * @param avgFn   A function that takes a const BucketType&, and returns the
 171    *                average of all the values in that bucket.
 172    *
 173    * @return Returns an estimate for N, where N is the number where exactly pct
 174    *         percentage of the data points in the histogram are less than N.
 175    */
 176   template <typename CountFn, typename AvgFn>
 177   ValueType getPercentileEstimate(double pct,
 178                                   CountFn countFromBucket,
 179                                   AvgFn avgFromBucket) const;
 180
 181   /*
 182    * Iterator access to the buckets.
 183    *
 184    * Note that the first bucket is for all values less than min, and the last
 185    * bucket is for all values greater than max.  The buckets tracking values in
 186    * the [min, max) actually start at the second bucket.
 187    */
 188   typename std::vector<BucketType>::const_iterator begin() const {
 189     return buckets_.begin();
 190   }
 191   typename std::vector<BucketType>::iterator begin() {
 192     return buckets_.begin();
 193   }
 194   typename std::vector<BucketType>::const_iterator end() const {
 195     return buckets_.end();
 196   }
 197   typename std::vector<BucketType>::iterator end() {
 198     return buckets_.end();
 199   }
 200
 201  private:
 202   const ValueType bucketSize_;
 203   const ValueType min_;
 204   const ValueType max_;
 205   std::vector<BucketType> buckets_;
 206 };
 207
 208 } // detail
 209
 210
 211 /*
 212  * A basic histogram class.
 213  *
 214  * Groups data points into equally-sized buckets, and stores the overall sum of
 215  * the data points in each bucket, as well as the number of data points in the
 216  * bucket.
 217  *
 218  * The caller must specify the minimum and maximum data points to expect ahead
 219  * of time, as well as the bucket width.
 220  */
 221 template <typename T>
 222 class Histogram {
 223  public:
 224   typedef T ValueType;
 225
 226   struct Bucket {
 227     Bucket()
 228       : sum(0),
 229         count(0) {}
 230
 231     void clear() {
 232       sum = 0;
 233       count = 0;
 234     }
 235
 236     ValueType sum;
 237     uint64_t count;
 238   };
 239
 240   Histogram(ValueType bucketSize, ValueType min, ValueType max)
 241     : buckets_(bucketSize, min, max, Bucket()) {}
 242
 243   /* Add a data point to the histogram */
 244   void addValue(ValueType value) {
 245     Bucket& bucket = buckets_.getByValue(value);
 246     // TODO: It would be nice to handle overflow here.
 247     bucket.sum += value;
 248     bucket.count += 1;
 249   }
 250
 251   /*
 252    * Remove a data point to the histogram
 253    *
 254    * Note that this method does not actually verify that this exact data point
 255    * had previously been added to the histogram; it merely subtracts the
 256    * requested value from the appropriate bucket's sum.
 257    */
 258   void removeValue(ValueType value) {
 259     Bucket& bucket = buckets_.getByValue(value);
 260     // TODO: It would be nice to handle overflow here.
 261     bucket.sum -= value;
 262     bucket.count -= 1;
 263   }
 264
 265   /* Remove all data points from the histogram */
 266   void clear() {
 267     for (int i = 0; i < buckets_.getNumBuckets(); i++) {
 268       buckets_.getByIndex(i).clear();
 269     }
 270   }
 271
 272   /* Returns the bucket size of each bucket in the histogram. */
 273   ValueType getBucketSize() const {
 274     return buckets_.getBucketSize();
 275   }
 276   /* Returns the min value at which bucketing begins. */
 277   ValueType getMin() const {
 278     return buckets_.getMin();
 279   }
 280   /* Returns the max value at which bucketing ends. */
 281   ValueType getMax() const {
 282     return buckets_.getMax();
 283   }
 284   /* Returns the number of buckets */
 285   unsigned int getNumBuckets() const {
 286     return buckets_.getNumBuckets();
 287   }
 288
 289   /* Returns the specified bucket (for reading only!) */
 290   const Bucket& getBucketByIndex(int idx) const {
 291     return buckets_.getByIndex(idx);
 292   }
 293
 294   /*
 295    * Returns the minimum threshold for the bucket at the given index.
 296    *
 297    * The bucket at the specified index will store values in the range
 298    * [bucketMin, bucketMin + bucketSize), or [bucketMin, max), if the overall
 299    * max is smaller than bucketMin + bucketSize.
 300    */
 301   ValueType getBucketMin(unsigned int idx) const {
 302     return buckets_.getBucketMin(idx);
 303   }
 304
 305   /*
 306    * Returns the maximum threshold for the bucket at the given index.
 307    *
 308    * The bucket at the specified index will store values in the range
 309    * [bucketMin, bucketMin + bucketSize), or [bucketMin, max), if the overall
 310    * max is smaller than bucketMin + bucketSize.
 311    */
 312   ValueType getBucketMax(unsigned int idx) const {
 313     return buckets_.getBucketMax(idx);
 314   }
 315
 316   /*
 317    * Get the bucket that the specified percentile falls into
 318    *
 319    * The lowest and highest percentile data points in returned bucket will be
 320    * returned in the lowPct and highPct arguments, if they are non-NULL.
 321    */
 322   unsigned int getPercentileBucketIdx(double pct,
 323                                       double* lowPct = NULL,
 324                                       double* highPct = NULL) const {
 325     // We unfortunately can't use lambdas here yet;
 326     // Some users of this code are still built with gcc-4.4.
 327     CountFromBucket countFn;
 328     return buckets_.getPercentileBucketIdx(pct, countFn, lowPct, highPct);
 329   }
 330
 331   /**
 332    * Estimate the value at the specified percentile.
 333    *
 334    * @param pct     The desired percentile to find, as a value from 0.0 to 1.0.
 335    *
 336    * @return Returns an estimate for N, where N is the number where exactly pct
 337    *         percentage of the data points in the histogram are less than N.
 338    */
 339   ValueType getPercentileEstimate(double pct) const {
 340     CountFromBucket countFn;
 341     AvgFromBucket avgFn;
 342     return buckets_.getPercentileEstimate(pct, countFn, avgFn);
 343   }
 344
 345   /*
 346    * Get a human-readable string describing the histogram contents
 347    */
 348   std::string debugString() const;
 349
 350  private:
 351   struct CountFromBucket {
 352     uint64_t operator()(const Bucket& bucket) const {
 353       return bucket.count;
 354     }
 355   };
 356   struct AvgFromBucket {
 357     ValueType operator()(const Bucket& bucket) const {
 358       if (bucket.count == 0) {
 359         return ValueType(0);
 360       }
 361       // Cast bucket.count to a signed integer type.  This ensures that we
 362       // perform division properly here: If bucket.sum is a signed integer
 363       // type but we divide by an unsigned number, unsigned division will be
 364       // performed and bucket.sum will be converted to unsigned first.
 365       // If bucket.sum is unsigned, the code will still do unsigned division
 366       // correctly.
 367       //
 368       // The only downside is if bucket.count is large enough to be negative
 369       // when treated as signed.  That should be extremely unlikely, though.
 370       return bucket.sum / static_cast<int64_t>(bucket.count);
 371     }
 372   };
 373
 374   detail::HistogramBuckets<ValueType, Bucket> buckets_;
 375 };
 376
 377 } // folly
 378
 379 #include "folly/Histogram-inl.h"
 380
 381 #endif // FOLLY_HISTOGRAM_H_