GMP and 64-bit systems

[librik at panix.com]

Torbjorn Granlund <tg at swox.com> wrote:
> Do you deny the rumours about that your inaction on LLP64 is related to
> the fact that you failed to extort a large sum of money from somebody
> who offered to help?  :-)

Dear Mister Granlund,

Nice bignum math library you've got here.  It would be a shame if anything
happened to it ... you know, accidentally.  Wouldn't you agree that ten
thousand dollars is a small price to pay for backwards compatibility --
if you know what I mean?  We'll be in touch.

Yours sincerely,
Tony "The Godfather" Soprano


Seriously though:  You bring up several issues which are important, but
which I don't completely understand.  I'll answer as best I can, and I
hope you can explain things further.

I think the "SAGE rage" grows out of a reasonable desire for an
LLP64-compatible GMP, and if GMP can be improved so it supports
all the 64-bit models without special-case code, everyone will
be happier, and fewer GMP supporters will fork off and die.


Okay, first...

> If we decide to supports Windoze's 64-bit ABI, we do not need to worry
> about actual 64-bit limb counts internally, since the limitations of
> mpz_t would make that almost pointless.  (We already support larger
> numbers at the mpn level for existing systems, but this has not been
> well-tested and is probably used very little.)

Oh no!  I have not made myself clear.  I want GMP to support 64-bit mpn
limb counts on LLP64.  That's a primary goal.  The public function
interface is important, but secondary!  If there are not 64-bit limb
counts, then there's no point changing anything, because the current
gmp.h is perfectly fine for the _status quo_ on LLP64.

The goal is basically to make this change to gmp.h:

    #if defined (_CRAY) && ! defined (_CRAYMPP)
    /* plain `int' is much faster (48 bits) */
    #define __GMP_MP_SIZE_T_INT     1
    typedef int                     mp_size_t;
    typedef int                     mp_exp_t;
    #else
    #define __GMP_MP_SIZE_T_INT     0
 +  #if defined (LONG_LONG_SIZE)
 +  typedef long long int           mp_size_t;
 +  typedef long long int           mp_exp_t;
 +  #else
    typedef long int                mp_size_t;
    typedef long int                mp_exp_t;
 +  #endif
    #endif

and have GMP "do the right thing" everywhere, when you #define
LONG_LONG_SIZE.

(Although there is more to the project than mp_size_t alone.)


> Also, public interfaces' types should not change.

This is a key sticking point.

I would say that if a public declaration in gmp.h such as:
   unsigned long int mpn_popcount(const mp_limb_t *s1p, mp_size_t n);
were changed to:
   typedef  unsigned long int  mp_bit_count_t;
   mp_bit_count_t mpn_popcount(const mp_limb_t *s1p, mp_size_t n);
then the types have NOT changed.  They are identical at the binary
level, the compiler-semantics level, and the C type compatibility
level.  Only the literal text name has changed.  "typedef" doesn't
create a new type, it creates a new identifier as a synonym for
the given type.

This is important.  If we agree on this, then we can move forward.

It then becomes possible to change the typedef in gmp.h to:
   #if !defined(LONG_LONG_SIZE)
   typedef  unsigned long int  mp_bit_count_t;
   #else
   typedef  unsigned long long int  mp_bit_count_t;
   #endif
Since LONG_LONG_SIZE is not defined on any current ABI, the types
in public functions STILL HAVE NOT CHANGED.

Finally, on LLP64 builds, we can turn on LONG_LONG_SIZE.
Now backwards compatibility might be broken for any LLP64 GMPs.
But GMP has never supported any LLP64 systems before, so there is
no backwards compatibility break!

And notice that the code is clearer.  We have a named type for
a bit count.  It is exactly the same type as it was before
(unsigned long) but now it is "conceptually right."

(Really, bit counts are kind of weird.  To be fully correct, a
bit count type must be 35 bits or 67 bits wide.  Otherwise there
will be an overflow when counting bits in very large mpns.  This
is true on all computers.)


So when you write:
> Supporting Windoze's 64-bit ABI is something we might want to do, but
> it is not a central goal of the GNU project.  We should not break
> binary compatibility for its sake.  In particular, "unsigned long" bit
> counts in user visible function should not change.

I would agree, if you are not attached to the actual words "unsigned long",
but are fine with a type name whose meaning is a 32-bit unsigned integer
on 32-bit systems, 64-bit integer on 64-bit systems.  This would be the
same as "unsigned long" on all currently supported 32-bit and 64-bit ABIs.



> There is one tricky thing about this, and it is whether to assume
> "long long" exixts.  When I started working on GMP, it certainly
> wasn't ubiquitous.  Unfortunately, I don't think we can assume it is
> now, since it was not specified until C99.

> We want there to be one GMP ABI, so we cannot define a user visible
> function with "long long" unless we decide to de-support C89
> environments.

I'm not sure I understand.  I'll try to answer what I think you're
saying.

I would say that we don't want any user-visible functions with the
literal words "long long", just as we don't want user-visible
functions with the literal word "long".

The reason a function would use "long long" is because it wants a
64-bit value and it's intended for an LLP64 system, where "long" is
inadequate.  But in that case, the user-visible function should use
a typedef name instead, just like mp_bit_count_t above.  That type is
identical to "long" on ILP32 and LP64 systems, and "long long" on
LLP64 systems; it's always 64 bits on a 64-bit machine.

Replacing "long" with a typedef name that is defined to be "long"
does not break compatibility, and works fine in C89 environments.
The typedef name can also be defined to "long long", but that
happens behind an #ifdef, so no C89 compilers will complain.

If I've misunderstood, could you give an example of a user-visible
function which might need an explicit "long long" in its public
declaration?


I believe that it is possible to improve GMP so that it:
* Remains as backwards-compatible as possible with previous supported
  versions.
* Provides a way for LLP64 users to easily create an LLP64 GMP with
  the same abilities as the currently-supported LP64 and ILP64 GMPs.
* Adds no special-case hacks to functions.
Nobody will have to write "Windoze OS code," but the Win64 people will
be satisfied.

What do you think?


- David Librik
librik at panix.com