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.
First, let me say that I am not anywhere near an expert on GMP, and that my impression of GMP's code, performance, etc., is based on fairly brief examinations.
If you look at GMP's code, you'll find that it includes many very low-level optimizations, so that whatever algorithm they implement, their code will be very close to the optimal implementation of that algorithm. They have assembly implementations of inner loops, they use condition codes for integer overflow (I don't know how to do this in C), etc. I suspect that for small integers GMP's code is many times faster than Gambit's. For larger bignums, GMP chooses from among a very wide variety of algorithms for, say, multiplication, based on the relative sizes of the arguments.
Of course, as you say, Gambit's bignum code is integrated closely with the language, but it is in a separate module (_num.scm), so each bignum operation incurs a cost of two trampoline calls, which for small bignums (size a few times a fixnum) take many more operations than the time for the basic arithmetic calculations.
Just out of general interest, is there any initiative currently to upgrade Gambit's bignum library to the same speed level as GMP?
I don't think this is possible except by using GMP itself at this point.
I've asked on the Gambit list before whether fast bignums are important to people, and I've found no one who says they use bignums in their codes.
I use bignums in some of my codes, and I've found that Knuth's algorithm for long division, at least in my implementation, takes about three or more times as long as it could with a bit of tweaking for problems with small quotient or divisor. (I'm following Knuth to the letter, and he's a bit lazy at one point. Or maybe my interpretation of what he says leads to laziness on my part.)
My ideas for how to improve Gambit's bignum code are as follows.
I plan to tweak the code for naive long division, which is used when the divisor or the quotient is small.
Speeding up the division code for small quotients will also improve GCD times. The times for large GCD are the only times I find a bit embarrassing right now.
Independently, I intend to improve GCD for smaller bignums. This is important for rational arithmetic and for a code I have that does what might be called verifiable computations/constructive analysis/the computable reals.
I plan to investigate a slightly different algorithm for calculating the approximate inverse of a bignum, similar to what is in Knuth but with a slightly less stringent error bound that I think will require one to keep fewer bignum digits in intermediate results (and hence use computer multiplications with fewer bits). This might increase the speed of division for large bignums.
Gambit is shining with performance in other areas, so this would be a really worthy area to shine in as well :-)
=90% of GMP's performance should be achievable while having the
bignum library written in Scheme, what do you think?
No. Generally, Gambit's code takes twice as long as similar C code; and C code often takes twice as long as well-written assembly code. So I suspect that from now on GMP will always be about four times as fast as Gambit in bignum code. Also, GMP implements many different algorithms for the same problem, and which algorithm is used is based on problem size.
I think that there were several design goals for Gambit's bignum code:
1. First, to implement in portable Scheme code the basic bignum algorithms as found in Knuth, volume II, say, by following the strategy explained by Jon L White many years ago in the included paper. We started this in 1998. This code worked out of the box for variations of machine characteristics: big-endian/little-endian and 32-bit words, 64-bit long long; 64-bit words, 64 bit long long; and 32-bit words, no long long.
2. Later, I wanted to implement fast variants of very large bignum operations with algorithms that were relatively compact and understandable. This led to using two somewhat novel algorithms, one for bignum multiplication that is much shorter than what GMP uses but which they rejected, and one for GCD, which I reconstructed from discussions with Schoenhage (there are a few comments in the code). I also use a few known compact algorithms with high performance, for inverting a bignum and for integer square root.
A secondary approach could possibly be to make GMP/MPFR/MPIR bindings for the bignum computations in Gambit, though GMP/etc.'s license is a bit narrow maybe.
It's LGPL, so that's not too restrictive for nearly all applications.
Anyhow, what would the basic challenge be in this, are Gambit's current bignum structures in a form that would go perfectly together with GMP/etc.'s interface & handling, would GMP/etc. deliver the full numeric tower?
I don't know whether GMP's bignum format is the same as Gambit's, but I doubt that it would be so.
GMP could certainly deliver the full numeric tower.
Brad
Afficher les réponses par date
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