folly::TDigest Class Reference

#include <TDigest.h>

Classes
class	Centroid

Public Member Functions
	TDigest (size_t maxSize=100)
	TDigest (std::vector< Centroid > centroids, double sum, double count, double max_val, double min_val, size_t maxSize=100)
TDigest	merge (presorted_t, Range< const double * > sortedValues) const
TDigest	merge (Range< const double * > unsortedValues) const
double	estimateQuantile (double q) const
double	mean () const
double	sum () const
double	count () const
double	min () const
double	max () const
bool	empty () const
const std::vector< Centroid > &	getCentroids () const
size_t	maxSize () const

Static Public Member Functions
static TDigest	merge (Range< const TDigest * > digests)

Private Attributes
std::vector< Centroid >	centroids_
size_t	maxSize_
double	sum_
double	count_
double	max_
double	min_

Detailed Description

Definition at line 50 of file TDigest.h.

Constructor & Destructor Documentation

folly::TDigest::TDigest ( size_t  maxSize = 100 )

inlineexplicit

Definition at line 81 of file TDigest.h.

References count(), estimateQuantile(), maxSize(), merge(), and sum().

Referenced by merge(), and TDigest().

      : maxSize_(maxSize), sum_(0.0), count_(0.0), max_(NAN), min_(NAN) {}

folly::TDigest::TDigest ( std::vector< Centroid >  centroids, double  sum, double  count, double  max_val, double  min_val, size_t  maxSize = 100  )

explicit

Definition at line 79 of file TDigest.cpp.

References centroids_, count_, max_, maxSize_, merge(), min_, folly::gen::move, sum_, and TDigest().

    : maxSize_(maxSize),
      sum_(sum),
      count_(count),
      max_(max_val),
      min_(min_val) {
  if (centroids.size() <= maxSize_) {
    centroids_ = std::move(centroids);
  } else {
    // Number of centroids is greater than maxSize, we need to compress them
    // When merging, resulting digest takes the maxSize of the first digest
    auto sz = centroids.size();
    std::array<TDigest, 2> digests{{
        TDigest(maxSize_),
        TDigest(std::move(centroids), sum_, count_, max_, min_, sz),
    }};
    *this = this->merge(digests);
  }
}

Member Function Documentation

double folly::TDigest::count ( ) const

inline

Definition at line 118 of file TDigest.h.

References count_.

Referenced by folly::detail::estimatesFromDigest(), merge(), TDigest(), and TEST().

                       {
    return count_;
  }

bool folly::TDigest::empty ( ) const

inline

Definition at line 130 of file TDigest.h.

References centroids_.

                     {
    return centroids_.empty();
  }

double folly::TDigest::estimateQuantile

(

double

q

)

const

Definition at line 312 of file TDigest.cpp.

References centroids_, folly::clamp(), count_, max(), max_, min(), min_, folly::pushmi::detail::t, and folly::value().

Referenced by estimateQuantile(), folly::detail::estimatesFromDigest(), TDigest(), TEST(), and TEST_P().

                                               {
  if (centroids_.empty()) {
    return 0.0;
  }
  double rank = q * count_;

  size_t pos;
  double t;
  if (q > 0.5) {
    if (q >= 1.0) {
      return max_;
    }
    pos = 0;
    t = count_;
    for (auto rit = centroids_.rbegin(); rit != centroids_.rend(); ++rit) {
      t -= rit->weight();
      if (rank >= t) {
        pos = std::distance(rit, centroids_.rend()) - 1;
        break;
      }
    }
  } else {
    if (q <= 0.0) {
      return min_;
    }
    pos = centroids_.size() - 1;
    t = 0;
    for (auto it = centroids_.begin(); it != centroids_.end(); ++it) {
      if (rank < t + it->weight()) {
        pos = std::distance(centroids_.begin(), it);
        break;
      }
      t += it->weight();
    }
  }

  double delta = 0;
  double min = min_;
  double max = max_;
  if (centroids_.size() > 1) {
    if (pos == 0) {
      delta = centroids_[pos + 1].mean() - centroids_[pos].mean();
      max = centroids_[pos + 1].mean();
    } else if (pos == centroids_.size() - 1) {
      delta = centroids_[pos].mean() - centroids_[pos - 1].mean();
      min = centroids_[pos - 1].mean();
    } else {
      delta = (centroids_[pos + 1].mean() - centroids_[pos - 1].mean()) / 2;
      min = centroids_[pos - 1].mean();
      max = centroids_[pos + 1].mean();
    }
  }
  auto value = centroids_[pos].mean() +
      ((rank - t) / centroids_[pos].weight() - 0.5) * delta;
  return clamp(value, min, max);
}

const std::vector<Centroid>& folly::TDigest::getCentroids ( ) const

inline

Definition at line 134 of file TDigest.h.

References centroids_.

Referenced by TEST().

                                                  {
    return centroids_;
  }

double folly::TDigest::max ( ) const

inline

Definition at line 126 of file TDigest.h.

References max_.

Referenced by estimateQuantile(), merge(), and TEST().

                     {
    return max_;
  }

size_t folly::TDigest::maxSize ( ) const

inline

Definition at line 138 of file TDigest.h.

References maxSize_.

Referenced by merge(), and TDigest().

                         {
    return maxSize_;
  }

double folly::TDigest::mean ( ) const

inline

Definition at line 110 of file TDigest.h.

References count_, and sum_.

Referenced by TEST().

                      {
    return count_ ? sum_ / count_ : 0;
  }

TDigest folly::TDigest::merge	(	presorted_t	,
		Range< const double * >	sortedValues
	)		const

Definition at line 126 of file TDigest.cpp.

References folly::TDigest::Centroid::add(), folly::Range< Iter >::begin(), centroids_, count_, folly::Range< Iter >::empty(), folly::Range< Iter >::end(), folly::k_to_q(), max, max_, maxSize_, folly::TDigest::Centroid::mean(), min, min_, folly::gen::move, cpp.ast::next(), folly::Range< Iter >::size(), sum_, and folly::TDigest::Centroid::weight().

Referenced by estimateQuantile(), folly::SlidingWindowQuantileEstimator< ClockT >::estimateQuantiles(), merge(), merge(), mergeDigests(), TDigest(), TEST(), and TEST_P().

                                                                           {
  if (sortedValues.empty()) {
    return *this;
  }

  TDigest result(maxSize_);

  result.count_ = count_ + sortedValues.size();

  double maybeMin = *sortedValues.begin();
  double maybeMax = *(sortedValues.end() - 1);
  if (count_ > 0) {
    // We know that min_ and max_ are numbers
    result.min_ = std::min(min_, maybeMin);
    result.max_ = std::max(max_, maybeMax);
  } else {
    // We know that min_ and max_ are NaN.
    result.min_ = maybeMin;
    result.max_ = maybeMax;
  }

  std::vector<Centroid> compressed;
  compressed.reserve(maxSize_);

  double k_limit = 1;
  double q_limit_times_count = k_to_q(k_limit++, maxSize_) * result.count_;

  auto it_centroids = centroids_.begin();
  auto it_sortedValues = sortedValues.begin();

  Centroid cur;
  if (it_centroids != centroids_.end() &&
      it_centroids->mean() < *it_sortedValues) {
    cur = *it_centroids++;
  } else {
    cur = Centroid(*it_sortedValues++, 1.0);
  }

  double weightSoFar = cur.weight();

  // Keep track of sums along the way to reduce expensive floating points
  double sumsToMerge = 0;
  double weightsToMerge = 0;

  while (it_centroids != centroids_.end() ||
         it_sortedValues != sortedValues.end()) {
    Centroid next;

    if (it_centroids != centroids_.end() &&
        (it_sortedValues == sortedValues.end() ||
         it_centroids->mean() < *it_sortedValues)) {
      next = *it_centroids++;
    } else {
      next = Centroid(*it_sortedValues++, 1.0);
    }

    double nextSum = next.mean() * next.weight();
    weightSoFar += next.weight();

    if (weightSoFar <= q_limit_times_count) {
      sumsToMerge += nextSum;
      weightsToMerge += next.weight();
    } else {
      result.sum_ += cur.add(sumsToMerge, weightsToMerge);
      sumsToMerge = 0;
      weightsToMerge = 0;
      compressed.push_back(cur);
      q_limit_times_count = k_to_q(k_limit++, maxSize_) * result.count_;
      cur = next;
    }
  }
  result.sum_ += cur.add(sumsToMerge, weightsToMerge);
  compressed.push_back(cur);
  compressed.shrink_to_fit();

  // Deal with floating point precision
  std::sort(compressed.begin(), compressed.end());

  result.centroids_ = std::move(compressed);
  return result;
}

TDigest folly::TDigest::merge

(

Range< const double * >

unsortedValues

)

const

Definition at line 109 of file TDigest.cpp.

References folly::Range< Iter >::begin(), folly::copy(), folly::detail::double_radix_sort(), folly::Range< Iter >::end(), merge(), folly::presorted, folly::Range< Iter >::size(), and uint64_t.

                                                                {
  auto n = unsortedValues.size();

  // We require 256 buckets per byte level, plus one count array we can reuse.
  std::unique_ptr<uint64_t[]> buckets{new uint64_t[256 * 9]};
  // Allocate input and tmp array
  std::unique_ptr<double[]> tmp{new double[n * 2]};
  auto out = tmp.get() + n;
  auto in = tmp.get();
  std::copy(unsortedValues.begin(), unsortedValues.end(), in);

  detail::double_radix_sort(n, buckets.get(), in, out);
  DCHECK(std::is_sorted(in, in + n));

  return merge(presorted, Range<const double*>(in, in + n));
}

TDigest folly::TDigest::merge ( Range< const TDigest * >  digests )

static

Definition at line 208 of file TDigest.cpp.

References folly::TDigest::Centroid::add(), folly::Range< Iter >::begin(), centroids_, count(), count_, folly::Range< Iter >::end(), folly::gen::first, i, folly::k_to_q(), max, max(), max_, maxSize(), min, min(), min_, folly::gen::move, folly::Range< Iter >::size(), sum_, TDigest(), and folly::TDigest::Centroid::weight().

                                                    {
  size_t nCentroids = 0;
  for (auto it = digests.begin(); it != digests.end(); it++) {
    nCentroids += it->centroids_.size();
  }

  if (nCentroids == 0) {
    return TDigest();
  }

  std::vector<Centroid> centroids;
  centroids.reserve(nCentroids);

  std::vector<std::vector<Centroid>::iterator> starts;
  starts.reserve(digests.size());

  double count = 0;

  // We can safely use these limits to avoid isnan checks below because we know
  // nCentroids > 0, so at least one TDigest has a min and max.
  double min = std::numeric_limits<double>::infinity();
  double max = -std::numeric_limits<double>::infinity();

  for (auto it = digests.begin(); it != digests.end(); it++) {
    starts.push_back(centroids.end());
    double curCount = it->count();
    if (curCount > 0) {
      DCHECK(!std::isnan(it->min_));
      DCHECK(!std::isnan(it->max_));
      min = std::min(min, it->min_);
      max = std::max(max, it->max_);
      count += curCount;
      for (const auto& centroid : it->centroids_) {
        centroids.push_back(centroid);
      }
    }
  }

  for (size_t digestsPerBlock = 1; digestsPerBlock < starts.size();
       digestsPerBlock *= 2) {
    // Each sorted block is digestPerBlock digests big. For each step, try to
    // merge two blocks together.
    for (size_t i = 0; i < starts.size(); i += (digestsPerBlock * 2)) {
      // It is possible that this block is incomplete (less than digestsPerBlock
      // big). In that case, the rest of the block is sorted and leave it alone
      if (i + digestsPerBlock < starts.size()) {
        auto first = starts[i];
        auto middle = starts[i + digestsPerBlock];

        // It is possible that the next block is incomplete (less than
        // digestsPerBlock big). In that case, merge to end. Otherwise, merge to
        // the end of that block.
        std::vector<Centroid>::iterator last =
            (i + (digestsPerBlock * 2) < starts.size())
            ? *(starts.begin() + i + 2 * digestsPerBlock)
            : centroids.end();
        std::inplace_merge(first, middle, last);
      }
    }
  }

  DCHECK(std::is_sorted(centroids.begin(), centroids.end()));

  size_t maxSize = digests.begin()->maxSize_;
  TDigest result(maxSize);

  std::vector<Centroid> compressed;
  compressed.reserve(maxSize);

  double k_limit = 1;
  double q_limit_times_count = k_to_q(k_limit, maxSize) * count;

  Centroid cur = centroids.front();
  double weightSoFar = cur.weight();
  double sumsToMerge = 0;
  double weightsToMerge = 0;
  for (auto it = centroids.begin() + 1; it != centroids.end(); ++it) {
    weightSoFar += it->weight();
    if (weightSoFar <= q_limit_times_count) {
      sumsToMerge += it->mean() * it->weight();
      weightsToMerge += it->weight();
    } else {
      result.sum_ += cur.add(sumsToMerge, weightsToMerge);
      sumsToMerge = 0;
      weightsToMerge = 0;
      compressed.push_back(cur);
      q_limit_times_count = k_to_q(k_limit++, maxSize) * count;
      cur = *it;
    }
  }
  result.sum_ += cur.add(sumsToMerge, weightsToMerge);
  compressed.push_back(cur);
  compressed.shrink_to_fit();

  // Deal with floating point precision
  std::sort(compressed.begin(), compressed.end());

  result.count_ = count;
  result.min_ = min;
  result.max_ = max;
  result.centroids_ = std::move(compressed);
  return result;
}

double folly::TDigest::min ( ) const

inline

Definition at line 122 of file TDigest.h.

References min_.

Referenced by estimateQuantile(), merge(), and TEST().

                     {
    return min_;
  }

double folly::TDigest::sum ( ) const

inline

Definition at line 114 of file TDigest.h.

References sum_.

Referenced by folly::TDigest::Centroid::add(), folly::detail::estimatesFromDigest(), TDigest(), TEST(), and folly::TDigest::Centroid::weight().

                     {
    return sum_;
  }

Member Data Documentation

std::vector<Centroid> folly::TDigest::centroids_

private

Definition at line 143 of file TDigest.h.

Referenced by empty(), estimateQuantile(), getCentroids(), merge(), and TDigest().

double folly::TDigest::count_

private

Definition at line 146 of file TDigest.h.

Referenced by count(), estimateQuantile(), mean(), merge(), and TDigest().

double folly::TDigest::max_

private

Definition at line 147 of file TDigest.h.

Referenced by estimateQuantile(), max(), merge(), and TDigest().

size_t folly::TDigest::maxSize_

private

Definition at line 144 of file TDigest.h.

Referenced by maxSize(), merge(), and TDigest().

double folly::TDigest::min_

private

Definition at line 148 of file TDigest.h.

Referenced by estimateQuantile(), merge(), min(), and TDigest().

double folly::TDigest::sum_

private

Definition at line 145 of file TDigest.h.

Referenced by mean(), merge(), sum(), and TDigest().

---

The documentation for this class was generated from the following files:

• proxygen/folly/folly/stats/TDigest.h
• proxygen/folly/folly/stats/TDigest.cpp