Repository: go
Issue: cmd/compile: jump tables perform much worse on AMD zen3?
Labels: Performance,NeedsInvestigation,compiler/runtime

On my AMD Ryzen 5900x, I noticed a drop in performance after jump tables were added (1ba96d8c0909eca59e28c048150c3834982f79fb).

---

The CL warns that microbenchmarks will favor the older binary search approach, while jump tables will be better utilized in larger benchmarks since it uses fewer hardware resources (branch predictors, etc.). To measure, this I tried to craft a micro-benchmark that would exercise edge cases of either approach. [This is what I came up with](https://go.dev/play/p/I86oW4oXHuP):
```go
func BenchmarkSame(b *testing.B) {
	for i := 0; i < b.N; i++ {
		for _, k := range sourcesSame {
			sink = KindString(k)
		}
	}
}
func BenchmarkOrdered(b *testing.B) {
	for i := 0; i < b.N; i++ {
		for _, k := range sourcesOrdered {
			sink = KindString(k)
		}
	}
}
func BenchmarkRandom(b *testing.B) {
	for i := 0; i < b.N; i++ {
		for _, k := range sourcesRandom {
			sink = KindString(k)
		}
	}
}
```
Essentially, `KindString` is just like `reflect.Kind.String` but uses a giant switch statement.
The `Same`, `Ordered`, and `Random` benchmarks keep calling `KindString` with either the same argument, sequentially ordered arguments (i.e., easily predictable), or completely random arguments. I would expect jump tables to perform better on `Random` over the binary search approach since binary search would continually run log2(27) layers of branch prediction failures.

I ran the benchmarks using a Go toolchain built at 1ba96d8c0909eca59e28c048150c3834982f79fb and also the commit right before it.

On at least 3 CPUs that I have access to, I see promising results:

```
cpu: Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz
benchmark              old ns/op     new ns/op     delta
BenchmarkSame-8        38859         31988         -17.68%
BenchmarkOrdered-8     41096         40540         -1.35%
BenchmarkRandom-8      154696        108772        -29.69%
```
Here, jump tables do better than binary search on all cases. Great!

```
cpu: Intel(R) Celeron(R) CPU J3355 @ 2.00GHz
benchmark              old ns/op     new ns/op     delta
BenchmarkSame-2        47493         44109         -7.13%
BenchmarkOrdered-2     81576         140271        +71.95%
BenchmarkRandom-2      240434        138600        -42.35%
```
Here, jump tables does worse on `Ordered`, but has much better performance on `Random`. Somewhat expected.

```
cpu: DO-Regular
benchmark            old ns/op     new ns/op     delta
BenchmarkSame        32203         23410         -27.30%
BenchmarkOrdered     35731         27531         -22.95%
BenchmarkRandom      179656        125754        -30.00%
```
Here, this is a Digital Ocean droplet, which is probably an Intel Xeon processor of some kind.
Here, we see jump tables do better than binary search on all cases. Great again!

However, things turn for the worse on an AMD Ryzen 5900X:
```
cpu: AMD Ryzen 9 5900X 12-Core Processor            
benchmark               old ns/op     new ns/op     delta
BenchmarkSame-24        19514         61886         +217.14%
BenchmarkOrdered-24     22926         75008         +227.17%
BenchmarkRandom-24      38740         72986         +88.40%
```
Here, the jump tables are dramatically worse on all cases. I'm surprised that it's worse by 2x on the `Random` benchmark, which is where I expect jump tables to outshine binary search.

---

I understand that performance improvements are really hard to quantify since what works well for one CPU design (e.g., Intel) may not be optimal for another CPU design (e.g., AMD). However, these results are much more drastic than I was expecting. I don't know whether this issue is just with the Ryzen 5900X or all AMD chips. I also, don't know if this is going to result in any changes to the implementation of jump tables, but I think this is a surprising result worth reporting.

\cc @randall77 @cherrymui