cmd/compile: optimize type switch

[bradfitz]

In code review https://go-review.googlesource.com/c/34773/, John Doe points out that a type switch in an inner loop can be optimized by pulling it out of the loop, setting an integer, and switching on the integer value instead.

John Doe provided this benchmark: https://play.golang.org/p/6LXF82e6U4

With tip, I get:

$ go test -v -bench=. -benchtime=2s
BenchmarkTypeSwitchInside-4         2000           1298710 ns/op
BenchmarkTypeSwitchOutside-4       10000            475899 ns/op

These seem like they could be identical. In both cases, it's just a switch on an integer. In the "Inside" case, that integer just happens to be in the first word of an interface value.

/cc @randall77 @mdempsky @josharian

[josharian]

cc @dr2chase who likes hoisting expensive operations out of loops

[mvdan]

Just to clarify, is this about optimizing all type switches or just about those that can be moved outside of a loop?

[josharian]

As I understand it, moving expensive things out of loops. But maybe I'm missing something.

[minux]

I think the first goal should be to lower the cost of type switches to that of integer switches and then we can talk about how to hoist expensive part out of loops. The first goal clearly benefits more than the 2nd because the programmer always have a way to do that themselves.

[mvdan]

I agree that the former is more interesting. It's also what I would understand given the issue title.

[randall77]

In go 1.8, the type switch compiles fairly small. The non-empty-interface-to-concrete-type switch compiles to just a few instructions.

func f(t I) int {
	switch t.(type) {
	case *T:
		return 1
	}
	return 0
}

generates for the switch

	0x0000 00000 (tmp1.go:14)	MOVQ	"".t+8(FP), AX    // AX = itab of interface
	0x0005 00005 (tmp1.go:14)	TESTQ	AX, AX
	0x0008 00008 (tmp1.go:14)	JEQ	52                // nil interface
	0x000a 00010 (tmp1.go:14)	MOVQ	8(AX), CX         // CX = type
	0x000e 00014 (tmp1.go:14)	MOVL	16(CX), DX        // DX = hash of type
	0x0011 00017 (tmp1.go:14)	CMPL	DX, $432690315
	0x0017 00023 (tmp1.go:14)	JNE	52
	0x0019 00025 (tmp1.go:14)	TESTQ	AX, AX
	0x001c 00028 (tmp1.go:14)	JEQ	$0, 62
	0x001e 00030 (tmp1.go:18)	LEAQ	type.*"".T(SB), AX
	0x0025 00037 (tmp1.go:14)	CMPQ	AX, CX
	0x0028 00040 (tmp1.go:14)	JNE	$0, 52
	0x002a 00042 (tmp1.go:16)	MOVQ	$1, "".~r1+24(FP)
	0x0033 00051 (tmp1.go:16)	RET
	0x0034 00052 (tmp1.go:18)	MOVQ	$0, "".~r1+24(FP)
	0x003d 00061 (tmp1.go:18)	RET
	0x003e 00062 (tmp1.go:14)	MOVQ	AX, CX
	0x0041 00065 (tmp1.go:18)	JMP	30

It's not optimal yet (the redundant TESTQ), but it's pretty small. The code is even slightly smaller when switching on empty interfaces.

Possibly for small switches we could get rid of the hash comparison and check the type pointers directly. (The hash enables binary search. We'd have to do linear search if we just used the type pointers.)

For nonempty interfaces, maybe we could even compare the itab with the address of the now-statically-known I/*T itab struct? Then we wouldn't even need to load the type out of the itab.

The more general question, how to pull this stuff out of the loop altogether, is harder. It involves memory operations so it isn't clear lifting is legal just from looking at the SSA form. We'd have to understand that some of the loads are from never-changing memory locations.

[gopherbot]

CL https://golang.org/cl/34810 mentions this issue.

[rasky]

For larger switches, given that we already have a compile-time known hash per type, it looks like it would be quite easy to use something along the lines of MRST. In other words, a small sequence of bits in those hashes could be used as perfect hashing to index a small jump table.

[randall77]

Jump tables: #5496, #10870

[josharian]

Jump tables see also #15780 (comment)

With go1.9beta2, I get

BenchmarkTypeSwitchInside-4         2000            687881 ns/op
BenchmarkTypeSwitchOutside-4        3000            443001 ns/op