# README
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 erigon.
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,
uint256wins overmath/bigin every single case, often with orders of magnitude. - And as of release
0.1.0, theuint256library is alloc-free. - With the
1.0.0release, it also has100%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
# Functions
FromBig is a convenience-constructor from big.Int.
FromDecimal is a convenience-constructor to create an Int from a decimal (base 10) string.
FromHex is a convenience-constructor to create an Int from a hexadecimal string.
MustFromBig is a convenience-constructor from big.Int.
MustFromDecimal is a convenience-constructor to create an Int from a decimal (base 10) string.
MustFromHex is a convenience-constructor to create an Int from a hexadecimal string.
NewInt returns a new initialized Int.
Reciprocal computes a 320-bit value representing 1/m
Notes: - specialized for m[3] != 0, hence limited to 2^192 <= m < 2^256 - returns zero if m[3] == 0 - starts with a 32-bit division, refines with newton-raphson iterations.
# Variables
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
# Type aliases
Int is represented as an array of 4 uint64, in little-endian order, so that Int[3] is the most significant, and Int[0] is the least significant.