Monorepo -> BN.js to BigInt: Performance Analysis

[holgerd77]

Part of #1024

We are currently considering transitioning either core parts of our library code or the libraries as a whole from using BN.js to using the new (ES2020) JS BigInt data type.

One advantage we suspect from this is getting to a better library performance, especially for the VM, which e.g. uses BN.js instances for the VM stack which in turn provides the data basis for most of the ocode operations.

This is a meta issue for collecting some references and experiments along BigInt performance to do some deeper analysis here and somewhat harden the evidence that performance gains play out as expected. 🙂

[holgerd77]

This is a really valuable source I found today with someone having written a master thesis trying to performance-optimize a crypto library, one of his trials was actually a BN.js to BigInt switch (actually in the analyzed case having the biggest impact on performance from all measures): https://www.epfl.ch/labs/dedis/wp-content/uploads/2020/01/report-2019-2-Julien-von-Felten-KyberJS-performance.pdf

[holgerd77]

Did the following very simple performance tests on arithmetics (relevant for the VM), promising results:

> console.time('p'); for (let i=1; i <= 100000; i++) { let res = new BN(500).mul(new BN(23)) }; console.timeEnd('p');
// I would manually re-run the above statement for each result below
p: 9.702ms
p: 9.578ms
p: 8.957ms
p: 9.114ms

> console.time('p'); for (let i=1; i <= 100000; i++) { let res = 500n*23n }; console.timeEnd('p');
p: 6.033ms
p: 5.498ms
p: 6.225ms
p: 6.503ms
p: 5.579ms

> console.time('p'); for (let i=1; i <= 100000; i++) { let res = new BN(500).add(new BN(23)) }; console.timeEnd('p');
p: 12.963ms
p: 14.301ms
p: 13.72ms
p: 14.609ms
p: 11.483ms

> console.time('p'); for (let i=1; i <= 100000; i++) { let res = 500n+23n }; console.timeEnd('p');
p: 1.136ms
p: 1.148ms
p: 1.446ms
p: 1.142ms
p: 1.104ms

> console.time('p'); for (let i=1; i <= 100000; i++) { let res = new BN(500).mod(new BN(23)) }; console.timeEnd('p');
p: 19.924ms
p: 10.162ms
p: 9.218ms
p: 12.504ms
p: 12.334ms

> console.time('p'); for (let i=1; i <= 100000; i++) { let res = 500n % 23n }; console.timeEnd('p');
p: 6.143ms
p: 5.136ms
p: 6.12ms
p: 5.953ms
p: 6.169ms

[gabrocheleau]

Did a little bit of testing locally, and the i-prefixed bn.js operators are faster than their non-i equivalent (e.g. iadd is faster than add by about 2x from my testing, for other operators it seems about 20-30% faster.)

BigInt is still much much faster though on my Thinkpad T480:

BN with add: 39.472ms
BN with iadd: 20.007ms
BigInt (add): 2.346ms

[axic]

The i-prefixed once are inline, i.e. modify the data. The others are creating clones first. Most of the VM code was using i-prefixed ones at some point as an optimisation, where it made sense.

[acolytec3]

This bigints now has a clean commit history that is just the VM changes related migrating the BN.js dep to bigints. Otherwise, should be aligned with master at 4d087b4

[acolytec3]

@holgerd77 @ryanio Do we need to keep this one open since the develop branch has now been migrated entirely to bigints?

[holgerd77]

No, guess we can close.

We should nevertheless try to at some point get a bit more holistic picture of the performance effects of what we are doing respectively on the changes on develop towards master. Not sure what's the best approach here though yet.