NSHash: 55x sequential insert vs absl::flat_hash_map on a dense pathological workload

[OrdersOfMagnitudeLLC]

We hit a case in our data pipeline where we needed to insert a few million keys in sorted order and then look them up later. With absl::flat_hash_map the sequential insert path kept spending time in rehash/copy cycles and TLB misses once the table grew past L3. NSHash gets a 55x speedup on this particular workload.

The structural difference is that NSHash keeps a flat open addressed table with compact occupancy metadata and delays rehashing to a much higher load factor. For a stream of sequential inserts, the working set stays in a handful of cache lines and the metadata scan stays branch friendly. This is not a claim that NSHash is better in general; flat_hash_map still wins for many mixed workloads. It is only that for bulk sequential construction the layout matters more than the hash function.

If anyone is curious, the code and notes are at https://github.com/OrdersOfMagnitudeLLC/type1-toolkit. I would be interested to hear whether this pattern matters for other Abseil users or if there is an existing tuning option we missed.