quantile::detail::TDigest< RealType, IndexType > Class Template Reference

#include <quantile.h>

Collaboration diagram for quantile::detail::TDigest< RealType, IndexType >:

Public Types
using	Memory = CentroidsMemory< RealType, IndexType >

Public Member Functions
	TDigest ()=default
DEVICE	TDigest (Memory &mem)
DEVICE	TDigest (SimpleAllocator *simple_allocator, IndexType buf_allocate, IndexType centroids_allocate)
DEVICE Centroids< RealType, IndexType > &	centroids ()
DEVICE void	add (RealType value)
DEVICE void	allocate ()
DEVICE void	mergeBuffer ()
DEVICE void	mergeSorted (RealType *sums, IndexType *counts, IndexType size)
DEVICE void	mergeTDigest (TDigest &t_digest)
DEVICE RealType	quantile (RealType const q)
DEVICE RealType	quantile (IndexType *buf, RealType const q)
DEVICE void	setBuffer (Memory &mem)
DEVICE void	setCentroids (Memory &mem)
DEVICE void	setCentroids (VectorView< RealType > const sums, VectorView< IndexType > const counts)
DEVICE IndexType	totalWeight () const

Private Member Functions
DEVICE RealType	max () const
DEVICE RealType	min () const
DEVICE IndexType	maxCardinality (IndexType const sum, IndexType const total_weight)
DEVICE void	mergeCentroids (Centroids< RealType, IndexType > &)
DEVICE RealType	firstCentroid (RealType const x)
DEVICE RealType	interiorCentroid (RealType const x, IndexType const idx1, IndexType const prefix_sum)
DEVICE RealType	lastCentroid (RealType const x, IndexType const N)
DEVICE RealType	oneCentroid (RealType const x)
DEVICE RealType	slope (IndexType const idx1, IndexType const idx2)

Private Attributes
Centroids< RealType, IndexType >	buf_
Centroids< RealType, IndexType >	centroids_
bool	forward_ {true}
SimpleAllocator *const	simple_allocator_ {nullptr}
IndexType const	buf_allocate_ {0}
IndexType const	centroids_allocate_ {0}

Detailed Description

template<typename RealType, typename IndexType = size_t>
class quantile::detail::TDigest< RealType, IndexType >

Definition at line 182 of file quantile.h.

Member Typedef Documentation

template<typename RealType , typename IndexType = size_t>

using quantile::detail::TDigest< RealType, IndexType >::Memory = CentroidsMemory<RealType, IndexType>

Definition at line 210 of file quantile.h.

Constructor & Destructor Documentation

template<typename RealType , typename IndexType = size_t>

quantile::detail::TDigest< RealType, IndexType >::TDigest ( )

default

template<typename RealType , typename IndexType = size_t>

DEVICE quantile::detail::TDigest< RealType, IndexType >::TDigest ( Memory &  mem )

inline

Definition at line 214 of file quantile.h.

References quantile::detail::TDigest< RealType, IndexType >::centroids_.

      : centroids_(mem.sums().data(), mem.counts().data(), mem.size()) {
    centroids_.clear();
  }

template<typename RealType , typename IndexType = size_t>

DEVICE quantile::detail::TDigest< RealType, IndexType >::TDigest ( SimpleAllocator *  simple_allocator, IndexType  buf_allocate, IndexType  centroids_allocate  )

inline

Definition at line 219 of file quantile.h.

      : simple_allocator_(simple_allocator)
      , buf_allocate_(buf_allocate)
      , centroids_allocate_(centroids_allocate) {}

Member Function Documentation

template<typename RealType , typename IndexType >

DEVICE void quantile::detail::TDigest< RealType, IndexType >::add

(

RealType

value

)

Definition at line 569 of file quantile.h.

                                                            {
  if (buf_.sums_.full()) {
    mergeBuffer();
  }
  buf_.sums_.push_back(value);
  buf_.counts_.push_back(1);
}

template<typename RealType , typename IndexType >

DEVICE void quantile::detail::TDigest< RealType, IndexType >::allocate

(

)

Definition at line 579 of file quantile.h.

Referenced by agg_approx_median_impl(), and approx_median_jit_rt().

                                                   {
  if (buf_.capacity() == 0) {
    auto* p0 = simple_allocator_->allocate(buf_allocate_ * sizeof(RealType));
    auto* p1 = simple_allocator_->allocate(buf_allocate_ * sizeof(IndexType));
    buf_ = Centroids<RealType, IndexType>(
        VectorView<RealType>(reinterpret_cast<RealType*>(p0), 0, buf_allocate_),
        VectorView<IndexType>(reinterpret_cast<IndexType*>(p1), 0, buf_allocate_));
    p0 = simple_allocator_->allocate(centroids_allocate_ * sizeof(RealType));
    p1 = simple_allocator_->allocate(centroids_allocate_ * sizeof(IndexType));
    centroids_ = Centroids<RealType, IndexType>(
        VectorView<RealType>(reinterpret_cast<RealType*>(p0), 0, centroids_allocate_),
        VectorView<IndexType>(reinterpret_cast<IndexType*>(p1), 0, centroids_allocate_));
  }
}

Here is the caller graph for this function:

template<typename RealType , typename IndexType = size_t>

DEVICE Centroids<RealType, IndexType>& quantile::detail::TDigest< RealType, IndexType >::centroids ( )

inline

Definition at line 226 of file quantile.h.

References quantile::detail::TDigest< RealType, IndexType >::centroids_.

{ return centroids_; }

template<typename RealType , typename IndexType >

DEVICE RealType quantile::detail::TDigest< RealType, IndexType >::firstCentroid ( RealType const  x )

private

Definition at line 664 of file quantile.h.

                                                                            {
  if (x < 1) {
    return min();
  } else if (centroids_.size() == 1) {
    return oneCentroid(x);
  } else if (centroids_.counts_.front() == 2) {
    RealType const sum = centroids_.sums_.front();
    return x == 1 ? 0.5 * sum : sum - min();
  } else {
    RealType const count = centroids_.counts_.front();
    RealType const dx = x - RealType(0.5) * (1 + count);
    RealType const mean = (centroids_.sums_.front() - min()) / (count - 1);
    return mean + slope(0, 0 < dx) * dx;
  }
}

template<typename RealType , typename IndexType >

DEVICE RealType quantile::detail::TDigest< RealType, IndexType >::interiorCentroid ( RealType const  x, IndexType const  idx1, IndexType const  prefix_sum  )

private

Definition at line 683 of file quantile.h.

References quantile::detail::anonymous_namespace{quantile.h}::isSingleton().

                                                                           {
  if (isSingleton(centroids_.counts_.begin() + idx1)) {
    RealType const sum1 = centroids_.sums_[idx1];
    if (x == prefix_sum - centroids_.counts_[idx1]) {
      if (isSingleton(centroids_.counts_.begin() + idx1 - 1)) {
        return 0.5 * (centroids_.sums_[idx1 - 1] + sum1);
      } else if (idx1 == 1 && centroids_.counts_[0] == 2) {
        return 0.5 * (centroids_.sums_[idx1 - 1] - min() + sum1);
      }
    }
    return sum1;
  } else {
    RealType const dx = x + RealType(0.5) * centroids_.counts_[idx1] - prefix_sum;
    IndexType const idx2 = idx1 + 2 * (0 < dx) - 1;
    return centroids_.mean(idx1) + slope(idx1, idx2) * dx;
  }
}

Here is the call graph for this function:

template<typename RealType , typename IndexType >

DEVICE RealType quantile::detail::TDigest< RealType, IndexType >::lastCentroid ( RealType const  x, IndexType const  N  )

private

Definition at line 705 of file quantile.h.

References quantile::detail::anonymous_namespace{quantile.h}::isSingleton().

                                                                              {
  if (N - 1 < x) {
    return max();
  }
  IndexType const idx1 = centroids_.size() - 1;
  RealType const sum1 = centroids_.sums_[idx1];
  IndexType const count1 = centroids_.counts_[idx1];
  if (count1 == 1) {  // => x == N - 1
    if (isSingleton(centroids_.counts_.begin() + (idx1 - 1))) {
      return 0.5 * (centroids_.sums_[idx1 - 1] + sum1);
    } else if (idx1 == 1 && centroids_.counts_[0] == 2) {
      return 0.5 * (centroids_.sums_[idx1 - 1] - min() + sum1);
    } else {
      return sum1;
    }
  } else if (count1 == 2) {  // => 3 <= N
    if (x == N - 1) {
      return 0.5 * sum1;
    } else if (x == N - 2) {
      RealType const sum2 = centroids_.sums_[idx1 - 1];
      if (isSingleton(centroids_.counts_.begin() + (idx1 - 1))) {
        return 0.5 * (sum2 + sum1 - max());
      } else if (idx1 == 1 && centroids_.counts_[0] == 2) {
        return 0.5 * (sum2 - min() + sum1 - max());
      }
    }
    return sum1 - max();
  } else {  // => 3 <= count1
    RealType const dx = x + RealType(0.5) * (count1 + 1) - N;
    RealType const mean = (sum1 - max()) / (count1 - 1);
    return mean + slope(idx1, idx1 - (dx < 0)) * dx;
  }
}

Here is the call graph for this function:

template<typename RealType , typename IndexType = size_t>

DEVICE RealType quantile::detail::TDigest< RealType, IndexType >::max ( ) const

inlineprivate

Definition at line 192 of file quantile.h.

References quantile::detail::TDigest< RealType, IndexType >::centroids_.

{ return centroids_.max_; }

template<typename RealType , typename IndexType >

DEVICE IndexType quantile::detail::TDigest< RealType, IndexType >::maxCardinality ( IndexType const  sum, IndexType const  total_weight  )

private

Definition at line 596 of file quantile.h.

                                                                           {
  IndexType const max_bins = centroids_.capacity();
  return max_bins < total_weight ? 2 * total_weight / max_bins : 0;
}

template<typename RealType , typename IndexType >

DEVICE void quantile::detail::TDigest< RealType, IndexType >::mergeBuffer

(

)

Definition at line 604 of file quantile.h.

References gpu_enabled::sort().

Referenced by ResultSet::calculateQuantile(), and quantile::detail::TDigest< RealType, IndexType >::mergeTDigest().

                                                      {
  if (buf_.size()) {
    gpu_enabled::sort(buf_.sums_.begin(), buf_.sums_.end());
    buf_.min_ = buf_.sums_.front();
    buf_.max_ = buf_.sums_.back();
    mergeCentroids(buf_);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename RealType , typename IndexType >

DEVICE void quantile::detail::TDigest< RealType, IndexType >::mergeCentroids ( Centroids< RealType, IndexType > &  buf )

private

Definition at line 637 of file quantile.h.

References quantile::detail::Centroids< RealType, IndexType >::clear(), and quantile::detail::CentroidsMerger< RealType, IndexType >::merge().

Referenced by quantile::detail::TDigest< RealType, IndexType >::mergeTDigest().

                                         {
  // Loop over sorted sequence of buf and centroids_.
  // Some latter centroids may be merged into the current centroid, so the number
  // of iterations is only at most equal to the number of initial centroids.
  using CM = CentroidsMerger<RealType, IndexType>;
  for (CM cm(&buf, &centroids_, forward_); cm.hasNext(); cm.next()) {
    // cm.prefixSum() == 0 on first iteration.
    // Max cardinality for current centroid to be fully merged based on scaling function.
    IndexType const max_cardinality = maxCardinality(cm.prefixSum(), cm.totalWeight());
    cm.merge(max_cardinality);
  }
  // Combine sorted centroids buf[0..curr_idx_] + centroids_[0..curr_idx_] if forward
  centroids_.appendAndSortCurrent(buf);
  buf.clear();
  forward_ ^= true;  // alternate merge direction on each call
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename RealType , typename IndexType >

DEVICE void quantile::detail::TDigest< RealType, IndexType >::mergeSorted	(	RealType *	sums,
		IndexType *	counts,
		IndexType	size
	)

Definition at line 614 of file quantile.h.

References gpu_enabled::fill(), VectorView< T >::set(), and quantile::detail::Centroids< RealType, IndexType >::sums_.

                                                                      {
  if (size) {
    if (buf_.capacity() == 0) {
      buf_ = Centroids<RealType, IndexType>(sums, counts, size);  // Set capacity and size
    } else {
      buf_.sums_.set(sums, size);  // Does not change capacity
      buf_.counts_.set(counts, size);
    }
    gpu_enabled::fill(buf_.counts_.begin(), buf_.counts_.end(), IndexType(1));
    buf_.min_ = buf_.sums_.front();
    buf_.max_ = buf_.sums_.back();
    mergeCentroids(buf_);
  }
}

Here is the call graph for this function:

template<typename RealType , typename IndexType = size_t>

DEVICE void quantile::detail::TDigest< RealType, IndexType >::mergeTDigest ( TDigest< RealType, IndexType > &  t_digest )

inline

Definition at line 239 of file quantile.h.

References quantile::detail::TDigest< RealType, IndexType >::centroids_, quantile::detail::TDigest< RealType, IndexType >::mergeBuffer(), and quantile::detail::TDigest< RealType, IndexType >::mergeCentroids().

                                              {
    mergeBuffer();
    t_digest.mergeBuffer();
    mergeCentroids(t_digest.centroids_);
  }

Here is the call graph for this function:

template<typename RealType , typename IndexType = size_t>

DEVICE RealType quantile::detail::TDigest< RealType, IndexType >::min ( ) const

inlineprivate

Definition at line 193 of file quantile.h.

References quantile::detail::TDigest< RealType, IndexType >::centroids_.

{ return centroids_.min_; }

template<typename RealType , typename IndexType >

DEVICE RealType quantile::detail::TDigest< RealType, IndexType >::oneCentroid ( RealType const  x )

private

Definition at line 742 of file quantile.h.

                                                                          {
  IndexType const N = centroids_.counts_.front();
  if (N - 1 < x) {  // includes case N == 1
    return max();
  } else if (N == 2) {  // x == 1
    return 0.5 * centroids_.sums_.front();
  } else if (N == 3) {  // 1 <= x <= 2
    if (x == 2) {
      return 0.5 * (centroids_.sums_.front() - min());
    } else {
      RealType const s = centroids_.sums_.front() - max();
      return x == 1 ? 0.5 * s : s - min();
    }
  } else {  // 3 < N
    RealType const dx = x - RealType(0.5) * N;
    RealType const mean = (centroids_.sums_.front() - (min() + max())) / (N - 2);
    RealType const slope = 2 * (0 < dx ? max() - mean : mean - min()) / (N - 2);
    return mean + slope * dx;
  }
}

template<typename RealType , typename IndexType = size_t>

DEVICE RealType quantile::detail::TDigest< RealType, IndexType >::quantile ( RealType const  q )

inline

Definition at line 246 of file quantile.h.

References quantile::detail::TDigest< RealType, IndexType >::buf_, and quantile::detail::TDigest< RealType, IndexType >::centroids_.

Referenced by ResultSet::calculateQuantile().

                                             {
    assert(centroids_.size() <= buf_.capacity());
    return quantile(buf_.counts_.data(), q);
  }

Here is the caller graph for this function:

template<typename RealType , typename IndexType >

DEVICE RealType quantile::detail::TDigest< RealType, IndexType >::quantile	(	IndexType *	buf,
		RealType const	q
	)

Definition at line 765 of file quantile.h.

References gpu_enabled::partial_sum(), and gpu_enabled::upper_bound().

                                                                                       {
  if (centroids_.size()) {
    VectorView<IndexType> partial_sum(buf, centroids_.size(), centroids_.size());
    gpu_enabled::partial_sum(
        centroids_.counts_.begin(), centroids_.counts_.end(), partial_sum.begin());
    IndexType const N = partial_sum.back();
    RealType const x = q * N;
    auto const it1 = gpu_enabled::upper_bound(partial_sum.begin(), partial_sum.end(), x);
    if (it1 == partial_sum.begin()) {
      return firstCentroid(x);
    } else if (it1 == partial_sum.end()) {  // <==> 1 <= q
      return max();
    } else if (it1 + 1 == partial_sum.end()) {
      return lastCentroid(x, N);
    } else {
      return interiorCentroid(x, it1 - partial_sum.begin(), *it1);
    }
  } else {
    return centroids_.nan;
  }
}

Here is the call graph for this function:

template<typename RealType , typename IndexType = size_t>

DEVICE void quantile::detail::TDigest< RealType, IndexType >::setBuffer ( Memory &  mem )

inline

Definition at line 255 of file quantile.h.

References quantile::detail::TDigest< RealType, IndexType >::buf_, quantile::detail::CentroidsMemory< RealType, IndexType >::counts(), VectorView< T >::data(), quantile::detail::CentroidsMemory< RealType, IndexType >::size(), and quantile::detail::CentroidsMemory< RealType, IndexType >::sums().

                                     {
    buf_ = Centroids<RealType, IndexType>(
        mem.sums().data(), mem.counts().data(), mem.size());
    buf_.clear();
  }

Here is the call graph for this function:

template<typename RealType , typename IndexType = size_t>

DEVICE void quantile::detail::TDigest< RealType, IndexType >::setCentroids ( Memory &  mem )

inline

Definition at line 262 of file quantile.h.

References quantile::detail::TDigest< RealType, IndexType >::centroids_, quantile::detail::CentroidsMemory< RealType, IndexType >::counts(), VectorView< T >::data(), quantile::detail::CentroidsMemory< RealType, IndexType >::size(), and quantile::detail::CentroidsMemory< RealType, IndexType >::sums().

                                        {
    centroids_ = Centroids<RealType, IndexType>(
        mem.sums().data(), mem.counts().data(), mem.size());
    centroids_.clear();
  }

Here is the call graph for this function:

template<typename RealType , typename IndexType = size_t>

DEVICE void quantile::detail::TDigest< RealType, IndexType >::setCentroids ( VectorView< RealType > const  sums, VectorView< IndexType > const  counts  )

inline

Definition at line 268 of file quantile.h.

References quantile::detail::TDigest< RealType, IndexType >::centroids_.

                                                               {
    centroids_ = Centroids<RealType, IndexType>(sums, counts);
    centroids_.clear();
  }

template<typename RealType , typename IndexType >

DEVICE RealType quantile::detail::TDigest< RealType, IndexType >::slope ( IndexType const  idx1, IndexType const  idx2  )

private

Definition at line 792 of file quantile.h.

References quantile::detail::anonymous_namespace{quantile.h}::isSingleton().

                                                                                  {
  IndexType const M = centroids_.size();
  if (idx1 == idx2) {  // Line segment is contained in either the first or last centroid.
    RealType const n = static_cast<RealType>(centroids_.counts_[idx1]);
    RealType const s = centroids_.sums_[idx1];
    return idx1 == 0 ? 2 * (s - n * min()) / ((n - 1) * (n - 1))
                     : 2 * (n * max() - s) / ((n - 1) * (n - 1));
  } else {
    bool const min1 = idx1 == 0;      // idx1 is the min centroid
    bool const max1 = idx1 == M - 1;  // idx1 is the max centroid
    bool const min2 = idx2 == 0;      // idx2 is the min centroid
    bool const max2 = idx2 == M - 1;  // idx2 is the max centroid
    RealType const n1 = static_cast<RealType>(centroids_.counts_[idx1] - min1 - max1);
    RealType const s1 = centroids_.sums_[idx1] - (min1 ? min() : max1 ? max() : 0);
    RealType const s2 = centroids_.sums_[idx2] - (min2 ? min() : max2 ? max() : 0);
    if (isSingleton(centroids_.counts_.begin() + idx2)) {
      return (idx1 < idx2 ? 2 : -2) * (n1 * s2 - s1) / (n1 * n1);
    } else {
      RealType const n2 = static_cast<RealType>(centroids_.counts_[idx2] - min2 - max2);
      return (idx1 < idx2 ? 2 : -2) * (n1 * s2 - n2 * s1) / (n1 * n2 * (n1 + n2));
    }
  }
}

Here is the call graph for this function:

template<typename RealType , typename IndexType = size_t>

DEVICE IndexType quantile::detail::TDigest< RealType, IndexType >::totalWeight ( ) const

inline

Definition at line 275 of file quantile.h.

References quantile::detail::TDigest< RealType, IndexType >::centroids_.

{ return centroids_.totalWeight(); }

Member Data Documentation

template<typename RealType , typename IndexType = size_t>

Centroids<RealType, IndexType> quantile::detail::TDigest< RealType, IndexType >::buf_

private

Definition at line 183 of file quantile.h.

Referenced by quantile::detail::TDigest< RealType, IndexType >::quantile(), and quantile::detail::TDigest< RealType, IndexType >::setBuffer().

template<typename RealType , typename IndexType = size_t>

IndexType const quantile::detail::TDigest< RealType, IndexType >::buf_allocate_ {0}

private

Definition at line 189 of file quantile.h.

template<typename RealType , typename IndexType = size_t>

Centroids<RealType, IndexType> quantile::detail::TDigest< RealType, IndexType >::centroids_

private

Definition at line 184 of file quantile.h.

Referenced by quantile::detail::TDigest< RealType, IndexType >::centroids(), quantile::detail::TDigest< RealType, IndexType >::max(), quantile::detail::TDigest< RealType, IndexType >::mergeTDigest(), quantile::detail::TDigest< RealType, IndexType >::min(), quantile::detail::TDigest< RealType, IndexType >::quantile(), quantile::detail::TDigest< RealType, IndexType >::setCentroids(), quantile::detail::TDigest< RealType, IndexType >::TDigest(), and quantile::detail::TDigest< RealType, IndexType >::totalWeight().

template<typename RealType , typename IndexType = size_t>

IndexType const quantile::detail::TDigest< RealType, IndexType >::centroids_allocate_ {0}

private

Definition at line 190 of file quantile.h.

template<typename RealType , typename IndexType = size_t>

bool quantile::detail::TDigest< RealType, IndexType >::forward_ {true}

private

Definition at line 185 of file quantile.h.

template<typename RealType , typename IndexType = size_t>

SimpleAllocator* const quantile::detail::TDigest< RealType, IndexType >::simple_allocator_ {nullptr}

private

Definition at line 188 of file quantile.h.

---

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

• /home/jenkins-slave/workspace/core-os-doxygen/Shared/quantile.h