Modexp reduction benchmark

README.md

MODEXP reduction benchmark

State tests were executed and execution time of the expmod(B, E, M) instruction in the MODEXP precompile were measured for master and the PR which uses BN.red for computing MODEXP.

The measurements are in millisecond, and they've been sorted to give an idea of generally how long the two approaches take. Corresponding lines in the two files do not necessarily represent the same modexp operation.

master-bench

47.337775
44.242218
40.469807
7.61243
7.087352
4.080516
3.233489
2.900622
2.169441
1.776961
1.50033
1.249678
1.121658
1.103889
1.048862
0.996883
0.888173
0.853541
0.815772
0.812774
0.806133
0.801782
0.792757
0.792147
0.792105
0.786174
0.781178
0.777867
0.768871
0.767899
0.766674
0.761704
0.736432
0.732927
0.732919
0.732476
0.731857
0.731833
0.731492
0.724268
0.723644
0.723422
0.721687
0.672971
0.669415
0.667687
0.664147
0.66346
0.654614
0.64292
0.634842
0.627618
0.624061
0.612117
0.598736
0.596501
0.590667
0.587637
0.579903
0.579084
0.564363
0.563001
0.39417
0.338865
0.338457
0.326544
0.287915
0.286005
0.285936
0.23443
0.22066
0.191718
0.188848
0.134563
0.077126
0.075385
0.07157
0.070917
0.069959
0.069575
0.069405
0.069007
0.068576
0.067284
0.066859
0.027408
0.01621
0.016103
0.015972
0.012458
0.012223
0.011749
0.011665
0.011649
0.01136
0.011353
0.011252
0.011018
0.010975
0.01073
0.010645
0.010597
0.010573
0.010497
0.010495
0.010439
0.010394
0.01033
0.010317
0.010271
0.010059
0.010051
0.009971
0.009962
0.009951
0.009906
0.009893
0.009892
0.009875
0.009782
0.009735
0.009721
0.009662
0.009607
0.00947
0.009195
0.00912
0.009117
0.009115
0.008994
0.008952
0.0089
0.008747
0.008594
0.008584
0.008578
0.00857
0.008484
0.008453
0.008407
0.008372
0.008302
0.008193
0.008158
0.007968
0.007902
0.007699
0.007696
0.007478
0.007286
0.006527
0.00645
0.006049
0.006005
0.005918
0.005908
0.005864
0.005863
0.005863
0.005854
0.005794
0.005755
0.005752
0.005746
0.005722
0.005702
0.005697
0.005671
0.005671
0.005647
0.005645
0.005644
0.005591
0.005579
0.00554
0.00549
0.005427
0.005424
0.005383
0.005296
0.005294
0.005285
0.005258
0.005257
0.005252
0.005242
0.005235
0.005217
0.005209
0.005105
0.005089
0.005079
0.005067
0.005046
0.005038
0.005029
0.005009
0.005003
0.004952
0.004934
0.004929
0.004916
0.004913
0.004909
0.004867
0.004853
0.00485
0.004849
0.004812
0.004762
0.00472
0.004711
0.004679
0.004666
0.00457
0.004223
0.004181
0.003846
0.003769
0.003732
0.003682
0.003587
0.003561
0.003538
0.00341
0.003334
0.003262
0.003253
0.003211
0.003197
0.003195
0.003135
0.003127
0.003109
0.003092
0.003027
0.003001
0.003
0.002895
0.002729
0.002674
0.002354
0.002349
0.002318
0.002298
0.002218

modexp-red-bench

45.535404
42.195274
41.220757
7.094783
5.687472
5.512817
2.445627
1.818581
1.804434
1.734515
1.669313
1.620124
1.25451
1.23995
1.100394
1.055259
1.052155
1.043043
0.972037
0.936126
0.909875
0.877859
0.871514
0.836976
0.808384
0.807875
0.757055
0.742719
0.688233
0.670781
0.62716
0.604515
0.603545
0.586759
0.585449
0.584874
0.582402
0.56057
0.560201
0.55613
0.555617
0.552715
0.551823
0.551512
0.551047
0.550547
0.550347
0.548841
0.533907
0.52491
0.523594
0.522693
0.518705
0.518013
0.515218
0.513496
0.504941
0.503547
0.498652
0.48523
0.482992
0.482342
0.345669
0.33528
0.276362
0.26484
0.26313
0.262471
0.250553
0.236058
0.181309
0.166301
0.150802
0.144289
0.127237
0.118643
0.097106
0.096347
0.094001
0.092692
0.090035
0.089684
0.08928
0.086839
0.057744
0.049603
0.044495
0.044136
0.041901
0.034045
0.033966
0.031952
0.031026
0.029878
0.029155
0.029055
0.028378
0.027843
0.027421
0.027275
0.027145
0.027084
0.0263
0.0261
0.025828
0.025582
0.025417
0.025086
0.023288
0.022712
0.022521
0.022455
0.022329
0.022064
0.021909
0.021515
0.021435
0.02134
0.021312
0.021236
0.021188
0.021168
0.021146
0.021051
0.020853
0.020538
0.020375
0.020366
0.020151
0.020018
0.019921
0.019864
0.019813
0.019807
0.019686
0.019649
0.019644
0.019639
0.019533
0.019428
0.019428
0.019386
0.019309
0.019249
0.01924
0.019222
0.019185
0.019035
0.018974
0.018925
0.018748
0.018183
0.018003
0.017918
0.015258
0.014832
0.014811
0.014288
0.014271
0.014238
0.013928
0.013707
0.013688
0.013642
0.013505
0.013498
0.01332
0.013295
0.013186
0.013085
0.013021
0.013015
0.012902
0.012646
0.012611
0.012341
0.01232
0.005287
0.004872
0.004872
0.004747
0.004608
0.00457
0.004397
0.004288
0.004259
0.004187
0.004137
0.003982
0.003908
0.003868
0.003862
0.003834
0.003792
0.003787
0.003782
0.003751
0.003728
0.003708
0.003613
0.003563
0.003555
0.003552
0.00354
0.003519
0.003515
0.003511
0.003491
0.003474
0.003454
0.003435
0.003421
0.003345
0.003317
0.00331
0.003282
0.003255
0.003018
0.002983
0.002977
0.002974
0.002966
0.002949
0.002936
0.002935
0.002916
0.002914
0.002907
0.002891
0.002885
0.002882
0.002878
0.002826
0.002818
0.002816
0.002796
0.002785
0.002739
0.002733
0.002708
0.002676
0.002609
0.002597
0.002526
0.002475
0.002114