There is room for improvement when some or all of a map is not in cache. The hierarchical design we use to enable incremental growth leaves us with several different allocations that can experience cache misses:

1. The Map itself (on m.Used)
2. The directory slice (on m.directoryAt)
3. The table (on t.groups.lengthMask)
4. The control word (on matchH2)
5. The slot key (on key comparison)
6. The slot value (on access in the caller)

(4), (5), and (6) are in the same object, so they may share a cache line depending on how far apart they are.

Some changes that may help (or may make things worse!):

• Grouping control words together (prototype).
  • Good for locality of control words. Probably most useful for lookup of keys that aren't in the map (as the key has worse locality with the control word).
  • Also good for optimistic prefetch of the first control word, something that Abseil does.
• Change the directory from []*table to []table (prototype).
  • Effectively merges cases (2) and (3).
• Store group data directly in the table. The table becomes variable size, with a table8 containing 1 group, table16 containing 2 groups, and so on up to table1024.
  • Effectively merges cases (3) and (4).
  • Allows optimistic prefetch of the control word / first key before even touching the table as they are at fixed offsets.
  • We'd likely want to store the size in the directory as well to enable above.
  • This is unfortunately mutually exclusive with the previous option, as the table is variable-sized.

There is also the question of whether to store the key and value together (KVKVKV...), as we do today, or to group the keys together (KKKVVV...), as we do in the old maps. Both cases have pros and cons:

K/V together:

• Map hit
  • Cache miss on control word
  • Cache miss on key comparison
  • No cache miss on value use in parent
• Map miss
  • Cache miss on control word
  • Cache miss on key comparison in false positive matches (~1%)
  • No value

All keys together:

• Map hit
  • Cache miss on control word
  • No cache miss on key comparison
  • Cache miss on value use in parent (if used)
• Map miss
  • Cache miss on control word
  • No cache miss on key comparison in false positive matches (~1%)
  • No value