speed of mpz_odd_p and lazy allocation

[Marc Glisse]

On Mon, 20 Aug 2012, Niels Möller wrote:

> Marc Glisse <marc.glisse at inria.fr> writes:
>
>> That's where move constructors appear. One can now define something
>> that is similar to a copy constructor, except that it leaves the
>> original object in some arbitrary state, so in particular it can steal
>> its resources.
>
> I don't know at all if it's possible to coerce std::vector to do this,
> but what do you think about the following procedure?
>
> 1. Allocate the new vector, mpz_init all elements (may suffer memory
>   allocation errors).
>
> 2. mpz_swap elements in the new and old vector. It will "steal"
>   resources efficiently, and as far I'm aware, it can't fail.
>
> 3. Now mpz_clear the old elements.
>
> 4. Initialize and assign the new element being appended, etc. In any
>   case, you have an intact vector with the original data.
>
> Sure, not very pretty to have to allocate a new limb for each mpz_t in
> step 1, just to free them in step 3. But at least it's O(n) work (n is the
> length of the vector).

This is perfectly fine, it is optimization n°2 for the case where the move 
constructor throws, but the move assignment (swap) doesn't. It is unclear 
whether this optimization will be implemented by any vendor. If mpz_init 
allocates, it remains slow.

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

Sounds nice.

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

Always hard to tell, and probably a compromise between different use 
patterns...

-- 
Marc Glisse