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]

Reply via email to