Repository: rust
Issue: Bad optimisation of slice equality across platforms and architectures.
Labels: I-slow

All of the information found here can be found and reproduced [here](https://github.com/OMGtechy/memcmp-issue).

The context for finding this problem is this: I was experimenting with string searching algorithms as a way of learning Rust, but when refactoring some code, hit a big performance regression.

The code having performance issues is a naive string search. It can be reproduced with different implementations, but I feel this one expresses things most concisely:
```rust
pub fn naive_search_manual(haystack: &[u8], needle: &[u8]) -> Option<usize> {
    if needle.is_empty() {
        return Some(0usize);
    }

    haystack.windows(needle.len()).position(|candidate| {
        for i in 0..candidate.len() {
            if needle[i] != candidate[i] {
                return false;
            }
        }

        return true;
    })
}
```
Let's call the above the "manual search." The compiler correctly recognises that `i` will never be out of bounds, since the window size is `needle`'s length and therefore `candidate` is always the same size as the needle. All is well so far. However, this is just doing simple equality testing ... why not just check for equality?
```rust
pub fn naive_search_equality(haystack: &[u8], needle: &[u8]) -> Option<usize> {
    if needle.is_empty() {
        return Some(0usize);
    }

    haystack.windows(needle.len()).position(|candidate| candidate == needle)
}
```
Much cleaner. However ...
```
test bench_equality ... bench:         341 ns/iter (+/- 140)
test bench_manual   ... bench:         175 ns/iter (+/- 11)
```
The performance is attrocious compared with the prior implementation. What's going on?

After running a profiler on it, I saw some calls out to VC++ libraries in the slow version that were not present in the fast version. Thinking there might be some performance hazard in the Rust FFI hopping back and forth to so frequently, I tried statically linking things. The VC++ libraries disappeared from the profile, but the performance issue did not. All I saw was a huge amount of time spent in `memcmp`.

After talking to some people on the Rust Language Community Discord server (https://discord.com/invite/rust-lang-community) - I thought it might be a Windows issue and did some investigation. I came across https://github.com/rust-lang/rust/issues/90360, which looked similar to what I was seeing. However, just to be sure, I checked on other platforms.

It reproduced on Linux (inside a docker instance). Assuming this was some quirk of docker on Windows, I tried it on my M1 Mac. It reproduced again. This does not appear to restricted to Windows at all.

The rustc version used is the same on each platform (except the host, of course)
```
rustc 1.57.0 (f1edd0429 2021-11-29)
binary: rustc
commit-hash: f1edd0429582dd29cccacaf50fd134b05593bd9c
commit-date: 2021-11-29
host: [ ... snip ... ]
release: 1.57.0
LLVM version: 13.0.0
```
The hosts are:
```
host: x86_64-pc-windows-msvc
host: x86_64-unknown-linux-gnu
host: aarch64-apple-darwin
```
The disassembly for each can be found in the repo linked at the start of this issue. The docker variant doesn't use `memcmp`, but does use `bcmp`.