rollinghash icon indicating copy to clipboard operation
rollinghash copied to clipboard

Use `Len64` from "math/bits" in `Deg`

Open albert-bedrock opened this issue 2 years ago • 0 comments

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 Deg
    Time (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/bits didn'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

albert-bedrock avatar Oct 04 '23 06:10 albert-bedrock