Skip to content

Optimise squared, Mul, and Exp #71

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
Merged
chfast merged 8 commits into from
Jun 5, 2020
Merged

Optimise squared, Mul, and Exp #71

chfast merged 8 commits into from
Jun 5, 2020

Conversation

@yperbasis
Copy link
Contributor

@yperbasis yperbasis commented Jun 4, 2020 •
edited
Loading 

name                     old time/op  new time/op  delta
Mul/single/uint256-8     8.23ns ± 2%  6.90ns ± 1%  -16.11%  (p=0.000 n=10+9)
Mul/single/big-8         64.5ns ± 1%  62.8ns ± 1%   -2.65%  (p=0.000 n=9+9)
_Exp/large/big-8         23.7µs ± 1%  23.7µs ± 1%     ~     (p=0.896 n=10+10)
_Exp/large/uint256-8     3.34µs ± 1%  2.72µs ± 3%  -18.63%  (p=0.000 n=8+10)
_Exp/small/big-8         7.12µs ± 2%  7.09µs ± 0%     ~     (p=0.345 n=10+9)
_Exp/small/uint256-8      283ns ± 1%   229ns ± 1%  -19.22%  (p=0.000 n=9+10)
Square/single/uint256-8  6.27ns ± 1%  5.14ns ± 1%  -17.91%  (p=0.000 n=10+10)
Square/single/big-8      60.0ns ± 2%  60.0ns ± 1%     ~     (p=0.781 n=10+10)

@yperbasis yperbasis changed the title Optimise Mul & Exp Optimise square, Mul, and Exp Jun 4, 2020
@yperbasis yperbasis changed the title Optimise square, Mul, and Exp Optimise squared, Mul, and Exp Jun 4, 2020
holiman
holiman approved these changes Jun 4, 2020
View reviewed changes
Copy link
Owner

@holiman holiman left a comment

Choose a reason for hiding this comment

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

Thanks, nice work!

@holiman holiman requested a review from chfast June 4, 2020 16:24
chfast
chfast reviewed Jun 4, 2020
View reviewed changes
Copy link
Collaborator

@chfast chfast left a comment

Choose a reason for hiding this comment

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

I'm starting to hate Go inliner...

@chfast
Copy link
Collaborator

chfast commented Jun 4, 2020

My benchmarks:

name                     old time/op  new time/op  delta
Mul/single/uint256-8     7.95ns ± 0%  6.56ns ± 0%  -17.46%  (p=0.000 n=16+18)
Mul/single/big-8         59.4ns ± 1%  59.2ns ± 0%     ~     (p=0.274 n=19+17)
Square/single/uint256-8  5.76ns ± 0%  4.94ns ± 0%  -14.20%  (p=0.000 n=18+19)
Square/single/big-8      57.5ns ± 0%  57.5ns ± 0%     ~     (p=0.077 n=18+18)
_Exp/large/big-8         21.3µs ± 1%  21.3µs ± 0%     ~     (p=0.925 n=20+18)
_Exp/large/uint256-8     3.00µs ± 0%  2.54µs ± 0%  -15.61%  (p=0.000 n=18+16)
_Exp/small/big-8         6.33µs ± 1%  6.34µs ± 1%     ~     (p=0.361 n=19+20)
_Exp/small/uint256-8      254ns ± 1%   217ns ± 0%  -14.42%  (p=0.000 n=20+15)

@chfast
Copy link
Collaborator

chfast commented Jun 4, 2020

The change you reverted in umul() is also worth having.

name                     old time/op  new time/op  delta
MulMod/small/uint256-8   33.6ns ± 0%  32.3ns ± 0%  -3.97%  (p=0.000 n=19+17)
MulMod/mod64/uint256-8   97.5ns ± 1%  96.1ns ± 0%  -1.48%  (p=0.000 n=20+18)
MulMod/mod128/uint256-8   176ns ± 0%   171ns ± 0%  -2.84%  (p=0.000 n=17+17)
MulMod/mod192/uint256-8   173ns ± 0%   168ns ± 0%  -3.15%  (p=0.000 n=20+20)
MulMod/mod256/uint256-8   169ns ± 0%   162ns ± 0%  -4.14%  (p=0.000 n=17+18)

@chfast
Copy link
Collaborator

chfast commented Jun 4, 2020

Can you rebase the branch? It contains some already merged commits and a merge commit.

@holiman
Copy link
Owner

holiman commented Jun 5, 2020 •
edited
Loading

@yperbasis try a git checkout fast_mul && git fetch origin && git rebase -i origin/master , which remove empty merge-commits.
(edited, should be git fetch origin)
And then followed by git push -f if all went well.

@holiman
Copy link
Owner

holiman commented Jun 5, 2020 •
edited
Loading

(and add back the improvement to umul)

@AlexeyAkhunov
Copy link

AlexeyAkhunov commented Jun 5, 2020

Test comment

@yperbasis
Copy link
Contributor Author

yperbasis commented Jun 5, 2020

@yperbasis try a git checkout fast_mul && git fetch origin && git rebase -i origin/master , which remove empty merge-commits.
(edited, should be git fetch origin)
And then followed by git push -f if all went well.

Done, but some history appears to still linger for some reason.

@yperbasis
Copy link
Contributor Author

yperbasis commented Jun 5, 2020

(and add back the improvement to umul)

Done

@holiman
Copy link
Owner

holiman commented Jun 5, 2020

Ok, don't worry about it - we can always squash-merge.

However, If you do want it explicitly it to be commit-merged, then it needs to be rebased, empty commits removed and/or squashed to relevant commits.

chfast
chfast approved these changes Jun 5, 2020
View reviewed changes
Copy link
Collaborator

@chfast chfast left a comment

Choose a reason for hiding this comment

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

LGTM, but I'd like to clean up git history. I will do it on a side and let you know.

@yperbasis
Copy link
Contributor Author

yperbasis commented Jun 5, 2020

Ok, don't worry about it - we can always squash-merge.

However, If you do want it explicitly it to be commit-merged, then it needs to be rebased, empty commits removed and/or squashed to relevant commits.

I'm fine if you squash-merge it.

@chfast chfast merged commit d2f698f into holiman:master Jun 5, 2020
@chfast
Copy link
Collaborator

chfast commented Jun 5, 2020

Done. Thanks a lot.

@yperbasis yperbasis deleted the fast_mul branch June 5, 2020 11:07
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@holiman holiman holiman approved these changes

@chfast chfast chfast 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.

4 participants

@yperbasis @chfast @holiman @AlexeyAkhunov