shanielh opened a new pull request, #542: URL: https://github.com/apache/datasketches-cpp/pull/542
Adds `kll_sketch::update(item, weight)`, equivalent to calling `update(item)` `weight` times. This mirrors `update(item, weight)` on the KLL sketches in datasketches-java. ## Behavior - If `weight` is smaller than the free space in level zero, the item is inserted `weight` times as plain updates. No compaction can happen on this path. - Otherwise, the update builds an exact sketch of the weighted item and merges it in. Since an item at level `h` counts as `2^h`, the exact sketch holds one copy of the item at each level whose bit is set in `weight`. Bits above level 60 fold into `weight >> 60` copies at level 60, because level capacities are only defined up to 61 levels. This path costs one merge with a sketch of at most 75 items, however large the weight. - A weight of zero throws `std::invalid_argument`, the same as in Java. NaN items are ignored, as in `update(item)`. - Serialization is unchanged, so a sketch built with weighted updates stays readable by every other implementation. ## Fix included The first commit fixes an infinite loop in `kll_helper::floor_of_log2_of_fraction`. Once `numer >= 2^63`, doubling `denom` overflows to zero before it exceeds `numer`. `ub_on_num_levels(n)` calls this function with the merged stream weight, so any merge that reaches `n >= 2^63` used to hang. A weighted update makes that weight easy to reach. The fix compares `denom` against `numer / 2`, which gives the same result without the overflow. The fix has its own unit cases. ## Tests New sections in `kll_sketch_test.cpp`: - zero weight throws - NaN is ignored - matches repeated updates exactly in exact mode - a single item with a `2^40 + 12345` weight - `UINT64_MAX - 1` weight, with a serialization round trip - large weights merged into a full sketch - 10,000 weighted items in estimation mode, ranks within the k=200 error bound, with a serialization round trip - strings The kll test suite passes on clang (macOS arm64) in a plain debug build and with `-fsanitize=address,undefined`. Companion PR for datasketches-rust: RUST_PR_URL 🤖 Generated with [Claude Code](https://claude.com/claude-code) -- 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]
