Performance analysis of Mul algorithms in the same range

[Torbjorn Granlund]

"Lingchuan Meng" <lingchuanmeng at gmail.com> writes:

  I'm new to GMP and trying to measure the performance of the four integer
  multiplication algorithms. I tried manually modifying the
  MUL_KARATSUBA_THRESHOLD MUL_TOOM3_THRESHOLD
  MUL_FFT_THRESHOLD in the 'gmp-mparam.h' as follows:
  
  #define MUL_KARATSUBA_THRESHOLD          1
  #define MUL_TOOM3_THRESHOLD              5100
  ....
  #define MUL_FFT_THRESHOLD              5100
  
  Then, I re-ran the configure and make. I expect it to force using
  Karatsuba when the sizes of operands are in [1, 5100) in terms of limb.
  However, the outcome doesn't change accordingly. It's more like that the
  Karatsuba hasn't been forced to be used throughout the testing range.
  
  Any suggestion is appreciated. Happy belated New Year!

Perhaps your modified gmp-mparam.h didn't survive the new configure?
Depending on your editor's behaviour, it might have modified just the
gmp-mparam.h in the build directory, or the file to which that
gmp-mparam.h symlink is pointing.

Instead of modifying gmp-mparam.h, I would suggest that you use the
tune/speed program to measure the various functions directly.

$ cd tune
$ make speed
[snip]
$ ./speed -c -s1-500 -f1.4 mpn_mul_basecase mpn_kara_mul_n mpn_toom3_mul_n
overhead 6.06 cycles, precision 10000 units of 4.56e-10 secs, CPU freq
king> 2192.19 MHz
        mpn_mul_basecase mpn_kara_mul_n mpn_toom3_mul_n
1              #25.18           n/a           n/a
2              #48.34        168.20           n/a
3              #79.56        250.84           n/a
4             #125.12        259.46           n/a
5             #179.32        340.70           n/a
7             #288.47        500.67           n/a
9             #546.90        762.40           n/a
12            #883.00        990.18           n/a
16           #1426.75       1440.50           n/a
22           #2482.60       2737.00       5593.50
30           #4341.00       4390.00       7159.50
42            8086.00      #7449.50       9831.00
58           14882.00     #12984.00      16218.00
81           28120.00     #22529.00      24048.00
113          53656.00     #39188.00      39234.00
158         103582.00      66951.00     #65582.00
221         200328.00     116396.00    #110659.00
309         389771.00     199235.00    #184190.00
432         757818.00     339379.00    #305710.00

-- 
Torbjörn