leerho opened a new issue, #780: URL: https://github.com/apache/datasketches-java/issues/780
This issue records a t-digest change in datasketches-java (PR #779, issue #739) and the sorting rule it establishes. The change is backward compatible and needs no action from the other language implementations; the rule is written down here so any implementation that adopts it later uses exactly the same one. ## The problem in Java When a t-digest compresses, it sorts the centroids by mean and then walks them in order, combining neighbors. Java's `Sort.stableSort` wasn't actually stable: it's a quicksort with a random pivot, so centroids with equal means but different weights came out in an arbitrary order. As a result, feeding Java identical input in identical order could produce different serialized sketches, and slightly different quantiles, from one run to the next. The PR author built the same sketch 8 times from 200,000 values with many duplicates and got 8 different images. C++, Go and Rust don't have this bug. They use true stable sorts, so they are already repeatable. ## What Java is doing 1. Centroids are sorted by **mean ascending, then weight ascending**. Two centroids that match on both can't be told apart, so the sort's output depends only on which centroids are present, not on their input order or a random pivot. 2. The scale function uses `StrictMath.log` instead of `Math.log`. `Math.log` may differ by 1 ulp between JVMs, which can occasionally change which centroids get combined. 3. The scale-function normalizer is computed once per merge rather than once per centroid. The result is identical; it just removes the cost of `StrictMath.log`. With these changes, the same sequence of updates and merges should produce byte-identical sketches on any Java 17+ JVM and on any platform. There are no compatibility issues: - The serialization format is unchanged. - Centroids are still written sorted by mean; only the order among equal means changes, and no implementation validates that order. - Old images, and images from any language, still deserialize and merge correctly. ## For the other languages (optional) If C++, Go, Rust or Python want their sort to also ignore input order, please adopt the **same** rule: mean ascending, then weight ascending. Each language's change would be backward compatible in the same way. What it would gain you: the result no longer depends on how the merge assembled the centroids (buffer first vs. centroids first, etc.). You are already repeatable for identical input in identical order, so this is a small improvement, not a fix. What it won't gain you: byte-identical results across platforms within your own language. That also depends on your math library and compiler: - C++: `std::log` varies by libm, and options like FMA contraction (`-ffp-contract`) or `-ffast-math` change the low bits. - Rust: `f64::ln` calls the platform libm. - Go: `math.Log` is pure Go and portable, but the Go compiler may fuse `x*y + z` into an FMA on some architectures. Effort: a comparator change in C++ and Go (Python follows C++). Rust needs more work, because its fast merge path is built to preserve the stable tie order. ## Why byte-identical images across languages aren't achievable for t-digest We should not promise byte-level compatibility across languages for this sketch, even with a shared sort rule: 1. **Different formulas for updating a centroid's mean.** Java and Rust compute `fma(delta, w/W, mean)`. C++ and Go compute `mean + (delta * w) / W`. These round differently, so the stored means differ in the last bits. 2. **Different `log` implementations.** The scale function calls `log` (Java `StrictMath`, glibc/MSVC/Apple libm in C++ and Rust, pure Go in Go). A 1-ulp difference can flip the threshold test that decides whether two centroids combine, and after that the sketches diverge structurally, not just in rounding. 3. **Compiler and platform floating-point behavior** in C++, Rust and Go (FMA contraction, fast-math), as described above. 4. **Arrival order matters in every language.** Buffer flushes happen at points that depend on the order values arrive, so even identical arithmetic gives different sketches for the same data in a different order. In principle, items 1–3 could be fixed by having every language use one specified formula, a portable correctly rounded `log`, and strict compiler settings. That's a lot of work across all the implementations, and the payoff is small: t-digest is an approximate sketch, and what we actually guarantee across languages is that each one can read and merge the others' images with the expected accuracy. Our cross-language tests check exactly that, and they will keep passing. Discussion: see the dev@ thread. Unless there are objections, the plan is to merge #779 once the two small changes above are in. -- 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]
