Re: [boost] Big Int

From: Guillaume Melquiond (guillaume.melquiond_at_[hidden])
Date: 2005-03-05 19:33:50

Le samedi 05 mars 2005 à 21:13 +0100, Christoph Ludwig a écrit :

> Can you point me to any data about the speedup of bigint operations due
> to ET? How complex need the expressions to be and what is the bitlength
> threshold so that programs profit from ET? (I am aware that ET can have a huge
> effect on the speed of matrix operations, but there you typically need to
> allocate / copy / deallocate much more data if you have temporary objects.)
> 
> Does anyone know what speedup one can expect if the move-semantic proposal is
> applied to bigint types? (Say, for simple expressions like x = y + z and 
> x = y * z.)

I can't tell you what it would be for this particular implementation,
but I can give you some results I got when using GMP some times ago. I
hope everybody will agree that GMP is a high quality implementation of
big integers, and hence the results are relevant.

The tests were comparing the cost of a superfluous temporary when using
basic arithmetic operations on 256 bit wide integers. So it applies to
your question, since we can suppose that a correct ET implementation
would not use a temporary for a single operation.

When using a temporary, a multiplication was executed around two times
slower, and a addition was executed around six times slower. Since GMP
is heavily optimized, the cost of a temporary (allocating memory,
copying data, freeing memory) for each operation is no more negligible.
Quite the contrary in fact, since it accounts for more than 80% of the
cost of an addition.

And the cost of a temporary becomes even worse, when the additional
memory requirements kick you out of L1 cache. Especially since a big
expression with temporaries can quickly require twice the memory needed
for the same expression without temporaries.

Best regards,

Guillaume

The body of the test for "c = a * b;" was
        mpz_t d;
        mpz_init(d);
        mpz_mul(d, a, b);
        mpz_set(c, d);
        mpz_clear(d);
when a temporary d was used to store the result of the multiplication.
Without temporary, it was simply
        mpz_mul(c, a, b);