v4.10.0

Faster lookups

• The probe reads four buckets at once. It used to look at one bucket at a time, so where a key turned up leaked into the branch pattern: hit at home, hit one further along, proven absent at the third. On lookups whose outcome is genuinely random that cost 1.35 branch mispredictions each. The probe now loads four buckets into one SSE2 register and compares each lane against the dist_and_fingerprint the key would carry there: equal is a fingerprint match worth a key comparison, less is the robin hood proof that the key is absent, and the lowest lane that is either one decides. That is a single data-dependent branch per lookup instead of one per bucket, and 0.70 mispredictions. The bucket array carries three sentinel buckets past its end so a window never runs off it. One probe() now serves find, insert and erase, and the scan for the bucket pointing at a moved value matches value indices the same way. (#211)

Measured on a Ryzen 9 7950X with clang, default -march, 50k entries, paired and interleaved with nanobench's compare() (milliseconds, lower is better):

workload	4.9.2	4.10.0
find, 50% hits	78.6	48.0
find, all hits	145	80
find, all misses	48	35
insert/erase	62.0	65.3

String keys move much less: find 218 → 210, insert/erase 226 → 212. Hashing a 200-byte key is 42 to 45% of those workloads, and the probe cannot help with that.

Configurations without a contiguous standard bucket keep the scalar probe: segmented maps, a custom bucket container, bucket_type::big, and non-x86 targets. SSE2 is part of the x86-64 baseline, so no build flags are needed to get this; ANKERL_UNORDERED_DENSE_HAS_SSE2 can be defined to 0 to ask for the scalar probe anyway. A build consumed as a C++20 module uses the scalar probe, because clang does not carry the intrinsic declarations across the module boundary.

Worth knowing

• Integer insert/erase is about 5% slower, roughly 20 more instructions per operation against 0.24 fewer mispredictions.
• Every map costs 24 bytes more, the three sentinel buckets. An allocator sized to exactly a power of two of buckets now sees a larger request.
• The benchmark changed, so its score is not comparable with 4.9.2's. The find workload of bench_quick_overall_udm reset its search rng to the insertion rng's seed, so its sequence of hits and misses repeated and a branch predictor with a long history learned much of it: 0.6 mispredictions per lookup where a random sequence costs 1.35. It was rewarding branchy probing and hiding this change, which measured 6% there and 64% once every lookup got an rng of its own. find_random.cpp still replays and was left alone.
• Sanitizer builds got slower and the test timeout was raised to suit. Ordinary builds are unaffected: without sanitizers this release and 4.9.2 run the same instruction count to within 0.5%.

No API changes.

Full Changelog: v4.9.2...v4.10.0