Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

perf: improve poseidon2 time by 2 times #739

Merged
merged 4 commits into from
Jan 14, 2025
Merged

perf: improve poseidon2 time by 2 times #739

merged 4 commits into from
Jan 14, 2025

Conversation

alxiong
Copy link
Contributor

@alxiong alxiong commented Jan 14, 2025 •
edited
Loading

closes: #738

This PR:

  • Unroll .pow(5) to significantly cut down permutation cost

Flamegraph

Download this: cargo 2025-01-14 16.20 profile.json

Go to https://profiler.firefox.com and load this file (which you can hover around to see the percentage clearly). Alternatively, see the below screenshot:

Screenshot 2025-01-14 at 4 39 17 PM

Right now, the new dominant cost leader is MulAssign which I don't think we can cut further, but I still didn't quite achieve the same performance than the paper reported, still a (7.2-6.5) gap for bls12, with t=2.

Before we can merge this PR, please make sure that all the following items have been
checked off. If any of the checklist items are not applicable, please leave them but
write a little note why.

  • Targeted PR against correct branch (main)
  • Linked to GitHub issue with discussion and accepted design OR have an explanation in the PR that describes this work.
  • Wrote unit tests
  • Updated relevant documentation in the code
  • Added relevant changelog entries to the CHANGELOG.md of touched crates.
  • Re-reviewed Files changed in the GitHub PR explorer

@alxiong alxiong requested a review from mrain as a code owner January 14, 2025 07:55
@alxiong alxiong changed the title perf: improve poseidon2 time by 2 times perf: improve poseidon2 time by 1.6 times Jan 14, 2025
@alxiong alxiong marked this pull request as draft January 14, 2025 08:38
@alxiong
Copy link
Contributor Author

alxiong commented Jan 14, 2025 •
edited
Loading

🥂 We are on-par with the expected speed:

Poseidon2 over (Bls12_381::Fr, t=2)/1k iter
                        time:   [5.3735 ms 5.3750 ms 5.3771 ms]
Poseidon2 over (Bls12_381::Fr, t=2)/100k iter
                        time:   [545.90 ms 557.12 ms 568.68 ms]

Poseidon2 over (Bls12_381::Fr, t=3)/1k iter
                        time:   [6.2261 ms 6.2424 ms 6.2607 ms]
Poseidon2 over (Bls12_381::Fr, t=3)/100k iter
                        time:   [623.22 ms 624.88 ms 626.58 ms]

Poseidon2 over (Bn254::Fr, t=3)/1k iter
                        time:   [6.1864 ms 6.2344 ms 6.2721 ms]
Poseidon2 over (Bn254::Fr, t=3)/100k iter
                        time:   [614.75 ms 617.18 ms 619.94 ms]

for comparison, the old one:

Poseidon2 over (Bls12_381::Fr, t=2)/1k iter
                        time:   [12.217 ms 12.254 ms 12.324 ms]
Poseidon2 over (Bls12_381::Fr, t=2)/100k iter
                        time:   [1.2291 s 1.2487 s 1.2811 s]

Poseidon2 over (Bls12_381::Fr, t=3)/1k iter
                        time:   [14.579 ms 14.650 ms 14.713 ms]
Poseidon2 over (Bls12_381::Fr, t=3)/100k iter
                        time:   [1.4549 s 1.4633 s 1.4767 s]

Poseidon2 over (Bn254::Fr, t=3)/1k iter
                        time:   [14.828 ms 14.891 ms 15.010 ms]
Poseidon2 over (Bn254::Fr, t=3)/100k iter
                        time:   [1.4809 s 1.4891 s 1.5012 s]

@alxiong alxiong marked this pull request as ready for review January 14, 2025 09:27
@alxiong alxiong changed the title perf: improve poseidon2 time by 1.6 times perf: improve poseidon2 time by 2 times Jan 14, 2025
mrain
mrain approved these changes Jan 14, 2025
View reviewed changes
Copy link
Contributor

@mrain mrain left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Could we also post the previous bench result here?

@alxiong
Copy link
Contributor Author

alxiong commented Jan 14, 2025

yes i have included the previous benchmark above @mrain

@alxiong alxiong merged commit 9595d84 into main Jan 14, 2025
7 checks passed
@alxiong alxiong deleted the perf-p2 branch January 14, 2025 14:32
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@mrain mrain mrain approved these changes

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

Performance: slow poseidon2 permutation
2 participants
@alxiong @mrain