Re: CLN, GMP inputs

[Kevin Ryde]

Hans Aberg <address@hidden> writes:
>
> 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).

I measured one unoptimized dynamic-linked libc malloc on an athlon at
no less than 700 cycles for malloc+free, or 1200 for
malloc+realloc+free.  The next gmp will have some code to measure that
sort of thing better (in the tune/speed.c program).

Of course if the run time for a program is dominated by allocate and
free then there's something badly wrong in the algorithm or its
implementation.

> 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.

Ben Hinkle posted this list a while back similarly wanting a single
malloced block for an mpf.  One idea on that front is to change to
something like

        typedef struct
        {
          int _mp_prec;
          int _mp_size;
          mp_exp_t _mp_exp;
          mp_limb_t _mp_d[];
        } __mpf_struct;

Which is allocated with enough space for the _mp_d data there in the
same block.  (An empty [] is a gcc extension I think, but _mp_d[1]
works just as well.)

The advantage of that is most sources would work unchanged, _mp_d
having just changed from a pointer to an array.  Init and clear become
very different though, and the semantics for applications too.  This
is not a bad idea for mpf because once a precision is set it doesn't
need to grow or shrink, but that's not true of mpz and mpq in general.

> 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.

I'd recommend making other arrangements to setup the mpz_t parts, if
that seems to be a problem.  I'm afraid the need for upward binary
compatibility will prevent any radical changes.

Since mpz_t is only small, one possibility would be an array of them.
A good malloc probably already does that for small blocks.  Otherwise,
or as well as that, I'd still suggest a free list of pre-initialized
values, to be handed out as needed.  I'm pretty sure that could work
well either with a garbage collector or reference counting.