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_up and erase_and_shift_down settle 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%.

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.

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):

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

Fixes

• A size at the limit produced an unusable table. Two independent faults, both at max_size(), both found by asking whether a test would notice a bug rather than whether it ran the line:

  • calc_shifts_for_size() walked the shift down past the point where the bucket array can still grow. calc_num_buckets() saturates at max_bucket_count(), so above max_bucket_count() * max_load_factor() the capacity being compared stopped growing while the loop kept decrementing — all the way to a shift of zero, where calc_num_buckets() asks for 1 << 64. That is undefined and in practice one: a table sized for billions of elements came back with a single bucket and a mask of zero, and the next probe read past the end of it. Reachable from rehash(), which does not allocate the values and so has nothing to fail first — map<uint32_t, uint32_t>::rehash(3865470566) reproduced it.
  • replace() and clear_and_fill_buckets_from_values() counted in value_idx_type. max_size() is exactly what that type can hold, so a container of precisely that many has a size that is not representable in it: the cast wrapped to zero, the loop never ran once, and the table came back reporting size() elements with no bucket pointing at any of them. (#192)

• The bucket type's contract is now checked at compile time. The fingerprint must fit strictly below dist_inc, and dist_inc must be a power of two. Both were always required — the probe arithmetic adds dist_inc expecting it to touch only the distance — but nothing said so, and a custom Bucket violating either failed at run time in ways that looked like a hashing bug. This only affects code supplying its own bucket type, and only where it was already broken. (#192)

No API changes. Everything else since v4.9.1 is tests, tooling and CI, which does not reach anyone consuming the header.

Full Changelog: v4.9.1...v4.9.2

Fixes

• Quadratic insert cost in the segmented containers. v4.9.0's exception-safety work grew segmented_vector's block pointer array with reserve(size + 1), which std::vector takes literally: every new segment reallocated the array and copied every pointer before it, so a plain insert loop into a segmented_map or segmented_set slowed quadratically — 8 million string keys took ~22 s instead of ~2 s. The array grows geometrically again, the no-leak guarantee on a failed allocation is kept, and a regression test counts allocations so it stays that way. Thanks @kraldan! (#188)

Full Changelog: v4.9.0...v4.9.1

New

• Look up with a hash computed once. hash_for(key) returns a precomputed hash that find, contains, count, equal_range and at accept as a second argument, so a key looked up in several tables is hashed once rather than once per table. The hash is tied to the hasher, so it is shared by every table using that hasher — a map<std::string, int> and a set<std::string> can use the same one. (#156)
• Mark a hash avalanching from outside it. ankerl::unordered_dense::hash_is_avalanching<Hash> can be specialized for a hash you did not write, including a std::hash specialization, and the table asks the trait everywhere it used to look for the member typedef. require_avalanching<Hash> wraps a hash and static_asserts that it qualifies, so a hash that quietly loses its marker fails to compile rather than silently costing a rehash. The trait deliberately has the same name, the same two spellings and the same meaning as boost::hash_is_avalanching, so a hash annotated for either library is read correctly by the other. (#92)

Behaviour change

wyhash produces different values than 4.8.1 for inputs of 8–16 bytes and for inputs over 48 bytes. Hash values and iteration order therefore differ from 4.8.1. Nothing ever promised either across versions, but anything that persists a hash, a bucket array or an iteration order needs re-checking.

Fixes

• Allocator handling in segmented_vector, in detail::table's constructors, and for the bucket container in copy, move, swap and assignment
• The bucket array is allocated on the first insert rather than in the constructor, so a default-constructed table costs no allocation
• The table is left valid and leak-free when a copy, move, assignment, erase or extract throws — including a block whose pointer could not be stored, and an erased value whose move out throws
• A max_load_factor that open addressing cannot honour is refused instead of hanging
• segmented_vector's iterator reports itself as random access
• A map that was extract()ed from is usable again
• Swapping two maps no longer allocates
• noexcept specifications now say what they meant to say
• A segmented BucketContainer no longer calls deallocate_bucket while growing
• MSVC C4163 on ARM64EC, macOS clang signedness warnings, and fmt/core.h deprecation

Performance

• Faster hashing, probing and erase
• The bucket array is copied once instead of twice
• No memset when clearing an already-empty table

Development

libFuzzer and AFL++ targets with committed corpora and a nightly fuzzing workflow, clang-format enforced at a pinned version, and CI extended to libc++ on Linux.

Full Changelog: v4.8.1...v4.9.0

Direct download: unordered_dense.h

What's Changed

• fix overlooked uint8_t missing std:: and fix missing cstdint header in module by @Arthapz in #151
• add stdint types linter for modules by @martinus in #152

Full Changelog: v4.8.0...v4.8.1

Direct download: unordered_dense.h

What's Changed

• support C++23 import std on unordered_dense module by @Arthapz in #95
• minor cleanup, bump version to 4.8.0 by @martinus in #150

New Contributors

• @Arthapz made their first contribution in #95

Full Changelog: v4.7.0...v4.8.0

This release adds a non-standard API replace_key as proposed by @Auburn. This adds the ability to replace a key while keeping the underlying container stable (no references & iterators will be invaliated). It is also faster than removing & inserting an element, especially when hashing is relatively slow like for std::string or when dealing with data that is slow to move.

Direct download: unordered_dense.h

What's Changed

• Add key replacement and erase-and-shift-down methods to unordered_dense by @martinus in #149

Full Changelog: v4.6.0...v4.7.0

This release took me quite some time unfortunately, and again it consists mostly of community contributions. Thanks a lot, and sorry that it took me so long to review them!

Direct download: unordered_dense.h

What's Changed

• Fix compilation issues and update CI workflow by @martinus in #142
• minor segmented_vector fixes by @bibmaster in #136
• Feature: segmented_vector::resize functions by @liss-h in #133
• Add tests for segmented_vector resize functionality by @martinus in #143
• Disable ubsan's integer sanitizer warnings by @jcelerier in #139
• Fixed compiler error C2061 in VS2022; syntax error: identifier 'T'" by @viable-alternative in #134
• Fix MinGW build with _WIN32_WINNT<0x600, GCC>=13, model=win32 by @palves in #132
• Add support for c++20 likely/unlikely attributes by @duckdoom5 in #130
• Enhance Linux CI workflow with compiler and architecture matrix support by @martinus in #144
• Adds a clang-tidy linter by @martinus in #145
• Fix README.md regarding stability of segmented_map and segmented_set references by @martinus in #146
• Add unit test for segmented_map in array_of_maps.cpp by @martinus in #147
• bump version to 4.6.0 by @martinus in #148

New Contributors

• @bibmaster made their first contribution in #136
• @liss-h made their first contribution in #133
• @viable-alternative made their first contribution in #134
• @palves made their first contribution in #132
• @duckdoom5 made their first contribution in #130

Full Changelog: v4.5.0...v4.6.0

This release is brought to you by the awesome community, thanks everybody!

Direct download: unordered_dense.h

What's Changed

• Fix build with current fmt (master branch) by @phprus in #107
• Just adds a disabled test, update dependencies by @martinus in #127
• Remove duplicate clang-tidy line by @bmagistro in #120
• segment_map: Also segment the bucket array by @StephanDollberg in #112
• Passthrough is_avalanching from std::hash by @Auburn in #114
• Add iter_t::operator++(int) overload by @TriceHelix in #128
• Adds ANKERL_UNORDERED_DENSE_DISABLE_PMR, bumps version by @martinus in #129

New Contributors

• @phprus made their first contribution in #107
• @bmagistro made their first contribution in #120
• @StephanDollberg made their first contribution in #112
• @Auburn made their first contribution in #114
• @TriceHelix made their first contribution in #128

Full Changelog: v4.4.0...v4.5.0