This is an automated email from the ASF dual-hosted git repository. leerho pushed a commit to branch kll-weighted-update in repository https://gitbox.apache.org/repos/asf/datasketches-cpp.git
commit 2bdae6ddee051172a4ec2cb7bc625d68977ac7f9 Author: Lee Rhodes <[email protected]> AuthorDate: Sun Nov 15 10:57:01 2026 -0800 KLL weighted update: match datasketches-java, allocate before writing - Reject weights above 2^61 - 1 (kll_constants::MAX_WEIGHT), as datasketches-java does, instead of folding the high bits into level 60. Java cannot read an image with n >= 2^63. - Allocate the items storage before writing into it. Since items are allocated lazily, the small-weight path wrote through a null pointer on a new sketch. Allocating first also leaves the sketch unchanged when the allocation fails. - Construct each copy before counting it, so that a failed copy leaves a valid sketch. - A weight of 1 is a plain update, as in Java. - Check the item before the weight, as in Java. - Tests: the maximum weight, weights above it, weight 1, the first weighted update of a new sketch on both paths, and allocation failures. Co-Authored-By: Claude Opus 5.5 <[email protected]> --- kll/include/kll_sketch.hpp | 6 +++- kll/include/kll_sketch_impl.hpp | 27 ++++++++++++------ kll/test/kll_sketch_allocation_test.cpp | 49 +++++++++++++++++++++++++++++++++ kll/test/kll_sketch_test.cpp | 40 +++++++++++++++++++++++++-- 4 files changed, 111 insertions(+), 11 deletions(-) diff --git a/kll/include/kll_sketch.hpp b/kll/include/kll_sketch.hpp index 6e1b7f43..f7011c74 100644 --- a/kll/include/kll_sketch.hpp +++ b/kll/include/kll_sketch.hpp @@ -39,6 +39,8 @@ namespace kll_constants { const uint16_t MIN_K = DEFAULT_M; /// max value of parameter K const uint16_t MAX_K = (1 << 16) - 1; + /// maximum weight of a weighted update, the same as in datasketches-java + const uint64_t MAX_WEIGHT = (1ULL << 61) - 1; } /** @@ -252,8 +254,10 @@ class kll_sketch { * with the logarithm of the weight rather than with the weight itself. * If cross-language portability is required, callers should ensure that * the input string uses a compatible encoding (valid UTF-8). + * The first update allocates storage for items, unless reserve() or a merge already did. * @param item from a stream of items - * @param weight number of times the item is repeated, must be positive + * @param weight number of times the item is repeated, from 1 to kll_constants::MAX_WEIGHT (2^61 - 1) + * @throw std::invalid_argument if the weight is 0 or greater than kll_constants::MAX_WEIGHT */ template<typename FwdT> void update(FwdT&& item, uint64_t weight); diff --git a/kll/include/kll_sketch_impl.hpp b/kll/include/kll_sketch_impl.hpp index b51da6bd..c31574e5 100644 --- a/kll/include/kll_sketch_impl.hpp +++ b/kll/include/kll_sketch_impl.hpp @@ -196,12 +196,25 @@ void kll_sketch<T, C, A>::update(FwdT&& item) { template<typename T, typename C, typename A> template<typename FwdT> void kll_sketch<T, C, A>::update(FwdT&& item, uint64_t weight) { - if (weight == 0) throw std::invalid_argument("weight must be positive"); if (!check_update_item(item)) { return; } + if (weight == 0) throw std::invalid_argument("weight must be at least 1"); + if (weight > kll_constants::MAX_WEIGHT) { + throw std::invalid_argument("weight must be less than 2^61: " + std::to_string(weight)); + } + if (weight == 1) { + update(std::forward<FwdT>(item)); + return; + } + allocate_items(); // first, so that a failure leaves the sketch unchanged if (weight < levels_[0]) { // fits into level zero without compaction update_min_max(static_cast<const T&>(item)); - for (uint64_t i = 1; i < weight; ++i) new (&items_[internal_update()]) T(static_cast<const T&>(item)); - new (&items_[internal_update()]) T(std::forward<FwdT>(item)); + // construct each copy before counting it, so that a failed copy leaves a valid sketch + for (uint64_t i = 1; i < weight; ++i) { + new (&items_[levels_[0] - 1]) T(static_cast<const T&>(item)); + internal_update(); + } + new (&items_[levels_[0] - 1]) T(std::forward<FwdT>(item)); + internal_update(); reset_sorted_view(); } else { merge(kll_sketch(k_, static_cast<const T&>(item), weight, comparator_, allocator_)); @@ -210,8 +223,7 @@ void kll_sketch<T, C, A>::update(FwdT&& item, uint64_t weight) { // An item at level h carries weight 2^h, so one copy of the item at each level // whose bit is set in the weight is an exact sketch of that many copies. -// Level capacities are defined up to 61 levels, so bits above the top level -// fold into weight >> 60 copies at level 60. +// The weight is less than 2^61, so this needs at most 61 levels. template<typename T, typename C, typename A> kll_sketch<T, C, A>::kll_sketch(uint16_t k, const T& item, uint64_t weight, const C& comparator, const A& allocator): comparator_(comparator), @@ -219,7 +231,7 @@ allocator_(allocator), k_(k), m_(kll_constants::DEFAULT_M), min_k_(k), -num_levels_(std::min<uint8_t>(64 - count_leading_zeros_in_u64(weight), 61)), +num_levels_(static_cast<uint8_t>(64 - count_leading_zeros_in_u64(weight))), is_level_zero_sorted_(true), n_(weight), levels_(num_levels_ + 1, 0, allocator), @@ -230,8 +242,7 @@ max_item_(item), sorted_view_(nullptr) { for (uint8_t level = 0; level < num_levels_; ++level) { - const uint64_t count = level + 1 < num_levels_ ? (weight >> level) & 1 : weight >> level; - levels_[level + 1] = levels_[level] + static_cast<uint32_t>(count); + levels_[level + 1] = levels_[level] + static_cast<uint32_t>((weight >> level) & 1); } items_size_ = levels_[num_levels_]; items_ = allocator_.allocate(items_size_); diff --git a/kll/test/kll_sketch_allocation_test.cpp b/kll/test/kll_sketch_allocation_test.cpp index a098b5a9..d04a7841 100644 --- a/kll/test/kll_sketch_allocation_test.cpp +++ b/kll/test/kll_sketch_allocation_test.cpp @@ -227,4 +227,53 @@ TEST_CASE("kll sketch allocation: failure at each allocation of the updates", "[ REQUIRE(test_allocator_net_allocations == 0); } +TEST_CASE("kll sketch allocation: failed first weighted update leaves the sketch unchanged", "[kll_sketch]") { + test_allocator_total_bytes = 0; + test_allocator_net_allocations = 0; + { + allocation_control control; + const failing_allocator<std::string> alloc(control); + const kll_string_failing_sketch fresh(200, std::less<std::string>(), alloc); + for (const uint64_t weight: {uint64_t(10), uint64_t(1000)}) { // copies into level zero, and a merge + kll_string_failing_sketch sketch(200, std::less<std::string>(), alloc); + control.arm(0); + REQUIRE_THROWS_AS(sketch.update(item(1), weight), std::bad_alloc); + check_empty(sketch, fresh); + control.disarm(); + sketch.update(item(2), weight); + REQUIRE(sketch.get_n() == weight); + REQUIRE(sketch.get_min_item() == item(2)); + } + } + REQUIRE(test_allocator_total_bytes == 0); + REQUIRE(test_allocator_net_allocations == 0); +} + +// Fail each allocation made by a stream of weighted updates in turn: the sketch must stay valid and usable. +TEST_CASE("kll sketch allocation: failure at each allocation of the weighted updates", "[kll_sketch]") { + test_allocator_total_bytes = 0; + test_allocator_net_allocations = 0; + { + allocation_control control; + const failing_allocator<std::string> alloc(control); + const kll_string_failing_sketch fresh(8, std::less<std::string>(), alloc); + bool completed = false; + for (long fail_at = 0; !completed; ++fail_at) { + kll_string_failing_sketch sketch(8, std::less<std::string>(), alloc); + control.arm(fail_at); + try { + for (int i = 0; i < 300; ++i) sketch.update(item(i), static_cast<uint64_t>(i % 7) * 100 + 1); + completed = true; + REQUIRE(fail_at > 0); + } catch (const std::bad_alloc&) { + if (fail_at == 0) check_empty(sketch, fresh); + check_usable(sketch, control); + } + control.disarm(); + } + } + REQUIRE(test_allocator_total_bytes == 0); + REQUIRE(test_allocator_net_allocations == 0); +} + } /* namespace datasketches */ diff --git a/kll/test/kll_sketch_test.cpp b/kll/test/kll_sketch_test.cpp index fc09505c..2e55d79c 100644 --- a/kll/test/kll_sketch_test.cpp +++ b/kll/test/kll_sketch_test.cpp @@ -896,8 +896,8 @@ TEST_CASE("kll sketch", "[kll_sketch]") { SECTION("weighted update: maximum weight") { kll_float_sketch sketch(200, std::less<float>(), 0); sketch.update(1.0f); - sketch.update(2.0f, std::numeric_limits<uint64_t>::max() - 1); - REQUIRE(sketch.get_n() == std::numeric_limits<uint64_t>::max()); + sketch.update(2.0f, kll_constants::MAX_WEIGHT); + REQUIRE(sketch.get_n() == kll_constants::MAX_WEIGHT + 1); REQUIRE(sketch.get_min_item() == 1.0f); REQUIRE(sketch.get_max_item() == 2.0f); REQUIRE(sketch.get_quantile(0.5) == 2.0f); @@ -912,6 +912,42 @@ TEST_CASE("kll sketch", "[kll_sketch]") { REQUIRE(sketch2.get_num_retained() == sketch.get_num_retained()); } + SECTION("weighted update: weight above the maximum throws") { + kll_float_sketch sketch(200, std::less<float>(), 0); + sketch.update(1.0f, 5); + const auto bytes = sketch.serialize(); + REQUIRE_THROWS_AS(sketch.update(2.0f, kll_constants::MAX_WEIGHT + 1), std::invalid_argument); + REQUIRE_THROWS_AS(sketch.update(2.0f, std::numeric_limits<uint64_t>::max()), std::invalid_argument); + REQUIRE(sketch.serialize() == bytes); + } + + SECTION("weighted update: weight 1 is a plain update") { + kll_float_sketch weighted(8, std::less<float>(), 0); + kll_float_sketch plain(8, std::less<float>(), 0); + random_utils::random_bit.seed(7); + for (int i = 0; i < 1000; ++i) weighted.update(static_cast<float>(i), 1); + random_utils::random_bit.seed(7); + for (int i = 0; i < 1000; ++i) plain.update(static_cast<float>(i)); + REQUIRE(weighted.serialize() == plain.serialize()); + } + + SECTION("weighted update: first update of a new sketch, both paths") { + // small weight: copies into level zero of the storage that this update allocates + kll_float_sketch small(200, std::less<float>(), 0); + small.update(3.0f, 10); + REQUIRE(small.get_n() == 10); + REQUIRE(small.get_num_retained() == 10); + REQUIRE(small.get_min_item() == 3.0f); + // large weight: merges an exact sketch of the item + kll_float_sketch large(200, std::less<float>(), 0); + large.update(3.0f, 1000); + REQUIRE(large.get_n() == 1000); + REQUIRE(large.get_max_item() == 3.0f); + uint64_t total_weight = 0; + for (auto pair: large) total_weight += pair.second; + REQUIRE(total_weight == 1000); + } + SECTION("weighted update: large weights into a full sketch") { kll_float_sketch sketch(200, std::less<float>(), 0); for (int i = 0; i < 1000; ++i) sketch.update(static_cast<float>(i)); --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
