Pathological performance of .sort() / .sort_unstable()

[lukaslueg]

The following code executes in ~0.03s on 1.79-stable, and ~3.7s on nightly 2024-06-24; very roughly a 100x increase in runtime cost. Increasing the size of the slice increases the runtime cost to 3s vs. ~inf, as you like.

This showed up because some other code of mine started showing pathological behavior, which I traced back to the sort_unstable(); same behavior for .sort(). My guess is that #124032 has something to do with it.

The problem only shows up if usize is embedded in another type. In my code, it's a Cell<Option<usize>> (reasons!...), but the problem readily shows up with a simple newtype as well.

I didn't investigate wether the quadratic-sawtooth-pattern reproduced below is actually part of the problem; its part of the data which originally caused me to investigate.

#[derive(PartialEq, Eq, PartialOrd, Ord)]
struct NewType(usize);

fn main() {
    println!("Hello, world!");

    let mut v = Vec::with_capacity(10000000);
    for i in 0..v.capacity() {
        v.push(NewType(i * ((i + 1) % 4713)));
    }
    v.sort();
}

[orlp]

I cannot reproduce with your example on Apple M2, with rustc 1.81.0-nightly (6b0f4b5ec 2024-06-24), neither with sort() nor sort_unstable().

Can you please give exact reproduction instructions, as well as the platform on which you reproduced the problem?

[LunarLambda]

@lukaslueg do you mean rustup toolchain nightly-2024-06-24 or rustc version 2024-06-24? Also, were you running in debug or release?

Note the difference:

current nightly (2024-06-25)
C:\Users\me>rustc +nightly --version
rustc 1.81.0-nightly (6b0f4b5ec 2024-06-24)

C:\Users\me>rustc +nightly-2024-06-24 --version
rustc 1.81.0-nightly (bcf94dec5 2024-06-23)

EDIT: Can't reproduce with either. x86_64-pc-windows-gnu target, in both debug and release, both sort and sort_unstable respectively have the same performance on today's nightly and yesterday's.

[orlp]

I am also skeptical of your claim that it ran in ~0.03s on 1.79-stable, that is an order of magnitude faster than on my machine, where it takes ~350ms. You have one mighty machine, if true.

[lukaslueg]

The problem turned out to be different profiles wrt to nightly. Sorry to have bothered.