The assembly code generated by calling `<[T]>::sort_unstable_by` contains bounds checking code

[EFanZh]

See https://godbolt.org/z/fE18sq4WK, you can find serval calls to the following functions:

• core::panicking::panic
• core::panicking::panic_bounds_check
• core::slice::index::slice_end_index_len_fail
• core::slice::index::slice_index_order_fail
• core::slice::index::slice_start_index_len_fail

To my understanding, if the sorting algorithm implementation is correct, no bounds checking failure will occur, so this might be something we can optimize, but I am not sure how much these bounds checking codes can affect performance or whether it’s worth looking into.

[hkratz]

@rustbot label I-slow T-libs

[leonardo-m]

That sorting code is complex. Unless it's formally proved down, I think it's better to keep some bound tests inside it and be memory safe. Humilty is better than being sorry and on cve.org.

but I am not sure how much these bounds checking codes can affect performance or whether it’s worth looking into.<

This is simple to do, just replacing the array/slice accesses and divisions by variable with their uncheked alternatives, allows to perform tests to measure the performance difference. Often only a (small) subset of the bound tests have some effect on performance.

[ChrisJefferson]

It's quite hard to avoid boundary checks -- for example g++'s std::sort will do out-of-bounds accesses and go UB if the ordering function isn't a strict total ordering. Obviously in Rust it isn't acceptable to do UB just because the sort ordering function isn't right.

[workingjubilee]

As Rust's sort is highly generic, it should also be noted that we cannot simply trust the Eq or Ord impls of the types we are implementing sort_unstable_by for, as well. So we cannot simply replace all the accesses with their unsafe variants. Obviously, the result of incorrect implementations would be a garbage sort, but that's not the problem we're concerned about here. We're only concerned about producing high-quality garbage as fast as possible.

[joboet]

@rustbot claim

[saethlin]

@joboet I just implemented a version of this and went to claim it, you beat me to claim by a few hours.

I'm very interested to see what you come up with. Might even be worth taking a crack at this before looking at what I've done, I resorted to more unsafe than I would prefer.

Here's my attempt: eb53658

[ChrisJefferson]

@saethlin : Have you benchmarked your code? How much (if at all) faster is it?