Use rustc-hash for the hottest hashmaps #40

Merged
wetneb merged 1 commit from Noratrieb/mergiraf:speedy-hash into main 2024-11-20 10:31:01 +01:00

1 commit

Author SHA1 Message Date
Noratrieb
3980d3e340 Use rustc-hash for the hottest hashmaps
All checks were successful
/ test (pull_request) Successful in 45s
Most of the time in the program is spent hashing things for hashmaps in
the matcher. It's currently using the default Rust hasher, which is
SipHash1-3. SipHash1-3 is not known for being particularly fast
(instead, it excels at its security properties).

I have tested several hashers to compare it, `foldhash` (0.1.3) fast and
quality, `fxhash` (0.2.1) and `rustc-hash` (2.0.0).

We instead use the `rustc-hash` crate which provides a very fast hash.
While `fxhash` performs equally well, that crate is not maintained, while rustc-hash is.

```
Benchmark 1: /home/nora/projects/mergiraf/target/release/mergiraf-foldhash-fast merge --git .merge_file_6vIArC .merge_file_KYG0x3 .merge_file_9waipA -s fb4f872 -x HEAD -y branch1 -p a.yaml
  Time (mean ± σ):      2.716 s ±  0.040 s    [User: 2.685 s, System: 0.054 s]
  Range (min … max):    2.672 s …  2.771 s    10 runs

Benchmark 2: /home/nora/projects/mergiraf/target/release/mergiraf-foldhash-quality merge --git .merge_file_6vIArC .merge_file_KYG0x3 .merge_file_9waipA -s fb4f872 -x HEAD -y branch1 -p a.yaml
  Time (mean ± σ):      2.734 s ±  0.039 s    [User: 2.703 s, System: 0.053 s]
  Range (min … max):    2.667 s …  2.791 s    10 runs

Benchmark 3: /home/nora/projects/mergiraf/target/release/mergiraf-fxhash merge --git .merge_file_6vIArC .merge_file_KYG0x3 .merge_file_9waipA -s fb4f872 -x HEAD -y branch1 -p a.yaml
  Time (mean ± σ):      2.317 s ±  0.060 s    [User: 2.288 s, System: 0.049 s]
  Range (min … max):    2.229 s …  2.431 s    10 runs

Benchmark 4: /home/nora/projects/mergiraf/target/release/mergiraf-rustc-hash merge --git .merge_file_6vIArC .merge_file_KYG0x3 .merge_file_9waipA -s fb4f872 -x HEAD -y branch1 -p a.yaml
  Time (mean ± σ):      2.273 s ±  0.035 s    [User: 2.241 s, System: 0.052 s]
  Range (min … max):    2.226 s …  2.335 s    10 runs

Benchmark 5: /home/nora/projects/mergiraf/target/release/mergiraf-normal merge --git .merge_file_6vIArC .merge_file_KYG0x3 .merge_file_9waipA -s fb4f872 -x HEAD -y branch1 -p a.yaml
  Time (mean ± σ):      5.043 s ±  0.081 s    [User: 5.019 s, System: 0.050 s]
  Range (min … max):    4.954 s …  5.223 s    10 runs

Summary
  /home/nora/projects/mergiraf/target/release/mergiraf-rustc-hash merge --git .merge_file_6vIArC .merge_file_KYG0x3 .merge_file_9waipA -s fb4f872 -x HEAD -y branch1 -p a.yaml ran
    1.02 ± 0.03 times faster than /home/nora/projects/mergiraf/target/release/mergiraf-fxhash merge --git .merge_file_6vIArC .merge_file_KYG0x3 .merge_file_9waipA -s fb4f872 -x HEAD -y branch1 -p a.yaml
    1.19 ± 0.03 times faster than /home/nora/projects/mergiraf/target/release/mergiraf-foldhash-fast merge --git .merge_file_6vIArC .merge_file_KYG0x3 .merge_file_9waipA -s fb4f872 -x HEAD -y branch1 -p a.yaml
    1.20 ± 0.03 times faster than /home/nora/projects/mergiraf/target/release/mergiraf-foldhash-quality merge --git .merge_file_6vIArC .merge_file_KYG0x3 .merge_file_9waipA -s fb4f872 -x HEAD -y branch1 -p a.yaml
    2.22 ± 0.05 times faster than /home/nora/projects/mergiraf/target/release/mergiraf-normal merge --git .merge_file_6vIArC .merge_file_KYG0x3 .merge_file_9waipA -s fb4f872 -x HEAD -y branch1 -p a.yaml
```

The benchmarking was performed on top of
e6b3b34abd (which adds DFS
precomputation).

The benchmark data was the same, a ~4k loc PNPM YAML lockfile with a
one-line change/conflict.
2024-11-19 20:49:38 +01:00