This is possible but requires significant cooperation from the garbage collector, which is not possible without a lot of work. This is work that it planned, however: efficient bigints are definitely in our sights.
On Friday, April 8, 2016, Erik Schnetter <[email protected]> wrote: > Laurent > > I'm afraid you can't use `reinterpret` with a type such as `BigInt`. > > I think what you want is an extension of `Nullable`: A nullable type > represents an object of a particular type that might or might not be > there; there's hope that this would be done efficiently, e.g. via an > additional bit. What you want is an efficient representation of a > discriminated union -- a type that can represent either of two types, > but without the overhead from boxing the types as is currently done in > a `Union`. Unfortunately, Julia currently doesn't provide this, but it > would make sense to have a feature request for this. > > This might look like this: > ```Julia > immutable FastInt > val::DiscriminatedUnion{Int, BigInt} > end > function (+)(a::FastInt, b::FastInt) > if typeindex(a.val) == 1 & typeindex(b.val) == 1 > ov,res = add_with_overflow(a.val[1], b.val[1]) > ov && return FastInt(BigInt(res)) > return FastInt(res) > end > # TODO: handle mixed case > FastInt(a.val[2] + b.val[2]) > end > ``` > > This would be the same idea as yours, but the `reinterpret` occurs > within Julia, in a type-safe and type-stable manner, in a way such > that the compiler can optimize better. > > You could try defining a type that contains two fields, both an `Int` > and a `BigInt` -- maybe `BigInt` will handle the case of a value that > is never used in a more efficient manner that doesn't require > allocating an object. > > -erik > > On Fri, Apr 8, 2016 at 2:07 AM, Laurent Bartholdi > <[email protected] <javascript:;>> wrote: > > Dear all, > > How hard would it be to code arbitrary-precision integers in Julia with > at > > worst 2x performance loss over native Ints? > > > > This is what I have in mind: have a bitstype structure, say 64 bits, > which > > is either the address of a BigInt (if even), or an Int64 (if odd). > Addition > > would be something like: > > > > function +(a::FastInt,b::FastInt) > > if a&b&1 > > (result,obit) = @llvm.sadd.with.overflow.i64(a,b&~1) > > obit ? reinterpret(FastInt,BigInt(a>>1)+(b>>1)) : result > > elseif a&1 > > reinterpret(FastInt,(a>>1) + reinterpret(BigInt,b)) > > elseif b&1 > > reinterpret(FastInt,reinterpret(BigInt,a) + b>>1) > > else > > reinterpret(FastInt,reinterpret(BigInt,a) + > reinterpret(BigInt,b)) > > end > > end > > > > (code not meant to be run, just a skeleton) > > > > This would be very useful in the development of computer algebra > systems, in > > which BigInts are too slow and eat up too much memory, but one is ready > to > > pay a small price for guard against arithmetic overflows. > > > > If this is too complicated, then perhaps at least a type of integers that > > would raise an error in case of over/underflows? Those could be caught in > > throw/catch enclosures, so the user could restart the operation with > > BigInts. > > > > TIA, Laurent > > > > -- > Erik Schnetter <[email protected] <javascript:;>> > http://www.perimeterinstitute.ca/personal/eschnetter/ >
