The texture cache's hash cache was a std::unordered_map, with nodes
from GSNodeAllocator's pool. It becomes a GSStableMap, new in C89. Sources
point at their entries, so an entry can't move the way a GSFlatMap's
values do. Here the slots are a stored hash and a node pointer, sixteen
bytes each, at most a quarter in use, with linear probing. Each node
holds its key next to its value, so a hit reads the slot and the node.
A node knows its slot and its place in a dense list of nodes, so an
erase neither looks it up nor hashes it again (backward shift for the
slots, the last node into its place in the list). A walk goes down the
list and can erase the entry it is at. AgeHashCache does that instead of
erasing through an iterator. Its purge list is a plain array of entries,
grown only when the cache is fuller than it has been. The slots for 800
entries are made when the cache is.
tests/gsstablemap checks the map against a model, with nodes from a
pool and from the allocator, including erases during a walk. With
GSSM_BENCH=1 it times both maps on 40-byte keys at 32 to 800 entries,
best of five, ns per operation, std then stable:
find hit 9-13 vs 6-9 (1.3-1.6x)
find miss 9-11 vs 7-8 (1.1-1.5x)
walk 1.1-3.8 vs 0.6-1.3 per entry (1.2-2.9x)
insert+erase 20-29 vs 15-20 (1.3-1.5x)
Within a few percent of the quarter-load boundary the miss and insert
times are even. Ridge Racer V's intro presents the same 19 frames, bit
for bit, and the steady-state allocation count stays at zero.
