speed of mpz_odd_p and lazy allocation

Marc Glisse marc.glisse at inria.fr
Mon Aug 13 17:16:51 CEST 2012

On Sun, 12 Aug 2012, Niels Möller wrote:

> Marc Glisse <marc.glisse at inria.fr> writes:
>> a piece of code that always bothered me:
>> /* Using "&" rather than "&&" means these can come out branch-free.  Every
>>    mpz_t has at least one limb allocated, so fetching the low limb is always
>>    allowed.  */
>> #define mpz_odd_p(z)   (((z)->_mp_size != 0) & __GMP_CAST (int, (z)->_mp_d[0]))
>> Is this branch in mpz_odd_p so bad, or can I move
>> it back to '&&'? (I also want to tweak mpz_get_ui so _mp_d is not
>> dereferenced when the size is 0)
> Why do you want to do that change now?

Because there are users expecting it ;-)

> If you'd prefer to have GMP never dereference mp_d when mp_size == 0, 
> then I think we ought to discuss that.

Sure, that's why I am posting.

> Off the top of my head, I think it would make some sense to do mpz_init
> without allocation as
> void mpz_init (mpz_t x)
> {
>  static const mp_limb_t zero = 0;
>  x->_mp_d = &zero;
>  x->_mp_alloc = x->_mp_size = 0;
> }

I considered using such a &zero trick (instead of memset(0)), where the 
reads are happy and every write first checks for this magic value or for 
alloc==0. Not dereferencing things of size 0 seemed cleaner to me. That's 
going to be quite a bit of work in any case (indeed the &zero solution is 
slightly less work, as we can leave the reads alone).

> I also have some related ideas, in particular to use _mp_alloc = 0 to
> mean that storage was allocated by the application. Such an mpz_t should
> be used only as input to gmp functions, never as output. One use would
> be for compile time constant bignums.

Hmm, if such mpz_t are only used as input, why do you need to specify 
anything? Or is it that they can also be used as output, but in that case 
they will allocate their own storage (kind of copy-on-write without 
reference counting)?

Marc Glisse

More information about the gmp-devel mailing list