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]