DOC: Comparison with HashMap

[bluss]

See the list here: https://github.com/rust-lang/rust/issues/45273#issuecomment-336626535

[bluss]

Also comparison here https://github.com/rust-lang/rust/pull/45282

Perf assessment: nothing too surprising. Ordermap holds up in the sense of having a usable performance but not the best for this use case.

perf comparison. With regular hashmap first, with ordermap second.

• cpu-clock http://perf.rust-lang.org/compare.html?start=af7de7b6774b061b7809ce9aa6db31ea29df33c8&end=43308d48de7bbeb014fcd9f4caa1e82e56e394c2&stat=cpu-clock
• wall time http://perf.rust-lang.org/compare.html?start=af7de7b6774b061b7809ce9aa6db31ea29df33c8&end=43308d48de7bbeb014fcd9f4caa1e82e56e394c2&stat=wall-time
• instructions http://perf.rust-lang.org/compare.html?start=af7de7b6774b061b7809ce9aa6db31ea29df33c8&end=43308d48de7bbeb014fcd9f4caa1e82e56e394c2&stat=instructions%3Au
• cycles http://perf.rust-lang.org/compare.html?start=af7de7b6774b061b7809ce9aa6db31ea29df33c8&end=43308d48de7bbeb014fcd9f4caa1e82e56e394c2&stat=cycles%3Au

[nico-abram]

rustc now uses hashbrown right? It's also been a long time. It might be interesting to try this again?

[bluss]

Well, it's certain that indexmap doesn't compete with hashbrown for performance in general. There are some special cases where indexmap might be faster, like for example iteration.

[jonhoo]

@bluss & @cuviper How feasible (if at all) do you think it is to make IndexMap wrap hashbrown rather than implement its own hash table from scratch? hashbrown has its "raw" API, which is intended exactly for when you need to have relatively low-level control over the hash table, and might make things easier?

I ask specifically because I've been seeing some pretty sad resizing behavior, which I've since built a fix for, but the way indexmap is currently organized, it seems very difficult to swap out its map implementation in the way I had hoped.

[cuviper]

@jonhoo very feasible 🙂 #131