• Keith Randall's avatar
    bytes,strings: in generic Index, use mix of IndexByte and Rabin-Karp · a0252775
    Keith Randall authored
    Use IndexByte first, as it allows us to skip lots of bytes quickly.
    If IndexByte is generating a lot of false positives, switch over to Rabin-Karp.
    
    Experiments for ppc64le
    bytes:
    name                             old time/op  new time/op  delta
    IndexPeriodic/IndexPeriodic2-2   1.12ms ± 0%  0.18ms ± 0%  -83.54%  (p=0.000 n=10+9)
    IndexPeriodic/IndexPeriodic4-2    635µs ± 0%   184µs ± 0%  -71.06%  (p=0.000 n=9+9)
    IndexPeriodic/IndexPeriodic8-2    289µs ± 0%   184µs ± 0%  -36.51%  (p=0.000 n=10+9)
    IndexPeriodic/IndexPeriodic16-2   133µs ± 0%   183µs ± 0%  +37.68%  (p=0.000 n=10+9)
    IndexPeriodic/IndexPeriodic32-2  68.3µs ± 0%  70.2µs ± 0%   +2.76%  (p=0.000 n=10+10)
    IndexPeriodic/IndexPeriodic64-2  35.8µs ± 0%  36.6µs ± 0%   +2.17%  (p=0.000 n=8+10)
    
    strings:
    name                             old time/op  new time/op  delta
    IndexPeriodic/IndexPeriodic2-2    184µs ± 0%   184µs ± 0%   +0.11%  (p=0.029 n=4+4)
    IndexPeriodic/IndexPeriodic4-2    184µs ± 0%   184µs ± 0%     ~     (p=0.886 n=4+4)
    IndexPeriodic/IndexPeriodic8-2    184µs ± 0%   184µs ± 0%     ~     (p=0.486 n=4+4)
    IndexPeriodic/IndexPeriodic16-2   185µs ± 1%   184µs ± 0%     ~     (p=0.343 n=4+4)
    IndexPeriodic/IndexPeriodic32-2   184µs ± 0%    69µs ± 0%  -62.37%  (p=0.029 n=4+4)
    IndexPeriodic/IndexPeriodic64-2   184µs ± 0%    37µs ± 0%  -80.17%  (p=0.029 n=4+4)
    
    Fixes #22578
    
    Change-Id: If2a4d8554cb96bfd699b58149d13ac294615f8b8
    Reviewed-on: https://go-review.googlesource.com/76070Reviewed-by: 's avatarAlberto Donizetti <alb.donizetti@gmail.com>
    a0252775
bytes_test.go 40.5 KB