Strange Rust heapsort performance difference, missed obvious llvm optimization

[hirschenberger]

I have a strange performance difference on the standard rust heapsort implementation and a trivial modification.
The only difference is in line 15 where the right index is calculated from the left index. I thought this is a trivial optimization for a compiler.

Related gist

running 2 tests
test bench_heapsort_new ... bench:   6,950,925 ns/iter (+/- 283,342)
test bench_heapsort_old ... bench:   7,799,111 ns/iter (+/- 181,397)

rustc 1.18.0-nightly (ddc5d7bd4 2017-04-20)

rustc --test -O slice.rs

[kennytm]

Not reproducible. The two have similar performance here (MacBook Pro). What is your platform?

$ rustc --test -O 1.rs

$ ./1 --bench

running 2 tests
test bench_heapsort_new ... bench:   6,505,975 ns/iter (+/- 805,094)
test bench_heapsort_old ... bench:   6,484,118 ns/iter (+/- 592,318)

test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured

$ ./1 --bench

running 2 tests
test bench_heapsort_new ... bench:   6,365,943 ns/iter (+/- 470,100)
test bench_heapsort_old ... bench:   6,501,713 ns/iter (+/- 725,469)

test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured

$ rustc -vV
rustc 1.18.0-nightly (ddc5d7bd4 2017-04-20)
binary: rustc
commit-hash: ddc5d7bd4b9ea3e8a8ccf82cb443e950be311d61
commit-date: 2017-04-20
host: x86_64-apple-darwin
release: 1.18.0-nightly
LLVM version: 3.9

[hirschenberger]

My platform is x64 Linux on 8core intel xeon.

[afonso360]

Can't reproduce this either
x64 Arch Linux i7-4510U

$ rustc --test -O slice.rs                                                                                                                           
$ ./slice --bench

running 2 tests
test bench_heapsort_new ... bench:   5,890,135 ns/iter (+/- 102,715)
test bench_heapsort_old ... bench:   6,019,368 ns/iter (+/- 69,508)

test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured

$ ./slice --bench

running 2 tests
test bench_heapsort_new ... bench:   5,876,645 ns/iter (+/- 88,551)
test bench_heapsort_old ... bench:   6,017,215 ns/iter (+/- 74,589)

test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured

$ rustc -vV
rustc 1.18.0-nightly (ddc5d7bd4 2017-04-20)
binary: rustc
commit-hash: ddc5d7bd4b9ea3e8a8ccf82cb443e950be311d61
commit-date: 2017-04-20
host: x86_64-unknown-linux-gnu
release: 1.18.0-nightly
LLVM version: 3.9

[leoyvens]

The generated assembly is in fact different between the versions, heapsort_old vs heapsort_new.

[hirschenberger]

I tested it on my Intel(R) Core(TM) i7-5600U CPU @ 2.60GHz notebook.
The impact is not so big here, but the old Version is still 4% slower every time.

[ljedrz]

I'm seeing a ~1% difference in favor of the new variant on my rig.

[hirschenberger]

On the current nightly compiler: rustc 1.39.0-nightly (eb48d6bde 2019-09-12) the old version is faster. I'm closing this because it seems to be irrelevant.