Tracking issue for release notes of #124032: Replace sort implementations about rust HOT 10 OPEN

Regarding how to communicate the performance improvements, saying ~2x for both stable and unstable sort is somewhat based in reality, however I'd much prefer not to mention a single number x or % improvement, as that depends on the input pattern, input length and input type, and we see in our testing changes ranging from no change at all, all the way up to 17x faster execution. I'd rather we say that the performance improved significantly and link to the relevant section in the design documents that explains our methodology and results for evaluating the change in performance slice::sort and slice::sort_unstable.

from rust.

cc @Voultapher @orlp if you want to have input on the relnotes here.

from rust.

Sketch for the compatibility aspect (not covering the details of the performance improvement):

The implementations of sort functions (sort, sort_by, sort_by_cached_key, sort_by_key, sort_unstable, sort_unstable_by, sort_unstable_by_key) now have higher performance. These functions may now panic if the implementation of Ord or the supplied comparison function is not a total order.

from rust.

select_nth_unstable, select_nth_unstable_by and select_nth_unstable_by_key are also affected. Though we expect to see less impactful performance differences on x86-64, Arm however should see larger improvements as it sees larger improvements for the new unstable partition code.

from rust.

Should probably use these permalinks specifically:

• https://github.com/Voultapher/sort-research-rs/blob/28d0cf339f123bf34b3a2dcea4f5d52e1867cfe3/writeup/driftsort_introduction/text.md#efficient
• https://github.com/Voultapher/sort-research-rs/blob/28d0cf339f123bf34b3a2dcea4f5d52e1867cfe3/writeup/ipnsort_introduction/text.md#efficient

from rust.

Do we have any source of randomness in the unstable sort to ensure it's really unstable (like hashmaps)? If not the compat note could also mention that the order changed in case someone accidentally relied on it.

from rust.

No, we do not, it's deterministic within a version.

from rust.

...and yes, it was in fact the case that someone asserted on this order in a test and the test was regressed as a result.

from rust.

No, we do not, it's deterministic within a version.

We do right now. I don't know if we actually guarantee this, and perhaps we could in the future use randomness for e.g. pivot selection. It's a bit weird because the current stable "current implementation" notes mention determinism, but.. well, it's in the "current implementation" section, not general guarantees.

from rust.

Should probably use these permalinks specifically:

It can be useful to have the ability to fix typos. I plan on keeping these links stable.

from rust.