DivRem is 2x slower than cpp_int
Marc Glisse
marc.glisse at inria.fr
Wed Oct 5 20:01:23 UTC 2016
On Wed, 5 Oct 2016, Andy wrote:
> I test under Linux. Multiplications are identical as cpp_int but divide
> with remainder is two times slower:
Posting code using a 3rd-party library (boost) might not be the most
efficient way to start the conversation. I am happy to discuss, but be
aware that it may discourage others.
> #define itype mpz_int
mpz_class seems to give exactly the same timing as mpz_int, so a bug in
the boost wrapper seems unlikely.
> void test(const itype n)
> {
> itype x = n;
Please indent your code.
Useless copy, you might as well declare void test(itype x).
> itype i, e;
> i = 3;
itype i = 3;
Don't predeclare for expensive types, that wastes cpu.
> e = sqrt(x);
> while (i <= e) {
> if ((x % i) == 0) break;
This involves creating a temporary for x%i, which is slow for GMP
(malloc+free), while it is cheap for cpp_int for small numbers. Declare
itype tmp; at the beginning, then recycle it:
if ((tmp = x % i) == 0) break;
I have in my TODO list to detect (x%i)==0 at compile-time and redirect it
to mpz_divisible_p (it has been on my TODO list for years, don't hold your
breath).
if (mpz_divisible_p(x.get_mpz_t(), i.get_mpz_t())) break;
makes the mpz_class timing better than cpp_int.
> i+=2;
> }
> }
> int main()
> {
> itype a("3448409664461");//prime
Ah, this is a rather small number to feed to a bignum library... May I
suggest using 'long long' instead?
More seriously, what I get from your email is that some GMP operations
(mpz_tdiv_r in particular) are not perfectly optimized for very small
numbers (one limb). That is true. Boost checks if the divisor has a single
limb and has a separate routine for that, in which it checks if the
dividend has a single limb and it has special code for that. GMP has the
special code for the divisor, but not the small dividend case (and we may
have more overhead than boost before calling the small divisor case). It
would be nice to have more "fast paths" for small integers (as long as
it doesn't slow down the regular case significantly), although there
may be better solutions if small integers are really common, see for
instance flint's fmpz, ghc's Integer, etc.
Would you be interested in writing a patch to help GMP handle your
testcase faster?
--
Marc Glisse
More information about the gmp-discuss
mailing list