cmd/compile: if x == a || x == b || x == c generates slower code than case a, b, c

[gaal]

go version devel +214be5b302 Sun Mar 26 04:40:20 2017 +0000 linux/amd64

While investigating issue 19789 I came across code that rans 25% slower than I expected. Context with runnable benchmark: https://gist.github.com/gaal/497361737dd55125cf2de998b49d948b

Please compare:

// BenchmarkFields/FieldsFuncLatin1Switch-12                1000000              2177 ns/op          78.08 MB/s
// BenchmarkFields/FieldsFuncLatin1If-12                     500000              2970 ns/op          57.24 MB/s

// isLatin1SpaceSwitch is is like unicode.IsSpace, but without the Unicode support.
// Presumably generates a jump table.
func isLatin1SpaceSwitch(r rune) bool {
	switch r {
	case '\t', '\n', '\v', '\f', '\r', ' ', 0x85, 0xA0:
		return true
	}
	return false
}

// Equivalent to isLatin1SpaceSwitch, but apparently generates much slower code.
func isLatin1SpaceIf(r rune) bool {
	return r == '\t' ||
		r == '\n' ||
		r == '\v' ||
		r == '\f' ||
		r == '\r' ||
		r == ' ' ||
		r == 0x85 ||
		r == 0xA0
}

It looks like the compiler could figure out that the expression is equivalent and could be optimized the same way. The speedup probably depends greatly on the number and kinds of arguments in the disjunction.

[bradfitz]

I seem to recall a bug open about this already, or something similar. @randall77 probably knows.

[randall77]

I don't know of any related issue.
The switch statement does a pretty good job of binary search. It also coalesces \t through \r which are adjacent numerically.
The || code is linear search with no coalescing.
Could be fixed, I suppose. I don't know what the right strategy would be.

[josharian]

We could do something during walk, where we look at disjunctions of equality checks, look for constants on one side and samesafeexprs on the other, and rewrite them into switch statements. I'm not convinced it's worth the code, since the benefit only kicks in when there are several disjuncts, and the author can simply use a switch statement instead.

[martisch]

There is #17622 about compiling switches into boolean functions.
Both can be combined to work on a possible improvement to fold if/switch statements that result in boolean values better in general.

[mvdan]

There is #5496 about compiling dense integer switches into jump tables. But that doesn't touch the fact that the if is slower than the switch.

I have a lexer/parser that has a lot of branching depending on runes/bytes, so I'm interested in this. I have come up with some benchmarks, also including a hand-made table: https://play.golang.org/p/QHwxgi0pBLn

$ go test -bench=.
goos: linux
goarch: amd64
BenchmarkSwitch-4       100000000               11.7 ns/op
BenchmarkIf-4           100000000               19.6 ns/op
BenchmarkArray-4        200000000                6.28 ns/op

Like in this issue, I see the switch being noticeably faster than the if. Perhaps unsurprisingly, the table is in turn noticeably faster than the switch.

The fun part, however, is that swapping a switch implementation for an if one brings a slight performance improvement in my lexer. I have yet to figure out why. It's actually the very same function that I show in the playground link above, just with different runes as inputs. In both cases, the function appears to be inlineable and inlined.

[randall77]

Your speed is probably very dependent on the order of comparisons and the likely input values. If your first if clause matches the most likely input value, then the if will be fast. If the most likely input value is the last one checked, it will be slow.
In contrast, the switch uses a binary tree of comparisons, so it is less input-value dependent, as it always does approximately the same number of comparisons irrespective of the input value.

Without information about the distribution of the input values, it is hard to make an always-correct decision in the optimizer. (That said, a jump table is likely a good idea in most cases.)

[mvdan]

Thank you - this makes sense. Seems like I should pay closer attention to the jump table issue rather than this one.

[randall77]

Let's close this in favor of the jump table issue (#5496).