search

pandaman64 / lean-regex

Apache License 2.0
19 stars 1 forks source link

Try ByteArray #1

Closed pandaman64 closed 7 months ago

pandaman64 commented 8 months ago

Try ByteArray instead of Array Bool for the node set. It turned out that Array Bool was 10% faster in a simple benchmark.

$ hyperfine --warmup 10 "./array-bool 'lean|rust' /usr/share/dict/american-english"  "./bytearray 'lean|rust' /usr/share/dict/american-english"
Benchmark 1: ./array-bool 'lean|rust' /usr/share/dict/american-english
  Time (mean ± σ):     270.7 ms ±  10.4 ms    [User: 262.2 ms, System: 8.2 ms]
  Range (min … max):   261.3 ms … 296.2 ms    11 runs

Benchmark 2: ./bytearray 'lean|rust' /usr/share/dict/american-english
  Time (mean ± σ):     298.1 ms ±   5.3 ms    [User: 290.1 ms, System: 7.9 ms]
  Range (min … max):   291.0 ms … 306.1 ms    10 runs

Summary
  ./array-bool 'lean|rust' /usr/share/dict/american-english ran
    1.10 ± 0.05 times faster than ./bytearray 'lean|rust' /usr/share/dict/american-english
pandaman64 commented 8 months ago

I tried a bit bigger regex, and Array Bool was faster in this case as well.

$ hyperfine --warmup 10 "./array-bool 'lean|rust|Isabelle|coq|agda' /usr/share/dict/american-english"  "./bytearray 'lean|rust|Isabelle|coq|agda' /usr/share/dict/american-english"
Benchmark 1: ./array-bool 'lean|rust|Isabelle|coq|agda' /usr/share/dict/american-english
  Time (mean ± σ):     356.5 ms ±  20.6 ms    [User: 336.6 ms, System: 19.9 ms]
  Range (min … max):   330.8 ms … 395.7 ms    10 runs

Benchmark 2: ./bytearray 'lean|rust|Isabelle|coq|agda' /usr/share/dict/american-english
  Time (mean ± σ):     429.4 ms ±  22.8 ms    [User: 415.5 ms, System: 13.9 ms]
  Range (min … max):   406.0 ms … 477.2 ms    10 runs

Summary
  ./array-bool 'lean|rust|Isabelle|coq|agda' /usr/share/dict/american-english ran
    1.20 ± 0.09 times faster than ./bytearray 'lean|rust|Isabelle|coq|agda' /usr/share/dict/american-english
pandaman64 commented 8 months ago

I avoided ≠ 0, which seemed to help a bit. However, ByteArray still performed worse than Array Bool. Probably I should also experiment with inlining for hot functions.

$ hyperfine --warmup 10 "./array-bool 'lean|rust|Isabelle|coq|agda' /usr/share/dict/american-english"  "./bytearray 'lean|rust|Isabelle|coq|agda' /usr/share/dict/american-english" "./bytearray-deceq 'lean|rust|Isabelle|coq|agda' /usr/share/dict/american-english"
Benchmark 1: ./array-bool 'lean|rust|Isabelle|coq|agda' /usr/share/dict/american-english
  Time (mean ± σ):     323.7 ms ±   5.3 ms    [User: 318.7 ms, System: 5.0 ms]
  Range (min … max):   316.6 ms … 334.9 ms    10 runs

Benchmark 2: ./bytearray 'lean|rust|Isabelle|coq|agda' /usr/share/dict/american-english
  Time (mean ± σ):     422.3 ms ±  30.7 ms    [User: 414.1 ms, System: 7.9 ms]
  Range (min … max):   393.7 ms … 483.1 ms    10 runs

Benchmark 3: ./bytearray-deceq 'lean|rust|Isabelle|coq|agda' /usr/share/dict/american-english
  Time (mean ± σ):     354.3 ms ±   8.1 ms    [User: 347.4 ms, System: 6.9 ms]
  Range (min … max):   342.7 ms … 371.6 ms    10 runs

Summary
  ./array-bool 'lean|rust|Isabelle|coq|agda' /usr/share/dict/american-english ran
    1.09 ± 0.03 times faster than ./bytearray-deceq 'lean|rust|Isabelle|coq|agda' /usr/share/dict/american-english
    1.30 ± 0.10 times faster than ./bytearray 'lean|rust|Isabelle|coq|agda' /usr/share/dict/american-english