tisonkun commented on code in PR #582:
URL: https://github.com/apache/datasketches-cpp/pull/582#discussion_r4626659092


##########
kll/include/kll_sketch_impl.hpp:
##########
@@ -193,6 +193,70 @@ void kll_sketch<T, C, A>::update(FwdT&& item) {
   reset_sorted_view();
 }
 
+template<typename T, typename C, typename A>
+template<typename FwdT>
+void kll_sketch<T, C, A>::update(FwdT&& item, uint64_t weight) {
+  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));
+  }

Review Comment:
   `MAX_WEIGHT` (`2^61 - 1`) bounds a single call, but `merge` (`const uint64_t 
final_n = n_ + other.n_;` at line 319) and the small-weight path do not check 
for `uint64_t` overflow on `n_`:
   
   - 5 calls of `update(x, MAX_WEIGHT)` already push `n_ >= 2^63` (producing 
images beyond Java's signed `long` range).
   - 9 calls of `update(x, MAX_WEIGHT)` wrap `n_` modulo `2^64` to `2^61 - 9`. 
Because `kll_helper::sum_the_sample_weights` wraps modulo `2^64` in the same 
way, `assert_correct_total_weight()` still passes on `k = 200`, silently 
leaving a corrupted `get_n()` (and on `k = 8`, accumulating 68+ items at level 
60 eventually throws `"depth > 60"` mid-merge after mutating `min_item_` and 
level zero).
   
   Checking `weight > std::numeric_limits<uint64_t>::max() - n_` (and `other.n_ 
> std::numeric_limits<uint64_t>::max() - n_` in `merge`, analogous to Java's 
`Math.addExact`) before mutating the sketch would prevent silent wraparound.



##########
kll/include/kll_sketch_impl.hpp:
##########
@@ -257,7 +321,7 @@ void kll_sketch<T, C, A>::merge(FwdSk&& other) {
     const uint32_t index = internal_update();
     new (&items_[index]) T(conditional_forward<FwdSk>(other.items_[i]));
   }
-  if (other.num_levels_ >= 2) { merge_higher_levels(other, final_n); }
+  if (other.num_levels_ >= 2) { 
merge_higher_levels(std::forward<FwdSk>(other), final_n); }

Review Comment:
   Forwarding `other` into `merge_higher_levels` only avoids copies on the 
`(self_pop == 0) && (other_pop > 0)` branch in `populate_work_arrays` 
(`kll_sketch_impl.hpp:963`). Once `this` is in estimation mode and has items at 
the same higher level as `other` (`(self_pop > 0) && (other_pop > 0)`, line 
968), `populate_work_arrays` calls the 8-argument 
`kll_helper::merge_sorted_arrays(const T* buf_a, ..., const T* buf_b, ...)` 
(`kll_helper_impl.hpp:164`), which has two issues when an item copy (or 
comparator) throws:
   
   1. `other.items_` is passed as `const T*` without forwarding, so elements 
from `other` are still copy-constructed (`new (&buf_c[c]) T(buf_b[b++])`). In 
addition, `buf_a` (`this->items_`) is also `const T*`, so `new (&buf_c[c]) 
T(std::move(buf_a[a]))` (`kll_helper_impl.hpp:177, 180`) produces `const T&&` 
and invokes `T`'s copy constructor rather than its move constructor right 
before calling `buf_a[a++].~T()`.
   2. If any copy or comparison throws inside `populate_work_arrays`, 
`workbuf`'s deleter (`kll_sketch_impl.hpp:891`) deallocates raw memory without 
destroying the objects already constructed in `workbuf` (leaking them), while 
`this->items_` has already destroyed elements in `levels_[0]..levels_[lvl]` and 
`[levels_[lvl], a)` without updating `levels_`. Subsequent destruction in 
`~kll_sketch()` (`kll_sketch_impl.hpp:146`) then calls `~T()` a second time on 
those destroyed slots (double-free / UB).
   
   The new `fragile_item` test (`kll_sketch_allocation_test.cpp:319`) does not 
reach this branch because `k = 200` with 5 updates stays at `num_levels_ == 1` 
(`self_pop == 0` for all `lvl >= 1`). Changing that fixture to `k = 8` with 9 
initial updates and `weight = 18` reproduces a leak at `fail_at = 5` and an 
ASan double-free in `~kll_sketch()` at `fail_at = 6`.
   
   Taking non-`const` `T* buf_a` in `merge_sorted_arrays` (and forwarding from 
`buf_b` when `other` is an rvalue), along with tracking constructed elements in 
`workbuf` and destroyed slots in `this->items_` on unwind, would close this gap.



##########
kll/include/kll_sketch_impl.hpp:
##########
@@ -193,6 +193,70 @@ void kll_sketch<T, C, A>::update(FwdT&& item) {
   reset_sorted_view();
 }
 
+template<typename T, typename C, typename A>
+template<typename FwdT>
+void kll_sketch<T, C, A>::update(FwdT&& item, uint64_t weight) {
+  if (!check_update_item(item)) { return; }
+  if (weight == 0) throw std::invalid_argument("weight must be at least 1");

Review Comment:
   Throwing on `weight == 0` matches `datasketches-java`'s `KllSketch`, though 
two points may be worth discussing for cross-sketch / cross-language alignment:
   
   1. In `datasketches-rust` (apache/datasketches-rust#293), we made 
`KllSketch::update_with_weight(item, 0)` a no-op to match 
`frequent_items_sketch::update(item, 0)` (which is also a no-op in both Java 
and C++) and `CountMinSketch`, since repeating `update(item)` zero times is 
naturally an identity operation when `weight` is unsigned (e.g., pre-aggregated 
bucket counts that can be 0). Happy to discuss whether we want to keep KLL 
aligned with Java's exception here or align zero-weight handling across 
sketches; we documented the difference explicitly on the Rust side for now.
   2. Because `check_update_item(item)` runs on line 199 before the `weight` 
validation, `sketch.update(NaN, 0)` (and `sketch.update(NaN, MAX_WEIGHT + 1)`) 
returns silently while `sketch.update(1.0f, 0)` throws `std::invalid_argument`.



##########
kll/include/kll_sketch.hpp:
##########
@@ -246,6 +248,20 @@ class kll_sketch {
     template<typename FwdT>
     void update(FwdT&& item);
 
+    /**
+     * Updates this sketch with the given data item repeated the given number 
of times.
+     * The result is equivalent to calling update(item) weight times, at a 
cost that grows
+     * with the logarithm of the weight rather than with the weight itself.

Review Comment:
   Nit: when `weight < levels_[0]` (up to `65,534` for `MAX_K`), `update(item, 
weight)` runs an `O(weight)` copy loop into level zero rather than 
`O(log(weight))`. Describing the two paths (direct level-zero insertion when 
`weight` fits in the remaining free space, and merging a binary-level sketch 
otherwise) would avoid overstating the complexity bound for large `k`.



##########
kll/include/kll_sketch_impl.hpp:
##########
@@ -193,6 +193,70 @@ void kll_sketch<T, C, A>::update(FwdT&& item) {
   reset_sorted_view();
 }
 
+template<typename T, typename C, typename A>
+template<typename FwdT>
+void kll_sketch<T, C, A>::update(FwdT&& item, uint64_t weight) {
+  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
+  reset_sorted_view(); // before any change, so that a failed copy can't leave 
a stale view
+  if (weight < levels_[0]) { // fits into level zero without compaction

Review Comment:
   `internal_update()` only compacts when `levels_[0] == 0`, so `weight == 
levels_[0]` also fits into level zero without compaction. With `<`, hitting the 
exact capacity boundary (for example, `k = 200` with 150 updates followed by 
`update(x, 50)`) takes the merge path and transitions into estimation mode 
(`num_levels_ = 6`, 153 retained items) at `n == k`, whereas 50 plain 
`update(x)` calls keep all 200 items in exact mode. Using `<=` keeps exact mode 
up to `n == k` unless `<` is intentionally kept to mirror Java's guard.



##########
kll/test/kll_sketch_test.cpp:
##########
@@ -845,11 +854,182 @@ TEST_CASE("kll sketch", "[kll_sketch]") {
     REQUIRE(sb.get_n() == 3);
   }
 
+  SECTION("weighted update: zero weight") {
+    kll_float_sketch sketch(200, std::less<float>(), 0);
+    REQUIRE_THROWS_AS(sketch.update(1.0f, 0), std::invalid_argument);
+    REQUIRE(sketch.is_empty());
+  }
+
+  SECTION("weighted update: NaN") {
+    kll_float_sketch sketch(200, std::less<float>(), 0);
+    sketch.update(std::numeric_limits<float>::quiet_NaN(), 1000);
+    REQUIRE(sketch.is_empty());
+  }
+
+  SECTION("weighted update: same as repeated updates in exact mode") {
+    kll_float_sketch weighted(200, std::less<float>(), 0);
+    kll_float_sketch repeated(200, std::less<float>(), 0);
+    for (int i = 1; i <= 15; ++i) {
+      weighted.update(static_cast<float>(i), i);
+      for (int j = 0; j < i; ++j) repeated.update(static_cast<float>(i));
+    }
+    REQUIRE(weighted.get_n() == repeated.get_n());
+    REQUIRE(weighted.get_num_retained() == repeated.get_num_retained());
+    REQUIRE_FALSE(weighted.is_estimation_mode());
+    for (int i = 0; i <= 16; ++i) {
+      REQUIRE(weighted.get_rank(static_cast<float>(i)) == 
repeated.get_rank(static_cast<float>(i)));
+      REQUIRE(weighted.get_rank(static_cast<float>(i), false) == 
repeated.get_rank(static_cast<float>(i), false));
+    }
+  }
+
+  SECTION("weighted update: one item with large weight") {
+    kll_float_sketch sketch(200, std::less<float>(), 0);
+    const uint64_t weight = (1ULL << 40) + 12345;
+    sketch.update(7.0f, weight);
+    REQUIRE(sketch.get_n() == weight);
+    REQUIRE(sketch.get_num_retained() == 7); // number of bits set in the 
weight
+    REQUIRE(sketch.get_min_item() == 7.0f);
+    REQUIRE(sketch.get_max_item() == 7.0f);
+    REQUIRE(sketch.get_rank(7.0f) == 1);
+    REQUIRE(sketch.get_rank(7.0f, false) == 0);
+    REQUIRE(sketch.get_quantile(0.5) == 7.0f);
+
+    uint64_t total_weight = 0;
+    for (auto pair: sketch) total_weight += pair.second;
+    REQUIRE(total_weight == weight);
+  }
+
+  SECTION("weighted update: maximum weight") {
+    kll_float_sketch sketch(200, std::less<float>(), 0);
+    sketch.update(1.0f);
+    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);
+
+    uint64_t total_weight = 0;
+    for (auto pair: sketch) total_weight += pair.second;
+    REQUIRE(total_weight == sketch.get_n());
+
+    auto bytes = sketch.serialize();
+    auto sketch2 = kll_float_sketch::deserialize(bytes.data(), bytes.size(), 
serde<float>(), std::less<float>(), 0);
+    REQUIRE(sketch2.get_n() == sketch.get_n());
+    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));
+    sketch.update(-1.0f, 1000);
+    sketch.update(2000.0f, 3000);
+    REQUIRE(sketch.get_n() == 5000);
+    REQUIRE(sketch.get_min_item() == -1.0f);
+    REQUIRE(sketch.get_max_item() == 2000.0f);
+    REQUIRE(sketch.get_rank(-1.0f) == Approx(0.2).margin(RANK_EPS_FOR_K_200));
+    REQUIRE(sketch.get_rank(2000.0f, false) == 
Approx(0.4).margin(RANK_EPS_FOR_K_200));
+  }
+
+  SECTION("weighted update: estimation mode") {
+    kll_float_sketch sketch(200, std::less<float>(), 0);

Review Comment:
   Nit: seeding `random_utils::random_bit` explicitly at the start of this 
section (as in `weight 1 is a plain update` on line 933) would keep it 
deterministic when executed standalone via Catch2 `-c "weighted update: 
estimation mode"`, instead of testing 10,000 queries against the 99% confidence 
bound `RANK_EPS_FOR_K_200` under a clock-based seed.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to