runtime: map cold cache improvements

[prattmic]

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

[gabyhelp]

Related Issues

• runtime: enhance map cacheline efficiency #48687
• runtime: use SwissTable #54766

Related Code Changes

• internal/runtime/maps: initial swiss table map implementation
• runtime: use SwissTable
• internal/runtime/maps: small maps point directly to a group
• internal/runtime/maps: use match to skip non-full slots in iteration
• cmd/compile,internal/runtime/maps: add extendible hashing
• maps,runtime: improve maps.Keys
• internal/runtime/maps: search group using simple for loop

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}