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, 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