[gambit-list] Bignum performance

Bradley Lucier lucier at math.purdue.edu
Thu Nov 3 17:46:10 EDT 2011


On Thu, 2011-11-03 at 16:11 -0400, Bradley Lucier wrote:
> Mikael sent me some comments about the bignum code, and he said it
> would be OK if I replied to the list.
> 
> On Thu, 2011-11-03 at 18:34 +0200, Mikael wrote:
> 
> > I saw the bignum benchmarks at
> > http://dynamo.iro.umontreal.ca/~gambit/wiki/index.php/Benchmarks .
> > 
> > I'd suppose though that for small bignums (<2^512 or so), Gambit's
> > bignum handling is even so highly performant also compared with
> > using GMP, as Gambit has a deep bignum integration for instance with
> > partial inlining of operations and fast object handling.

I believe that the following are somewhat accurate comparisons of
Gambit's bignum multiplication with GMP's on my machine, which is

model name	: Intel(R) Core(TM)2 Quad  CPU   Q8200  @ 2.33GHz

running Ubuntu 11.10.  I'm using the gmp binary compiled by the Ubuntu.

The top of the gmpbench output file is:

***** GMPbench version 0.2 *****
Using default CFLAGS = "-O3 -fomit-frame-pointer"
Using default CC = "gcc"
Using default LIBS = "-static -lgmp"
Using compilation command: gcc -O3 -fomit-frame-pointer foo.c -o foo
-static -lgmp
You may want to override CC, CFLAGS, and LIBS
Using gmp version: 5.0.1
Compiling benchmarks
Running benchmarks (propagated score accuracy exceeds printed
intermediates)
  Category base
    Program multiply (weight=1)
      GMPbench.base.multiply(128)                        4.785e+07
      GMPbench.base.multiply(512)                        8.715e+06
      GMPbench.base.multiply(8192)                       7.738e+04
      GMPbench.base.multiply(131072)                          1351
      GMPbench.base.multiply(2097152)                         47.9
      GMPbench.base.multiply(128,128)                    4.732e+07
      GMPbench.base.multiply(512,512)                    6.379e+06
      GMPbench.base.multiply(8192,8192)                  5.208e+04
      GMPbench.base.multiply(131072,131072)                    975
      GMPbench.base.multiply(2097152,2097152)                 24.5
      GMPbench.base.multiply(15000,10000)                2.707e+04
      GMPbench.base.multiply(20000,10000)                 2.03e+04
      GMPbench.base.multiply(30000,10000)                  1.3e+04
      GMPbench.base.multiply(16777216,512)                     191
      GMPbench.base.multiply(16777216,262144)                 7.62
    GMPbench.base.multiply                         18229

If multiply has only one argument, it means square a random integer with
that many bits.  If it has two arguments, it means multiply two random
integers with that many bits.  The number in the right column says how
many times that gmp can multiply two numbers of that size in one second.
So GMP can square a 128-bit number 4.785e+07 times in one second.  The
last number is the geometric mean of the individual results.

I benchmarked (+ 1 2) through Gambit's trampoline and found that it can
be executed 24890460.8318176 times in one second, so GMP can square a
128-bit number faster than that!

The corresponding rates for Gambit's multiplication are

(6069524.591984656
 1138447.92534668
 7861.313833590035
 470.5588253675315
 22.921199423388575
 5982941.863471437
 981751.6044178925
 6149.764635625322
 329.4516592427443
 15.90357661498334
 2585.696979797345
 2133.2000083328157
 1221.8808552808007
 32.51829280995132
 1.6805677630130624)
3216.6699235153046

So for very large bignums, GMP is about twice as fast, and for small
bignums it is about 8 times as fast, as Gambit.  Gambit has no special
code for taking advantage of the difference in size of the arguments.

The geometric average of the GMP rates is about 5.7 times as fast as
Gambit.

So I can think of some ways that I'd like to speed up Gambit, but it's
not going to be faster than GMP again at any operation (for a while it
was faster for large GCD).

Brad



More information about the Gambit-list mailing list