Skip to content

Latest commit

 

History

History
145 lines (116 loc) · 8.07 KB

README.md

File metadata and controls

145 lines (116 loc) · 8.07 KB
Raw

Fixed size 256-bit math library

This is a library specialized at replacing the big.Int library for math based on 256-bit types, used by both go-ethereum and turbo-geth.

Go Reference codecov DeepSource

Benchmarks

Current benchmarks, with tests ending with big being the standard big.Int library, and uint256 being this library.

Current status

  • As of 2020-03-18, uint256 wins over math/big in every single case, often with orders of magnitude.
  • And as of release 0.1.0, the uint256 library is alloc-free.
  • With the 1.0.0 release, it also has 100% test coverage.

Bitwise

benchmark u256 time/op big time/op time diff u256 B/op big B/op B diff u256 allocs/op big allocs/op allocs diff
And/single 2.03ns 8.46ns -76.04% 0 0 ~ 0 0 ~
Or/single 2.03ns 10.98ns -81.51% 0 0 ~ 0 0 ~
Xor/single 2.03ns 12.19ns -83.34% 0 0 ~ 0 0 ~
Rsh/n_eq_0 5.00ns 48.11ns -89.61% 0 64 -100.00% 0 1 -100.00%
Rsh/n_gt_0 10.42ns 48.41ns -78.48% 0 64 -100.00% 0 1 -100.00%
Rsh/n_gt_64 6.94ns 52.39ns -86.76% 0 64 -100.00% 0 1 -100.00%
Rsh/n_gt_128 5.49ns 44.21ns -87.59% 0 48 -100.00% 0 1 -100.00%
Rsh/n_gt_192 3.43ns 28.71ns -88.04% 0 8 -100.00% 0 1 -100.00%
Lsh/n_eq_0 4.89ns 40.49ns -87.92% 0 64 -100.00% 0 1 -100.00%
Lsh/n_gt_0 10.14ns 53.25ns -80.96% 0 80 -100.00% 0 1 -100.00%
Lsh/n_gt_64 7.50ns 53.92ns -86.08% 0 80 -100.00% 0 1 -100.00%
Lsh/n_gt_128 5.39ns 56.86ns -90.52% 0 96 -100.00% 0 1 -100.00%
Lsh/n_gt_192 3.90ns 57.61ns -93.23% 0 96 -100.00% 0 1 -100.00%

Conversions

benchmark u256 time/op big time/op time diff u256 B/op big B/op B diff u256 allocs/op big allocs/op allocs diff
FromHexString 116.70ns 861.30ns -86.45% 32 88 -63.64% 1 3 -66.67%
FromDecimalString 7973.00ns 32850.00ns -75.73% 0 2464 -100.00% 0 77 -100.00%
Float64/Float64 2366.00ns 28483.00ns -91.69% 0 23424 -100.00% 0 510 -100.00%
EncodeHex/large 95.26ns 184.30ns -48.31% 80 140 -42.86% 1 2 -50.00%
Decimal/ToDecimal 67384.00ns 83431.00ns -19.23% 11344 31920 -64.46% 248 594 -58.25%
Decimal/ToPrettyDecimal 84208.00ns 123953.00ns -32.06% 14720 61376 -76.02% 251 1100 -77.18%

Math

benchmark u256 time/op big time/op time diff u256 B/op big B/op B diff u256 allocs/op big allocs/op allocs diff
Add/single 1.99ns 18.11ns -89.02% 0 0 ~ 0 0 ~
Sub/single 2.00ns 17.19ns -88.35% 0 0 ~ 0 0 ~
Mul/single 12.10ns 57.69ns -79.03% 0 0 ~ 0 0 ~
SDiv/large 94.64ns 642.10ns -85.26% 0 312 -100.00% 0 6 -100.00%
Sqrt/single 594.90ns 1844.00ns -67.74% 0 528 -100.00% 0 7 -100.00%
Square/single 12.49ns 56.10ns -77.74% 0 0 ~ 0 0 ~
Cmp/single 4.78ns 12.79ns -62.61% 0 0 ~ 0 0 ~
Div/small 12.91ns 48.31ns -73.28% 0 8 -100.00% 0 1 -100.00%
Div/mod64 65.77ns 111.20ns -40.85% 0 8 -100.00% 0 1 -100.00%
Div/mod128 93.67ns 301.40ns -68.92% 0 80 -100.00% 0 1 -100.00%
Div/mod192 86.52ns 263.80ns -67.20% 0 80 -100.00% 0 1 -100.00%
Div/mod256 77.17ns 252.80ns -69.47% 0 80 -100.00% 0 1 -100.00%
AddMod/small 13.84ns 48.16ns -71.26% 0 4 -100.00% 0 0 ~
AddMod/mod64 22.83ns 57.58ns -60.35% 0 11 -100.00% 0 0 ~
AddMod/mod128 48.31ns 145.00ns -66.68% 0 12 -100.00% 0 0 ~
AddMod/mod192 47.26ns 160.00ns -70.46% 0 12 -100.00% 0 0 ~
AddMod/mod256 14.44ns 143.20ns -89.92% 0 12 -100.00% 0 0 ~
MulMod/small 40.81ns 63.14ns -35.37% 0 8 -100.00% 0 1 -100.00%
MulMod/mod64 91.66ns 112.60ns -18.60% 0 48 -100.00% 0 1 -100.00%
MulMod/mod128 136.00ns 362.70ns -62.50% 0 128 -100.00% 0 2 -100.00%
MulMod/mod192 151.70ns 421.20ns -63.98% 0 144 -100.00% 0 2 -100.00%
MulMod/mod256 188.80ns 489.20ns -61.41% 0 176 -100.00% 0 2 -100.00%
Exp/small 433.70ns 7490.00ns -94.21% 0 7392 -100.00% 0 77 -100.00%
Exp/large 5145.00ns 23043.00ns -77.67% 0 18144 -100.00% 0 189 -100.00%
Mod/mod64 70.94ns 118.90ns -40.34% 0 64 -100.00% 0 1 -100.00%
Mod/small 14.82ns 46.27ns -67.97% 0 8 -100.00% 0 1 -100.00%
Mod/mod128 99.58ns 286.90ns -65.29% 0 64 -100.00% 0 1 -100.00%
Mod/mod192 95.31ns 269.30ns -64.61% 0 48 -100.00% 0 1 -100.00%
Mod/mod256 84.13ns 222.90ns -62.26% 0 8 -100.00% 0 1 -100.00%
MulOverflow/single 27.68ns 57.52ns -51.88% 0 0 ~ 0 0 ~
MulDivOverflow/small 2.83ns 22.97ns -87.69% 0 0 ~ 0 0 ~
MulDivOverflow/div64 2.85ns 23.13ns -87.66% 0 0 ~ 0 0 ~
MulDivOverflow/div128 3.14ns 31.29ns -89.96% 0 2 -100.00% 0 0 ~
MulDivOverflow/div192 3.17ns 30.28ns -89.54% 0 2 -100.00% 0 0 ~
MulDivOverflow/div256 3.54ns 35.56ns -90.06% 0 5 -100.00% 0 0 ~
Lt/small 3.12ns 10.43ns -70.06% 0 0 ~ 0 0 ~
Lt/large 3.49ns 10.32ns -66.18% 0 0 ~ 0 0 ~

Other

benchmark u256 time/op u256 B/op u256 allocs/op
SetBytes/generic 104.30ns 0 0
Sub/single/uint256_of 1.99ns 0 0
SetFromBig/overflow 3.57ns 0 0
ToBig/2words 73.84ns 64 2
SetBytes/specific 45.81ns 0 0
ScanScientific 674.10ns 0 0
SetFromBig/4words 3.82ns 0 0
ToBig/4words 68.82ns 64 2
RLPEncoding 11917.00ns 11911 255
SetFromBig/1word 2.99ns 0 0
SetFromBig/3words 4.12ns 0 0
ToBig/3words 70.12ns 64 2
ToBig/1word 75.38ns 64 2
MulMod/mod256/uint256r 77.11ns 0 0
HashTreeRoot 11.27ns 0 0
SetFromBig/2words 3.90ns 0 0

Helping out

If you're interested in low-level algorithms and/or doing optimizations for shaving off nanoseconds, then this is certainly for you!

Implementation work

Choose an operation, and optimize the s**t out of it!

A few rules, though, to help your PR get approved:

  • Do not optimize for 'best-case'/'most common case' at the expense of worst-case.
  • We'll hold off on go assembly for a while, until the algos and interfaces are finished in a 'good enough' first version. After that, it's assembly time.

Doing benchmarks

To do a simple benchmark for everything, do

go test -run - -bench . -benchmem

To see the difference between a branch and master, for a particular benchmark, do

git checkout master
go test -run - -bench Benchmark_Lsh -benchmem -count=10 > old.txt

git checkout opt_branch
go test -run - -bench Benchmark_Lsh -benchmem -count=10 > new.txt

benchstat old.txt new.txt