Skip to content

optimize Exp for even bases#189

Merged
holiman merged 3 commits intoholiman:masterfrom
Valeh2012:optimized-exp
Dec 6, 2024
Merged

optimize Exp for even bases#189
holiman merged 3 commits intoholiman:masterfrom
Valeh2012:optimized-exp

Conversation

@Valeh2012
Copy link
Copy Markdown
Contributor

@Valeh2012 Valeh2012 commented Oct 30, 2024

full benchstat:

goarch: amd64
pkg: github.com/holiman/uint256
cpu: Intel(R) Xeon(R) Platinum 8370C CPU @ 2.80GHz
                         │    old.txt     │               new.txt               │
                         │     sec/op     │   sec/op     vs base                │
Exp/large/big-2               21.01µ ± 8%   21.60µ ± 5%        ~ (p=0.393 n=10)
Exp/large/even/big-2          6.033µ ± 6%   6.133µ ± 6%        ~ (p=0.353 n=10)
Exp/large/uint256-2           2.311µ ± 4%   2.348µ ± 5%        ~ (p=0.315 n=10)
Exp/large/even/uint256-2   2279.500n ± 4%   6.894n ± 3%  -99.70% (p=0.000 n=10)
Exp/small/big-2               7.050µ ± 8%   6.753µ ± 3%        ~ (p=0.579 n=10)
Exp/small/even/big-2          1.979µ ± 6%   1.982µ ± 6%        ~ (p=0.684 n=10)
Exp/small/uint256-2           200.0n ± 4%   205.8n ± 5%        ~ (p=0.853 n=10)
Exp/small/even/uint256-2    206.300n ± 4%   7.024n ± 5%  -96.60% (p=0.000 n=10)
geomean                       2.104µ        671.8n       -68.07%

                         │    old.txt     │                new.txt                │
                         │      B/op      │     B/op      vs base                 │
Exp/large/big-2            17.72Ki ± 0%     17.72Ki ± 0%       ~ (p=1.000 n=10) ¹
Exp/large/even/big-2       1.391Ki ± 0%     1.391Ki ± 0%       ~ (p=1.000 n=10) ¹
Exp/large/uint256-2          0.000 ± 0%       0.000 ± 0%       ~ (p=1.000 n=10) ¹
Exp/large/even/uint256-2     0.000 ± 0%       0.000 ± 0%       ~ (p=1.000 n=10) ¹
Exp/small/big-2            7.219Ki ± 0%     7.219Ki ± 0%       ~ (p=1.000 n=10) ¹
Exp/small/even/big-2       1.203Ki ± 0%     1.203Ki ± 0%       ~ (p=1.000 n=10) ¹
Exp/small/uint256-2          0.000 ± 0%       0.000 ± 0%       ~ (p=1.000 n=10) ¹
Exp/small/even/uint256-2     0.000 ± 0%       0.000 ± 0%       ~ (p=1.000 n=10) ¹
geomean                                 ²                 +0.00%                ²
¹ all samples are equal
² summaries must be >0 to compute geomean

                         │   old.txt    │               new.txt               │
                         │  allocs/op   │ allocs/op   vs base                 │
Exp/large/big-2            189.0 ± 0%     189.0 ± 0%       ~ (p=1.000 n=10) ¹
Exp/large/even/big-2       15.00 ± 0%     15.00 ± 0%       ~ (p=1.000 n=10) ¹
Exp/large/uint256-2        0.000 ± 0%     0.000 ± 0%       ~ (p=1.000 n=10) ¹
Exp/large/even/uint256-2   0.000 ± 0%     0.000 ± 0%       ~ (p=1.000 n=10) ¹
Exp/small/big-2            77.00 ± 0%     77.00 ± 0%       ~ (p=1.000 n=10) ¹
Exp/small/even/big-2       13.00 ± 0%     13.00 ± 0%       ~ (p=1.000 n=10) ¹
Exp/small/uint256-2        0.000 ± 0%     0.000 ± 0%       ~ (p=1.000 n=10) ¹
Exp/small/even/uint256-2   0.000 ± 0%     0.000 ± 0%       ~ (p=1.000 n=10) ¹
geomean                               ²               +0.00%                ²
¹ all samples are equal
² summaries must be >0 to compute geomean

closes #188

@codecov
Copy link
Copy Markdown

codecov bot commented Oct 30, 2024 •
edited
Loading

Codecov Report

All modified and coverable lines are covered by tests ✅

Project coverage is 100.00%. Comparing base (555918b) to head (837a767).
Report is 2 commits behind head on master.

Additional details and impacted files 
@@            Coverage Diff            @@
##            master      #189   +/-   ##
=========================================
  Coverage   100.00%   100.00%           
=========================================
  Files            5         5           
  Lines         1666      1673    +7     
=========================================
+ Hits          1666      1673    +7

@holiman
Copy link
Copy Markdown
Owner

holiman commented Dec 6, 2024

Sorry for the delay.
I have rewitten the benchmarks -- the 'even' checks were always hitting the early exit due to >8bit exponent. Now the even-tests are more fair, at exactly 8 bits exponent.

I also simplified your implementation a bit, and cleaned up the declarations. PTAL

@holiman holiman changed the title optimize exp for even bases optimize Exp for even bases Dec 6, 2024
@holiman holiman merged commit a17fcfb into holiman:master Dec 6, 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.

optimize exp for even bases

2 participants

@Valeh2012 @holiman