cmd/compile: use hashing for switch statements

[mdempsky]

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.

[josharian]

Drive-by comment from phone: It wouldn’t surprise me if “use the first word of the string data” turns out to in practice to be a decent first-cut hash, and it is certainly cheap (can be generated inline, should be just a few instructions).

[pierrec]

After reading minimal perfect hash function which does have an implementation go-mph, maybe that can just be used as is?

[lranjbar]

@mdempsky @josharian @pierrec @toothrot Has anyone started on this issue? It seems interesting.

[mdempsky]

@lranjbar I don't think anyone has started on it yet. Happy to answer any quick questions to get you started. (I probably won't be able to give any more serious guidance/feedback for another week though.)

[lranjbar]

@mdempsky I okay with waiting a little bit for more guidance. (I do actually have a pretty busy week myself.) I can still dig into it a bit more on my own, I was just curious before I started. :)

[jupj]

About the jump table, we probably prefer a near minimal perfect hash function. A strict minimal perfect hash function would always lead to a collision for the default case of the switch. One option is to extend the size of the jump table from minimal to the next power of 2, and jump to the default case for indexes that don't collide with a pre-computed hash. At the same time, that would allow us to use cheaper bitwise operators instead of the more expensive % operator when calculating the hash/index for the jump table.

A question is how to evaluate the performance of binary search vs jump table. Constructing the near minimal hash probably requires some additional cycles, compared to a cheap hash (or the even cheaper "use the first word of the string data", as mentioned by @josharian). I suppose that the performance benefits of the jump table comes with large n. For small n, the difference might be less clear?

[jupj]

I've implemented a hash function using fnv, based on string length and minimal unique prefix (@lranjbar I hope you don't mind). Also have a working implementation of a near minimal perfect hash function for a jump table.

This finds a unique hash reasonably fast (typically within the first 1-2 seeds) and hash/jumptable benchmarks indicate performance close to maphash on linux/amd64. (I've used all string-typed switch cases from the golang/go repo as testdata.)

@mdempsky how/where should I submit this code?

[mdempsky]

@jupj Great! Thanks for working on this. Do you have the code available somewhere that I can take a look?

What would probably be best is if you can make a standalone Go package that we can include in the standard repo as something like "cmd/compile/internal/phash" (or ".../perfect hash" or whatever; open to suggestions).

With that done, I can help wire it into gc/swt.go. Or give you pointers on doing this yourself if you'd like.

[jupj]

@mdempsky please find the code here: https://github.com/jupj/go-issue-34381 (findhash.go contains the hash functions) I'll modify this to a standalone package that could be included in the standard repo.

I'm new to compiler work, so I appreciate any help and/or pointers to wire it into gc/swt.go!

Edit: added pointer to findhash.go

[lranjbar]

@jupj No worries. It's been almost a year and clearly I didn't have time outside of work to focus on this. 😅 Good luck with your submission.

[gopherbot]

Change https://golang.org/cl/256898 mentions this issue: cmd/compile: add internal package phash

[josharian]

I think we're on a good path for this, but one thing to double-check as we integrate is that if a giant string arrives for a switch statement only composed of small strings, we don't end up doing O(giant) work to calculate a hash. This protection could have many forms (hash function design, checking max length, checking exact length before hashing, etc.), but we should make sure it's there.

[jupj]

I think we're on a good path for this, but one thing to double-check as we integrate is that if a giant string arrives for a switch statement only composed of small strings, we don't end up doing O(giant) work to calculate a hash. This protection could have many forms (hash function design, checking max length, checking exact length before hashing, etc.), but we should make sure it's there.

Thanks, I updated the CL mentioned above, re-added the check for the minimum unique prefix length. This limits the work to O(prefixLen), with the maximum case string length in the switch statement as the upper bound of prefixLen. Is this sufficient to protect from giant strings?

---

Any tips for how to wire the perfect hashes into swt.go? I think this could be the next step, to validate the perfect hash functionality. I have two options in mind:

1. For each switch statement, generate an AST that implements the ad-hoc hash as an anonymous function. So switch s { will be rewritten to switch func(s string) uint32 { /* generated AST */ }(s) {, where the AST implements the selected perfect hash function with given seed and prefix length.

2. Generate functions (go source code) for all different combinations of cheap hashes and include them in the runtime library as runtime.phash_Len, runtime.phash_First, runtime.phash_LenFirst, etc. The compiler will rewrite the switch statements to use these, eg. statement switch s { will be rewritten to switch runtime.phash_LenFirst(s) {. The compiler will include seed and prefix parameters to the hash function where needed.

I don't have any experience generating AST, so I feel the latter option would be more approachable for me. There are 31 different combinations (fnv fallback included), so I think it would make sense to generate the functions into the runtime library, at least for programs with more than 31 switch cases.

Comments?

[josharian]

We should generate AST.

Or leave it alone in swt.go and generate SSA in gc/ssa.go. I find generating SSA easier than generating AST, but since this would be the first switch-to-SSA direct lowering there's no sample code to work from and you're more likely to hit unexpected stumbling blocks.

[gopherbot]

Change https://golang.org/cl/260597 mentions this issue: cmd/compile: add -d=swthash flag for string switch hashing

[mdempsky]

As an update here: On Sunday, I played with integrating phash into the Go compiler and got it mostly working. CL is 260597 above. (If you're really curious, I streamed the compiler development process on Twitch at https://www.twitch.tv/videos/761008858; string hashing stuff starts at 37m20s and runs to the end of the stream. Beware Twitch only stores videos for 14 days.)

You can build targets with -gcflags=all=-d=swthash to enable the optimization. I haven't done any performance/size benchmarking yet.

[jupj]

Thanks for the stream, very insightful to watch!

[jupj]

Update: I've updated phash to generate ir for computing the hash (https://golang.org/cl/256898), and updated mdempsky's proof-of-concept to use the new ir nodes in https://golang.org/cl/307191

Benchmarked with compilecmp:

compilecmp master -> HEAD
master (c40dc677be): go/doc: avoid panic on references to functions with no body
HEAD (49958c0094): swthash always on

benchstat -geomean  /tmp/951139350 /tmp/784215165

completed 100 of 100, estimated time remaining 0s (ETA 8:37PM)      
name                      old time/op       new time/op       delta
Template                        327ms ± 4%        326ms ± 3%    ~     (p=0.957 n=98+100)
Unicode                         141ms ± 9%        141ms ± 9%    ~     (p=0.474 n=98+100)
GoTypes                         1.78s ± 2%        1.78s ± 2%    ~     (p=0.329 n=99+100)
Compiler                        153ms ± 9%        152ms ± 8%    ~     (p=0.114 n=97+95)
SSA                             12.9s ± 1%        12.8s ± 2%  -0.27%  (p=0.002 n=100+100)
Flate                           205ms ± 5%        205ms ± 5%    ~     (p=0.366 n=100+98)
GoParser                        306ms ± 4%        305ms ± 5%    ~     (p=0.207 n=92+99)
Reflect                         723ms ± 2%        723ms ± 2%    ~     (p=0.428 n=99+97)
Tar                             285ms ± 5%        285ms ± 6%    ~     (p=0.876 n=99+100)
XML                             368ms ± 3%        369ms ± 4%    ~     (p=0.179 n=98+98)
LinkCompiler                    628ms ± 3%        630ms ± 3%    ~     (p=0.124 n=97+95)
ExternalLinkCompiler            1.72s ± 2%        1.72s ± 2%    ~     (p=0.733 n=94+96)
LinkWithoutDebugCompiler        394ms ± 4%        395ms ± 4%    ~     (p=0.592 n=99+100)
[Geo mean]                      539ms             539ms       -0.02%

name                      old user-time/op  new user-time/op  delta
Template                        409ms ± 6%        408ms ± 8%    ~     (p=0.515 n=99+100)
Unicode                         186ms ±14%        185ms ±12%    ~     (p=0.752 n=99+100)
GoTypes                         2.19s ± 5%        2.19s ± 5%    ~     (p=0.415 n=100+100)
Compiler                        186ms ±12%        184ms ±14%    ~     (p=0.220 n=100+100)
SSA                             17.4s ± 4%        17.2s ± 5%  -0.90%  (p=0.002 n=100+100)
Flate                           249ms ± 9%        247ms ±10%    ~     (p=0.380 n=98+99)
GoParser                        359ms ± 9%        358ms ± 9%    ~     (p=0.200 n=96+99)
Reflect                         914ms ± 4%        914ms ± 4%    ~     (p=0.948 n=97+99)
Tar                             345ms ± 9%        347ms ±11%    ~     (p=0.430 n=99+100)
XML                             449ms ± 7%        449ms ± 6%    ~     (p=0.904 n=100+100)
LinkCompiler                    1.09s ± 5%        1.10s ± 4%  +0.63%  (p=0.032 n=100+100)
ExternalLinkCompiler            2.09s ± 3%        2.09s ± 4%    ~     (p=0.220 n=100+100)
LinkWithoutDebugCompiler        511ms ± 8%        515ms ± 6%  +0.92%  (p=0.043 n=99+97)
[Geo mean]                      689ms             689ms       -0.06%

name                      old text-bytes    new text-bytes    delta
HelloSize                       814kB ± 0%        813kB ± 0%  -0.09%  (p=0.000 n=100+100)

name                      old data-bytes    new data-bytes    delta
HelloSize                      13.1kB ± 0%       13.1kB ± 0%    ~     (all equal)

name                      old bss-bytes     new bss-bytes     delta
HelloSize                       206kB ± 0%        206kB ± 0%    ~     (all equal)

name                      old exe-bytes     new exe-bytes     delta
HelloSize                      1.21MB ± 0%       1.21MB ± 0%  -0.03%  (p=0.000 n=100+100)

file      before    after     Δ       %       
addr2line 3696741   3696773   +32     +0.001% 
api       5166358   5170862   +4504   +0.087% 
asm       4734867   4738515   +3648   +0.077% 
buildid   2445407   2445631   +224    +0.009% 
cgo       4453043   4453171   +128    +0.003% 
compile   23377375  23428593  +51218  +0.219% 
cover     4565624   4566136   +512    +0.011% 
dist      3288992   3295920   +6928   +0.211% 
doc       3742131   3745099   +2968   +0.079% 
fix       3154314   3159106   +4792   +0.152% 
link      6561029   6562917   +1888   +0.029% 
nm        3666294   3669582   +3288   +0.090% 
objdump   4093865   4095577   +1712   +0.042% 
pack      2218057   2217913   -144    -0.006% 
pprof     13600084  13606156  +6072   +0.045% 
test2json 2521324   2521068   -256    -0.010% 
trace     10223351  10227271  +3920   +0.038% 
vet       7033010   7040450   +7440   +0.106% 
total     108541866 108640740 +98874  +0.091% 

[gopherbot]

Change https://golang.org/cl/307191 mentions this issue: cmd/compile: hash strings in walk/switch.go

[shaneHowearth]

I streamed the compiler development process on Twitch at https://www.twitch.tv/videos/761008858; string hashing stuff starts at 37m20s and runs to the end of the stream. Beware Twitch only stores videos for 14 days.)

Could this content have been stored on another service (eg. Youtube/Vimeo/etc) because, 8 months later and I'm reading this issue gaining some fantastic learnings, and am not able to see that stream, which has obviously been helpful to the creation of the code

[gopherbot]

Change https://golang.org/cl/357330 mentions this issue: cmd/compile: implement jump tables

[gopherbot]

Change https://go.dev/cl/395714 mentions this issue: cmd/compile: modify switches of strings to use jump table for lengths