tisonkun opened a new pull request, #282: URL: https://github.com/apache/datasketches-rust/pull/282
Total-weight overflow can silently corrupt sketch state in release builds: a merged REQ sketch can become empty, a T-Digest can retain data with a wrapped total, and a small-integer Count-Min sketch can wrap after only a few weighted updates. KLL already rejects overflow, but its update check runs after changing extrema or compacting retained items. This change rejects overflowing operations before modifying the sketch, using checks at the total-weight boundary. This follows #281 and its discussion of [the Java frequent-items emptiness fix](https://github.com/apache/datasketches-java/pull/770). The broader audit found that preserving a meaningful total weight also matters beyond frequent items; this PR starts from main after #281 was merged. ## Behavior and scope | Sketch | Change | Overflow behavior | | --- | --- | --- | | KLL | Move the existing update check ahead of extrema changes and compaction. The internal insertion path relies on the public update/merge checks. | Update panics; merge already returns an error. | | REQ | Check `n + 1` on update and `n + other.n` on merge. | Update panics; merge returns `InvalidArgument`. | | T-Digest | Check the combined compressed and buffered weight before update/merge changes extrema or takes the buffer. | Update and merge panic, preserving their existing signatures. | | Count-Min | Check the accumulated absolute weight on update/merge, including signed minimum values whose magnitude is unrepresentable. | Update panics; merge returns `InvalidArgument`. | Count-Min needs two related boundary rules: - Every bucket's magnitude is bounded by the total absolute weight. Checking that total protects all bucket additions, so the update and merge loops keep ordinary arithmetic. Deserialization validates the same invariant once, rejecting negative totals and out-of-range bucket magnitudes. Valid negative counters remain supported. - `upper_bound()` clamps to the counter type's maximum if adding the error allowance would overflow. This is a query bound, not saturation of stored counters or weights. Cancellation of signed updates still consumes absolute weight. No public signatures change. The implementation diff spans five files and adds 59 net lines including API documentation. This does not add checks to every internal addition, introduce a shared overflow framework, or constrain Tuple's caller-defined summary arithmetic. Tuple's default policies intentionally delegate to `AddAssign`; a universal checked-arithmetic requirement would change that generic contract. Frequent items is already handled by #281. The bounded retained-state/register counters in the other sketch families are outside this total-stream-weight change. ## Is this worth checking? The practical case is strongest for Count-Min: `u8` only holds 255 total units, `i8` holds 127 absolute units, and explicit weights can reach the limit immediately. Applications can choose a wider type or use the existing unsigned decay/halving operations. For the `u64` sketches, ordinary unit updates are extremely unlikely to reach the limit: even one billion updates per second would take about 585 years. Merging changes that calculation. Starting with one item, 63 rounds of doubling and adding one reach `u64::MAX`; one more item or nonempty merge then overflows. These are valid public operations, though repeated doubling is primarily a boundary test and could reflect accidental repeated aggregation rather than a typical production workload. The tests do not require forged serialized data to reach this state. The recommendation is to keep these few boundary checks because overflow destroys the interpretation of the whole sketch, while avoiding a general campaign to check every arithmetic operation. The performance results below do not establish that the checks are free. ## Java and C++ comparison Upstream does not have a uniform "let it overflow" policy. These observations are pinned to Java `37b4b1d` and C++ `70e462f`: | Sketch | Java | C++ | | --- | --- | --- | | KLL | [Items merge uses `Math.addExact`](https://github.com/apache/datasketches-java/blob/37b4b1dd45fc653a223f28b254bf7a5020d34794/src/main/java/org/apache/datasketches/kll/KllItemsHelper.java#L136); [heap Items update increments normally](https://github.com/apache/datasketches-java/blob/37b4b1dd45fc653a223f28b254bf7a5020d34794/src/main/java/org/apache/datasketches/kll/KllHeapItemsSketch.java#L268). | [Update and merge have no explicit overflow check](https://github.com/apache/datasketches-cpp/blob/70e462fcd03977e378c34ca121ba9f40d17ecef3/kll/include/kll_sketch_impl.hpp#L203-L228). | | REQ | [Merge](https://github.com/apache/datasketches-java/blob/37b4b1dd45fc653a223f28b254bf7a5020d34794/src/main/java/org/apache/datasketches/req/ReqSketch.java#L387) and [update](https://github.com/apache/datasketches-java/blob/37b4b1dd45fc653a223f28b254bf7a5020d34794/src/main/java/org/apache/datasketches/req/ReqSketch.java#L453) use unchecked arithmetic. | [Update and merge use unchecked arithmetic](https://github.com/apache/datasketches-cpp/blob/70e462fcd03977e378c34ca121ba9f40d17ecef3/req/include/req_sketch_impl.hpp#L182-L205). | | T-Digest | [Both update and merge use `Math.addExact`](https://github.com/apache/datasketches-java/blob/37b4b1dd45fc653a223f28b254bf7a5020d34794/src/main/java/org/apache/datasketches/tdigest/TDigestDouble.java#L102-L123). | [Compressed weight is accumulated without an explicit check](https://github.com/apache/datasketches-cpp/blob/70e462fcd03977e378c34ca121ba9f40d17ecef3/tdigest/include/tdigest_impl.hpp#L295). | | Count-Min | [Update](https://github.com/apache/datasketches-java/blob/37b4b1dd45fc653a223f28b254bf7a5020d34794/src/main/java/org/apache/datasketches/count/CountMinSketch.java#L243-L247) and [merge](https://github.com/apache/datasketches-java/blob/37b4b1dd45fc653a223f28b254bf7a5020d34794/src/main/java/org/apache/datasketches/count/CountMinSketch.java#L381) use unchecked arithmetic. | [Update](https://github.com/apache/datasketches-cpp/blob/70e462fcd03977e378c34ca121ba9f40d17ecef3/count/include/count_min_impl.hpp#L188-L190) and [merge](https://github.com/apache/datasketches-cpp/blob/70e462fcd03977e378c34ca121ba9f40d17ecef3/count/include/count_min_impl.hpp#L249) use unchecked arithmetic. | Unchecked code is an implementation observation, not a documented promise that wrapping results remain meaningful. Java's signed `long` limits also differ from Rust's `u64` limits. This PR follows Rust's existing method signatures for panic versus returned error and checks before any state mutation. ## Validation and performance - `cargo x check`, `cargo x test` (696 tests including doctests and serialization compatibility), and `cargo x lint` pass. - Six focused overflow regressions also pass under `--release`. Tests cover reaching the exact limit through public operations, rejecting the next update/merge without changing state, pending T-Digest buffers and extrema, Count-Min signed minimum/cancellation, and upper-bound clamping. A serialization regression rejects Count-Min states that would invalidate the arithmetic invariant. - Local commands used `DEVELOPER_DIR=/Library/Developer/CommandLineTools` because the selected Xcode installation required license acceptance; no machine configuration was changed. Existing Divan update workloads were compared with main (`7f4c145`) using separate release binaries on an Apple M4 Max, rustc `1.99.0-nightly (3d6c19bb9)`. Three alternating runs per binary used at least 0.3 seconds per case. Median-of-run-medians for representative cases: | Workload | Main | This PR | Change in time | | --- | ---: | ---: | ---: | | Count-Min u64, 10,000 inputs | 92.62 us | 92.16 us | -0.5% | | KLL, 100,000 inputs | 2.200 ms | 2.238 ms | +1.7% | | REQ, 100,000 inputs | 1.762 ms | 1.751 ms | -0.6% | | T-Digest, 100,000 inputs | 2.459 ms | 2.441 ms | -0.7% | The short T-Digest 1,000-input case initially varied enough to show +7.7%. Longer two-second measurements in before/after/after/before order overlapped: median times were 12.15–12.86 us before and 12.36–12.86 us after; mean times were 12.79–12.80 us before and 12.77–12.87 us after. The corresponding 100,000-input reruns ranged from -0.2% to +2.8% by paired median. This local smoke comparison did not establish a consistent slowdown; it is not a zero-overhead claim or a comprehensive performance study. -- 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]
