You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by jm...@apache.org on 2022/05/06 03:06:12 UTC
[datasketches-cpp] 01/01: move quantiles and req from quantile_calculator to sorted_view (and fix a quantiles deser bug)
This is an automated email from the ASF dual-hosted git repository.
jmalkin pushed a commit to branch sorted_view
in repository https://gitbox.apache.org/repos/asf/datasketches-cpp.git
commit 5008526064330d5f2bd558d3f495b388fe9fb3e8
Author: Jon <jm...@apache.org>
AuthorDate: Thu May 5 20:05:54 2022 -0700
move quantiles and req from quantile_calculator to sorted_view (and fix a quantiles deser bug)
---
common/CMakeLists.txt | 2 -
common/include/quantile_calculator.hpp | 69 -----------------------
common/include/quantile_calculator_impl.hpp | 62 ---------------------
hll/test/CouponListTest.cpp | 1 +
hll/test/HllUnionTest.cpp | 1 +
quantiles/include/quantiles_sketch.hpp | 15 ++---
quantiles/include/quantiles_sketch_impl.hpp | 73 +++++++++++--------------
quantiles/test/quantiles_compatibility_test.cpp | 1 -
req/include/req_sketch.hpp | 15 ++---
req/include/req_sketch_impl.hpp | 45 +++++----------
10 files changed, 60 insertions(+), 224 deletions(-)
diff --git a/common/CMakeLists.txt b/common/CMakeLists.txt
index 3d4919b..df7f1c0 100644
--- a/common/CMakeLists.txt
+++ b/common/CMakeLists.txt
@@ -43,8 +43,6 @@ install(FILES
include/conditional_forward.hpp
include/ceiling_power_of_2.hpp
include/bounds_binomial_proportions.hpp
- include/quantile_calculator.hpp
- include/quantile_calculator_impl.hpp
include/quantile_sketch_sorted_view.hpp
include/quantile_sketch_sorted_view_impl.hpp
DESTINATION "${CMAKE_INSTALL_INCLUDEDIR}/DataSketches")
diff --git a/common/include/quantile_calculator.hpp b/common/include/quantile_calculator.hpp
deleted file mode 100644
index 0d93dc1..0000000
--- a/common/include/quantile_calculator.hpp
+++ /dev/null
@@ -1,69 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-
-#ifndef QUANTILE_CALCULATOR_HPP_
-#define QUANTILE_CALCULATOR_HPP_
-
-#include <functional>
-
-namespace datasketches {
-
-template<
- typename T,
- typename Comparator,
- typename Allocator
->
-class quantile_calculator {
-public:
- quantile_calculator(uint64_t n, const Allocator& allocator);
-
- void add(const T* begin, const T* end, uint8_t lg_weight);
-
- template<bool inclusive>
- void convert_to_cummulative();
-
- const T* get_quantile(double rank) const;
-
-private:
- using Entry = std::pair<const T*, uint64_t>;
- using AllocEntry = typename std::allocator_traits<Allocator>::template rebind_alloc<Entry>;
- using Container = std::vector<Entry, AllocEntry>;
-
- template<typename C>
- struct compare_pairs_by_first_ptr {
- bool operator()(const Entry& a, const Entry& b) {
- return C()(*a.first, *b.first);
- }
- };
-
- struct compare_pairs_by_second {
- bool operator()(const Entry& a, const Entry& b) {
- return a.second < b.second;
- }
- };
-
- uint64_t n_;
- Container entries_;
-};
-
-} /* namespace datasketches */
-
-#include "quantile_calculator_impl.hpp"
-
-#endif
diff --git a/common/include/quantile_calculator_impl.hpp b/common/include/quantile_calculator_impl.hpp
deleted file mode 100644
index fe707b3..0000000
--- a/common/include/quantile_calculator_impl.hpp
+++ /dev/null
@@ -1,62 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-
-#ifndef QUANTILE_CALCULATOR_IMPL_HPP_
-#define QUANTILE_CALCULATOR_IMPL_HPP_
-
-#include <algorithm>
-
-namespace datasketches {
-
-template<typename T, typename C, typename A>
-quantile_calculator<T, C, A>::quantile_calculator(uint64_t n, const A& allocator):
-n_(n),
-entries_(allocator)
-{}
-
-template<typename T, typename C, typename A>
-void quantile_calculator<T, C, A>::add(const T* begin, const T* end, uint8_t lg_weight) {
- if (entries_.capacity() < entries_.size() + std::distance(begin, end)) entries_.reserve(entries_.size() + std::distance(begin, end));
- const size_t size_before = entries_.size();
- for (auto it = begin; it != end; ++it) entries_.push_back(Entry(it, 1 << lg_weight));
- if (size_before > 0) std::inplace_merge(entries_.begin(), entries_.begin() + size_before, entries_.end(), compare_pairs_by_first_ptr<C>());
-}
-
-template<typename T, typename C, typename A>
-template<bool inclusive>
-void quantile_calculator<T, C, A>::convert_to_cummulative() {
- uint64_t subtotal = 0;
- for (auto& entry: entries_) {
- const uint64_t new_subtotal = subtotal + entry.second;
- entry.second = inclusive ? new_subtotal : subtotal;
- subtotal = new_subtotal;
- }
-}
-
-template<typename T, typename C, typename A>
-const T* quantile_calculator<T, C, A>::get_quantile(double rank) const {
- uint64_t weight = static_cast<uint64_t>(rank * n_);
- auto it = std::lower_bound(entries_.begin(), entries_.end(), Entry(nullptr, weight), compare_pairs_by_second());
- if (it == entries_.end()) return entries_[entries_.size() - 1].first;
- return it->first;
-}
-
-} /* namespace datasketches */
-
-#endif
diff --git a/hll/test/CouponListTest.cpp b/hll/test/CouponListTest.cpp
index c6fd14b..a2f0e8a 100644
--- a/hll/test/CouponListTest.cpp
+++ b/hll/test/CouponListTest.cpp
@@ -32,6 +32,7 @@
namespace datasketches {
void println_string(std::string str) {
+ unused(str);
//std::cout << str << std::endl;
}
diff --git a/hll/test/HllUnionTest.cpp b/hll/test/HllUnionTest.cpp
index 756aab6..821d3f0 100644
--- a/hll/test/HllUnionTest.cpp
+++ b/hll/test/HllUnionTest.cpp
@@ -26,6 +26,7 @@
namespace datasketches {
static void println(std::string& str) {
+ unused(str);
//std::cout << str << "\n";
}
diff --git a/quantiles/include/quantiles_sketch.hpp b/quantiles/include/quantiles_sketch.hpp
index b9a200e..466d0df 100644
--- a/quantiles/include/quantiles_sketch.hpp
+++ b/quantiles/include/quantiles_sketch.hpp
@@ -24,7 +24,7 @@
#include <memory>
#include <vector>
-#include "quantile_calculator.hpp"
+#include "quantile_sketch_sorted_view.hpp"
#include "common_defs.hpp"
#include "serde.hpp"
@@ -241,8 +241,9 @@ public:
*
* @return the approximation to the value at the given rank
*/
+ using quantile_return_type = typename quantile_sketch_sorted_view<T, C, A>::quantile_return_type;
template<bool inclusive = false>
- const T& get_quantile(double rank) const;
+ quantile_return_type get_quantile(double rank) const;
/**
* This is a more efficient multiple-query version of get_quantile().
@@ -441,6 +442,9 @@ public:
const_iterator begin() const;
const_iterator end() const;
+ template<bool inclusive = false>
+ quantile_sketch_sorted_view<T, C, A> get_sorted_view(bool cumulative) const;
+
private:
using Level = std::vector<T, Allocator>;
using AllocLevel = typename std::allocator_traits<Allocator>::template rebind_alloc<Level>;
@@ -481,13 +485,6 @@ private:
T* max_value_;
bool is_sorted_;
- using QuantileCalculator = quantile_calculator<T, Comparator, Allocator>;
- using AllocCalc = typename std::allocator_traits<Allocator>::template rebind_alloc<QuantileCalculator>;
- class calculator_deleter;
- using QuantileCalculatorPtr = typename std::unique_ptr<QuantileCalculator, calculator_deleter>;
- template<bool inclusive>
- QuantileCalculatorPtr get_quantile_calculator() const;
-
// for deserialization
class item_deleter;
class items_deleter;
diff --git a/quantiles/include/quantiles_sketch_impl.hpp b/quantiles/include/quantiles_sketch_impl.hpp
index 7235a51..1518839 100644
--- a/quantiles/include/quantiles_sketch_impl.hpp
+++ b/quantiles/include/quantiles_sketch_impl.hpp
@@ -359,8 +359,12 @@ auto quantiles_sketch<T, C, A>::deserialize(std::istream &is, const SerDe& serde
// load base buffer
const uint32_t bb_items = compute_base_buffer_items(k, items_seen);
uint32_t items_to_read = (levels_needed == 0 || is_compact) ? bb_items : 2 * k;
- Level base_buffer = deserialize_array(is, items_to_read, 2 * k, serde, allocator);
-
+ Level base_buffer = deserialize_array(is, bb_items, 2 * k, serde, allocator);
+ if (items_to_read > bb_items) { // either equal or greater, never read fewer items
+ // read remaining items, but don't store them
+ deserialize_array(is, items_to_read - bb_items, items_to_read - bb_items, serde, allocator);
+ }
+
// populate vector of Levels directly
VectorLevels levels(allocator);
levels.reserve(levels_needed);
@@ -470,9 +474,14 @@ auto quantiles_sketch<T, C, A>::deserialize(const void* bytes, size_t size, cons
// load base buffer
const uint32_t bb_items = compute_base_buffer_items(k, items_seen);
uint32_t items_to_read = (levels_needed == 0 || is_compact) ? bb_items : 2 * k;
- auto base_buffer_pair = deserialize_array(ptr, end_ptr - ptr, items_to_read, 2 * k, serde, allocator);
+ auto base_buffer_pair = deserialize_array(ptr, end_ptr - ptr, bb_items, 2 * k, serde, allocator);
ptr += base_buffer_pair.second;
-
+ if (items_to_read > bb_items) { // either equal or greater, never read fewer items
+ // read remaining items, only use to advance the pointer
+ auto extras = deserialize_array(ptr, end_ptr - ptr, items_to_read - bb_items, items_to_read - bb_items, serde, allocator);
+ ptr += extras.second;
+ }
+
// populate vector of Levels directly
VectorLevels levels(allocator);
levels.reserve(levels_needed);
@@ -637,56 +646,39 @@ double quantiles_sketch<T, C, A>::get_normalized_rank_error(uint16_t k, bool is_
: 1.576 / std::pow(k, 0.9726);
}
-template<typename T, typename C, typename A>
-class quantiles_sketch<T, C, A>::calculator_deleter {
- public:
- explicit calculator_deleter(const AllocCalc& allocator): allocator_(allocator) {}
- void operator() (QuantileCalculator* ptr) {
- if (ptr != nullptr) {
- ptr->~QuantileCalculator();
- allocator_.deallocate(ptr, 1);
- }
- }
- private:
- AllocCalc allocator_;
-};
-
template<typename T, typename C, typename A>
template<bool inclusive>
-auto quantiles_sketch<T, C, A>::get_quantile_calculator() const -> QuantileCalculatorPtr {
- // allow side effect of sorting the base buffer
- // can't set the sorted flag since this is a const method
+quantile_sketch_sorted_view<T, C, A> quantiles_sketch<T, C, A>::get_sorted_view(bool cumulative) const {
+ // allow side-effect of sorting the base buffer; can't set the flag since
+ // this is a const method
if (!is_sorted_) {
std::sort(const_cast<Level&>(base_buffer_).begin(), const_cast<Level&>(base_buffer_).end(), C());
}
+ quantile_sketch_sorted_view<T, C, A> view(get_num_retained(), allocator_);
- AllocCalc ac(allocator_);
- QuantileCalculatorPtr quantile_calculator_ptr(
- new (ac.allocate(1)) quantile_calculator<T, C, A>(n_, ac),
- calculator_deleter(ac)
- );
-
- uint8_t lg_weight = 0;
- quantile_calculator_ptr->add(base_buffer_.data(), base_buffer_.data() + base_buffer_.size(), lg_weight);
+ uint64_t weight = 1;
+ view.add(base_buffer_.begin(), base_buffer_.end(), weight);
for (auto& level : levels_) {
- ++lg_weight;
+ weight <<= 1;
if (level.empty()) { continue; }
- quantile_calculator_ptr->add(level.data(), level.data() + k_, lg_weight);
+ view.add(level.begin(), level.end(), weight);
}
- quantile_calculator_ptr->template convert_to_cummulative<inclusive>();
- return quantile_calculator_ptr;
+
+ if (cumulative) view.template convert_to_cummulative<inclusive>();
+ return view;
}
template<typename T, typename C, typename A>
template<bool inclusive>
-const T& quantiles_sketch<T, C, A>::get_quantile(double rank) const {
+auto quantiles_sketch<T, C, A>::get_quantile(double rank) const -> quantile_return_type {
if (is_empty()) return get_invalid_value();
if (rank == 0.0) return *min_value_;
if (rank == 1.0) return *max_value_;
if ((rank < 0.0) || (rank > 1.0)) {
throw std::invalid_argument("Rank cannot be less than zero or greater than 1.0");
}
- return *(get_quantile_calculator<inclusive>()->get_quantile(rank));
+ // possible side-effect: sorting base buffer
+ return get_sorted_view<inclusive>(true).get_quantile(rank);
}
template<typename T, typename C, typename A>
@@ -694,8 +686,11 @@ template<bool inclusive>
std::vector<T, A> quantiles_sketch<T, C, A>::get_quantiles(const double* ranks, uint32_t size) const {
std::vector<T, A> quantiles(allocator_);
if (is_empty()) return quantiles;
- QuantileCalculatorPtr quantile_calculator_ptr(nullptr, calculator_deleter(allocator_));
quantiles.reserve(size);
+
+ // possible side-effect: sorting base buffer
+ auto view = get_sorted_view<inclusive>(true);
+
for (uint32_t i = 0; i < size; ++i) {
const double rank = ranks[i];
if ((rank < 0.0) || (rank > 1.0)) {
@@ -704,11 +699,7 @@ std::vector<T, A> quantiles_sketch<T, C, A>::get_quantiles(const double* ranks,
if (rank == 0.0) quantiles.push_back(*min_value_);
else if (rank == 1.0) quantiles.push_back(*max_value_);
else {
- if (!quantile_calculator_ptr) {
- // has side effect of sorting level zero if needed
- quantile_calculator_ptr = const_cast<quantiles_sketch*>(this)->get_quantile_calculator<inclusive>();
- }
- quantiles.push_back(*(quantile_calculator_ptr->get_quantile(rank)));
+ quantiles.push_back(view.get_quantile(rank));
}
}
return quantiles;
diff --git a/quantiles/test/quantiles_compatibility_test.cpp b/quantiles/test/quantiles_compatibility_test.cpp
index 620f8fd..bd9aab7 100644
--- a/quantiles/test/quantiles_compatibility_test.cpp
+++ b/quantiles/test/quantiles_compatibility_test.cpp
@@ -62,7 +62,6 @@ static void quantiles_decode_and_check(uint16_t k, uint64_t n, const std::string
(std::istreambuf_iterator<char>(infile)),
(std::istreambuf_iterator<char>()));
infile.close();
-
auto sketch_bytes = quantiles_double_sketch::deserialize(bytes.data(), bytes.size(), serde<double>(), 0);
REQUIRE(sketch_bytes.get_quantile(median_rank) == expected_median);
}
diff --git a/req/include/req_sketch.hpp b/req/include/req_sketch.hpp
index 715483f..4406ee3 100755
--- a/req/include/req_sketch.hpp
+++ b/req/include/req_sketch.hpp
@@ -22,7 +22,7 @@
#include "req_common.hpp"
#include "req_compactor.hpp"
-#include "quantile_calculator.hpp"
+#include "quantile_sketch_sorted_view.hpp"
#include <stdexcept>
@@ -180,8 +180,9 @@ public:
* @param rank the given normalized rank
* @return approximate quantile given the normalized rank
*/
+ using quantile_return_type = typename quantile_sketch_sorted_view<T, Comparator, Allocator>::quantile_return_type;
template<bool inclusive = false>
- const T& get_quantile(double rank) const;
+ quantile_return_type get_quantile(double rank) const;
/**
* Returns an array of quantiles that correspond to the given array of normalized ranks.
@@ -314,6 +315,9 @@ public:
const_iterator begin() const;
const_iterator end() const;
+ template<bool inclusive = false>
+ quantile_sketch_sorted_view<T, Comparator, Allocator> get_sorted_view(bool cumulative) const;
+
private:
Allocator allocator_;
uint16_t k_;
@@ -345,13 +349,6 @@ private:
static double get_rank_ub(uint16_t k, uint8_t num_levels, double rank, uint8_t num_std_dev, uint64_t n, bool hra);
static bool is_exact_rank(uint16_t k, uint8_t num_levels, double rank, uint64_t n, bool hra);
- using QuantileCalculator = quantile_calculator<T, Comparator, Allocator>;
- using AllocCalc = typename std::allocator_traits<Allocator>::template rebind_alloc<QuantileCalculator>;
- class calculator_deleter;
- using QuantileCalculatorPtr = typename std::unique_ptr<QuantileCalculator, calculator_deleter>;
- template<bool inclusive>
- QuantileCalculatorPtr get_quantile_calculator() const;
-
// for deserialization
class item_deleter;
req_sketch(uint16_t k, bool hra, uint64_t n, std::unique_ptr<T, item_deleter> min_value, std::unique_ptr<T, item_deleter> max_value, std::vector<Compactor, AllocCompactor>&& compactors);
diff --git a/req/include/req_sketch_impl.hpp b/req/include/req_sketch_impl.hpp
index 2aeabf0..e4755ed 100755
--- a/req/include/req_sketch_impl.hpp
+++ b/req/include/req_sketch_impl.hpp
@@ -231,14 +231,15 @@ auto req_sketch<T, C, S, A>::get_CDF(const T* split_points, uint32_t size) const
template<typename T, typename C, typename S, typename A>
template<bool inclusive>
-const T& req_sketch<T, C, S, A>::get_quantile(double rank) const {
+auto req_sketch<T, C, S, A>::get_quantile(double rank) const -> quantile_return_type {
if (is_empty()) return get_invalid_value();
if (rank == 0.0) return *min_value_;
if (rank == 1.0) return *max_value_;
if ((rank < 0.0) || (rank > 1.0)) {
throw std::invalid_argument("Rank cannot be less than zero or greater than 1.0");
}
- return *(get_quantile_calculator<inclusive>()->get_quantile(rank));
+ // possible side-effect of sorting level zero
+ return get_sorted_view<inclusive>(true).get_quantile(rank);
}
template<typename T, typename C, typename S, typename A>
@@ -246,8 +247,11 @@ template<bool inclusive>
std::vector<T, A> req_sketch<T, C, S, A>::get_quantiles(const double* ranks, uint32_t size) const {
std::vector<T, A> quantiles(allocator_);
if (is_empty()) return quantiles;
- QuantileCalculatorPtr quantile_calculator_ptr(nullptr, calculator_deleter(allocator_));
quantiles.reserve(size);
+
+ // possible side-effect of sorting level zero
+ auto view = get_sorted_view<inclusive>(true);
+
for (uint32_t i = 0; i < size; ++i) {
const double rank = ranks[i];
if ((rank < 0.0) || (rank > 1.0)) {
@@ -256,47 +260,26 @@ std::vector<T, A> req_sketch<T, C, S, A>::get_quantiles(const double* ranks, uin
if (rank == 0.0) quantiles.push_back(*min_value_);
else if (rank == 1.0) quantiles.push_back(*max_value_);
else {
- if (!quantile_calculator_ptr) {
- // has side effect of sorting level zero if needed
- quantile_calculator_ptr = const_cast<req_sketch*>(this)->get_quantile_calculator<inclusive>();
- }
- quantiles.push_back(*(quantile_calculator_ptr->get_quantile(rank)));
+ quantiles.push_back(view.get_quantile(rank));
}
}
return quantiles;
}
-template<typename T, typename C, typename S, typename A>
-class req_sketch<T, C, S, A>::calculator_deleter {
- public:
- calculator_deleter(const AllocCalc& allocator): allocator_(allocator) {}
- void operator() (QuantileCalculator* ptr) {
- if (ptr != nullptr) {
- ptr->~QuantileCalculator();
- allocator_.deallocate(ptr, 1);
- }
- }
- private:
- AllocCalc allocator_;
-};
-
template<typename T, typename C, typename S, typename A>
template<bool inclusive>
-auto req_sketch<T, C, S, A>::get_quantile_calculator() const -> QuantileCalculatorPtr {
+quantile_sketch_sorted_view<T, C, A> req_sketch<T, C, S, A>::get_sorted_view(bool cumulative) const {
if (!compactors_[0].is_sorted()) {
const_cast<Compactor&>(compactors_[0]).sort(); // allow this side effect
}
- AllocCalc ac(allocator_);
- QuantileCalculatorPtr quantile_calculator_ptr(
- new (ac.allocate(1)) quantile_calculator<T, C, A>(n_, ac),
- calculator_deleter(ac)
- );
+ quantile_sketch_sorted_view<T, C, A> view(get_num_retained(), allocator_);
for (auto& compactor: compactors_) {
- quantile_calculator_ptr->add(compactor.begin(), compactor.end(), compactor.get_lg_weight());
+ view.add(compactor.begin(), compactor.end(), 1 << compactor.get_lg_weight());
}
- quantile_calculator_ptr->template convert_to_cummulative<inclusive>();
- return quantile_calculator_ptr;
+
+ if (cumulative) view.template convert_to_cummulative<inclusive>();
+ return view;
}
template<typename T, typename C, typename S, typename A>
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org