golang/go

cmd/compile: use hashing for switch statements

Open

#34,381 opened on Sep 18, 2019

View on GitHub
 (22 comments) (11 reactions) (0 assignees)Go (19,008 forks)batch import
NeedsInvestigationcompiler/runtimehelp wanted

Repository metrics

Stars
 (133,883 stars)
PR merge metrics
 (No merged PRs in 30d)

Description

Currently we implement switch statements with binary search. This works well for values that fit into a register, but for strings it might be better to compute a hash function.

Some thoughts:

  1. Even in the simple case of using a full hash function, exactly two passes over the switched value is probably better than O(log N) possible passes over it.

  2. Since we have the expected keys statically, we can use a simple, cheap universal hash (e.g., FNV? djb2?) and keep trying different seeds until we get one without any collisions.

  3. Instead of hashing all of the input bytes, we can hash just enough of them to avoid collisions.

  4. We can try using a minimal (or near minimal) perfect hash to emit a jump table instead of binary search. (This might even be useful for sparse integer values too.)

If someone can help figure out code that can take a []string and figures out an appropriate and cheap hash function to use, I can help wire it into swt.go.

Contributor guide