tisonkun opened a new pull request, #290: URL: https://github.com/apache/datasketches-rust/pull/290
## Summary Rank queries used two custom binary-search comparators followed by insertion-point corrections to select their interpolation anchors. Use `partition_point` to express the two cases directly: adjacent centroids between distinct means, or the first and last centroids in an equal-mean run. Only an exact match needs the second search. The existing tail checks establish the index bounds. Weight accumulation and interpolation remain unchanged. This removes two comparator helpers and 24 lines from the implementation, adds one weighted-repeat boundary test and repeated-mean query benchmarks, and updates the changelog. ## Validation - `cargo x check`, `cargo x test` (746 tests), and `cargo x lint` pass. - `cargo bench --package benchmarks --bench benchmarks -- tdigest::query::rank_repeated_means` passes for all four query values. - External differential probes against `48165ed` cover 4,800 digest states and 6,220,288 query points. Mutable and frozen rank, CDF, PMF, batch quantile results, and serialized bytes match bit-for-bit. Cases include weighted ties, signed zero, extreme finite values, weights near `u64::MAX`, updates, borrowed merges, and owned collection. - The new integration test independently calculates the centers of unequal-weight centroids to verify exact matches at the first, middle, and last equal-mean runs, plus interpolation between runs. Existing assertions and serialization fingerprints are retained. ## Performance Release-mode external probes link the base and candidate libraries into the same executable on Apple ARM64 (`rustc 1.99.0-nightly`, `3d6c19bb9`). Each result is the median of nine rounds with alternating execution order. Setup is outside timing; scalar-query rounds use 500,000 calls, and CDF rounds use 50,000 calls. Unless noted, digests use `k = 200` and 100,000 input values. Uniform inputs retain 264 centroids; repeated inputs cycle through values 0 through 7 and retain 248. Mixed queries use a deterministic mix of centroid means and interval midpoints. | Workload | Base | This PR | | --- | ---: | ---: | | Uniform, rank between middle means | 33.79 ns | 29.24 ns | | Uniform, rank at a middle mean | 32.71 ns | 28.30 ns | | Uniform, mixed rank queries | 37.16 ns | 33.52 ns | | Repeated values, mixed rank queries | 63.58 ns | 57.49 ns | | Uniform, CDF with 100 split points | 2.842 us | 2.055 us | | Repeated values, CDF with 100 split points | 2.173 us | 1.612 us | | 8-value digest, rank at the first mean | 6.94 ns | 7.90 ns | | Uniform, `k = 2000`, mixed rank queries | 173.96 ns | 177.26 ns | The smaller-query and larger-`k` regressions are retained explicitly: this is a simpler anchor lookup with workload-dependent performance, not a universal speedup. Scalar rank still sums preceding weights, so its worst-case complexity remains linear in the retained centroid count. These measurements do not imply an application-wide improvement. -- 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]
