Improving performance by updating Abseil design

[gaujay]

I heard that HashMap is based on Google original design for absl::flat_hash_map.

And noticed there was some room for improvement in Abseil implementation, so I rolled out my own (C++) versions with and without tombstones recently, including comparative benchmarks (for llvm, gcc, msvc).

I think Hashbrown/the Rust std lib could also benefit from these improvements (and additional benchmark scenarios)
by updating few things in its current design (based on the model of indivi::flat_wmap). Mainly, it would imply using 8-bits hash fragments instead of 7 to reduce fast performance divergence on high load scenarios (in particular lookup-miss, see graphs curves).

For more details (benchmarks, documentation, impl specifics), please check this thread (in particular the discussion with u/matthieum):
https://www.reddit.com/r/rust/comments/1mloi7k/rust_hashmap_implementationperformance/

[matthieu-m]

Reference

I once experimented with some of the differences that Boost's unordered_flat_map touted as important, namely:

• 8 bits residuals, which required special-casing to (still) reserve 2 values for EMPTY and DELETED.
• Overflow/Displacement tracking, though in a less-local way than Boost's implementation, to minimize the impact on the implementation.

And as can be seen in the benchmarks in those 2 PRs, the results were not earth-shattering.

Now, there may be multiple reasons for those results:

• The changes simply do not make as much sense for hashbrown.
• My implementations are just not great in the first place; so whatever algorithmic improvement I could have gotten is lost to mechanical antipathy.
• The benchmark suite used by hashbrown failed to surface the improvements.

Benchmarks

I think it may be worth examining the benchmark suite's possible failings, here.

@gaujay pointed to me that the "bloom-filter" overflow/displacement tracking implemented in Boost's is most helpful in reducing probing sequence length for lookups resulting in misses in very full maps, as per @joaquintindes' own analysis in Inside boost::unordered_flat_map, and that maybe the benchmark suite of hashbrown simply doesn't track this specific usecase well.

@gaujay also pointed out to me that there may be cache effects at play, in general, in the benchmark suite and after checking I noticed that indeed:

1. The benchmark suite never flushes the caches.
2. The benchmark suite uses small sizes: SIZE = 1000 & Map<usize, usize> (essentially) for a 16KB footprint, just L1 sized.
3. The benchmark suite measures throughput, not latency distribution.

This means that while the first few iterations of b.iter will experience cache misses, subsequent iterations will benefit from a mostly warm cache. If the Bencher uses a warm-up period, it will discard the early cache misses, and even if it simply uses an average + standard deviation amalgam, it will still not reflect early hiccups in the final statistics.

In particular, this may drastically change the performance profile of long probing sequences, where (repeated) cache misses are expected to dominate the wall-clock time in real-world workloads.

I do think having warm cache benchmarks matter: they allow focusing on the performance of the CPU code.

I also think that it may be worth having additional cold cache benchmarks, where the cache is flushed (as best as possible) between each iteration.

Finally, I also think it may be useful to have a specific long-probe sequence benchmark, which could be generated by wrapping the hasher so as to erase some of the bottom 16 bits of the hash (& 0x0000_0F00 for example) thereby ensuring long probe sequences.

[gaujay]

I updated my repo to add benchmark results for LLVM using the same custom hash (murmur3/FNV-1a) for every map. This should give a better view about what could be gained from different designs in Rust (see last table/detailed graph from link above).

Improving Hashbrown benchmarks should indeed be the first step here, so proposed changes can be properly validated.
This is a tricky topic, as mentioned in Google second video about their flat_hash_map:
https://www.youtube.com/watch?v=JZE3_0qvrMg
At 19:46 you can see separate performance graphs for both hot and cold tables. But still, they admit that only plugging it into production code can give proper feedback in the end.

Last thing I should mention, I also significantly improved iteration speed in flat_wmap compared to abseil.
This improvement could also be cherry-picked, but might be a bit more complex (it removes the need for a dedicated sentinel value but require specific end of array checks).

[cuviper]

But still, they admit that only plugging it into production code can give proper feedback in the end.

rustc itself is a pretty heavy benchmark of hash tables, for which we have perf.rust-lang.org. If you can arrange your changes as a draft PR to rust-lang/rust, e.g. with cargo [patch] to your hashbrown, then we can compare them that way.

[gaujay]

I made some new benchmarks to monitor lookup hit/miss performances depending on load factor.
Here are the typical results on my machine:

// FoldHashMap, RandomKeys
test lookup_size_14500             ... bench:       3,505.05 ns/iter (+/- 37.71)
test lookup_size_16500             ... bench:       3,474.36 ns/iter (+/- 11.88)
test lookup_size_18500             ... bench:       3,482.29 ns/iter (+/- 14.58)
test lookup_size_20500             ... bench:       3,478.73 ns/iter (+/- 20.59)
test lookup_size_22500             ... bench:       3,416.84 ns/iter (+/- 94.83)
test lookup_size_24500             ... bench:       3,450.97 ns/iter (+/- 82.86)
test lookup_size_26500             ... bench:       3,493.92 ns/iter (+/- 37.22)
test lookup_size_28500             ... bench:       3,484.17 ns/iter (+/- 24.00)

test lookup_fail_size_14500        ... bench:       2,900.72 ns/iter (+/- 28.27)
test lookup_fail_size_16500        ... bench:       3,009.21 ns/iter (+/- 23.97)
test lookup_fail_size_18500        ... bench:       3,157.28 ns/iter (+/- 24.10)
test lookup_fail_size_20500        ... bench:       3,480.48 ns/iter (+/- 27.06)
test lookup_fail_size_22500        ... bench:       4,048.19 ns/iter (+/- 47.99)
test lookup_fail_size_24500        ... bench:       5,265.12 ns/iter (+/- 65.23)
test lookup_fail_size_26500        ... bench:       7,494.26 ns/iter (+/- 90.56)
test lookup_fail_size_28500        ... bench:      11,593.97 ns/iter (+/- 108.62)

All maps have the same capacity of 28672 (i.e. 32768 * 0.875).
You can see the clear degradation of failed lookups when load increase above ~0.7 (from 0.44).

I am no Rust developer, but here is the code if you're interested:
https://godbolt.org/z/TzasKhGMM
I can also check to open a PR if you want.

Note: good idea for rustc as a benchmark. I'm guessing it mainly uses small maps internally?