mergiraf/mergiraf
mergiraf/mergiraf
9
213
Fork 45
Code Issues 51 Pull requests 7 Releases 19 Activity Actions

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
Conversation 1 Commits 1 Files changed 8 +33 -20
Noratrieb commented 2024-11-18 20:32:46 +01:00
Contributor
Copy link

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 (#39) (which adds DFS
precomputation).

The benchmark data was the same, a ~4k loc PNPM YAML lockfile with a
one-line change/conflict.

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 e6b3b34abd0e0fd688bb35a41e4e363e49551091 (#39) (which adds DFS precomputation). The benchmark data was the same, a ~4k loc PNPM YAML lockfile with a one-line change/conflict.
Noratrieb changed title from Use FxHash for the hottest hashmaps to Use rustc-hash for the hottest hashmaps 2024-11-18 20:33:03 +01:00
wetneb approved these changes 2024-11-19 04:57:21 +01:00
wetneb left a comment
Owner
Copy link

Really nice too! The speedup is impressive and the change feels intuitively sensible. Thank you!

Really nice too! The speedup is impressive and the change feels intuitively sensible. Thank you!
wetneb merged commit a9136b983f into main 2024-11-20 10:31:01 +01:00
Sign in to join this conversation.
Reviewers
No reviewers
wetneb
Labels
Clear labels   
Compat/Breaking

Breaking change that won't be backward compatible

  
Kind
Bad merge
Examples where the merging algorithm doesn't work as well as it should

  
Kind
Bug
Something is not working

  
Kind
Documentation
Documentation changes

  
Kind
Enhancement
Improve existing functionality

  
Kind
Feature
New functionality

  
Kind
New language

  
Kind
Security
This is security issue

  
Kind
Testing
Issue or pull request related to testing

  
Priority
Critical
The priority is critical

  
Priority
High
The priority is high

  
Priority
Low
The priority is low

  
Priority
Medium
The priority is medium

  
Reviewed
Confirmed
Issue has been confirmed

  
Reviewed
Duplicate
This issue or pull request already exists

  
Reviewed
Invalid
Invalid issue

  
Reviewed
Won't Fix
This issue won't be fixed

  
Status
Abandoned
Somebody has started to work on this but abandoned work

  
Status
Blocked
Something is blocking this issue or pull request

  
Status
Need More Info
Feedback is required to reproduce issue or to continue work

No labels
Compat/Breaking
Kind
Bad merge
Kind
Bug
Kind
Documentation
Kind
Enhancement
Kind
Feature
Kind
New language
Kind
Security
Kind
Testing
Priority
Critical
Priority
High
Priority
Low
Priority
Medium
Reviewed
Confirmed
Reviewed
Duplicate
Reviewed
Invalid
Reviewed
Won't Fix
Status
Abandoned
Status
Blocked
Status
Need More Info
Milestone
Clear milestone
No items
No milestone
Projects
Clear projects
No items
No project
Assignees
Clear assignees
No assignees
2 participants
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference: mergiraf/mergiraf#40
No description provided.
Delete branch "Noratrieb/mergiraf:speedy-hash"

Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?