leerho commented on PR #779: URL: https://github.com/apache/datasketches-java/pull/779#issuecomment-6390251483
Thanks @luciakalf, this is a clean fix with no new dependencies, and the tests are good. It fixes a real bug: `Sort.stableSort` was never actually stable, because the random pivot left centroids with equal means in arbitrary order. As a result, identical input could produce different serialized sketches from run to run. Before we merge, please make two small changes in `TDigestDouble`: 1. **Use `StrictMath.log` instead of `Math.log`** in `ScaleFunction.z()`. The spec lets `Math.log` differ by up to 1 ulp between JVMs and platforms (it's usually an intrinsic). A 1-ulp difference can occasionally flip the `proposedWeight <= ...` test in `merge()`, which changes which centroids get combined. `StrictMath.log` is defined bit-for-bit (fdlibm), so it gives the same result everywhere. 2. **Compute `normalizer` once, before the `while` loop** in `merge()`. Its inputs (`k_ * 2` and `centroidsWeight_`) don't change inside the loop, so the result is bit-identical. It also means one `log` call per merge instead of one per centroid, which more than makes up for `StrictMath.log` being slower than the intrinsic. Please also state the tie-break rule in the Javadoc: centroids are ordered by mean ascending, then weight ascending. Once released, this rule becomes part of the sketch's behavior. **What this achieves:** with these changes, the same sequence of updates and merges should produce byte-identical sketches on any modern JVM (Java 17+, where all floating-point arithmetic is strict and `Math.fma` is exactly specified), on any platform. It does **not** make sketches byte-identical across languages (C++, Go, Rust, Python). Those implementations use a different formula to update a centroid's mean and different `log` implementations, so their results will still differ in the low-order bits. That's expected and isn't something this PR needs to solve. Compatibility: the serialization format is unchanged, and images written before this change still deserialize and merge correctly, in Java and in the other languages. I'll send a note to dev@ describing the tie-break rule so the other language implementations can adopt it if they choose. -- 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]
