unordered_dense v5.2.0

A fast & densely stored hashmap and hashset

Release notes

Two changes since 5.1.0, both to the insert path: `try_emplace` and `operator[]` no longer pay for the placement on a key that is already there (#322), and `insert()` and `emplace()` look the key up before they construct anything (#323). That is the first time a set gets any of this, since a set has no `try_emplace`.

## `operator[]` on a present key needs 29% fewer instructions with clang

In 5.1.0 clang kept the whole insert out of line, so a hit paid a call and a six-register prologue for the placement code it never ran. Now the lookup in the key's home group and the common placement are inlined into the caller, and only the rare walk past the home group is behind a call. `emplace_back` is flattened into the insert, because otherwise gcc runs out of inlining budget right there and spills the caller's map to the stack around every insert.

Measured on a Ryzen 9 7950X, clang 22 and gcc 16, one map per binary, 50000 entries, `try_emplace` in a loop. Instructions per operation, 5.1.0 → 5.2.0:

| key | clang hit | clang miss | gcc hit | gcc miss |
|---|---|---|---|---|
| `uint64_t` | 72.0 → 51.3 | 96.0 → 81.2 | 45.1 → 44.3 | 77.9 → 69.0 |
| `std::string` | 147.1 → 109.6 | 312.9 → 294.0 | 109.1 → 110.1 | 291.7 → 287.3 |

The benchmark suite's overall score, one header per binary, goes up about 2% with clang and 8% with gcc (1.022 and 1.077), and no workload in it executes more instructions than in 5.1.0. In [ClickHouse's hash table aggregation benchmark](https://github.com/ClickHouse/hash-table-aggregation-benchmark), 100M rows per column, the cycles per row drop by 9% to 19% with clang and 3% to 10% with gcc, in every column. In MySQL 9.7.2 I could not measure a difference: relinking mysqld alone moves a query by 2.4%, which I found out with a join that never calls the map. The map call MySQL makes for `EXCEPT`, `segmented_map::emplace(key, mapped)` with 8-byte keys, takes 19% fewer cycles on its own.

## Sets and `insert()` no longer build a value just to throw it away

`insert(value)` and `emplace(value)` used to construct the element at the end of the value vector, look for its key, and pop it again when the key was already there. For a `std::string` key that is an allocation and a copy per duplicate. Now, when the arguments already are the value (a `value_type`, or a map's key and mapped type), the key is looked up first. Cycles per operation, same setup:

| operation | clang | gcc |
|---|---|---|
| `set<std::string>` insert, key present | 185.1 → 83.4 | 181.1 → 82.2 |
| `set<std::string>` insert, new key | 147.8 → 120.3 | 148.4 → 110.4 |
| `map<uint64_t, ...>` `insert({k, v})`, key present | 121.4 → 26.8 | 27.3 → 23.6 |
| `map<uint64_t, ...>` `insert({k, v})`, new key | 99.7 → 40.9 | 31.5 → 29.1 |

Arguments that would be converted are still used to build the value first, as before. `emplace(k, new int)` into a `map<..., std::unique_ptr<int>>` still hands the pointer to a `unique_ptr` when `k` is present, so it cannot leak.

## What else changes

- On a present key, `insert(value_type&&)` and `emplace(value_type&&)` now leave their argument as it was, where 5.1.0 moved from it into an element that was popped right after. If your types count copies, moves or destructions, you will see fewer of them.
- Past the caches the gain is smaller: at a million entries, in the [README's benchmark](https://github.com/martinus/unordered_dense/blob/main/scripts/ab/bench_readme.sh), building a `map<uint64_t, uint64_t>` is 3.6% faster and everything else is within 1%. The insert waits on memory there, and what 5.2.0 saves is instructions. The README's charts are unchanged.
- Unfortunately the inlining costs code size. With gcc, `flatten` copies the vector's growth path into every insert site: a binary with one map grows by less than 2 KB, but the benchmark suite, with hundreds of insert sites, grows by 46% in `.text`. MSVC gets the gcc shape without `flatten`, and I have not measured its speed.

All numbers, the roughly 20 variants that los…

Share this resource