This is an automated email from the ASF dual-hosted git repository.
alsay pushed a commit to branch kll_no_default_construction
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-cpp.git
The following commit(s) were added to refs/heads/kll_no_default_construction by
this push:
new 7f96aa1 use allocator and no default construction of T in quantiles
calculator
7f96aa1 is described below
commit 7f96aa1b6d82fd9e4866eba4adf9e5f0c1713836
Author: AlexanderSaydakov <[email protected]>
AuthorDate: Tue Jul 23 15:29:49 2019 -0700
use allocator and no default construction of T in quantiles calculator
---
kll/include/kll_helper.hpp | 5 +--
kll/include/kll_quantile_calculator.hpp | 59 ++++++++++++++++++++-------------
kll/include/kll_sketch.hpp | 48 +++++++++++++--------------
3 files changed, 62 insertions(+), 50 deletions(-)
diff --git a/kll/include/kll_helper.hpp b/kll/include/kll_helper.hpp
index e39cb7a..67925b1 100644
--- a/kll/include/kll_helper.hpp
+++ b/kll/include/kll_helper.hpp
@@ -349,10 +349,11 @@ class kll_helper {
}
template<typename T>
- static void move_construct(T* src, size_t src_first, size_t src_last, T*
dst, size_t dst_first) {
+ static void move_construct(T* src, size_t src_first, size_t src_last, T*
dst, size_t dst_first, bool destroy) {
while (src_first != src_last) {
new (&dst[dst_first++]) T(std::move(src[src_first]));
- src[src_first++].~T();
+ if (destroy) src[src_first].~T();
+ src_first++;
}
}
diff --git a/kll/include/kll_quantile_calculator.hpp
b/kll/include/kll_quantile_calculator.hpp
index 54801f3..91c906b 100644
--- a/kll/include/kll_quantile_calculator.hpp
+++ b/kll/include/kll_quantile_calculator.hpp
@@ -24,27 +24,34 @@
#include <cmath>
#include <assert.h>
+#include "kll_helper.hpp"
+
namespace datasketches {
-template <typename T, typename C>
+template <typename T, typename C, typename A>
class kll_quantile_calculator {
+ typedef typename std::allocator_traits<A>::template rebind_alloc<uint32_t>
AllocU32;
+ typedef typename std::allocator_traits<A>::template rebind_alloc<uint64_t>
AllocU64;
public:
// assumes that all levels are sorted including level 0
kll_quantile_calculator(const T* items, const uint32_t* levels, uint8_t
num_levels, uint64_t n) {
n_ = n;
- const uint32_t num_items(levels[num_levels] - levels[0]);
- items_ = new T[num_items];
- weights_ = new uint64_t[num_items + 1]; // one more is intentional
- levels_ = new uint32_t[num_levels + 1];
+ const uint32_t num_items = levels[num_levels] - levels[0];
+ items_ = A().allocate(num_items);
+ weights_ = AllocU64().allocate(num_items + 1); // one more is intentional
+ levels_size_ = num_levels + 1;
+ levels_ = AllocU32().allocate(levels_size_);
populate_from_sketch(items, num_items, levels, num_levels);
blocky_tandem_merge_sort(items_, weights_, num_items, levels_,
num_levels_);
convert_to_preceding_cummulative(weights_, num_items + 1);
}
~kll_quantile_calculator() {
- delete [] items_;
- delete [] weights_;
- delete [] levels_;
+ const uint32_t num_items = levels_[num_levels_] - levels_[0];
+ for (uint32_t i = 0; i < num_items; i++) items_[i].~T();
+ A().deallocate(items_, num_items);
+ AllocU64().deallocate(weights_, num_items + 1);
+ AllocU32().deallocate(levels_, levels_size_);
}
T get_quantile(double fraction) const {
@@ -56,14 +63,15 @@ class kll_quantile_calculator {
T* items_;
uint64_t* weights_;
uint32_t* levels_;
+ uint8_t levels_size_;
uint8_t num_levels_;
void populate_from_sketch(const T* items, uint32_t num_items, const
uint32_t* levels, uint8_t num_levels) {
- std::copy(&items[levels[0]], &items[levels[num_levels]], items_);
- uint8_t src_level(0);
- uint8_t dst_level(0);
- uint64_t weight(1);
- uint32_t offset(levels[0]);
+ kll_helper::copy_construct<T>(items, levels[0], levels[num_levels],
items_, 0);
+ uint8_t src_level = 0;
+ uint8_t dst_level = 0;
+ uint64_t weight = 1;
+ uint32_t offset = levels[0];
while (src_level < num_levels) {
const uint32_t from_index(levels[src_level] - offset);
const uint32_t to_index(levels[src_level + 1] - offset); // exclusive
@@ -123,12 +131,17 @@ class kll_quantile_calculator {
static void blocky_tandem_merge_sort(T* items, uint64_t* weights, uint32_t
num_items, const uint32_t* levels, uint8_t num_levels) {
if (num_levels == 1) return;
- // duplicate the input in preparation for the "ping-pong" copy reduction
strategy
- std::unique_ptr<T[]> items_tmp(new T[num_items]);
- std::copy(items, &items[num_items], items_tmp.get());
- std::unique_ptr<uint64_t[]> weights_tmp(new uint64_t[num_items]); //
don't need the extra one here
- std::copy(weights, &weights[num_items], weights_tmp.get());
- blocky_tandem_merge_sort_recursion(items_tmp.get(), weights_tmp.get(),
items, weights, levels, 0, num_levels);
+ // move the input in preparation for the "ping-pong" reduction strategy
+ auto tmp_items_deleter = [num_items](T* ptr) {
+ for (uint32_t i = 0; i < num_items; i++) ptr[i].~T();
+ A().deallocate(ptr, num_items);
+ };
+ std::unique_ptr<T, decltype(tmp_items_deleter)>
tmp_items(A().allocate(num_items), tmp_items_deleter);
+ kll_helper::move_construct<T>(items, 0, num_items, tmp_items.get(), 0,
false); // do not destroy since the items will be moved back
+ auto tmp_weights_deleter = [num_items](uint64_t* ptr) {
AllocU64().deallocate(ptr, num_items); };
+ std::unique_ptr<uint64_t[], decltype(tmp_weights_deleter)>
tmp_weights(AllocU64().allocate(num_items), tmp_weights_deleter); // don't need
the extra one here
+ std::copy(weights, &weights[num_items], tmp_weights.get());
+ blocky_tandem_merge_sort_recursion(tmp_items.get(), tmp_weights.get(),
items, weights, levels, 0, num_levels);
}
static void blocky_tandem_merge_sort_recursion(T* items_src, uint64_t*
weights_src, T* items_dst, uint64_t* weights_dst, const uint32_t* levels,
uint8_t starting_level, uint8_t num_levels) {
@@ -156,21 +169,21 @@ class kll_quantile_calculator {
while ((i_src_1 < to_index_1) and (i_src_2 < to_index_2)) {
if (C()(items_src[i_src_1], items_src[i_src_2])) {
- items_dst[i_dst] = items_src[i_src_1];
+ items_dst[i_dst] = std::move(items_src[i_src_1]);
weights_dst[i_dst] = weights_src[i_src_1];
i_src_1++;
} else {
- items_dst[i_dst] = items_src[i_src_2];
+ items_dst[i_dst] = std::move(items_src[i_src_2]);
weights_dst[i_dst] = weights_src[i_src_2];
i_src_2++;
}
i_dst++;
}
if (i_src_1 < to_index_1) {
- std::copy(&items_src[i_src_1], &items_src[to_index_1],
&items_dst[i_dst]);
+ std::move(&items_src[i_src_1], &items_src[to_index_1],
&items_dst[i_dst]);
std::copy(&weights_src[i_src_1], &weights_src[to_index_1],
&weights_dst[i_dst]);
} else if (i_src_2 < to_index_2) {
- std::copy(&items_src[i_src_2], &items_src[to_index_2],
&items_dst[i_dst]);
+ std::move(&items_src[i_src_2], &items_src[to_index_2],
&items_dst[i_dst]);
std::copy(&weights_src[i_src_2], &weights_src[to_index_2],
&weights_dst[i_dst]);
}
}
diff --git a/kll/include/kll_sketch.hpp b/kll/include/kll_sketch.hpp
index 350c00b..13fd1e5 100644
--- a/kll/include/kll_sketch.hpp
+++ b/kll/include/kll_sketch.hpp
@@ -290,7 +290,7 @@ class kll_sketch {
uint8_t find_level_to_compact() const;
void add_empty_top_level_to_completely_full_sketch();
void sort_level_zero();
- std::unique_ptr<kll_quantile_calculator<T, C>> get_quantile_calculator();
+ std::unique_ptr<kll_quantile_calculator<T, C, A>>
get_quantile_calculator();
std::unique_ptr<double[]> get_PMF_or_CDF(const T* split_points, uint32_t
size, bool is_CDF) const;
void increment_buckets_unsorted_level(uint32_t from_index, uint32_t
to_index, uint64_t weight,
const T* split_points, uint32_t size, double* buckets) const;
@@ -306,6 +306,19 @@ class kll_sketch {
static void check_preamble_ints(uint8_t preamble_ints, uint8_t flags_byte);
static void check_serial_version(uint8_t serial_version);
static void check_family_id(uint8_t family_id);
+
+ // implementation for floating point types
+ template<typename TT = T, typename
std::enable_if<std::is_floating_point<TT>::value, int>::type = 0>
+ static TT get_invalid_value() {
+ return std::numeric_limits<TT>::quiet_NaN();
+ }
+
+ // implementation for all other types
+ template<typename TT = T, typename
std::enable_if<!std::is_floating_point<TT>::value, int>::type = 0>
+ static TT get_invalid_value() {
+ throw std::runtime_error("getting quantiles from empty sketch is not
supported for this type of values");
+ }
+
};
template<typename T, typename C, typename S, typename A>
@@ -475,34 +488,19 @@ bool kll_sketch<T, C, S, A>::is_estimation_mode() const {
template<typename T, typename C, typename S, typename A>
T kll_sketch<T, C, S, A>::get_min_value() const {
- if (is_empty()) {
- if (std::is_floating_point<T>::value) {
- return std::numeric_limits<T>::quiet_NaN();
- }
- throw std::runtime_error("getting quantiles from empty sketch is not
supported for this type of values");
- }
+ if (is_empty()) return get_invalid_value();
return *min_value_;
}
template<typename T, typename C, typename S, typename A>
T kll_sketch<T, C, S, A>::get_max_value() const {
- if (is_empty()) {
- if (std::is_floating_point<T>::value) {
- return std::numeric_limits<T>::quiet_NaN();
- }
- throw std::runtime_error("getting quantiles from empty sketch is not
supported for this type of values");
- }
+ if (is_empty()) return get_invalid_value();
return *max_value_;
}
template<typename T, typename C, typename S, typename A>
T kll_sketch<T, C, S, A>::get_quantile(double fraction) const {
- if (is_empty()) {
- if (std::is_floating_point<T>::value) {
- return std::numeric_limits<T>::quiet_NaN();
- }
- throw std::runtime_error("getting quantiles from empty sketch is not
supported for this type of values");
- }
+ if (is_empty()) return get_invalid_value();
if (fraction == 0.0) return *min_value_;
if (fraction == 1.0) return *max_value_;
if ((fraction < 0.0) or (fraction > 1.0)) {
@@ -516,7 +514,7 @@ T kll_sketch<T, C, S, A>::get_quantile(double fraction)
const {
template<typename T, typename C, typename S, typename A>
std::unique_ptr<T[]> kll_sketch<T, C, S, A>::get_quantiles(const double*
fractions, uint32_t size) const {
if (is_empty()) { return nullptr; }
- std::unique_ptr<kll_quantile_calculator<T, C>> quantile_calculator;
+ std::unique_ptr<kll_quantile_calculator<T, C, A>> quantile_calculator;
std::unique_ptr<T[]> quantiles(new T[size]);
for (uint32_t i = 0; i < size; i++) {
const double fraction = fractions[i];
@@ -931,9 +929,9 @@ void kll_sketch<T, C, S, A>::sort_level_zero() {
}
template<typename T, typename C, typename S, typename A>
-std::unique_ptr<kll_quantile_calculator<T, C>> kll_sketch<T, C, S,
A>::get_quantile_calculator() {
+std::unique_ptr<kll_quantile_calculator<T, C, A>> kll_sketch<T, C, S,
A>::get_quantile_calculator() {
sort_level_zero();
- std::unique_ptr<kll_quantile_calculator<T, C>> quantile_calculator(new
kll_quantile_calculator<T, C>(items_, levels_, num_levels_, n_));
+ std::unique_ptr<kll_quantile_calculator<T, C, A>> quantile_calculator(new
kll_quantile_calculator<T, C, A>(items_, levels_, num_levels_, n_));
return std::move(quantile_calculator);
}
@@ -1037,7 +1035,7 @@ void kll_sketch<T, C, S, A>::merge_higher_levels(const
kll_sketch& other, uint64
items_ = A().allocate(items_size_);
}
const uint32_t free_space_at_bottom = result.final_capacity -
result.final_num_items;
- kll_helper::move_construct<T>(workbuf.get(), outlevels[0], outlevels[0] +
result.final_num_items, items_, free_space_at_bottom);
+ kll_helper::move_construct<T>(workbuf.get(), outlevels[0], outlevels[0] +
result.final_num_items, items_, free_space_at_bottom, true);
if (levels_size_ < (result.final_num_levels + 1)) {
AllocU32().deallocate(levels_, levels_size_);
@@ -1057,7 +1055,7 @@ void kll_sketch<T, C, S, A>::populate_work_arrays(const
kll_sketch& other, T* wo
worklevels[0] = 0;
// the level zero data from "other" was already inserted into "this"
- kll_helper::move_construct<T>(items_, levels_[0], levels_[1], workbuf, 0);
+ kll_helper::move_construct<T>(items_, levels_[0], levels_[1], workbuf, 0,
true);
worklevels[1] = safe_level_size(0);
for (uint8_t lvl = 1; lvl < provisional_num_levels; lvl++) {
@@ -1066,7 +1064,7 @@ void kll_sketch<T, C, S, A>::populate_work_arrays(const
kll_sketch& other, T* wo
worklevels[lvl + 1] = worklevels[lvl] + self_pop + other_pop;
if ((self_pop > 0) and (other_pop == 0)) {
- kll_helper::move_construct<T>(items_, levels_[lvl], levels_[lvl] +
self_pop, workbuf, worklevels[lvl]);
+ kll_helper::move_construct<T>(items_, levels_[lvl], levels_[lvl] +
self_pop, workbuf, worklevels[lvl], true);
} else if ((self_pop == 0) and (other_pop > 0)) {
kll_helper::copy_construct<T>(other.items_, other.levels_[lvl],
other.levels_[lvl] + other_pop, workbuf, worklevels[lvl]);
} else if ((self_pop > 0) and (other_pop > 0)) {
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
