v5.2.0

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, 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, 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 lost, and the scripts are in notes/index-design.md under "split at the home group" and "the arguments already are the value".

Same hash values and same iteration order as 5.1.0. The inline namespace follows the version, so this is v5_2_0.