speed of mpz_odd_p and lazy allocation
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 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
More information about the gmp-devel