Re: CLN, GMP inputs

[Hans Aberg]

At 09:14 +1000 2001/04/30, Kevin Ryde wrote:
>> As for the ref count and the unboxed number representation, perhaps it is
>> possible to implement it on the C-level: One only mimics what one might do
>> in C++.
>
>An idea to store one limb values in the mpz_t itself, not through
>_mp_d[0] got kicked around for a while.  I think it's been dropped as
>too much work for too little gain.

This is the "unboxed" variation used in say functional languages in order
to avoid too much overhead.

How effective it is I figure can only be determined by actual timing. The
thing is that every malloc or "new" take up several tens of cycles (I made
a count on my computer, and it was up to 80 cycles).

The reason that one might want to have it integrated into GMP is that
overflow checks and such takes up a lot of cycles, so one might want to go
down on an assembler level for doing that.

>> typedef struct {
>>   union {
>>     mp_int     _mp_n;
>>     mp_limb_t* _mp_all;       /* Pointer to all.  */
>>   };
>>   int unboxed;
>> } __mpz_struct;
>>
>> #define _mpz_alloc  _mp_all[0]
>> #define _mpz_count  _mp_all[1]
>> #define _mpz_size   _mp_all[2]
>> #define _mpz_d      _mp_all + 3
>
>I guess that's an idea, but geared towards c++ where those reference
>counts can be maintained magically.  I think the current scheme
>probably suits plain c better.

The ref count is really only one method to do GC (garbage collecting).

There is the variation that one writes GMP so that one can add a ref count
under C++ by changing the memory allocation functions malloc, etc. The
advantage of this method is that one can get the whole structure into one
memory allocation without settling for one particular type of GC (i.e.,
working with other methods of GC than ref counts).

It would involve writing the code so that the other fields _mpz_alloc, etc,
are not addressed before the _mpz_d field. For example:
  mpz_init (mpz_ptr x)
  {
    x->_mp_alloc = 1;   /* Reference before allocation */
    x->_mp_d = (mp_ptr) (*_mp_allocate_func) (BYTES_PER_MP_LIMB);
    x->_mp_size = 0;
  }
would be changed to
  mpz_init (mpz_ptr x)
  {
    x->_mp_d = (mp_ptr) (*_mp_allocate_func) (BYTES_PER_MP_LIMB);
    x->_mp_alloc = 1;   /* Reference after allocation */
    x->_mp_size = 0;
  }

Then, under C++ using a ref count, one can define

size_t _mp_d_offset     = 3 * sizeof(mp_limb_t);

#define malloc(size)  ((char*)malloc(size + _mp_d_offset) + _mp_d_offset)
#define realloc(oldptr, new_size)  ((char*)realloc((char*)oldptr -
_mp_d_offset, new_size + _mp_d_offset) + _mp_d_offset)
#define free(ptr)  (free((char*)ptr - _mp_d_offset))

typedef struct
{
  mp_limb_t *_mp_d;             /* Pointer to all.  */
} __mpz_struct;

#define _mp_count  _mp_d[-3]
#define _mp_alloc  _mp_d[-2]
#define _mp_size   _mp_d[-1]

The only problem with this approach is that the __mpf_struct has a field
using the same name _mp_d as the __mpz_struct, which will screw up the
macros.

If I should sum the above up seen from the perspective of GMP development,
then what one wants is that all the stuff relating to the dynamic behavior
of the __mpz_struct and __mpf_struct ending up in the memory allocation, so
that one can avoid having to do another such memory allocation.

  Hans Aberg