Exploit mpq functions for Rational{BigInt}?

[stevengj]

As discussed on julia-dev, there is some performance advantage to using the GMP mpq functions for Rational{BigInt} operations.

The easiest way to do this would be:

• Make BigInt an immutable type. (It currently has immutable semantics anyway.) This way, Rational{BigInt} would be binary compatible with GMP's mpq_t (a pointer to an __mpq_struct consisting of the numerator __mpz_struct followed by the denominator), since our BigInt type is already a mirror of __mpz_struct.
• Define specialized + etc. methods for Rational{BigInt} that call GMP mpq functions.

I get the impression that the main reason that BigInt is a type and not immutable is that this makes it easier to pass by reference to GMP functions. So changing this to immutable would benefit greatly from a better way to pass ccall "out" arguments by reference, as discussed in #2322.

Alternatively, if you want to leave BigInt as-is, then one needs an easy way to convert BigInt to/from an immutable version thereof, and this requires us to add an additional "internal" constructor function BigInt(alloc::Cint, size::Cint, d::Ptr{Limb}).

[stevengj]

Alternatively, we could try to just make BigInt fast enough that there is no advantage to calling mpq. This would obviously be preferable, but it is not clear how achievable it is. The basic thing that appears to be needed is to find a way to aggressively re-use a pool of temporary variables, and is something we've discussed many times. I'm also not sure if GMP's mpq functions are doing something special (besides using in-place operations to minimize temporaries) that our Rational functions are not?

[wbhart]

There are other issues here. The mpq_t interface is quite standard and supported by many libraries (including numerous libraries written by people interested in using Julia). If you use a different rational format to GMP, you no longer get the benefit of any new rational function implementations GMP provides, or easy/efficient interface to those libraries that represent rationals as mpq_t's or at least interface to them.

GMP rationals are extremely efficient for numerous reasons:

1. Use of in-place operations
2. Very careful use of macros
3. Very careful avoidance of copying data unnecessarily
4. Very careful avoidance of incurring additional allocations/reallocations
5. Very judicious use of gcd for canonicalisation
6. Fast code paths for certain inputs, e.g. for zero inputs or squaring vs mul, etc.
7. Avoiding function call overhead of mpz functions where possible by manually inlining relevant portions of mpz functions
8. Avoiding certain paths in mpz functions which are provably not encountered when using them in the way they are used in rational functions
9. Branch hinting

No matter how sophisticated Julia becomes, it isn't going to approach that kind of optimised performance if it uses a generic implementation to handle rational arithmetic. GMP is twenty years old at least and meticulously and insanely optimised.

[Liozou]

I know this is quite an old issue but just for reference, there is now a wrapper around GMP rational functions in https://github.com/Liozou/BigRationals.jl, in case people need to use it.
To comment on the initial proposal, changing the status of BigInt from mutable to immutable sounds difficult because GMP manages its own memory, so BigInts should have a fixed memory address and I don't think there can be such a guarantee for immutable objects.

[StefanKarpinski]

To comment on the initial proposal, changing the status of BigInt from mutable to immutable sounds difficult because GMP manages its own memory, so BigInts should have a fixed memory address and I don't think there can be such a guarantee for immutable objects.

Indeed—GMP objects need to be finalized and immutable objects cannot be finalized.

[vtjnash]

Can this be closed?

[simonbyrne]

It might be possible to support this, but you would have to convert from a Rational{BigInt} to an mpq object and back again at every operation. Can this be done with minimal overhead?

[stevengj]

It looks like conversion would be extremely cheap, since it just involves copying 6 scalar fields back and forth (compare BigInt to BigRational).

[simonbyrne]

I wasn't sure if we needed to init the mpq object separately from the mpz ones, but it appears that is not the case. Here is a simple proof-of-concept:

import Base.GMP: Limb

mutable struct MPQ
    num_alloc::Cint
    num_size::Cint
    num_d::Ptr{Limb}
    den_alloc::Cint
    den_size::Cint
    den_d::Ptr{Limb}
end

MPQ(x::Rational{BigInt}) = MPQ(x.num.alloc, x.num.size, x.num.d,
                               x.den.alloc, x.den.size, x.den.d)

function update!(x::Rational{BigInt}, xq::MPQ)
    x.num.alloc = xq.num_alloc
    x.num.size  = xq.num_size
    x.num.d     = xq.num_d
    x.den.alloc = xq.den_alloc
    x.den.size  = xq.den_size
    x.den.d     = xq.den_d
end
    
const mpq_t = Ref{MPQ}

function add(x::Rational{BigInt}, y::Rational{BigInt})
    z = Rational{BigInt}(0)
    zq = MPQ(z)
    ccall((:__gmpq_add, :libgmp), Cvoid,
          (mpq_t,mpq_t,mpq_t), zq, MPQ(x), MPQ(y))
    update!(z,zq)
    return z
end

julia> add(big(2//3), big(2//3))
4//3

[simonbyrne]

One difference is that mpq functions don't support our "rational infinites" (1//0 and -1//0), so these would need to be handled differently.

[thofma]

This is quite a fragile "interface". As soon you call MPQ(z) you need to GC.@preserve z. In particular the add function needs to preserve x, y and z.

[simonbyrne]

Good point. The easiest solution would be to tack on z::Rational{BigInt} to the end of the struct.