Insert and erase get the treatment lookups got in 4.10.0: one SSE2 decision instead of one branch per bucket.
What changed
place_and_shift_upanderase_and_shift_downsettle four buckets from one mask. The robin hood shift used to ask "is this bucket occupied" once per bucket, and that question is a coin flip -- 73% of inserts shift nothing, 11% shift one -- costing 0.61 branch mispredictions per insert. It is 0.24 now, at 126 instructions against 101.- wyhash returns from its short path instead of falling through, and enters the six lane block only when it can run twice.
Nothing in the public API changed and no type changed size.
Measurements
Paired A/B against 4.9.2 on a Ryzen 9 7950X with clang: twelve interleaved passes at 32 epochs, pinned to one physical core, and repeated with the two headers' roles swapped inside the binary so that code layout could not be mistaken for the map. The two orientations agreed to 0.19%.
| workload | speedup |
|---|---|
| find64 | 1.59x |
| ie64 | 1.26x |
| build64 | 1.17x |
| iestr | 1.17x |
| findstr | 1.16x |
| buildstr | 1.10x |
| itstr | 1.01x |
| it64 | 0.98x |
| geomean | 1.17x |
Against 4.10.0 alone -- the part that is new in this release -- the shift work is 1.12x on build64, 1.08x on ie64 and 1.04x on iestr, for a 1.036x geomean.
it64 is 2.5% slower, reproducibly and in both orientations. Iteration touches none of the changed code, so this is the new vector code displacing the iteration loop in the instruction cache. It costs about 0.5% of the geomean against gains many times that.
Note on the benchmark
The keys of bench_quick_overall_udm changed in #213, so its score is not comparable with 4.10.0's:
- string keys run from 8 to 135 bytes instead of a fixed 200, because a hash dispatches on length and one length makes that dispatch perfectly predictable (0.01 mispredictions per hash against 0.31);
- integer keys are scrambled through a bijection instead of being small and sequential, because the top bits of multiples of a small integer walk a lattice -- nothing collided, so the probe never probed and the shifts never shifted;
- a build-from-empty workload was added, because nothing in the score had ever grown a table.