Xuanwo opened a new pull request, #308: URL: https://github.com/apache/datasketches-rust/pull/308
`KllSketch::rank` currently scans every retained item. Use `partition_point` on sorted levels, counting the qualifying prefix and applying the existing level weight. Level zero keeps its linear scan when it is an unsorted update buffer. A shared predicate preserves inclusive/exclusive comparison semantics. ### Benchmark Measured `5945dfe1787b16568442807d1844d11ad6eef4a5` against `675e3e123fda6da19657d345038252b16adc2ebb` on an isolated EC2 c7i.2xlarge (Xeon Platinum 8488C), Rust 1.99.1 release defaults, one process pinned to CPU 2, with warmup and seven alternating pairs. Public `rank` queries use identical saved i64 sketch fixtures; sketch construction/deserialization is outside timing. The main fixture uses k=200 and 100,000 updates. Compile-time constant criteria and runtime criteria are distinct cases. | Rank workload | Before | After | Paired speedup | | --- | ---: | ---: | ---: | | k=200, static exclusive | 253.12 ns | 33.57 ns | 7.52× | | k=200, static inclusive | 282.34 ns | 38.42 ns | 7.34× | | Tiny exact sketch, static inclusive | 5.02 ns | 5.23 ns | 0.96× | | Tiny exact sketch, runtime inclusive | 6.15 ns | 9.48 ns | 0.65× | The runtime-criteria tiny case adds approximately 3 ns (about 50% at this scale); tiny static criteria stay close to baseline. The unchanged update control measured about 2% slower, so no update gain is claimed. Latencies are sample medians; speedups are medians of paired ratios. Targeted checks compare weighted-rank results with a linear retained-item reference, including sorted/unsorted level zero, both criteria, duplicates, and custom ordering. ### Validation On the measured revision: `cargo x prepare-testdata`, `cargo x check`, `cargo x test` (776 passed, 0 failed), and `cargo x lint` all passed. Baseline and candidate targeted-check output matched exactly. -- 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]
