Repository: go
Issue: runtime: performance regression for small Swiss Table map access for non-specialized keys
Labels: Performance,NeedsInvestigation,compiler/runtime

**Edit:** Initially, I thought this was an "optimization opportunity" and wrote it up as such, but later realized it is seemingly a regression from Go 1.23 ([comment](https://github.com/golang/go/issues/70849#issuecomment-2543389413)). Changed title accordingly.

---

I was reading through the (excellent!) new Swiss Table implementation from #54766 and noticed a potential optimization opportunity for lookups with small maps (<= 8 elems) for the normal case of non-specialized keys.

I suspect the current linear scan for these maps might be better off if we instead build a match bitmap and jump to the candidate match. I mailed https://go.dev/cl/634396 with this change.

For predictable keys, it might be a small win or close to a wash, but for unpredictable keys, it might be a larger win.

To better illustrate this (as well as to help with analyzing a couple other experiments I'm trying), I also updated the benchmarks (#70700) to shuffle the keys for the newer benchmarks, and also added a new "Hot" benchmark that repeatedly looks up a single key (Hot=1 below) or a small number of random keys (Hot=3 below). 

The geomean here is -28.69%. These results are for amd64 and use the SIMD optimizations. I did not test on arm or without the SIMD optimizations.

```
                                                │  no-fix-new-bmarks  │ fix-with-new-bmarks   │
                                                │      sec/op         │  sec/op       vs base │
MapAccessHit/Key=smallType/Elem=int32/len=6-4            24.55n ±  0%   13.63n ±  0%  -44.48% (p=0.000 n=25)
MapAccessMiss/Key=smallType/Elem=int32/len=6-4          12.500n ±  0%   9.517n ± 32%  -23.86% (p=0.007 n=25)
MapAccessHitHot/Key=smallType/Elem=int32/len=6/Hot=1-4   13.73n ±  4%   13.54n ±  0%        ~ (p=0.096 n=25)
MapAccessHitHot/Key=smallType/Elem=int32/len=6/Hot=3-4   21.93n ±  1%   13.57n ±  1%  -38.12% (p=0.000 n=25)
MapSmallAccessHit/Key=smallType/Elem=int32/len=1-4       13.07n ±  0%   13.54n ±  0%   +3.60% (p=0.000 n=25)
MapSmallAccessHit/Key=smallType/Elem=int32/len=2-4       19.05n ±  0%   13.53n ±  0%  -28.98% (p=0.000 n=25)
MapSmallAccessHit/Key=smallType/Elem=int32/len=3-4       21.46n ±  0%   13.52n ±  0%  -37.00% (p=0.000 n=25)
MapSmallAccessHit/Key=smallType/Elem=int32/len=4-4       23.06n ±  0%   13.53n ±  0%  -41.33% (p=0.000 n=25)
MapSmallAccessHit/Key=smallType/Elem=int32/len=5-4       23.94n ±  0%   13.53n ±  0%  -43.48% (p=0.000 n=25)
MapSmallAccessHit/Key=smallType/Elem=int32/len=6-4       24.46n ±  0%   13.54n ±  0%  -44.64% (p=0.000 n=25)
MapSmallAccessHit/Key=smallType/Elem=int32/len=7-4       24.91n ±  0%   13.54n ±  0%  -45.64% (p=0.000 n=25)
MapSmallAccessHit/Key=smallType/Elem=int32/len=8-4       25.12n ±  0%   13.56n ±  0%  -46.02% (p=0.000 n=25)
MapSmallAccessMiss/Key=smallType/Elem=int32/len=1-4     12.480n ±  0%   9.523n ±  0%  -23.69% (p=0.000 n=25)
MapSmallAccessMiss/Key=smallType/Elem=int32/len=2-4     12.480n ±  0%   9.516n ±  0%  -23.75% (p=0.000 n=25)
MapSmallAccessMiss/Key=smallType/Elem=int32/len=3-4     12.490n ±  0%   9.516n ±  0%  -23.81% (p=0.000 n=25)
MapSmallAccessMiss/Key=smallType/Elem=int32/len=4-4     12.480n ±  0%   9.520n ±  0%  -23.72% (p=0.001 n=25)
MapSmallAccessMiss/Key=smallType/Elem=int32/len=5-4     12.480n ±  0%   9.520n ±  0%  -23.72% (p=0.000 n=25)
MapSmallAccessMiss/Key=smallType/Elem=int32/len=6-4     12.490n ± 20%   9.527n ± 32%  -23.72% (p=0.003 n=25)
MapSmallAccessMiss/Key=smallType/Elem=int32/len=7-4      12.48n ±  0%   12.09n ± 21%   -3.12% (p=0.000 n=25)
MapSmallAccessMiss/Key=smallType/Elem=int32/len=8-4      12.49n ± 16%   11.77n ± 19%   -5.76% (p=0.000 n=25)
geomean                                                  16.58n         11.82n        -28.69%
```
-----

In all cases, I suspect the misses are predictable, but in some cases the predictable miss is with a predictable key vs. a miss on an unpredictable key in other cases. For a single group like these, that probably doesn't matter.

For the hits and misses, these are the ones that I expect to have predictable keys:
```
MapAccessHitHot/Key=smallType/Elem=int32/len=6/Hot=1-4   13.73n ±  4%   13.54n ±  0%        ~ (p=0.096 n=25)
MapSmallAccessHit/Key=smallType/Elem=int32/len=1-4       13.07n ±  0%   13.54n ±  0%   +3.60% (p=0.000 n=25)
MapSmallAccessMiss/Key=smallType/Elem=int32/len=1-4     12.480n ±  0%   9.523n ±  0%  -23.69% (p=0.000 n=25)
```
(Those three are also listed above in the larger list, but pulling them out here for commentary).

The first has predictable keys because a single key is looked up repeatedly per run (with 6 elements in the small map). The second two have predictable keys because there is only a single element. In other words, the keys are shuffled in all ~20 of these benchmarks, but in the three here, the shuffling is effectively a no-op.

CC @prattmic