Re: CLN, GMP inputs

[Hans Aberg]

At 12:58 +0200 2001/05/11, Torbjorn Granlund wrote:
>  If only overflow detection is available, I think that will help a lot,
>  because it can help making the small nums fast. Once one gets an overflow,
>  one knocks on a lot of cycles because of the memory allocation, so then it
>  does not matter much about inconvenience (from the point of view of speed).
>
>Memory allocation is not an issue here, is it?  Just because we have
>code for special-handling of single-limb numbers doesn't mean that we
>will need to perform memory reallocation.  We often already have
>enough space.

Regardless how one in the end decides to resolve the problems with small
number representation, the idea is to avoid any dynamic (malloc etc) memory
allocations at all for those small numbers.

The second requirement is that it should be possible for a user of the
library to detect whether the small number format is used, and further, it
should most likely be a native signed type.

So the picture I have something my mind is something like this: One starts
off with only small number arithmetic. Then there should be no dynamic
memory allocations. If one uses a type like
  typedef struct  {
    _mp_int _mp_s;     /* Small number representation. */
    mp_limb_t *_mp_d;  /* Pointer to the limbs and all other data.  */
  } __mpz_struct;
with _mp_d == NULL, then no dynamic allocations will be needed.

Then somehow one gets an overflow, and GMP shifts to its _mp_d format. It
should contain all the other data, mp_alloc and _mp_size or whatever,
because that is how it will be used (several pointers may point towards the
same _mp_d).

Then there is another question: Suppose that one now computes with the
large _mp_d format, if the number now fits into one limb, should it convert
back to the small number format. -- GHC does not do that; once small
numbers have overflowed to large numbers, one is stuck with that.

But I think it would help if GMP does that, converts back to a small number
format whenever it can.

>In fact, memory management is not an issue for any properly written
>GMP application.

I am not exactly sure what you mean here:

It looks as though GHC is doing some exceptional memory management, and
abusing GMP's internal format. It is unavoidable, because GHC uses its own
conservative GC.

A common thing between building a C++ wrap and uses like GHC is that the
_mpd_ field needs some extra reserved memory for internal use (in the case
of the C++ wrap, a ref count):

If I should build an optimized C++ wrap with a ref count, then if that code
should be compatible with some C code calling the same mpz structures, then
GMP must be aware of the extra memory offset.

But for a program like GHC, it probably does not matter, because it will
convert to its own internal format anyway. But if GHC would start to write
extensions that allows one to mix C code and Haskell code in an optimized
manner, then one would end up with the same equations as with the C++ using
a ref count, I think.

So it the question is whether it is worth knocking on cycles for extra
offset computations.

  Hans Aberg