Skip to content

uint256: optimize umul, MulOverflow, MulMod, MulDivOverflow #166

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
holiman merged 1 commit into from
May 13, 2024
Merged

uint256: optimize umul, MulOverflow, MulMod, MulDivOverflow #166

holiman merged 1 commit into from
May 13, 2024

Conversation

@AaronChen0
Copy link
Contributor

@AaronChen0 AaronChen0 commented May 12, 2024

The API of umul is changed to reduce an array copy.

Test

go test ./...

ok  	github.com/holiman/uint256	1.381s

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                │
Mul/single/uint256-16              4.306n ± 2%   4.248n ± 1%   -1.36% (p=0.007 n=10)
Mul/single/big-16                  37.11n ± 2%   36.92n ± 1%        ~ (p=0.072 n=10)
MulOverflow/single/uint256-16      14.64n ± 2%   10.07n ± 1%  -31.22% (p=0.000 n=10)
MulOverflow/single/big-16          37.04n ± 2%   37.02n ± 2%        ~ (p=0.698 n=10)
MulMod/small/uint256-16            20.92n ± 1%   17.79n ± 1%  -14.99% (p=0.000 n=10)
MulMod/mod64/uint256-16            37.74n ± 1%   36.41n ± 1%   -3.52% (p=0.000 n=10)
MulMod/mod128/uint256-16           61.82n ± 1%   57.38n ± 2%   -7.19% (p=0.000 n=10)
MulMod/mod192/uint256-16           77.23n ± 1%   72.75n ± 1%   -5.80% (p=0.000 n=10)
MulMod/mod256/uint256-16           88.37n ± 1%   86.69n ± 2%   -1.90% (p=0.000 n=10)
MulMod/mod256/uint256r-16          42.05n ± 1%   38.02n ± 1%   -9.57% (p=0.000 n=10)
MulMod/small/big-16                36.24n ± 1%   36.25n ± 1%        ~ (p=0.812 n=10)
MulMod/mod64/big-16                58.35n ± 1%   58.09n ± 1%        ~ (p=0.781 n=10)
MulMod/mod128/big-16               194.7n ± 0%   194.5n ± 1%        ~ (p=0.362 n=10)
MulMod/mod192/big-16               223.4n ± 1%   223.6n ± 1%        ~ (p=0.566 n=10)
MulMod/mod256/big-16               258.7n ± 1%   258.6n ± 0%        ~ (p=0.956 n=10)
MulDivOverflow/small/uint256-16    23.77n ± 2%   22.72n ± 1%   -4.44% (p=0.000 n=10)
MulDivOverflow/div64/uint256-16    27.85n ± 1%   27.46n ± 1%   -1.40% (p=0.001 n=10)
MulDivOverflow/div128/uint256-16   45.97n ± 1%   43.82n ± 1%   -4.69% (p=0.000 n=10)
MulDivOverflow/div192/uint256-16   59.26n ± 0%   56.96n ± 1%   -3.87% (p=0.000 n=10)
MulDivOverflow/div256/uint256-16   76.16n ± 1%   73.23n ± 1%   -3.85% (p=0.000 n=10)
MulDivOverflow/small/big-16        56.44n ± 1%   57.05n ± 1%   +1.07% (p=0.006 n=10)
MulDivOverflow/div64/big-16        63.14n ± 0%   63.33n ± 1%        ~ (p=0.492 n=10)
MulDivOverflow/div128/big-16       194.7n ± 1%   196.4n ± 1%   +0.85% (p=0.000 n=10)
MulDivOverflow/div192/big-16       227.0n ± 0%   230.2n ± 1%   +1.43% (p=0.000 n=10)
MulDivOverflow/div256/big-16       260.6n ± 0%   260.9n ± 0%        ~ (p=0.567 n=10)
geomean                            58.68n        56.38n        -3.92%

@codecov
Copy link

codecov bot commented May 12, 2024

Codecov Report

All modified and coverable lines are covered by tests ✅

Project coverage is 100.00%. Comparing base (34f0760) to head (51a2085).

Additional details and impacted files 
@@            Coverage Diff            @@
##            master      #166   +/-   ##
=========================================
  Coverage   100.00%   100.00%           
=========================================
  Files            5         5           
  Lines         1626      1628    +2     
=========================================
+ Hits          1626      1628    +2

@holiman
Copy link
Owner

holiman commented May 13, 2024

The numbers look really nice!

[user@work uint256]$ benchstat umul.1 umul.2
name                             old time/op    new time/op    delta
Mul/single/uint256-8               12.2ns ±35%    13.0ns ±42%     ~     (p=0.780 n=10+10)
MulOverflow/single/uint256-8       43.9ns ±37%    25.3ns ±42%  -42.45%  (p=0.000 n=10+10)
MulMod/small/uint256-8             54.9ns ±54%    36.3ns ±23%  -33.93%  (p=0.013 n=10+9)
MulMod/mod64/uint256-8              101ns ±53%     105ns ±31%     ~     (p=0.579 n=10+10)
MulMod/mod128/uint256-8             205ns ±43%     181ns ±39%     ~     (p=0.211 n=10+10)
MulMod/mod192/uint256-8             212ns ±53%     216ns ±42%     ~     (p=0.494 n=10+10)
MulMod/mod256/uint256-8             269ns ±41%     198ns ±37%  -26.29%  (p=0.042 n=10+10)
MulMod/mod256/uint256r-8            131ns ±14%     111ns ±36%     ~     (p=0.085 n=10+10)
MulDivOverflow/small/uint256-8     70.4ns ±44%    47.9ns ±29%     ~     (p=0.053 n=10+9)
MulDivOverflow/div64/uint256-8     93.1ns ±42%    84.8ns ±46%     ~     (p=0.436 n=10+10)
MulDivOverflow/div128/uint256-8     117ns ±23%     123ns ±54%     ~     (p=0.631 n=10+10)
MulDivOverflow/div192/uint256-8     177ns ±54%     182ns ±41%     ~     (p=0.739 n=10+10)
MulDivOverflow/div256/uint256-8     215ns ±66%     216ns ±59%     ~     (p=0.631 n=10+10)

@holiman holiman merged commit 5ecf78c into holiman:master May 13, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

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