par_sort_unstable_by_cached_key?

[FranklinYu]

For rayon::slice::ParallelSliceMut I saw both par_sort_by_cached_key and par_sort_unstable_by_key. Is there a version that is both unstable and cached?

[cuviper]

Usually an unstable version is desirable because it can be faster and not allocate additional memory. Here, the "cached key" already requires an allocation proportional to the slice length, and then it actually uses par_sort_unstable internally. It keeps stability because that cache also includes the original indices, so we're really sorting (key, index).

I suppose a par_sort_unstable_by_cached_key could ignore the index for slightly faster comparisons, but I'm not sure how much benefit that would really bring.

These properties are identical to the various sorting methods in the standard library. I see that an unstable version was considered in rust-lang/rust#34447 (comment), but I guess nobody thought of ignoring the index in the inner sort. Would you be interested in proposing this for the standard library first?

You could also experiment with that change yourself, as both the std and rayon implementations of this function are fairly short implementations around the inner sort algorithm. Maybe just use a newtype Wrapper(key, index) that only compares the key, and leave the rest the same.

[FranklinYu]

I see, so the performance benefit would be marginal. I can imagine that. Thanks for detailed explanation! I’ll close this for now, but if people find it otherwise (e.g. benchmarking) feel free to reopen.