Re: CLN, GMP inputs

[Hans Aberg]

At 09:44 +1000 2001/05/06, Kevin Ryde wrote:
>I might have guessed the opposite, that function call overheads and
>memory allocations (if they occur repeatedly) would be the worst
>slowdowns.

In a two space GC, one simply allocates memory by changing the stack
pointer until memory has run out in one space. Then at GC time, one has to
trace the still active objects form the root set, and then copies them over
to the free space. So as long as one does not hit GC time, the memory
allocation time is insignificant.

I saw another interesting memory allocation technique mentioned by Hans
Boehm: If the objects are of the same size, it is quick to have two singly
linked lists inside an array, one for allocated and one for free space, as
memory chunks can be quickly moved from one list to another. So one then
simply has arrays for memory chunks of size 2^n, n = N, N+1, ... The
problem though is what to do when one runs out of memory, that is, finding
a balance between the different arrays.

>  But no doubt it's best to fire up the profiler or do some
>sample measurements and find out for sure.

Only the use of a profiler can tell that.

>> If GMP would add small number representations, that might even be a
>> complication, because GHC might still need to convert to its internal
>> format.
>
>You know a possibility would be to reserve one bit of a 32-bit int as
>a flag indicating it's not a number but a pointer to a bignum.  Then
>maybe all arithmetic could be inlined and just have traps to special
>code if a bignum is encountered.  But no doubt others smarter than me
>have thought more about such things.

I also thought of that variation: An obvious overflow candidate for signed
integral types is the smallest negative number, binary 100... For floating
small number reprenetations, one might use NaN as a flag.

But perhaps ther representation could be
  typedef struct  {
    _mp_int _mp_s;     /* Small number representation. */
    mp_limb_t *_mp_d;  /* Pointer to the limbs and all other data.  */
  } __mpz_struct;
where simply _mp_d is set to NULL if one is using the small number
representation.

In this model, mp_alloc and _mp_size would be in _mp_d, but the _mp_s could
be used for other data not directly linked to the number itself:

One idea is to put the sign in _mp_s; then sign changes could be made fast,
if one allows a function returning the same pointer. For example, a version
of the function mpz_neg could merely change the sign bit in _mp_s, and also
set a bit indicating that it did not allocate any more space. The thing is
that if one is using some form of conservative GC, then it is OK to have
several objects pointing at the same memory allocation. If the memory
sharing bit is set, it merely means that one must make a copy before
mutating. It is easy to build a version (as macro or inline) that always
make new storage on top of such functions.

  Hans Aberg