leerho opened a new pull request, #582: URL: https://github.com/apache/datasketches-cpp/pull/582
Adds `kll_sketch::update(item, weight)`, equivalent to calling `update(item)` `weight` times. It follows the weighted update of the KLL sketches in datasketches-java. This builds on #542 by Shani Elharrar, whose two commits are kept here unchanged, with fixes on top. ## 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 with one copy of the item at each level whose bit is set in `weight`, and merges it in. This costs one merge with a sketch of at most 61 items, however large the weight. - A weight of 1 is a plain update. A weight of 0, or above 2^61 - 1 (`kll_constants::MAX_WEIGHT`), throws `std::invalid_argument`. These are the same rules as in Java, which cannot read an image with n >= 2^63. - NaN items are ignored, as in `update(item)`. - Serialization is unchanged. ## Fixes on top of #542 - The small-weight path wrote through a null pointer on a new sketch: since #558, the items storage is allocated on first use. The weighted update now allocates first, like `update(item)`, so a failed allocation also leaves the sketch unchanged. - Each copy is constructed before it is counted, so a failed copy leaves a valid sketch. - Weights of 2^61 and above are rejected, as described above, instead of folding the high bits into level 60. ## Also included - `kll_helper::floor_of_log2_of_fraction` looped forever once `numer >= 2^63`, because doubling `denom` overflowed to zero. Any merge that reached n >= 2^63 hung. This is the first commit from #542. Java computes the same bound without a loop, so it is not affected. - The KLL iterator started at level 0 without skipping empty levels. When level zero was empty, which a merge can leave, every item was reported with weight 1. Weighted updates with an even weight leave level zero empty every time, but plain merges hit it too: in 2,000 random merge trials on master, 384 had wrong iterator weights. Quantile queries were not affected, since the sorted view reads the levels directly. Java's iterator skips empty levels and is correct. ## Tests - Weighted update sections in `kll_sketch_test.cpp`: zero weight, NaN, same as repeated updates in exact mode, one item with a large weight, the maximum weight with a serialization round trip, weights above the maximum, weight 1, the first weighted update of a new sketch on both paths, large weights into a full sketch, estimation mode within the k=200 error bound, and strings. - Allocation failures in `kll_sketch_allocation_test.cpp`: a failed first weighted update leaves the sketch unchanged on both paths, and failing each allocation of a stream of weighted updates in turn leaves a valid, usable sketch. - A test that iterator weights sum to n after merges that leave level zero empty. It fails on master. All tests pass under ASan and UBSan. 🤖 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]
