Benchmark results

[axic]

I have run the benchmarks (including #88) and it could be better. Not sure whether it is representative at all in terms of commonly used methods.

Where bn.js failed:

• toString(10)
• toString(16)
• mul 35% slower
• mul-jumbo 96% slower (this might be a broken test, but two others were at least twice as fast as bn.js)
• sqr 26% slower
• div 63% slower
• mod 57% slower
• pow 80% slower
• gcd 27% slower

Regarding toString(10): a dedicated case might speed things up.

Re: toString(16): the fact that 26 bits are stored in a word makes it a lengthier process. Storing 24 or 32 bits would make this significantly faster. What is the actual reason behind going for 26 bits?

The full output:

bash-3.2$ node index.js 
Benchmarking: create-10
bn.js#create-10 x 917,636 ops/sec ±2.74% (8 runs sampled)
bignum#create-10 x 224,568 ops/sec ±2.60% (9 runs sampled)
bigi#create-10 x 571,307 ops/sec ±11.43% (8 runs sampled)
yaffle#create-10 x 912,360 ops/sec ±4.76% (9 runs sampled)
silentmatt-biginteger#create-10 x 73,199 ops/sec ±1.61% (8 runs sampled)
bignumber#create-10 x 479,789 ops/sec ±1.88% (9 runs sampled)
------------------------
Fastest is bn.js#create-10,yaffle#create-10
========================
Benchmarking: create-hex
bn.js#create-hex x 1,178,547 ops/sec ±11.80% (9 runs sampled)
bignum#create-hex x 189,415 ops/sec ±13.69% (8 runs sampled)
bigi#create-hex x 548,509 ops/sec ±6.54% (9 runs sampled)
sjcl#create-hex x 743,918 ops/sec ±3.52% (8 runs sampled)
yaffle#create-hex x 874,148 ops/sec ±5.63% (9 runs sampled)
silentmatt-biginteger#create-hex x 19,237 ops/sec ±4.85% (8 runs sampled)
bignumber#create-hex x 17,456 ops/sec ±1.67% (8 runs sampled)
------------------------
Fastest is bn.js#create-hex
========================
Benchmarking: toString-10
bn.js#toString-10 x 493,331 ops/sec ±2.14% (9 runs sampled)
bignum#toString-10 x 377,052 ops/sec ±3.66% (9 runs sampled)
bigi#toString-10 x 56,522 ops/sec ±1.85% (8 runs sampled)
yaffle#toString-10 x 1,160,115 ops/sec ±5.15% (9 runs sampled)
silentmatt-biginteger#toString-10 x 3,089,024 ops/sec ±4.15% (9 runs sampled)
bignumber#toString-10 x 22,371 ops/sec ±4.83% (9 runs sampled)
------------------------
Fastest is silentmatt-biginteger#toString-10
========================
Benchmarking: toString-hex
bn.js#toString-hex x 373,833 ops/sec ±7.83% (9 runs sampled)
bignum#toString-hex x 2,053,779 ops/sec ±3.73% (9 runs sampled)
bigi#toString-hex x 597,184 ops/sec ±2.52% (9 runs sampled)
sjcl#toString-hex x 380,253 ops/sec ±6.30% (9 runs sampled)
yaffle#toString-hex x 336,258 ops/sec ±4.74% (9 runs sampled)
silentmatt-biginteger#toString-hex x 9,564 ops/sec ±5.16% (9 runs sampled)
bignumber#toString-hex x 24,026 ops/sec ±5.71% (9 runs sampled)
------------------------
Fastest is bignum#toString-hex
========================
Benchmarking: add
bn.js#add x 7,486,633 ops/sec ±2.01% (8 runs sampled)
bignum#add x 113,935 ops/sec ±2.02% (8 runs sampled)
bigi#add x 1,994,830 ops/sec ±7.26% (9 runs sampled)
sjcl#add x 3,863,970 ops/sec ±4.71% (9 runs sampled)
yaffle#add x 5,122,197 ops/sec ±2.97% (9 runs sampled)
silentmatt-biginteger#add x 1,328,770 ops/sec ±5.26% (9 runs sampled)
bignumber#add x 1,475,561 ops/sec ±5.36% (8 runs sampled)
------------------------
Fastest is bn.js#add
========================
Benchmarking: sub
bn.js#sub x 5,438,894 ops/sec ±4.31% (9 runs sampled)
bignum#sub x 112,649 ops/sec ±4.04% (9 runs sampled)
bigi#sub x 1,612,451 ops/sec ±16.89% (8 runs sampled)
sjcl#sub x 3,326,135 ops/sec ±17.04% (8 runs sampled)
yaffle#sub x 4,654,711 ops/sec ±4.51% (8 runs sampled)
silentmatt-biginteger#sub x 3,256,610 ops/sec ±6.52% (9 runs sampled)
bignumber#sub: 
------------------------
Fastest is bn.js#sub
========================
Benchmarking: mul
bn.js#mul x 1,492,842 ops/sec ±3.50% (9 runs sampled)
bn.js[FFT]#mul x 114,362 ops/sec ±4.76% (9 runs sampled)
bignum#mul x 58,624 ops/sec ±26.16% (7 runs sampled)
bigi#mul x 390,251 ops/sec ±7.24% (8 runs sampled)
sjcl#mul x 2,287,125 ops/sec ±3.93% (9 runs sampled)
yaffle#mul x 1,409,295 ops/sec ±6.91% (9 runs sampled)
silentmatt-biginteger#mul x 514,773 ops/sec ±4.03% (8 runs sampled)
bignumber#mul x 556,803 ops/sec ±1.41% (9 runs sampled)
------------------------
Fastest is sjcl#mul
========================
Benchmarking: mul-jumbo
bn.js#mul-jumbo x 1,190 ops/sec ±4.87% (9 runs sampled)
bn.js[FFT]#mul-jumbo x 3,026 ops/sec ±3.93% (9 runs sampled)
bignum#mul-jumbo x 28,532 ops/sec ±7.91% (9 runs sampled)
bigi#mul-jumbo x 1,157 ops/sec ±5.46% (8 runs sampled)
sjcl#mul-jumbo x 2,841 ops/sec ±3.68% (9 runs sampled)
yaffle#mul-jumbo x 1,552 ops/sec ±2.28% (9 runs sampled)
silentmatt-biginteger#mul-jumbo x 599 ops/sec ±6.48% (9 runs sampled)
bignumber#mul-jumbo x 593 ops/sec ±7.00% (8 runs sampled)
------------------------
Fastest is bignum#mul-jumbo
========================
Benchmarking: sqr
bn.js#sqr x 1,328,815 ops/sec ±5.63% (8 runs sampled)
bignum#sqr x 59,338 ops/sec ±28.25% (7 runs sampled)
bigi#sqr x 249,727 ops/sec ±11.39% (8 runs sampled)
sjcl#sqr x 1,810,258 ops/sec ±3.90% (8 runs sampled)
yaffle#sqr x 1,364,301 ops/sec ±5.63% (8 runs sampled)
silentmatt-biginteger#sqr x 318,959 ops/sec ±5.51% (9 runs sampled)
bignumber#sqr x 522,413 ops/sec ±3.23% (8 runs sampled)
------------------------
Fastest is sjcl#sqr
========================
Benchmarking: div
bn.js#div x 253,720 ops/sec ±6.84% (8 runs sampled)
bignum#div x 35,872 ops/sec ±64.38% (6 runs sampled)
bigi#div x 121,087 ops/sec ±6.19% (7 runs sampled)
yaffle#div x 677,293 ops/sec ±3.85% (9 runs sampled)
silentmatt-biginteger#div x 23,874 ops/sec ±3.83% (9 runs sampled)
bignumber#div x 38,726 ops/sec ±3.88% (8 runs sampled)
------------------------
Fastest is yaffle#div
========================
Benchmarking: mod
bn.js#mod x 213,368 ops/sec ±18.17% (9 runs sampled)
bignum#mod x 52,249 ops/sec ±22.77% (7 runs sampled)
bigi#mod x 97,774 ops/sec ±6.44% (9 runs sampled)
yaffle#mod x 500,369 ops/sec ±6.86% (8 runs sampled)
silentmatt-biginteger#mod x 17,479 ops/sec ±6.18% (8 runs sampled)
------------------------
Fastest is yaffle#mod
========================
Benchmarking: mul-mod k256
bn.js#mul-mod k256 x 821,985 ops/sec ±3.56% (8 runs sampled)
sjcl#mul-mod k256 x 349,720 ops/sec ±5.63% (7 runs sampled)
------------------------
Fastest is bn.js#mul-mod k256
========================
Benchmarking: pow k256
bn.js#pow k256 x 3,235 ops/sec ±9.99% (9 runs sampled)
bignum#pow k256 x 15,680 ops/sec ±39.71% (9 runs sampled)
------------------------
Fastest is bignum#pow k256
========================
Benchmarking: invm k256
bn.js#invm k256 x 5,544 ops/sec ±3.72% (8 runs sampled)
sjcl#invm k256 x 3,930 ops/sec ±7.69% (8 runs sampled)
------------------------
Fastest is bn.js#invm k256
========================
Benchmarking: gcd
bn.js#gcd x 21,713 ops/sec ±5.84% (9 runs sampled)
bigi#gcd x 29,660 ops/sec ±4.42% (8 runs sampled)
------------------------
Fastest is bigi#gcd
========================
Benchmarking: egcd
bn.js#egcd x 5,435 ops/sec ±23.47% (8 runs sampled)
------------------------
Fastest is bn.js#egcd
========================
Benchmarking: bitLength
bn.js#bitLength x 19,521,537 ops/sec ±44.08% (8 runs sampled)
------------------------
Fastest is bn.js#bitLength
========================

[indutny]

It doesn't look like mul is slower than anything else...

[indutny]

And sqr seems to be quite good too.

[indutny]

Others are quite slow indeed.

[indutny]

The reason for using 26 bits is that we have only 52bits of precision in javascript.

[axic]

@indutny sorry I don't get it the 26 vs 52 (53). That means words[i] as a Number could store up to 53 bits. Is any function doing in-place multiplication where it is beneficial to have that overhead? I probably miss something here.

[indutny]

@axic in mulTo we do a * b where both a and b are 26bit numbers. If they would be 32bit number, the result would overflow and precision would be lost. words[i] store up to 26bits

[axic]

@indutny that was my guess. As a long term change, how about using 32bits in the entire library and changing mulTo to:

• first transform the input into 26bit chunks (or even 24bits)
• do the multiplication
• transform back to 32bits

Working on 32bits would speed up the rest I would say considerably.

Is there any analysis which methods are the most frequently used in common use cases of this library? ECC, serialization, what else?

[indutny]

@axic it will make things slower. The most expensive operation through the library is multiplication, so the whole library is optimized for doing it. Additions are quite fast already (see benchmark results), and there is simply no crypto that is based solely on additions, so the bottleneck will be mul anyway.

Example: mul takes 2 seconds, add takes 0.1 seconds. If you are doing 1 mul and 10 adds - total time is 3 seconds. If you will speed up add by the factor of 2 (this is very optimistic) at the cost of slowing down mul by the factor of 2 - total time will be 4.5 seconds. So there is no point in this optimization.

[axic]

@indutny I do get that mul is crucial, that's why I've asked if there's any analysis of how much time is spent on each for the typical use cases. Informed decisions can be made based on such data.

[axic]

Rerun the benchmarks with 4.6.6. There are some improvements, we're still behind on:

• create-10
• toString-10
• mul
• mul_jumbo
• div
• mod
• pow k256
• gcd

Full output:

Seed: 8b5201195b35684780494734dabc0cc92789b149530241d6bf54429d4c8b140f
Benchmarking: create-10
bn.js#create-10 x 581,715 ops/sec ±2.18% (8 runs sampled)
bignum#create-10 x 187,743 ops/sec ±1.45% (9 runs sampled)
bigi#create-10 x 405,997 ops/sec ±0.83% (8 runs sampled)
yaffle#create-10 x 614,492 ops/sec ±3.27% (7 runs sampled)
silentmatt-biginteger#create-10 x 41,612 ops/sec ±1.07% (9 runs sampled)
------------------------
Fastest is yaffle#create-10
========================
Benchmarking: create-hex
bn.js#create-hex x 864,854 ops/sec ±3.35% (7 runs sampled)
bignum#create-hex x 192,326 ops/sec ±1.68% (8 runs sampled)
bigi#create-hex x 519,357 ops/sec ±0.97% (9 runs sampled)
sjcl#create-hex x 582,982 ops/sec ±1.03% (8 runs sampled)
yaffle#create-hex x 613,402 ops/sec ±1.80% (9 runs sampled)
silentmatt-biginteger#create-hex x 12,081 ops/sec ±14.02% (8 runs sampled)
------------------------
Fastest is bn.js#create-hex
========================
Benchmarking: toString-10
bn.js#toString-10 x 269,551 ops/sec ±2.08% (9 runs sampled)
bignum#toString-10 x 263,367 ops/sec ±1.03% (9 runs sampled)
bigi#toString-10 x 89,301 ops/sec ±1.84% (9 runs sampled)
yaffle#toString-10 x 589,709 ops/sec ±2.14% (8 runs sampled)
silentmatt-biginteger#toString-10 x 1,502,177 ops/sec ±2.91% (9 runs sampled)
------------------------
Fastest is silentmatt-biginteger#toString-10
========================
Benchmarking: toString-hex
bn.js#toString-hex x 230,448 ops/sec ±12.18% (9 runs sampled)
bignum#toString-hex x 1,487,925 ops/sec ±6.87% (7 runs sampled)
bigi#toString-hex x 452,852 ops/sec ±1.52% (8 runs sampled)
sjcl#toString-hex x 239,688 ops/sec ±2.60% (9 runs sampled)
yaffle#toString-hex x 189,974 ops/sec ±10.22% (9 runs sampled)
silentmatt-biginteger#toString-hex x 3,006 ops/sec ±8.38% (9 runs sampled)
------------------------
Fastest is bignum#toString-hex
========================
Benchmarking: add
bn.js#add x 4,710,258 ops/sec ±5.80% (8 runs sampled)
bignum#add x 109,712 ops/sec ±3.05% (9 runs sampled)
bigi#add x 1,557,992 ops/sec ±7.30% (9 runs sampled)
sjcl#add x 2,727,034 ops/sec ±9.09% (9 runs sampled)
yaffle#add x 3,149,534 ops/sec ±1.89% (8 runs sampled)
silentmatt-biginteger#add x 1,375,840 ops/sec ±3.16% (7 runs sampled)
------------------------
Fastest is bn.js#add
========================
Benchmarking: sub
bn.js#sub x 3,915,050 ops/sec ±3.72% (9 runs sampled)
bignum#sub x 96,333 ops/sec ±11.03% (8 runs sampled)
bigi#sub x 1,639,071 ops/sec ±6.48% (9 runs sampled)
sjcl#sub x 3,087,504 ops/sec ±7.09% (9 runs sampled)
yaffle#sub x 3,293,859 ops/sec ±10.85% (9 runs sampled)
silentmatt-biginteger#sub x 2,529,666 ops/sec ±7.18% (7 runs sampled)
------------------------
Fastest is bn.js#sub
========================
Benchmarking: mul
bn.js#mul x 2,551,957 ops/sec ±3.74% (9 runs sampled)
bn.js[FFT]#mul x 62,624 ops/sec ±0.68% (9 runs sampled)
bignum#mul x 103,476 ops/sec ±2.98% (9 runs sampled)
bigi#mul x 558,626 ops/sec ±0.82% (7 runs sampled)
sjcl#mul x 427,425 ops/sec ±1.23% (9 runs sampled)
yaffle#mul x 748,872 ops/sec ±1.01% (9 runs sampled)
silentmatt-biginteger#mul x 284,387 ops/sec ±0.90% (8 runs sampled)
------------------------
Fastest is bn.js#mul
========================
Benchmarking: mul-jumbo
bn.js#mul-jumbo x 1,385 ops/sec ±0.81% (8 runs sampled)
bn.js[FFT]#mul-jumbo x 3,331 ops/sec ±0.84% (9 runs sampled)
bignum#mul-jumbo x 30,649 ops/sec ±6.74% (9 runs sampled)
bigi#mul-jumbo x 1,337 ops/sec ±4.79% (9 runs sampled)
sjcl#mul-jumbo x 2,715 ops/sec ±1.57% (9 runs sampled)
yaffle#mul-jumbo x 1,427 ops/sec ±1.42% (9 runs sampled)
silentmatt-biginteger#mul-jumbo x 626 ops/sec ±1.03% (9 runs sampled)
------------------------
Fastest is bignum#mul-jumbo
========================
Benchmarking: sqr
bn.js#sqr x 2,665,669 ops/sec ±1.34% (9 runs sampled)
bignum#sqr x 99,877 ops/sec ±2.65% (9 runs sampled)
bigi#sqr x 745,474 ops/sec ±2.08% (8 runs sampled)
sjcl#sqr x 399,811 ops/sec ±1.69% (9 runs sampled)
yaffle#sqr x 752,297 ops/sec ±0.64% (9 runs sampled)
silentmatt-biginteger#sqr x 253,316 ops/sec ±0.69% (9 runs sampled)
------------------------
Fastest is bn.js#sqr
========================
Benchmarking: div
bn.js#div x 235,129 ops/sec ±0.79% (8 runs sampled)
bignum#div x 82,360 ops/sec ±2.87% (9 runs sampled)
bigi#div x 257,078 ops/sec ±2.06% (9 runs sampled)
yaffle#div x 325,853 ops/sec ±1.58% (9 runs sampled)
silentmatt-biginteger#div x 13,205 ops/sec ±1.08% (9 runs sampled)
------------------------
Fastest is yaffle#div
========================
Benchmarking: mod
bn.js#mod x 240,210 ops/sec ±0.45% (8 runs sampled)
bignum#mod x 92,469 ops/sec ±3.22% (9 runs sampled)
bigi#mod x 265,893 ops/sec ±1.96% (8 runs sampled)
yaffle#mod x 301,554 ops/sec ±1.41% (9 runs sampled)
silentmatt-biginteger#mod x 11,860 ops/sec ±0.69% (9 runs sampled)
------------------------
Fastest is yaffle#mod
========================
Benchmarking: mul-mod k256
bn.js#mul-mod k256 x 887,071 ops/sec ±1.38% (9 runs sampled)
sjcl#mul-mod k256 x 218,260 ops/sec ±1.09% (9 runs sampled)
------------------------
Fastest is bn.js#mul-mod k256
========================
Benchmarking: pow k256
bn.js#pow k256 x 2,196 ops/sec ±0.77% (8 runs sampled)
bignum#pow k256 x 9,280 ops/sec ±73.57% (6 runs sampled)
------------------------
Fastest is bignum#pow k256
========================
Benchmarking: invm k256
bn.js#invm k256 x 5,389 ops/sec ±0.87% (9 runs sampled)
sjcl#invm k256 x 4,197 ops/sec ±0.88% (9 runs sampled)
------------------------
Fastest is bn.js#invm k256
========================
Benchmarking: gcd
bn.js#gcd x 13,189 ops/sec ±1.24% (9 runs sampled)
bigi#gcd x 20,862 ops/sec ±1.29% (9 runs sampled)
------------------------
Fastest is bigi#gcd
========================
Benchmarking: egcd
bn.js#egcd x 3,245 ops/sec ±2.44% (9 runs sampled)
------------------------
Fastest is bn.js#egcd
========================
Benchmarking: bitLength
bn.js#bitLength x 20,066,915 ops/sec ±1.44% (9 runs sampled)
------------------------
Fastest is bn.js#bitLength
========================

[fanatid]

JFYI @axic I got less performance with 16-bit word (instead 26-bit) in secp256k1-node embedded pure js

[indutny]

How are we still behind on mul if?

Fastest is bn.js#mul

Sorry, but I still don't see what value this PR provides, except making benchmarks run slower. I'm actually thinking about removing some of these libraries from them, because it became to cumbersome.

[axic]

@indutny sorry I guess looked at the wrong window, mul isn't any slower now, but mul_jumbo is still behind the others.

This isn't a PR. I think you're confusing it with #88.

This is just a log of executing the benchmark in the vanilla git master.