Description
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();
}