Benchmarking GMP gives poor results for small numbers

[Richard Cavell]

Hi,

I just wanted to let everyone know of some benchmarking results that I've had with my program.

My program finds the factors of large compound numbers, which has applications for cryptography.  The program should be able to factorize 2048-bit numbers.  At the 
moment I'm testing it with 256-bit numbers just while I get my program working properly.

I coded the program using GMP and optimised it as far as I could.  One optimisation that I introduced was to re-use GMP variables.  It's murder on your benchmarks to do 
mpz_init() or mpz_clear() during your main loop.  So I introduced global variables to use as a holding place for temporary results, and it works well.  I also used pass-by-
reference wherever possible.

I then recoded the program using <stdint.h>, which includes uint64_t (a 64 bit integer).  I coded my own 128-bit and 256-bit number classes using this variable type.  The 
classes are less than satisfactory, because, for example, I can't access the carry bit after an addition (which I would be able to do from assembler).  

These results were obtained factorizing a 256-bit number using a Mac G4, which has a 32*32bit = 64bit answer hardware multiply (though you need two instructions to access 
the full result).

Number 1 : GMP - 66 seconds.  My code - 5 seconds.
Number 2 : GMP - 694 seconds.  My code - 73 seconds.
Number 3 : GMP - 555 seconds.  My code - less than 1 second.

For number 1 and 2, I think it's because the compiler (GCC 3.3) can optimize my code at compile-time, plus I suspect the CPU is able to keep the result in registers and better 
rearrange the instructions out-of-order, etc.

In the case of number 3, my code is streets ahead because I have introduced code to abort multistage operations (shifts and multiplies etc) prematurely when the result cannot 
be what I want, instead of waiting for the operation to complete and then comparing it and discarding it.

So I don't want to knock GMP code so much as I want to tell people that for numbers less than about 1024 bits, I strongly recommend using your own code for performance.


-- 
___________________________________________________________
Sign-up for Ads Free at Mail.com
http://promo.mail.com/adsfreejump.htm