t-digest: deterministic centroid sort rule (mean, then weight) and why cross-language binary compatibility isn't achievable #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 in that compression step, not on how they happen to be arranged in the array or on a random pivot. (This is about the order of centroids within one sort. It does not make the sketch independent of the order in which values arrive; see point 4 below.)
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 centroid sort to also ignore how the centroids are arranged going into each compression step, 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: within a single compression step, 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 would not change: the sketch as a whole still depends on the order in which values arrive (see point 4 below), in every language. "Within-language binary compatibility" here means the same input in the same order gives the same bytes.

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.