Waterpine opened a new pull request, #332: URL: https://github.com/apache/datasketches-rust/pull/332
## Summary `KllSketch` now does less work per update, merge, deserialization, and sorted-view query. Results of every operation are unchanged: same retained items, same tie order, same serialized bytes, same deserialization errors. On the benchmark machine, updates take 4% to 14% less time, `merge` 22% less, `deserialize` 13% less, and `quantile` and `quantiles` 29% to 31% less (time ratios 0.96 to 0.69, see "Results"). - **Updates:** the total capacity depends only on the number of levels, so a compaction recomputes it only when it adds a level. - **Merges:** `merge` reads the other sketch's levels by reference instead of cloning them first. For item types without drop glue, the sorted merge selects the source with the comparison result instead of branching on it. - **Memory:** when a compaction adds a new top level, that level holds the downsampled half in the compacted level's buffer, about twice its length, and keeps it until the level below compacts again. It is now shrunk to fit, which costs one reallocation per added level. - **Deserialization:** a sorted level lies within its first and last items, so the minimum/maximum check looks at those two and falls back to the full scan only when one of them is out of range. The error names the same first offending item as before. - **Sorted view:** the first merge round combines pairs of levels straight from the sketch instead of copying every level into entries first; later rounds are unchanged. - **Comparisons:** `KllFloat::cmp` uses `<` and `>` instead of `partial_cmp().unwrap()`. Values are never NaN, so the order is the same, without an unreachable panic path. ## Results Main benchmark suite, 8 rounds. The ratio is the time after this change divided by the time before; below 1 is faster. | benchmark | time ratio | | --- | --- | | `kll::update::update/1000` | 0.96 | | `kll::update::update/10000` | 0.88 | | `kll::update::update/100000` | 0.86 | | `kll::merge::merge` | 0.78 | | `kll::serde::deserialize` | 0.87 | | `kll::query::quantile/0.5` | 0.69 | | `kll::query::batch_quantiles` | 0.71 | `kll::query::rank`, `quantile/0.0`, `quantile/1.0`, and `sorted_view_quantile` are unchanged within noise; they do not run the changed code. Additional workloads that are not in the repository's suite (8 rounds, k = 200 unless noted, with a fixed random seed so that both builds draw the same compaction bits): | workload | time ratio | | --- | --- | | update, `f32` / `i64` items, k = 200 | 0.83 / 0.85 | | update, `f64`, k = 8 / k = 1000 | 0.78 / 0.88 | | update, ascending / descending / many equal values | 0.84 / 0.81 / 0.76 | | merge, `f32` / `i64` items | 0.78 / 0.79 | | merge 256 sketches of 500 items into one | 0.91 | | deserialize, `f32` / `i64` items | 0.90 / 0.93 | | deserialize, `f64` k = 1000 | 0.86 | | `quantile`, `f64` k = 1000 | 0.91 | Memory: I measured the exact heap owned by a sketch with a counting allocator and a fixed random seed, so that this branch and `main` draw identical compaction bits. It was sampled after each of the first 20,000 updates (and every 97th update up to 300,000) and after each of 256 merges, for k = 8, 50, 200, 1000, with `f32` and `f64` items and merge parts of 50, 500, and 5,000 items. Of 186,160 samples, none is higher than before; the mean is 4% to 16% lower. ## Scope of the results The gains come from doing less work, not from a CPU feature, but they depend on the workload: - Item types with drop glue gain much less. With `String` items, updates take 1.5% less time, merges 5% less, deserialization 3% less, and `quantile` is not faster (ratio 1.01, possibly about 1% slower), because cloning and comparing strings dominates. - Small sketches gain little: 2,000 updates at k = 200 take 3% less time. - The select-based merge replaces branches that mispredict on unordered input; how much that is worth depends on the CPU's branch predictor. - The extra `shrink_to_fit` adds one reallocation per added level. Merging a 100,000-item sketch into a 100-item sketch measured a time ratio of 1.00 (95% confidence interval 0.90 to 1.12), so I could not detect a cost. - `kll::serde::serialize` measured 1.03 in the repository suite, although this change does not touch it and the machine code generated for it is identical in both builds. I attribute the difference to code placement; a separate probe measured the same function 13% faster. All numbers come from one machine; I have not measured others. ## Checks `cargo x check`, `cargo x lint`, `cargo x test`, and `cargo +1.86.0 check -p datasketches --all-features` pass. Measured on one machine (2x Xeon E5-2660 v3, Linux 6.8) against `main` at `4ba130e` with the repository's benchmark runner (`kll:: --repeat 3`), pinned to one core, with the two builds alternating over 8 rounds; ratios are the geometric mean of per-round median ratios. -- 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]
