Perf regression with LLVM 16 for `slice::sort`

[Voultapher]

Code

I tried this code, sorting 30 million random u64:

fn main() {
    use std::time::Instant;

    let mut v = sort_test_tools::patterns::random(30_000_000)
        .into_iter()
        .map(|e| e as u64)
        .collect::<Vec<u64>>();

    let start = Instant::now();
    sort_comp::stable::rust_std::sort(&mut v);

    let diff = start.elapsed().as_millis();

    if diff >= 1720 {
        panic!();
    }
}

On this machine:

Linux 6.3.1
AMD Ryzen 9 5900X 12-Core Processor (Zen3 micro-architecture)

Using the vendored version of slice::sort from mid 2022 see here https://github.com/Voultapher/sort-research-rs/blob/d3bab202e18a2010e26674677e90ae3048721232/src/stable/rust_std.rs

I expected to see this happen: Runtime ~1.45s

Instead, this happened: Runtime ~2s

Version it worked on

rustc 1.70.0-nightly (8be3c2bda 2023-03-24)
binary: rustc
commit-hash: 8be3c2bda6b683f87b24714ba595e8b04faef54c
commit-date: 2023-03-24
host: x86_64-unknown-linux-gnu
release: 1.70.0-nightly
LLVM version: 15.0.7

Version with regression

rustc 1.70.0-nightly (0c61c7a97 2023-03-25)
binary: rustc
commit-hash: 0c61c7a978fe9f7b77a1d667c77d2202dadd1c10
commit-date: 2023-03-25
host: x86_64-unknown-linux-gnu
release: 1.70.0-nightly
LLVM version: 16.0.0

---

I bisected the issue down to 0c61c7a with cargo bisect-rustc --start=2022-12-07 --end=2023-05-13 --script=./test.sh.

---

The same happens if you do v.sort() instead of sort_comp::stable::rust_std::sort(&mut v). So this also affects the current implementation which is very similar to my vendored version.

[Voultapher]

Dinging into it, I think the relevant code that has this impact is in the merge function. Which has two blocks of logic one for if the left side is shorter and one if the right side is shorter. Previously both sides generated code that is branchless in terms of jumping based on the comparison result. Now the block handling left side is shorter generates a jump based on the comparison result.

LLVM 15:

LLVM 16:

This can be fixed in code by using 'proper' branchless code:

let to_copy = if is_less(&*right, &**left) {
    get_and_increment(&mut right)
} else {
    get_and_increment(left)
};
ptr::copy_nonoverlapping(to_copy, get_and_increment(out), 1);

->

let is_l = is_less(&*right, &**left);
let to_copy = if is_l { right } else { *left };
ptr::copy_nonoverlapping(to_copy, get_and_increment(out), 1);
right = right.add(is_l as usize);
*left = left.add(!is_l as usize);

This would fix the stdlib, but it would still mean a regression for any other code out there that relies on this.

[workingjubilee]

I feel like I should attach the usual disclaimer that this kind of optimization can never be considered fully stable, specifically LLVM has various heuristics that affect whether it compiles a segment of code to use a "branchless" CMOV-alike or use a jump, however that doesn't mean there's nothing we can do here.

@rustbot label: +A-LLVM +A-codegen +regression-from-stable-to-beta +I-slow

[apiraino]

WG-prioritization assigning priority (Zulip discussion).

@rustbot label -I-prioritize +P-low +T-compiler

[Voultapher]

@apiraino out of curiosity. What is the future for a perf regression marked as P-low? Is there any work planned on this? Personally I was surprised that it even generated branchless code in the first place.