invmod (and mod) with one BigInt and one Int is slow

[Glen-O]

The invmod function is quite fast when used on two BigInt values... but is noticeably slower if given one BigInt and one Int.

For example, using BenchmarkTools on my computer, I get

Code	Timing
@btime invmod(6859298177628010541,7156363682119191629)	294.757 ns (0 allocations: 0 bytes)
@btime invmod(big"6859298177628010541",big"7156363682119191629")	671.951 ns (10 allocations: 168 bytes)
@btime invmod(big"6859298177628010541",7156363682119191629)	20.000 μs (642 allocations: 12.17 KiB)
@btime invmod(6859298177628010541,big"7156363682119191629")	19.800 μs (639 allocations: 12.13 KiB)

I am unsure as to the specific reasoning for why the code performs like this; however, I can get much better performance with the following functions

invmod_new(a::Int,b::Int)=invmod(a,b)
invmod_new(a::BigInt,b::BigInt)=invmod(a,b)
invmod_new(a::Int,b::BigInt)=invmod(BigInt(a),b)
invmod_new(a::BigInt,b::Int)=invmod(Int(mod(a,b)),b)
# or invmod_new(a::BigInt,b::Int)=BigInt(invmod(Int(mod(a,b)),b)) to keep types consistent with invmod, only a little slower
# Alternatively, invmod_new(a::BigInt,b::Int)=invmod(a,BigInt(b)) - but this takes about twice as long

With these, I get

Code	Timing
@btime invmod_new(6859298177628010541,7156363682119191629)	293.939 ns (0 allocations: 0 bytes)
@btime invmod_new(big"6859298177628010541",big"7156363682119191629")	666.250 ns (10 allocations: 168 bytes)
@btime invmod_new(big"6859298177628010541",7156363682119191629)	486.667 ns (5 allocations: 80 bytes)
@btime invmod_new(6859298177628010541,big"7156363682119191629")	793.137 ns (13 allocations: 208 bytes)

This is a 20-40x speedup for the mixed cases.

A similar issue applies for mod, although the difference is smaller (a factor of ~3x for mod(Int,BigInt) or mod(BigInt,Int) compared with mod(BigInt,BigInt)) - I am uncertain how to improve this one, as mod_new(a::Int,b::BigInt)=mod(BigInt(a),b) does not improve performance, in this case, but it definitely seems inefficient.

[oscardssmith]

These solutions seem sub-optimal, but definitely better. Theoretically, we should be able to return Int for all these cases of mod, but it's probably more trouble than it's worth

[Glen-O]

Okay, so I've looked further into libgmp, and mod can be accelerated for mod(BigInt,Int) cases quite well, with this:

mod_new(a::BigInt,b::Int)=ccall((:__gmpn_mod_1,:libgmp),Int,(Ptr{UInt},Int,Int),a.d,a.size,b)
# This produces an Int output, not BigInt - easily changed if desired.

For comparison (with constants switched compared with the first post):

Code	Timing
@btime mod(big"7156363682119191629",6859298177628010541)	272.512 ns (5 allocations: 80 bytes)
@btime mod_new(big"7156363682119191629",6859298177628010541)	12.538 ns (0 allocations: 0 bytes)

As you can see, this produces a big speedup. Note that this does not handle negative inputs correctly - this can be corrected with a bit of extra code.

There are some other issues, of course, along the way.