DivRem is 2x slower than cpp_int

[Marc Glisse]

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