v5.3.0

A map can now be saved and loaded back without hashing a single key, or used in place straight from a file. Also, the insert has one shape for every compiler now, which removes the 3-3.7x slowdowns 5.2.0 had in some callers' loops, and costs 2.4% (clang) and 5.2% (gcc) on the benchmark suite's score. Same hash values and same iteration order as 5.2.0.

Load a map from its values and its index (#299, #301, #303)

A map is two arrays, the values and the index, and the index is plain bytes without any pointers in it. index() hands it out, and the owning constructor builds a map from both arrays again, 3-17x faster than inserting at 1M to 64M entries. map_view and set_view use both arrays in place, e.g. from a file mapping or shared memory, and copy nothing. The new header mapped_view.h maps a file and owns the view over it; on hugetlbfs random hits are 1.02-1.16x faster than on 4 KB pages from 4M to 64M entries. The constructors take trust::checked or trust::unchecked, there is no default: a checked view costs 0.85 ns per entry, once.

Smaller changes

• map is 64 bytes instead of 80, and an empty map reads a shared, never written index, so find does not test for an empty table any more (#329).
• A key of 8, 12 or 16 bytes is hashed with 4 byte reads, so a key written field by field right before its lookup can be forwarded from the stores: 146 -> 40 cycles (#311).

The insert has one shape for every compiler (#310)

5.2.0 inlined the whole insert. In some loops that pushes the caller's variables to the stack, and the loop then stops overlapping its cache misses. 5.3.0 inlines the lookup in the key's home group and calls the rest. Cycles per operation in the caller corpus, Ryzen 9 7950X, one binary per loop, header and compiler, at 65536 / 4194304 entries:

loop	clang 5.2.0	clang 5.3.0	gcc 5.2.0	gcc 5.3.0
struct_key	152.4 / 1034.5	49.9 / 299.3	151.6 / 1038.8	41.0 / 292.6
bump_mod	91.0 / 475.6	27.6 / 191.9	90.6 / 478.6	25.0 / 167.0
churn_mod	135.1 / 742.7	81.1 / 329.2	107.3 / 472.5	137.8 / 731.5
build	48.0 / 142.4	51.9 / 155.9	44.7 / 133.4	52.2 / 156.8

The shape was picked by its worst loop, not by the average, so the slowest loop against the better header goes from 3.46 to 1.09 with clang and 3.69 to 1.55 with gcc. Unfortunately the average pays for it. The benchmark suite's score, one header per binary, is 0.976 (clang 22) and 0.948 (gcc 16) of 5.2.0, a plain insert loop is 8-9% slower with clang and 17-18% with gcc, and gcc's churn_mod is 1.28-1.55x slower. If your code is mostly plain inserts compiled with gcc, 5.2.0 is faster for you.

All numbers and scripts are in notes/index-design.md. The inline namespace is v5_3_0.