I understand my sketch is very specific... if memory efficiency is at issue, it's important to treat pointers as 61-bit and to accept working with 63-bit signints if discriminated unions are to exist at no memory cost. (In the computer algebra applications I have in mind, losing 50% speed is fine, losing 50% memory is not)
On Fri, Apr 8, 2016, 17:47 Stefan Karpinski <[email protected]> wrote: > This could help if both parts of the union were plain old data like Int64 > and Float64, but in the case of Int and BigInt, one of them is a more > complex type, which would currently force the whole thing to be boxed and > live in the heap anyway. What's needed here is the ability to > stack-allocate objects that refer to the heap. We cannot do that now, but > it is an important planned CG improvement. > > On Fri, Apr 8, 2016 at 11:28 AM, Scott Jones <[email protected]> > wrote: > >> I like very much the idea of a discriminated union - that would help >> enormously with some of the stuff I work on. >> >> >> On Friday, April 8, 2016 at 8:47:59 AM UTC-4, Erik Schnetter 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]> 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]> >>> http://www.perimeterinstitute.ca/personal/eschnetter/ >>> >> > -- Laurent Bartholdi DMA, École Normale Supérieure, 45 rue d'Ulm, 75005 Paris. +33 14432 2060 Mathematisches Institut, Universität Göttingen, Bunsenstrasse 3-5, D-37073 Göttingen. +49 551 39 7826
