rand
rand copied to clipboard

Published 20 hours ago •

Reame
Issues

Implement shuffle query

Open webmaster128 opened this issue 3 years ago • 2 comments

Mar 18 '22 17:03 webmaster128

This compares gas consumption between Inverse Riffle Shuffle and Fisher-Yates:

Inverse Riffle Shuffle + ChaCha8Rng

list elements	CosmWasm gas¹	MGas per list element
1	7900500017	7900.5
5	8731050017	1746.2101
10	10240200017	1024.02
25	21157800017	846.312
50	25306950017	506.139
100	44730150017	447.3015
250	114807900017	459.2316
500	268322550017	536.64514
750	398082450017	530.77655
900	"bad randomness source"	"bad randomness source"
1000	"bad randomness source"	"bad randomness source"

Fisher-Yates + ChaCha8Rng

list elements	CosmWasm gas¹	MGas per list element
1	4642350017	4642.35
5	7912650017	1582.53
10	8383050017	838.30505
25	9933300017	397.332
50	15531900017	310.63797
100	23793900017	237.939
250	52775700017	211.1028
500	103547700017	207.0954
750	150906150017	201.20819
900	182277750017	202.53084
1000	199157100017	199.1571

¹ See https://github.com/CosmWasm/cosmwasm/blob/main/docs/GAS.md

Contract size

Optimized test contract using cosmwasm/rust-optimizer:0.12.5

with Inverse Riffle Shuffle: 566K
with Fisher-Yates: 564K

Mar 19 '22 09:03 webmaster128

And we can save gas and contract size using a non-cryptographically secure RNG:

Fisher-Yates + Xoshiro128PlusPlus

list elements	CosmWasm gas	MGas per list element
1	4530000017	4530
5	4936200017	987.24005
10	5421300017	542.13007
25	7130400017	285.216
50	9816300017	196.32599
100	15364350017	153.64351
250	36164700017	144.6588
500	70457850017	140.9157
750	104595750017	139.46101
900	124424100017	138.24901
1000	138592950017	138.59294

Contract size

Optimized test contract using cosmwasm/rust-optimizer:0.12.5

with Fisher-Yates and ChaCha8Rng: 564K
with Fisher-Yates and Xoshiro128PlusPlus: 555K

Mar 19 '22 10:03 webmaster128