Skip to content
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: use bit tests for binary search in type switches #29292

Open
josharian opened this Issue Dec 16, 2018 · 3 comments

Comments

Projects
None yet
2 participants
@josharian
Copy link
Contributor

commented Dec 16, 2018

Consider a large type switch with constant (non-interface) cases, like:

package p

func f(e interface{}) int {
	switch e.(type) {
	case int:
		return 0
	case bool:
		return 1
	case byte:
		return 2
	case uint16:
		return 3
	case string:
		return 4
	}
	return 5
}

The generated code does a binary search using < over hashes for the type cases. However, the actual values, being hashes, are large, so the generated code contains large constants for doing the comparisons. Using 1.11 for the above code, here's an excerpt from the middle:

	0x000a 00010 (type_switch_opt.go:7)	MOVL	16(AX), CX
	0x000d 00013 (type_switch_opt.go:7)	CMPL	CX, $1715356255
	0x0013 00019 (type_switch_opt.go:7)	JHI	99
	0x0015 00021 (type_switch_opt.go:7)	CMPL	CX, $335480517
	0x001b 00027 (type_switch_opt.go:7)	JNE	91

But since the constants are know to be hashes, we could do our binary search using bit tests instead: First split on whether hash&1 != 0, then the second bit, and so on as needed. This should afford a shorter instruction encoding and perhaps even faster execution. (This might need to apply to only some architectures; investigation required.) It would be a good idea to confirm at compile time that the bit test will do a good job of splitting the inputs (almost) in half, and moving on to higher bits if the candidate bit doesn't work well.

@josharian josharian added this to the Unplanned milestone Dec 16, 2018

@martisch

This comment has been minimized.

Copy link
Member

commented Dec 16, 2018

The compiler could calculate the entropies in each of the possible splits produced by bit tests (maybe on some architectures we might use multiple flags for more than 2 way splits with some operations, e.g. shifts) and choose the split that results in the most information gain. Repeat until there are only the case items of the switch branch left. Such a decision tree building mechanism could even be enhanced with profile guided optimization data later and used for non-type switches.

@josharian

This comment has been minimized.

Copy link
Contributor Author

commented Dec 16, 2018

@martisch it doesn’t work as nicely for all non-type switches, because non-type switches often have more natural structure, e.g. contiguous ranges of values that all map to the same case, and it is a bit harder to figure out how to take advantage of that while still making optimism decisions higher in the tree. The fact that type switches use a hash makes them easier and simpler and thus a good place to start.

@martisch

This comment has been minimized.

Copy link
Member

commented Dec 16, 2018

@josharian Agreed that hashes should have a nicer distribution that can be leveraged better. Definitely a nice place to start. I was thinking this could be tested and extended to e.g. large enum like switches later once there is infrastructure that the compiler can then use to make a decision on applying this to a more wider range of applicable switches. However enums usually are smaller so the size difference for compares would not seem to matter as much. There could be some easy filtering heuristic that doesn't even try this on switches with ranges so no work is wasted on them during compilation. But all this is future talk. Better to start simple and develop, test and benchmark something that works nicely with type switches first which is the scope of this issue.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.