Fix the HashMap Performance

[StefanoD]

See: https://users.rust-lang.org/t/hashmap-performance/6476

[arthurprs]

Here're are my results with latest nightly.

Simple in this case is the same strategy used by unordered_map, just return the integer as the hash. C++ does even more trickery with it's templates and for integers it won't even store the hash, making it more concise in memory.

Anyway, we're actually faster using the simple hasher.

Code: https://gist.github.com/arthurprs/88eef0b57b9f8341c54e2d82ec775698

2000
SIP13 Duration { secs: 6, nanos: 709803720 }
2000
SIP24 Duration { secs: 7, nanos: 654518957 }
2000
FNV Duration { secs: 5, nanos: 179056737 }
2000
Simple Duration { secs: 0, nanos: 897325662 }
➜  temp ./a.out 
2000 map 18.505 s
2000 unordered 1.9361 s

[brson]

While I appreciate the sentiment, as stated I don't see this as being actionable. The topic has been revisited many times, and Rust's hashmaps are the way they are for reasons.

Some alternate ideas for issues to address this area: 'Add Fnv hashing to std', 'specialize HashMap for small keys' (with a plausible strategy).

[inv2004]

@brson , Sorry if I missed something, but the problem with HashMap performance is not the problem with hash function. I just found the issue and I found exactly the same problem: HashMap with hasher which use key like hash without any modifications is much slower is rust. You can compare with indexmap for example.

[arthurprs]

@inv2004 can you rephrase that? I'm not sure I follow.

[inv2004]

@arthurprs
Most of the topics related performance problem of the collections::HashMap is about hash-functions. But we can clearly see big difference in performance of indexmap and collections::HashMap with the same hash-function.

[arthurprs]

@inv2004 IndexMap makes different tradeoffs, it's not a slam-dunk like you're suggesting. While iteration is much faster, there's a trade-off towards insertion speed (away from lookup and memory). The load factor 75% (compared to 92%) plays a big factor.