speed of mpz_odd_p and lazy allocation

[Gabriel Dos Reis]

On Mon, Aug 20, 2012 at 2:24 PM, Marc Glisse <marc.glisse at inria.fr> wrote:
> 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.

What would be the basis for a vendor to assume that
the elements from the old vector should be assigned
as opposed to being copy constructed into the new vector?

>
>
>> 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
>
> _______________________________________________
> gmp-devel mailing list
> gmp-devel at gmplib.org
> https://gmplib.org/mailman/listinfo/gmp-devel