speed of mpz_odd_p and lazy allocation

Marc Glisse marc.glisse at inria.fr
Tue Aug 21 13:14:20 CEST 2012


On Tue, 21 Aug 2012, Torbjorn Granlund wrote:

> nisse at lysator.liu.se (Niels Möller) writes:
>
>  To me, it would make sense to let mpz_init not allocate storage, but
>  point to a shared limb, possibly read-only, and set _mp_alloc to zero.
>  But I haven't reviewed the code to see where _mp_d[0] is written without
>  checking _mp_alloc. So I don't know if an extra branch in those places,
>  to support lazy allocation, matters for performance.
> 
> We should study the feasbility of avoiding limb allocation at mpz_init
> time (and the other GMP init functions).
>
> For readers, we should almost surely play some tricks with pointing the
> mp_d field somewhere safe.  We might nevertheless check how many places
> make dummy reads.
>
> As Marc points out, some functions will write one-limb results without
> checking the alloc field.  That was a design decision by me when writing
> the original library.  An example would be mpz_set_ui.
>
> We need to find places that would need an MPZ_REALLOC.
>
> And we will need to change MPZ_REALLOC (the macro or a functions it
> calls) to either allocate or reallocate.
>
> How much editing will be needed?  What performance impacts are expected?

There is quite a bit of editing needed. I remember from when I prototyped 
it in 2009 (code is long lost). But that's still manageable if we want to 
go there. From an email I sent at the time, it looks like the gains were 
2% on one application and 20% on another one. The thing is, those gains 
are mostly for C++ programs that use a non-reference-counted wrapper. 
Nicely written C programs are less likely to mpz_init a variable and not 
use it until mpz_clear. In C++, this can mean that a=b+c+d+e+f+g uses a 
single allocation instead of 5. I guess I should simulate the gains for 
std::vector, since those would also apply to gmpxx and not just external 
wrappers.

-- 
Marc Glisse


More information about the gmp-devel mailing list