Skip to content

uint256: optimize MulMod, MulModWithReciprocal#172

Merged
holiman merged 1 commit intoholiman:masterfrom
AaronChen0:master
May 27, 2024
Merged

uint256: optimize MulMod, MulModWithReciprocal#172
holiman merged 1 commit intoholiman:masterfrom
AaronChen0:master

Conversation

@AaronChen0
Copy link
Copy Markdown
Contributor

@AaronChen0 AaronChen0 commented May 23, 2024

The api of reduce4 is changed to reduce array copies.

  1. The function reduce4 doesn't change the values of its parameters x, m, and mu. So it's fine to pass by pointers.
  2. In the case of z == m (They are alias), m is used before z, and z is only written in the last step. So this is fine too.

Benchmark

goos: linux
goarch: amd64
pkg: github.com/holiman/uint256
cpu: AMD Ryzen 7 7735H with Radeon Graphics         
                          │     old     │                 new                 │
                          │   sec/op    │   sec/op     vs base                │
MulMod/small/uint256-16     15.84n ± 2%   15.63n ± 1%   -1.33% (p=0.049 n=10)
MulMod/mod64/uint256-16     29.44n ± 1%   29.09n ± 2%   -1.17% (p=0.030 n=10)
MulMod/mod128/uint256-16    51.92n ± 1%   52.62n ± 2%        ~ (p=0.183 n=10)
MulMod/mod192/uint256-16    66.39n ± 2%   65.42n ± 1%        ~ (p=0.086 n=10)
MulMod/mod256/uint256-16    87.02n ± 2%   77.26n ± 1%  -11.20% (p=0.000 n=10)
MulMod/mod256/uint256r-16   38.07n ± 2%   27.52n ± 2%  -27.70% (p=0.000 n=10)
geomean                     41.79n        38.64n        -7.53%

@codecov
Copy link
Copy Markdown

codecov bot commented May 23, 2024

Codecov Report

All modified and coverable lines are covered by tests ✅

Project coverage is 100.00%. Comparing base (70cbe2b) to head (adec10c).

Additional details and impacted files 
@@            Coverage Diff            @@
##            master      #172   +/-   ##
=========================================
  Coverage   100.00%   100.00%           
=========================================
  Files            5         5           
  Lines         1632      1630    -2     
=========================================
- Hits          1632      1630    -2

holiman
holiman approved these changes May 27, 2024
View reviewed changes
Copy link
Copy Markdown
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.

LGTM, thanks!

@holiman
Copy link
Copy Markdown
Owner

holiman commented May 27, 2024 •
edited
Loading

Doesn't repro on my machine though:

goos: linux
goarch: amd64
pkg: github.com/holiman/uint256
cpu: 12th Gen Intel(R) Core(TM) i7-1270P
                         │ bench.mulmod.1 │             bench.mulmod.2              │
                         │     sec/op     │     sec/op      vs base                 │
MulMod/small/uint256-8     36.33n ± 32%     47.02n ± 28%          ~ (p=0.105 n=10)
MulMod/mod64/uint256-8     57.80n ± 15%     65.16n ± 41%          ~ (p=0.143 n=10)
MulMod/mod128/uint256-8    108.5n ±  9%     138.3n ± 45%    +27.47% (p=0.019 n=10)
MulMod/mod192/uint256-8    148.2n ± 18%     230.3n ± 40%          ~ (p=0.063 n=10)
MulMod/mod256/uint256-8    197.3n ± 66%     204.8n ± 53%          ~ (p=0.565 n=10)
MulMod/mod256/uint256r-8   87.19n ± 47%     80.01n ± 35%          ~ (p=0.280 n=10)
MulMod/small/big-8         84.76n ±   ∞ ¹   81.11n ±   ∞ ¹        ~ (p=0.229 n=3+4)

OTOH, my machine has variations going all over the place. I'll trust your numbers more.

@holiman holiman merged commit b85bc2a into holiman:master May 27, 2024
@AaronChen0
Copy link
Copy Markdown
Contributor Author

AaronChen0 commented May 27, 2024

You can consider spinning up a ubuntu vps on DigitalOcean or Vultr for testing and delete the machine after finishing testing.

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

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@AaronChen0 @holiman