cc @dr2chase who likes hoisting expensive operations out of loops

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

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

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

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.

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

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.

Jump tables: #5496, #10870

Jump tables see also #15780 (comment)

With go1.9beta2, I get

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

Go 1.11.2:

BenchmarkTypeSwitchInside-4         3000            513823 ns/op
BenchmarkTypeSwitchOutside-4        3000            444997 ns/op

For Go1.15, here are the results

$ benchstat before.txt after.txt 
name          old time/op  new time/op  delta
TypeSwitch-8   576µs ± 4%   579µs ± 4%   ~     (p=0.548 n=5+5)

after

$ go test -run=^$ -bench=. -count=5 
goos: darwin
goarch: amd64
pkg: github.com/odeke-em/bugs/golang/18492
BenchmarkTypeSwitchInside-8    	    2011	    572145 ns/op
BenchmarkTypeSwitchInside-8    	    2148	    555198 ns/op
BenchmarkTypeSwitchInside-8    	    2050	    579787 ns/op
BenchmarkTypeSwitchInside-8    	    2040	    586727 ns/op
BenchmarkTypeSwitchInside-8    	    1983	    583754 ns/op
BenchmarkTypeSwitchOutside-8   	    2128	    576922 ns/op
BenchmarkTypeSwitchOutside-8   	    2080	    557053 ns/op
BenchmarkTypeSwitchOutside-8   	    2116	    588772 ns/op
BenchmarkTypeSwitchOutside-8   	    2005	    582071 ns/op
BenchmarkTypeSwitchOutside-8   	    2013	    592535 ns/op
PASS
ok  	github.com/odeke-em/bugs/golang/18492	13.956s

Perhaps we can close this issue, as the tertiary improvements have their own issues.

I wonder whether the thing that "fixed" this was https://go-review.googlesource.com/c/go/+/228106

Either way, yes, let's call this good. Thanks for checking, @odeke-em.