[Openmcl-devel] Bignums using GMP.

[Gary Byers]

This is great, thanks.

See below ...

On Sat, 13 Feb 2010, Waldek Hebisch wrote:

> Attached are two files which together cause Closure CL to use GMP
> for bignum arithmetic.  The routines are specific to 64-bit Amd
> (and Intel) architecture.  For relatively small bignums current
> Closure CL multiplication is quite competitive and the routines
> use it, however for really large bignums GMP is faster.  For
> division (truncate), gcd and integer square root GMP is faster
> even for smallest bignums so the routines just use GMP.  In fact,
> fixnum isqrt is slower than isqrt for small bignums via GMP.
>
> I use GMP "mpn" routines.  Because the "mpn" interface is quite
> restrictive I use two helper C routines.  On Lisp side there
> are LAP routines to do reasonably fact copy and replacements
> for Closuse CL bignums routines.  Like originals the replacements
> are careful to stack allocate temporaries.
>
> To try the routines compile the C file to get shared library
> (as indicated at the top of the file), then compile the lisp
> file.  After starting Closure CL load GMP library, then the
> helper library and the fasl.  After that Closure CL will use
> new routines.
>
> To give you some idea of speed, on 2.4 GHz Core 2 Quadro,
> gcd of 90949470177292823791503906250000000 and
> 7178979876918525887702490000000 takes 11us using current
> version and 1us using GMP (I used GMP 5.0, GMP 4.2
> is slower).
>
> Comments welcame.  In particular what is best method to
> make sure that multiplication works OK after starting
> from saved image.  For my purpose I modified Closure CL
> kernel makefile to link in my C routines and GMP.  But
> without linking GMP to Lisp kernel there is risk that
> replacement bignum routines will try to use GMP before
> it is loaded (IIUC saved core image will contain
> replacement bignum routines, but have no access to GMP
> before it is explicitely loaded).
>
> I wonder if there is interst to include such routines in
> Closure CL (possibly as optional feature, if depending on
> GMP is considered undesirable).

If GMP was bundled/preinstalled with all platforms, it'd be
considerably more desirable than it is. (When it is bundled -
or available via things like Cygwin/MacPorts/Fink - there
might also be issues with version dependencies.  I honestly
don't know whether the GMP APIs of interest change between
releases or not.)

Depending on it may be undesirable, but there isn't much
downside to being able to exploit it if it's present.

I haven't looked at your code yet, but I wonder if it'd
be possible to do that exploitation via something like:

(defvar *use-gmp* nil) ; initially

;;; Implementation
(defun multiply-bignums (x y)
   (if *use-gmp*
     (gmp-multiply-bignums x y)
     ;; fall back to legacy, non-GMP implementation
     ...))

----
(defun load-gmp ()
   (open-shared-library *gmp-library-path*) ; may be platform/site-specific
   (require "GMP-SUPPORT") ; (re)define GMP-MULTIPLY-BIGNUMS
   ;; If we get this far and all is well,
   (setq *use-gmp* t))
----
(defun save-application (...)
   (setq *use-gmp* nil)
   ...)

The image-startup code will try to re-open shared libraries that
were open when the image was saved.  If it fails, it should do
so quietly and leave foreign functions defined in the missing
library undefined.  If it's successful in loading libgmp and
the lisp's GMP support is present, some other startup code
sets *use-gmp* to true and the image should ... use GMP; if
the gmp library isn't present, that shouldn't prevent the
image from starting up.

As you point out, there may be some incidental bignum arithmetic in
the startup code before we even get to this point.  Assuming that
the idea sketched out above actually works, that incidental bignum
arithmetic wouldn't depend on gmp's presence (if it's "incidental",
that shouldn't matter.)

That's all secondary: the harder part (providing GMP-based implementations
of CCL's bignum functions) sounds like it's already done.  Thanks!






> --
>                              Waldek Hebisch
> hebisch at math.uni.wroc.pl
>