Making benchmarks better

[WaDelma]

The benchmarks should really be using criterion It would be interesting to benchmark it against bytell-hash-map which I did rust implementation for (Haven't optimised it that much and should really make it usable library).

[WaDelma]

Also each benchmarked hashmap should be using the same hashing algorithm as otherwise you are comparing apples and oranges

[matthieu-m]

Current discussion on r/cpp about benchmark many hashmaps: https://www.reddit.com/r/cpp/comments/auwbmg/hashmap_benchmarks_what_should_i_add/

It may give ideas about new benchmarks and new hashmaps to consider.

Also, it's notable that Abseil's Swiss Table seem to struggle in benchmarks featuring insert/erase. In the benchmarks in the README we see hashbrown lagging 10% behind FxHashMap in grow_by_insertion, and otherwise always being faster, so it's unclear if hashbrown also suffers from this.

[Amanieu]

@matthieu-m Are the benchmark results available somewhere?

[matthieu-m]

Not that I know of, yet, short of running them yourself. At the moment the OP is gathering maps and benchmarks ideas, I am hoping that once everything is setup he'll publish some results.

[alkis]

For benchmarks you should replicate these. They are really good. They test:

1. LookupHit
2. LookupMiss
3. Insert
4. InsertErase (repeatedly insert and erase)
5. Iteration
6. Clear+InsertOrdered (ordered = same order as iteration order of the hashtable)
7. Clear+InsertUnordered (unordered = random order)

The tests are parametrized to run across the cross product of these dimensions:

1. payload sizes (4, 8, 16, 32, 64)
2. hot and cold tables (hot=in cache, cold=not in cache)
3. high and low density tables (high=max load factor, low=min load factor)

There is a good discussion in the forum about the design of these benchmarks and how they are useful. The most notable thing we found about benchmarks when implementing SwissTable is that benchmarks that predict production performance are very hard to write. In the end we wrote benchmarks to act as tools of understanding how a table behaves under certain loads and conditions: lookup/insert/miss, hot/cold, dense/sparse, etc. The only benchmarks we found useful for the hashtable as a whole was running large production workloads against them. In your case you have rustc-perf.