Performance regression

[retep998]

When moving from the June 20 to the June 26 nightly, this code became twice as slow (comparison of ASM included):

https://gist.github.com/retep998/bf4fd704bbd456912c22

Went from 250 microseconds to 500 microseconds.

My build command: rustc.exe --opt-level=3 euler.rs --test --emit=asm,link -Ctarget-cpu=amdfam10 -Cllvm-args="--x86-asm-syntax=intel"

Using Windows 8.1 x64 with an AMD Phenom II processor.

[Blei]

cc @dotdash, there's a suspicion that it's caused by the bool -> i1 conversion.

[retep998]

Okay, I have narrowed it down specifically to let mut sieve = Vec::from_elem(size, true); For some reason, that bit of code is responsible for almost all the time taken by that function. The old version simply ran memset across the Vec, while the new version is iterating over the entire Vec storing 1 in each element manually.

[mahkoh]

    let mut sieve = Vec::with_capacity(size);
    unsafe {
        let p = sieve.as_mut_ptr();
        std::ptr::set_memory(p, 1, size);
        sieve.set_len(size);
    }

This generates code with memset. And it is much, much slower than the code that stores the 1s by hand. Lots of pagefaults too.

[dotdash]

@mahkoh that code is almost three times faster that storing the ones for me.

Original:

running 1 test
test bench_p3 ... bench:    315992 ns/iter (+/- 1850)

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

With your "hack":

running 1 test
test bench_p3 ... bench:    138248 ns/iter (+/- 304)

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

[mahkoh]

Ha, you're right. It's the same here. I didn't realize that rust would change the benchmark depending on the results. I was looking at the output of perf only.

[dotdash]

LLVM's LoopIdionRecognize pass currently only considers integers that are byte width multiples, i.e. i8, i16 and so on, when looking for opportunities to replace stores by a memset. I've modified the relevant places to also accept values with a bitwidth < 8. With that, at least opt generates memset calls again, but it's just a hack so far and still crashes in the LLVM test suite. Also, we'll have to see what upstream thinks of this. I'll try to refine the patch this weekend and submit it to upstream then.

[dotdash]

Actually, the test suite crash was just my fragile "debugging" code. Removing that made it pass the test suite. So I'll test the new patched LLVM version with rustc tomorrow and submit the patch upstream if it works as expected.

@retep998 Thanks for spotting this!

[dotdash]

Just a small update since this takes longer than expected / "announced" ;-)

Looking through LLVM's code I noticed a few more optz that won't trigger with i1 used for the in-memory representation of boolean value. Extendind all those places to handle i1 isn't trivial and IMHO not worth the trouble.

Also, I realized that I actually misread the comment in the clang sources that made me use i1 for the memory representation of boolean value, instead of just for the SSA values. The latter is what clang does and means that the value is truncated on loads and zero-extended on stores.

The difference from what rust used to do, is that it happens on load and store instead of e.g. br. IOW it depends on where the value lives, not on its current usage. I'm now working on a patch to replicate clang's behaviour in rustc.