tisonkun opened a new pull request, #235: URL: https://github.com/apache/datasketches-rust/pull/235
## Summary - stream overlapping sorted centroid buffers directly through T-Digest compression during reverse-order merges - centralize the compression decision in one state machine shared by the regular and fused paths - retain the existing linear two-pass path for forward-order and disjoint merges, plus the stable-sort fallback for buffered or unsorted inputs - preserve serialized output byte-for-byte for a representative 64-state merge sequence This is an alternative implementation of the optimization explored in #233. Its main design difference is that the compression rule has a single owner instead of being duplicated inside the fused merge loop. ## Design Notes T-Digest alternates compression direction. During descending compression, two sorted inputs can be consumed from their ends while completed centroids are written backward into the unused tail of the left allocation. The output cannot overwrite unread left-hand input because the number of completed centroids never exceeds the number of consumed inputs. `CentroidCompression` owns the scale-function boundary and the current centroid. The ordinary in-place compression loop and the fused two-way merge only provide the next centroid and store each completed result. Stable ordering is unchanged: descending traversal takes the left side on ties, which reverses back to the existing right-before-left ascending order. Forward compression would overwrite unread input without another buffer. Disjoint sorted runs are also cheaper on the existing linear materialize-then-compress path. Those cases deliberately remain unchanged. ## Performance Divan A/B runs compare `main` at `c3c08f9` with this branch on the same machine. Times are medians of five-second runs over 64 serialized native states. | workload | main -> this PR | change | | --- | ---: | ---: | | 8 rows/state, overlapping ranges | 34.18 us -> 30.56 us | 10.6% faster | | 64 rows/state, overlapping ranges | 72.35 us -> 63.36 us | 12.4% faster | | 8 rows/state, disjoint ranges | 29.35 us -> 28.86 us | effectively neutral | | 64 rows/state, disjoint ranges | 62.98 us -> 63.15 us | effectively neutral | Allocation counts and serialized formats are unchanged. These local microbenchmarks are directional rather than a performance contract. ## Compatibility - no public API or serialized-format changes - native serialized merge regression remains byte-for-byte identical to `main` - buffered, unsorted, forward-order, and disjoint merges keep their prior 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]
