-
Notifications
You must be signed in to change notification settings - Fork 17.9k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
cmd/compile: optimize type switch #18492
Comments
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 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.
|
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.
generates for the switch
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 see also #15780 (comment) |
When doing i.(T) for non-empty-interface i and concrete type T, there's no need to read the type out of the itab. Just compare the itab to the itab we expect for that interface/type pair. Also optimize type switches by putting the type hash of the concrete type in the itab. That way we don't need to load the type pointer out of the itab. Update #18492 Change-Id: I49e280a21e5687e771db5b8a56b685291ac168ce Reviewed-on: https://go-review.googlesource.com/34810 Run-TryBot: Keith Randall <khr@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com> Reviewed-by: David Chase <drchase@google.com>
With go1.9beta2, I get
|
Go 1.11.2:
|
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. |
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:
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
The text was updated successfully, but these errors were encountered: