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]

Reply via email to