speed of mpz_odd_p and lazy allocation
Gabriel Dos Reis
gdr at integrable-solutions.net
Mon Aug 20 21:31:51 CEST 2012
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 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
> Marc Glisse
> gmp-devel mailing list
> gmp-devel at gmplib.org
More information about the gmp-devel