proxygen: folly::detail::HistogramBuckets< T, BucketT

#include <Histogram.h>

Public Types
typedef T	ValueType

typedef BucketT	BucketType

Public Member Functions
	HistogramBuckets (ValueType bucketSize, ValueType min, ValueType max, const BucketType &defaultBucket)

ValueType	getBucketSize () const

ValueType	getMin () const

ValueType	getMax () const

size_t	getNumBuckets () const

size_t	getBucketIdx (ValueType value) const

BucketType &	getByValue (ValueType value)

const BucketType &	getByValue (ValueType value) const

BucketType &	getByIndex (size_t idx)

const BucketType &	getByIndex (size_t idx) const

ValueType	getBucketMin (size_t idx) const

ValueType	getBucketMax (size_t idx) const

template<typename CountFn >
uint64_t	computeTotalCount (CountFn countFromBucket) const

template<typename CountFn >
size_t	getPercentileBucketIdx (double pct, CountFn countFromBucket, double lowPct=nullptr, double highPct=nullptr) const

template<typename CountFn , typename AvgFn >
ValueType	getPercentileEstimate (double pct, CountFn countFromBucket, AvgFn avgFromBucket) const

std::vector< BucketType >::const_iterator	begin () const

std::vector< BucketType >::iterator	begin ()

std::vector< BucketType >::const_iterator	end () const

std::vector< BucketType >::iterator	end ()

template<typename CountFn , typename AvgFn >
T	getPercentileEstimate (double pct, CountFn countFromBucket, AvgFn avgFromBucket) const

Private Attributes
ValueType	bucketSize_

ValueType	min_

ValueType	max_

std::vector< BucketType >	buckets_

Detailed Description

template<typename T, typename BucketT>
class folly::detail::HistogramBuckets< T, BucketT >

Definition at line 39 of file Histogram.h.

Member Typedef Documentation

template<typename T, typename BucketT>

typedef BucketT folly::detail::HistogramBuckets< T, BucketT >::BucketType

Definition at line 42 of file Histogram.h.

template<typename T, typename BucketT>

typedef T folly::detail::HistogramBuckets< T, BucketT >::ValueType

Definition at line 41 of file Histogram.h.

Constructor & Destructor Documentation

template<typename T , typename BucketT >

folly::detail::HistogramBuckets< T, BucketT >::HistogramBuckets	(	ValueType	bucketSize,
		ValueType	min,
		ValueType	max,
		const BucketType &	defaultBucket
	)

Definition at line 29 of file Histogram-defs.h.

References folly::detail::HistogramBuckets< T, BucketT >::buckets_, folly::detail::HistogramBuckets< T, BucketT >::bucketSize_, int64_t, folly::detail::HistogramBuckets< T, BucketT >::max_, and folly::detail::HistogramBuckets< T, BucketT >::min_.

     : bucketSize_(bucketSize), min_(min), max_(max) {
   CHECK_GT(bucketSize_, ValueType(0));
   CHECK_LT(min_, max_);
 
   // Deliberately make this a signed type, because we're about
   // to compare it against max-min, which is nominally signed, too.
   int64_t numBuckets = int64_t((max - min) / bucketSize);
   // Round up if the bucket size does not fit evenly
   if (numBuckets * bucketSize < max - min) {
     ++numBuckets;
   }
   // Add 2 for the extra 'below min' and 'above max' buckets
   numBuckets += 2;
   buckets_.assign(size_t(numBuckets), defaultBucket);
 }

Member Function Documentation

template<typename T, typename BucketT>

std::vector<BucketType>::const_iterator folly::detail::HistogramBuckets< T, BucketT >::begin ( ) const

inline

Definition at line 210 of file Histogram.h.

                                                              {
     return buckets_.begin();
   }

template<typename T, typename BucketT>

std::vector<BucketType>::iterator folly::detail::HistogramBuckets< T, BucketT >::begin ( )

inline

Definition at line 213 of file Histogram.h.

                                                  {
     return buckets_.begin();
   }

template<typename T , typename BucketType >

template<typename CountFn >

template uint64_t folly::detail::HistogramBuckets< T, BucketT >::computeTotalCount< Histogram< int64_t >::CountFromBucket > ( CountFn countFromBucket ) const

Computes the total number of values stored across all buckets.

Runs in O(numBuckets)

Parameters

countFn A function that takes a const BucketType&, and returns the number of values in that bucket

Returns: Returns the total number of values stored across all buckets

Definition at line 64 of file Histogram-defs.h.

References folly::detail::HistogramBuckets< T, BucketT >::buckets_, count, and uint64_t.

Referenced by folly::detail::HistogramBuckets< ValueType, ContainerType >::getBucketMax().

                                    {
   uint64_t count = 0;
   for (size_t n = 0; n < buckets_.size(); ++n) {
     count += countFromBucket(const_cast<const BucketType&>(buckets_[n]));
   }
   return count;
 }

template<typename T, typename BucketT>

std::vector<BucketType>::const_iterator folly::detail::HistogramBuckets< T, BucketT >::end ( ) const

inline

Definition at line 216 of file Histogram.h.

                                                            {
     return buckets_.end();
   }

template<typename T, typename BucketT>

std::vector<BucketType>::iterator folly::detail::HistogramBuckets< T, BucketT >::end ( )

inline

Definition at line 219 of file Histogram.h.

                                                {
     return buckets_.end();
   }

template<typename T , typename BucketType >

size_t folly::detail::HistogramBuckets< T, BucketType >::getBucketIdx ( ValueType value ) const

Definition at line 51 of file Histogram-defs.h.

References folly::detail::HistogramBuckets< T, BucketT >::buckets_, folly::detail::HistogramBuckets< T, BucketT >::bucketSize_, folly::detail::HistogramBuckets< T, BucketT >::max_, and folly::detail::HistogramBuckets< T, BucketT >::min_.

Referenced by folly::detail::HistogramBuckets< ValueType, ContainerType >::getByValue(), and folly::detail::HistogramBuckets< ValueType, ContainerType >::getNumBuckets().

                                                                           {
   if (value < min_) {
     return 0;
   } else if (value >= max_) {
     return buckets_.size() - 1;
   } else {
     // the 1 is the below_min bucket
     return size_t(((value - min_) / bucketSize_) + 1);
   }
 }

template<typename T, typename BucketT>

ValueType folly::detail::HistogramBuckets< T, BucketT >::getBucketMax ( size_t idx ) const

inline

Definition at line 142 of file Histogram.h.

Referenced by folly::detail::HistogramBuckets< T, BucketT >::getPercentileEstimate(), and folly::Histogram< T >::toTSV().

                                            {
     if (idx == buckets_.size() - 1) {
       return std::numeric_limits<ValueType>::max();
     }
 
     return ValueType(min_ + (idx * bucketSize_));
   }

template<typename T, typename BucketT>

ValueType folly::detail::HistogramBuckets< T, BucketT >::getBucketMin ( size_t idx ) const

inline

Definition at line 124 of file Histogram.h.

Referenced by folly::TimeseriesHistogram< T, CT, C >::getBucketMin(), folly::detail::HistogramBuckets< T, BucketT >::getPercentileEstimate(), folly::TimeseriesHistogram< T, CT, C >::getString(), and folly::Histogram< T >::toTSV().

                                            {
     if (idx == 0) {
       return std::numeric_limits<ValueType>::min();
     }
     if (idx == buckets_.size() - 1) {
       return max_;
     }
 
     return ValueType(min_ + ((idx - 1) * bucketSize_));
   }

template<typename T, typename BucketT>

ValueType folly::detail::HistogramBuckets< T, BucketT >::getBucketSize ( ) const

inline

Definition at line 64 of file Histogram.h.

Referenced by folly::Histogram< T >::copy(), folly::TimeseriesHistogram< T, CT, C >::getBucketSize(), folly::Histogram< T >::merge(), and folly::Histogram< T >::subtract().

                                   {
     return bucketSize_;
   }

template<typename T, typename BucketT>

BucketType& folly::detail::HistogramBuckets< T, BucketT >::getByIndex ( size_t idx )

inline

Definition at line 108 of file Histogram.h.

                                      {
     return buckets_[idx];
   }

template<typename T, typename BucketT>

const BucketType& folly::detail::HistogramBuckets< T, BucketT >::getByIndex ( size_t idx ) const

inline

Definition at line 113 of file Histogram.h.

                                                  {
     return buckets_[idx];
   }

template<typename T, typename BucketT>

BucketType& folly::detail::HistogramBuckets< T, BucketT >::getByValue ( ValueType value )

inline

Definition at line 93 of file Histogram.h.

Referenced by folly::TimeseriesHistogram< T, CT, C >::addValue().

                                           {
     return buckets_[getBucketIdx(value)];
   }

template<typename T, typename BucketT>

const BucketType& folly::detail::HistogramBuckets< T, BucketT >::getByValue ( ValueType value ) const

inline

Definition at line 98 of file Histogram.h.

                                                       {
     return buckets_[getBucketIdx(value)];
   }

template<typename T, typename BucketT>

ValueType folly::detail::HistogramBuckets< T, BucketT >::getMax ( ) const

inline

Definition at line 74 of file Histogram.h.

Referenced by folly::Histogram< T >::copy(), folly::TimeseriesHistogram< T, CT, C >::getMax(), folly::Histogram< T >::merge(), and folly::Histogram< T >::subtract().

                            {
     return max_;
   }

template<typename T, typename BucketT>

ValueType folly::detail::HistogramBuckets< T, BucketT >::getMin ( ) const

inline

Definition at line 69 of file Histogram.h.

Referenced by folly::Histogram< T >::copy(), folly::TimeseriesHistogram< T, CT, C >::getMin(), folly::Histogram< T >::merge(), and folly::Histogram< T >::subtract().

                            {
     return min_;
   }

template<typename T, typename BucketT>

size_t folly::detail::HistogramBuckets< T, BucketT >::getNumBuckets ( ) const

inline

Definition at line 85 of file Histogram.h.

                                {
     return buckets_.size();
   }

template<typename T , typename BucketType >

template<typename CountFn >

template size_t folly::detail::HistogramBuckets< T, BucketT >::getPercentileBucketIdx< Histogram< int64_t >::CountFromBucket >	(	double	pct,
		CountFn	countFromBucket,
		double *	lowPct = `nullptr`,
		double *	highPct = `nullptr`
	)		const

Determine which bucket the specified percentile falls into.

Looks for the bucket that contains the Nth percentile data point.

Parameters

pct	The desired percentile to find, as a value from 0.0 to 1.0.
countFn	A function that takes a const BucketType&, and returns the number of values in that bucket.
lowPct	The lowest percentile stored in the selected bucket will be returned via this parameter.
highPct	The highest percentile stored in the selected bucket will be returned via this parameter.

Returns: Returns the index of the bucket that contains the Nth percentile data point.

Definition at line 75 of file Histogram-defs.h.

References folly::detail::HistogramBuckets< T, BucketT >::buckets_, and uint64_t.

Referenced by folly::detail::HistogramBuckets< ValueType, ContainerType >::getBucketMax(), folly::TimeseriesHistogram< T, CT, C >::getPercentileBucketIdx(), and folly::detail::HistogramBuckets< T, BucketT >::getPercentileEstimate().

                            {
   CHECK_GE(pct, 0.0);
   CHECK_LE(pct, 1.0);
 
   auto numBuckets = buckets_.size();
 
   // Compute the counts in each bucket
   std::vector<uint64_t> counts(numBuckets);
   uint64_t totalCount = 0;
   for (size_t n = 0; n < numBuckets; ++n) {
     uint64_t bucketCount =
         countFromBucket(const_cast<const BucketType&>(buckets_[n]));
     counts[n] = bucketCount;
     totalCount += bucketCount;
   }
 
   // If there are no elements, just return the lowest bucket.
   // Note that we return bucket 1, which is the first bucket in the
   // histogram range; bucket 0 is for all values below min_.
   if (totalCount == 0) {
     // Set lowPct and highPct both to 0.
     // getPercentileEstimate() will recognize this to mean that the histogram
     // is empty.
     if (lowPct) {
       *lowPct = 0.0;
     }
     if (highPct) {
       *highPct = 0.0;
     }
     return 1;
   }
 
   // Loop through all the buckets, keeping track of each bucket's
   // percentile range: [0,10], [10,17], [17,45], etc.  When we find a range
   // that includes our desired percentile, we return that bucket index.
   double prevPct = 0.0;
   double curPct = 0.0;
   uint64_t curCount = 0;
   size_t idx;
   for (idx = 0; idx < numBuckets; ++idx) {
     if (counts[idx] == 0) {
       // skip empty buckets
       continue;
     }
 
     prevPct = curPct;
     curCount += counts[idx];
     curPct = static_cast<double>(curCount) / totalCount;
     if (pct <= curPct) {
       // This is the desired bucket
       break;
     }
   }
 
   if (lowPct) {
     *lowPct = prevPct;
   }
   if (highPct) {
     *highPct = curPct;
   }
   return idx;
 }

template<typename T, typename BucketT>

template<typename CountFn , typename AvgFn >

T folly::detail::HistogramBuckets< T, BucketT >::getPercentileEstimate	(	double	pct,
		CountFn	countFromBucket,
		AvgFn	avgFromBucket
	)		const

Definition at line 144 of file Histogram-defs.h.

References folly::detail::HistogramBuckets< T, BucketT >::buckets_, folly::detail::HistogramBuckets< T, BucketT >::getBucketMax(), folly::detail::HistogramBuckets< T, BucketT >::getBucketMin(), folly::detail::HistogramBuckets< T, BucketT >::getPercentileBucketIdx(), max, folly::detail::HistogramBuckets< T, BucketT >::max_, min, folly::detail::HistogramBuckets< T, BucketT >::min_, and folly::T.

                                {
   // Find the bucket where this percentile falls
   double lowPct;
   double highPct;
   size_t bucketIdx =
       getPercentileBucketIdx(pct, countFromBucket, &lowPct, &highPct);
   if (lowPct == 0.0 && highPct == 0.0) {
     // Invalid range -- the buckets must all be empty
     // Return the default value for ValueType.
     return ValueType();
   }
   if (lowPct == highPct) {
     // Unlikely to have exact equality,
     // but just return the bucket average in this case.
     // We handle this here to avoid division by 0 below.
     return avgFromBucket(buckets_[bucketIdx]);
   }
 
   CHECK_GE(pct, lowPct);
   CHECK_LE(pct, highPct);
   CHECK_LT(lowPct, highPct);
 
   // Compute information about this bucket
   ValueType avg = avgFromBucket(buckets_[bucketIdx]);
   ValueType low;
   ValueType high;
   if (bucketIdx == 0) {
     if (avg > min_) {
       // This normally shouldn't happen.  This bucket is only supposed to track
       // values less than min_.  Most likely this means that integer overflow
       // occurred, and the code in avgFromBucket() returned a huge value
       // instead of a small one.  Just return the minimum possible value for
       // now.
       //
       // (Note that if the counter keeps being decremented, eventually it will
       // wrap and become small enough that we won't detect this any more, and
       // we will return bogus information.)
       LOG(ERROR) << "invalid average value in histogram minimum bucket: " << avg
                  << " > " << min_ << ": possible integer overflow?";
       return getBucketMin(bucketIdx);
     }
     // For the below-min bucket, just assume the lowest value ever seen is
     // twice as far away from min_ as avg.
     high = min_;
     low = high - (2 * (high - avg));
     // Adjust low in case it wrapped
     if (low > avg) {
       low = std::numeric_limits<ValueType>::min();
     }
   } else if (bucketIdx == buckets_.size() - 1) {
     if (avg < max_) {
       // Most likely this means integer overflow occurred.  See the comments
       // above in the minimum case.
       LOG(ERROR) << "invalid average value in histogram maximum bucket: " << avg
                  << " < " << max_ << ": possible integer overflow?";
       return getBucketMax(bucketIdx);
     }
     // Similarly for the above-max bucket, assume the highest value ever seen
     // is twice as far away from max_ as avg.
     low = max_;
     high = low + (2 * (avg - low));
     // Adjust high in case it wrapped
     if (high < avg) {
       high = std::numeric_limits<ValueType>::max();
     }
   } else {
     low = getBucketMin(bucketIdx);
     high = getBucketMax(bucketIdx);
     if (avg < low || avg > high) {
       // Most likely this means an integer overflow occurred.
       // See the comments above.  Return the midpoint between low and high
       // as a best guess, since avg is meaningless.
       LOG(ERROR) << "invalid average value in histogram bucket: " << avg
                  << " not in range [" << low << ", " << high
                  << "]: possible integer overflow?";
       return (low + high) / 2;
     }
   }
 
   // Since we know the average value in this bucket, we can do slightly better
   // than just assuming the data points in this bucket are uniformly
   // distributed between low and high.
   //
   // Assume that the median value in this bucket is the same as the average
   // value.
   double medianPct = (lowPct + highPct) / 2.0;
   if (pct < medianPct) {
     // Assume that the data points lower than the median of this bucket
     // are uniformly distributed between low and avg
     double pctThroughSection = (pct - lowPct) / (medianPct - lowPct);
     return T(low + ((avg - low) * pctThroughSection));
   } else {
     // Assume that the data points greater than the median of this bucket
     // are uniformly distributed between avg and high
     double pctThroughSection = (pct - medianPct) / (highPct - medianPct);
     return T(avg + ((high - avg) * pctThroughSection));
   }
 }

template<typename T, typename BucketT>

template<typename CountFn , typename AvgFn >

ValueType folly::detail::HistogramBuckets< T, BucketT >::getPercentileEstimate	(	double	pct,
		CountFn	countFromBucket,
		AvgFn	avgFromBucket
	)		const

Estimate the value at the specified percentile.

Parameters

pct	The desired percentile to find, as a value from 0.0 to 1.0.
countFn	A function that takes a const BucketType&, and returns the number of values in that bucket.
avgFn	A function that takes a const BucketType&, and returns the average of all the values in that bucket.