You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@datasketches.apache.org by "tisonkun (via GitHub)" <gi...@apache.org> on 2026/08/24 06:24:37 UTC
[PR] perf(tdigest): reduce allocation overhead during compression (datasketches-rust)
tisonkun opened a new pull request, #209:
URL: https://github.com/apache/datasketches-rust/pull/209
## Summary
- add a Divan benchmark suite with allocation profiling for t-digest update, lifecycle, compression, merge, serialization, deserialization, and query paths
- replace eager `k`-sized reservations with staged buffer growth so short-lived digests allocate in proportion to retained data
- reuse the centroid vector during compression and merge, compact merged centroids in place, and hoist loop-invariant scale normalization
- preserve stable centroid ordering and existing serialized-state behavior
## Benchmarks
Measured with `cargo bench -p datasketches --features tdigest --bench tdigest` on an Apple M4 Max using Rust 1.86.0. Values are medians from release builds.
| Benchmark | `main` | This PR | Change |
| --- | ---: | ---: | ---: |
| 1-value create/update/serialize/drop | 112.6 ns | 57.6 ns | -48.8% |
| 8-value create/update/serialize/drop | 225.6 ns | 112.3 ns | -50.2% |
| 64-value create/update/serialize/drop | 1.230 us | 896.9 ns | -27.1% |
| Serialize 512 64-value partial states | 301.1 us | 151.6 us | -49.7% |
| Deserialize 512 64-value partial states | 164.0 us | 118.0 us | -28.0% |
| Merge 64 64-value partial states | 154.0 us | 96.1 us | -37.6% |
Allocation profiler results for create/update/serialize/drop:
| Values | `main` heap bytes | This PR heap bytes | Change |
| ---: | ---: | ---: | ---: |
| 1 | 19.77 KB | 96 B | -99.5% |
| 8 | 20.09 KB | 352 B | -98.2% |
| 64 | 22.78 KB | 3.10 KB | -86.4% |
The fixed-size cases are synthetic stress points, not estimates of any production distribution. The 64-value update-only benchmark is approximately neutral; the lifecycle improvement comes from avoiding eager centroid allocation and reusing storage during compression and serialization.
This implementation does not change centroid count or serialized bytes for equivalent inputs. The benchmark results therefore demonstrate local CPU and allocator improvements only, not reduced serialized payloads or end-to-end application latency.
## Validation
- `cargo x check`
- `cargo x test`
- `cargo x lint`
- `cargo bench -p datasketches --features tdigest --bench tdigest -- --test`
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] perf(tdigest): reduce allocation overhead during compression (datasketches-rust)
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun commented on code in PR #209:
URL: https://github.com/apache/datasketches-rust/pull/209#discussion_r3841211938
##########
datasketches/src/tdigest/sketch.rs:
##########
@@ -762,54 +795,53 @@ impl TDigestMut {
/// # Contract
///
/// * `buffer` must have at least one centroid.
- /// * `buffer` is generated from `self.buffer`, and thus:
- /// * No `NAN` values are present in `buffer`.
- /// * We should clear `self.buffer` after merging.
+ /// * `buffer` contains all existing centroids and values from `self.buffer`.
+ /// * No `NAN` values are present in `buffer`.
+ /// * We should clear `self.buffer` after merging.
fn do_merge(&mut self, mut buffer: Vec<Centroid>, weight: u64) {
- buffer.extend(std::mem::take(&mut self.centroids));
buffer.sort_by(centroid_cmp);
if self.reverse_merge {
buffer.reverse();
}
self.centroids_weight += weight;
- let mut num_centroids = 0;
+ let mut num_centroids = 1;
let len = buffer.len();
- self.centroids.push(buffer[0]);
- num_centroids += 1;
+ let centroids_weight = self.centroids_weight as f64;
+ let normalizer = scale_function::normalizer((2 * self.k) as f64, centroids_weight);
let mut current = 1;
Review Comment:
Good catch. The expression predated this PR, but hoisting it made the overflow reachable even for a one-value digest. Commit 3e02376 converts k to f64 before multiplication and adds a u16::MAX regression test.
##########
datasketches/src/tdigest/sketch.rs:
##########
@@ -762,54 +795,53 @@ impl TDigestMut {
/// # Contract
///
/// * `buffer` must have at least one centroid.
- /// * `buffer` is generated from `self.buffer`, and thus:
- /// * No `NAN` values are present in `buffer`.
- /// * We should clear `self.buffer` after merging.
+ /// * `buffer` contains all existing centroids and values from `self.buffer`.
+ /// * No `NAN` values are present in `buffer`.
+ /// * We should clear `self.buffer` after merging.
Review Comment:
Good catch. Updated the contract in 3e02376 to cover the centroids supplied by both compress() and merge(), document the weight invariant, and clarify finiteness and buffer clearing.
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] perf(tdigest): reduce allocation overhead during compression (datasketches-rust)
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun merged PR #209:
URL: https://github.com/apache/datasketches-rust/pull/209
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] perf(tdigest): reduce allocation overhead during compression (datasketches-rust)
Posted by "Copilot (via GitHub)" <gi...@apache.org>.
Copilot commented on code in PR #209:
URL: https://github.com/apache/datasketches-rust/pull/209#discussion_r3841179197
##########
datasketches/src/tdigest/sketch.rs:
##########
@@ -762,54 +795,53 @@ impl TDigestMut {
/// # Contract
///
/// * `buffer` must have at least one centroid.
- /// * `buffer` is generated from `self.buffer`, and thus:
- /// * No `NAN` values are present in `buffer`.
- /// * We should clear `self.buffer` after merging.
+ /// * `buffer` contains all existing centroids and values from `self.buffer`.
+ /// * No `NAN` values are present in `buffer`.
+ /// * We should clear `self.buffer` after merging.
Review Comment:
`do_merge`’s contract comment says the `buffer` contains "all existing centroids and values from `self.buffer`", but `merge()` also passes in the other digest’s buffered values and centroids. This makes the contract misleading for future callers/maintainers; consider wording it as “all centroids/values to be merged (including self’s existing centroids and any buffered values from both digests)” or similar.
##########
datasketches/src/tdigest/sketch.rs:
##########
@@ -762,54 +795,53 @@ impl TDigestMut {
/// # Contract
///
/// * `buffer` must have at least one centroid.
- /// * `buffer` is generated from `self.buffer`, and thus:
- /// * No `NAN` values are present in `buffer`.
- /// * We should clear `self.buffer` after merging.
+ /// * `buffer` contains all existing centroids and values from `self.buffer`.
+ /// * No `NAN` values are present in `buffer`.
+ /// * We should clear `self.buffer` after merging.
fn do_merge(&mut self, mut buffer: Vec<Centroid>, weight: u64) {
- buffer.extend(std::mem::take(&mut self.centroids));
buffer.sort_by(centroid_cmp);
if self.reverse_merge {
buffer.reverse();
}
self.centroids_weight += weight;
- let mut num_centroids = 0;
+ let mut num_centroids = 1;
let len = buffer.len();
- self.centroids.push(buffer[0]);
- num_centroids += 1;
+ let centroids_weight = self.centroids_weight as f64;
+ let normalizer = scale_function::normalizer((2 * self.k) as f64, centroids_weight);
let mut current = 1;
Review Comment:
`scale_function::normalizer((2 * self.k) as f64, …)` multiplies two `u16` values before casting, so `k > 32767` will overflow in debug builds (panic) and wrap in release builds, producing an incorrect compression value. To avoid overflow, cast before multiplying (e.g., `2.0 * self.k as f64` or `(2u32 * self.k as u32) as f64`).
--
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: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org