Optimizing rustc: replace HashMap with OrderMap?

[ghost]

Just for fun, I tried changing

pub type FxHashMap<K, V> = HashMap<K, V, BuildHasherDefault<FxHasher>>;

to

pub type FxHashMap<K, V> = OrderMap<K, V, BuildHasherDefault<FxHasher>>;

Using the new compiler, compilation time of my crate went down from 28.24 seconds to 25.46 seconds. I didn't do any further benchmarks yet, but the results seem promising. Looks like we could easily shave 5-10% from compilation time simply by changing the hash map implementation.

I was wondering if anyone else considered doing the same, and whether this is something I should experiment with further? What do you think?

cc @bluss

[kennytm]

Perhaps you could submit a PR, which we could do a benchmark using perf.rust-lang.org (cc @Mark-Simulacrum).

[bluss]

To tell the most important parts of the context for OrderMap as I understand it.

• Its key-value pairs are stored compactly
  • Pro iteration is just as fast as iterating &[(u64, K, V)]
• Its hash buckets and its key-value pairs are stored in two separate Vecs
  • Pro Less data to move in remove
  • Pro Less data to move when resizing
  • Pro More buckets fit in cache when scanning for lookup
  • Con Lookup always touches two places in memory even in the best case. Once in the hash buckets, and once in the separate k-v vector
• OrderMap grows at a load factor of 75%
  • Pro Simpler code / faster lookup
  • Con More memory usage
• OrderMap does not fully implement its reserve method. It can grow correctly, it can be preallocated with with_capacity correctly, but not more.

There are some systemic factors here like the separation of buckets and k-v entries; ordermap should not be able to compete with HashMap's lookup speed, if the data is not in cache.

I think this means we must look at larger compile jobs to draw conclusions.

[ghost]

More compilation timings:

crate	HashMap	OrderMap
crossbeam	31.94 secs	26.44 secs
rayon	9.40 secs	8.20 secs
pdqsort	0.23 secs	0.18 secs
chan	6.16 secs	5.26 secs
string-cache	10.13 secs	9.71 secs
parking_lot	5.45 secs	4.92 secs
timely-dataflow	19.69 secs	16.55 secs

[ghost]

Closing because we didn't get good results. See #45282.