mpn_mul is embarrassingly slow

Torbjörn Granlund tg at gmplib.org
Wed Apr 25 10:30:39 UTC 2018


More embarrassments.  :-)

I ran some timing tests without my proposed change and with the squqring
exception code still there.  Please consider the following two
measurements for doing n x 19 limb (first table) and n x 20 limb
multiplication.

MUL_TOOM22_THREASHLD is 20 for this machine (compiled in, but also
measured now).  My comments below.

shell$ s=19; /var/tmp/gmp-obj/shell-stat-64/tune/speed -p10000000 -C -s$s-10000 -f1.18921 mpn_mul_basecase.$s mpn_mul.$s
        mpn_mul_basecase.19    mpn_mul.19
19           #52.6538       53.6265
22           #52.3229       52.5160
26           #51.7320       52.3353
30           #51.0956       51.4094
35           #51.6668       51.8058
41           #51.0281       51.1521
48           #50.3089       50.7814
57            50.9483      #50.6005
67           #50.0544       50.3068
79           #50.0011       50.2852
93           #49.9273       49.9390
110          #49.5500       49.7827
130          #50.1870       50.4552
154          #49.8056       50.2093
183          #53.3242       53.3843
217          #49.2789       49.2824
258          #49.2653       49.3045
306          #49.4464       49.5687
363           49.8730      #49.8098
431           50.2299      #49.9768
512          #49.2733       49.7746
608          #49.3598       49.8171
723          #49.1601       49.3890
859          #49.0863       49.8433
1021          49.7723      #49.3362
1214         #50.3789       50.7310
1443         #49.3266       49.7170
1716         #52.7154       52.8587
2040         #49.3229       49.3615
2425         #49.3359       49.5272
2883         #49.0648       49.5257
3428         #49.0177       49.3466
4076         #49.3203       49.3304
4847         #49.3943       49.8041
5764         #49.2198       49.5425
6854         #48.9811       49.6710
8150         #49.2303       49.4877
9692         #49.1880       49.5698

shell$ s=20; /var/tmp/gmp-obj/shell-stat-64/tune/speed -p10000000 -C -s$s-10000 -f1.18921 mpn_mul_basecase.$s mpn_mul.$s
        mpn_mul_basecase.20    mpn_mul.20
20            53.7537      #53.2094
23            54.3137      #54.2321
27           #53.8805       56.3679
32           #52.7558       55.7628
38           #53.5706       64.9707
45           #53.0549       69.5985
53           #52.7709       72.1807
63           #52.7172       59.1984
74           #52.6356       61.0932
88           #52.2926       65.1293
104          #52.0060       61.0254
123          #52.1420       64.3351
146          #51.9075       62.9850
173          #51.9356       66.2089
205          #51.6655       65.6402
243          #51.5910       65.2338
288          #51.5630       64.3180
342          #51.9705       63.6947
406          #51.5944       65.1629
482          #51.4753       65.0087
573          #51.5081       66.7520
681          #51.4781       65.8361
809          #51.3717       65.3255
962          #51.2893       64.7490
1144         #51.3710       64.9312
1360         #51.3043       65.2083
1617         #51.2859       65.3962
1922         #51.3485       66.1818
2285         #51.4109       65.4166
2717         #51.3573       66.1410
3231         #51.3410       65.6465
3842         #51.2987       65.1884
4568         #51.2987       66.6584
5432         #51.7155       65.1674
6459         #51.3443       65.5936
7681         #51.2728       66.9525
9134         #51.3411       65.4536

While mpn_mul_basecase scales as expected, we see a huge drop for
mpn_mul.  I haven't analysed this yet, but ths should be low hanging
fruit and quite important to fix.

When we reach n x 30 things start to look normal:

30            81.4431      #71.5543
35            80.5471      #74.3086
41            79.5520      #71.4262
48            79.1028      #68.1515
57            79.0777      #76.9255
67           #79.1647       82.1738
79           #78.8699       81.4099
93            78.5466      #73.9677
110           78.1847      #74.1361
130          #78.8731       79.6757
154           77.8928      #74.7900
183           81.8825      #77.8441
217           77.7174      #75.7915
258          #77.7774       79.3755
306          #77.8217       78.1472
363           77.4641      #76.1196
431           80.8164      #77.9355
512           77.5541      #77.1744
608          #77.3506       78.0776
723           77.4727      #77.4272
859          #77.6385       79.4917
1021          77.2880      #76.9525
1214         #77.1217       77.6029
1443         #77.2112       78.1277
1716          80.3526      #77.7431
2040         #77.3116       77.5759
2425         #77.2802       77.6045
2883          77.6359      #77.0870
3428         #77.4548       78.0557
4076         #77.2320       77.8208
4847         #77.3840       79.3593
5764          77.4421      #76.9061
6854          77.3076      #77.2082
8150         #77.4396       77.4831
9692         #77.2755       77.5709


-- 
Torbjörn
Please encrypt, key id 0xC8601622


More information about the gmp-devel mailing list