rollinghash
rollinghash copied to clipboard
Use `Len64` from "math/bits" in `Deg`
Switches the Deg function in rabinkarp64/polynomials.go to use Len64 instead of the bit hacks version.
On my machine, this does not produce much of a speedup for go run roll/main.go but does speed up the rabin karp tests from ~23s to ~6s .
Benches
A small difference, but I did an unpaired t-test and it seems to be real.
Command:
hyperfine 'go run roll/main.go -size 2G'
- On main branch
Time (mean ± σ): 9.293 s ± 0.069 s [User: 6.782 s, System: 2.563 s] Range (min … max): 9.200 s … 9.411 s 10 runs - With changes to
DegTime (mean ± σ): 9.114 s ± 0.079 s [User: 6.632 s, System: 2.529 s] Range (min … max): 8.981 s … 9.236 s 10 runs
Notes
-
math/bitsdidn't exist until Go 1.9 ( https://pkg.go.dev/math/bits?tab=versions ) - Tests were done on a relatively new ARM apple macbook so maybe the speedup isn't replicable for other devices