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