tisonkun opened a new pull request, #233: URL: https://github.com/apache/datasketches-rust/pull/233
## Summary - fuse sorted centroid merging with compression for overlapping, fully compressed inputs when T-Digest traverses them in descending order - keep the existing two-pass linear merge for forward compression and disjoint ranges, and retain the stable-sort fallback for buffered or unsorted inputs - extend the ScopeDB-shaped benchmark to cover 8- and 64-row overlapping partial states and pin a 64-state native merge sequence to its existing serialized bytes ## Design Notes T-Digest alternates compression direction. During descending compression, both sorted inputs can be consumed from the end while completed centroids are written backward into the unused tail of the left allocation. This avoids materializing the fully merged array and then scanning it again, without adding another allocation. Forward compression would need to shift unread input or allocate a second buffer. Disjoint ranges also make the existing merge nearly a single-run copy. Those cases intentionally keep the simpler path, making this an adaptive optimization rather than a blanket replacement. Stable ordering remains unchanged: the left side wins descending ties, which is the reverse of the existing ascending order where the right side precedes the left. ## Performance Divan A/B runs compared `main` at `c3c08f9` with this branch on the same machine, using a two-second minimum and 300 samples. Times are medians. | workload | main -> this PR | change | | --- | ---: | ---: | | merge: two overlapping 100k-row digests | 2.080 us -> 1.581 us | 24.0% faster | | compute: 64 overlapping native states, 8 rows/state | 34.75 us -> 31.91 us | 8.2% faster | | compute: 64 overlapping native states, 64 rows/state | 73.50 us -> 65.04 us | 11.5% faster | | compute: 64 disjoint native states, 8 rows/state | 30.66 us -> 29.70 us | effectively neutral | | compute: 64 disjoint native states, 64 rows/state | 64.50 us -> 63.91 us | effectively neutral | Allocation counts and allocated bytes are unchanged. These local microbenchmarks are directional rather than a performance contract. ## Compatibility - the public API and serialized format are unchanged - the 64-state regression snapshot remains byte-for-byte identical to `main` - buffered, unsorted, forward-order, and disjoint merges retain their previous paths -- 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]
