Performance regression introduced by commit 760b93a

[SergioBenitez]

Commits 6a58537 / 760b93a (Thu May 29 19:03:06) introduced a performance regression in std::collections::HashMap insertion. The regression appears to be isolated to instances where the key is a string, but I have only tested with string and integer keys.

I have set up a test benchmark at https://github.com/SergioBenitez/rust-perf-regression that showcases the issue. It inserts 100 string/int key/value pairs into a HashMap. good.sh runs the benchmark using the last good compiler build, 3ec321f, and bad.sh runs the first bad compiler build, 760b93a, assuming rustc from 3ec321f is in /usr/local/good/bin/rustc and rustc from 760b93a is in the current $PATH.

Here are the results on my machine (Core i7-920, 24GB RAM, OS X 10.9.2):

$ ./good.sh (--opt-level=3 test.rs --cfg=good --test -o test.out)
test insert_100 ... bench:      7770 ns/iter (+/- 1294)

$ ./bad.sh (--opt-level=3 test.rs --cfg=bad --test -o test.out)
test insert_100 ... bench:      9443 ns/iter (+/- 1742)

@cmr on IRC suggested adding -Z lto. Here are the results with that flag:

$ ./good.sh (-Z lto --opt-level=3 test.rs --cfg=good --test -o test.out)
test insert_100 ... bench:      7148 ns/iter (+/- 1912)

$ ./bad.sh (-Z lto --opt-level=3 test.rs --cfg=bad --test -o test.out)
test insert_100 ... bench:      9066 ns/iter (+/- 1771)

As can be seen, the binary built from the compiler at 760b93a is about 25% slower than the binary from the compiler at 3ec321f.

[alexcrichton]

This is likely explained in my description of #14538

Due to using a custom trait, the SipHasher implementation has lost its
specialized methods for writing integers. These can be re-added
backwards-compatibly in the future via default methods if necessary, but the
FNV hashing should satisfy much of the need for speedier hashing.

[pnkfelix]

cc me

[thestinger]

The ability to use single-pass hashing instead of state machines is important and seems to be missing or at least not leveraged. At the moment, Rust's SipHash implementation is far slower than a naive C implementation, and that's without getting into the large gains you can get by using SIMD.

but the FNV hashing should satisfy much of the need for speedier hashing.

I don't think that's a satisfactory workaround. In addition to not providing protection against pathological data (DoS attacks), FNV is also a very weak hash and suffers from many collisions even with random inputs. It's also not the default hash, and the out-of-the-box performance is what matters most. AFAIK, a proper SipHash implementation is significantly faster in terms of cycles per byte than FNV, and should be winning on large keys where the initial cost becomes less significant.

[SergioBenitez]

So it's clear, is the current consensus that the issue could be that the default hashing algorithm was switched to FNV from SipHash? If so, what's preventing the switch back?

[pcwalton]

@thestinger What should our hashing API be? I guess it needs to be redesigned?

[brson]

@SergioBenitez no, the default hashing algorithm has not changed.

If there are problems with the SipHash implementation, please file them as seperate issues and let's fix them.

[thestinger]

@pcwalton: Ideally, HashMap wouldn't require hashes to be implemented as a state machine. It can be useful to have that capability, but in the common case a single-pass implementation would be nicer. I haven't fully thought out how this needs to be done via traits, but I think it's doable.

[brson]

I'm untagging all pre-1.0 regressions to repurpose it for stable regressions.

[alexcrichton]

A pretty huge amount of time has changed since this was originally filed, so I'm going to close this as "probably stale", although if numbers still show a regression we should definitely fix!