I did a quick test of Int256. In this test it is slower that BigInt, probably because of divisions…

function test_hm(rtype,rank)
hm(rank)=[rtype(1)//(n+m) for n in 1:rank, m in 1:rank]
m=hm(rank)
one(m)==m*inv(m)
end
julia> @btime test_hm(Int256,45)
3.213 s (56720623 allocations: 1.12 GiB)
true
julia> @btime test_hm(BigInt,45)
703.989 ms (10933914 allocations: 210.82 MiB)
true

And that’s not what I was saying. 30 out of 10^9 doesn’t matter. The question is how many expressions in your code overflows. Only repeated calculation that can overflow matters.

Well, actually, it is a single one (complicated) expression which overflows (about 30 times in 10^9).
The values of the variables in the expression are different each time and I cannot predict which values
will make the expression overflow.

And in any case, what’s special about typemax(Int128) in your calculations for it to be a effective upper bound of those numbers or what’s the distribution of the numbers involved.

2^128 is just the largest number for which integer arithmetic is fast. The majority of numbers (perhaps 99%) actually fit in Int32. Perhaps 1% do not fit in Int32, and 0.001% do not fit in Int64. This kind of Poisson law is typical of what happens in my computations…

If this kind of distribution is what you have then it’s better to just detect the error and redo the ones with higher precision. In this case you still pretty much want to optimize only for the cases that fits instead of trying to make every operation safe and slower.

detect the error and redo with higher precision is exactly what the union type we are discussing can do automatically for you, saving you a lot of difficult programming

It would be great if someone who has a need for this would create a package for this kind of approach as an experiment.

Obviously there would be a performance penalty compared to Int, but I am not sure how big that would be with modern CPUs if the BigInt branch is actually rarely taken. It may just be a tolerable trade-off for some applications, especially compared to always using BigInt, but we won’t know until it is tried.

Look at the Nemo package, Nemo.fmpz is a wrapper over flint big integers, which uses GMP for actual big numbers, but otherwise stores an small integer inline. Unfortunately Nemo.fmpz is not currently a subtype of Integer, so this can limit its applicability as a replacement for BigInt.

Here’s a naïve proof of concept that someone might be interested in fleshing out (I’m only implementing multiplication here):

using Base: mul_with_overflow
struct SometimesBigInt
value::Union{Int, Base.RefValue{BigInt}}
end
SometimesBigInt(x::BigInt) = SometimesBigInt(Ref(x))
function Base.show(io::IO, x::SometimesBigInt)
print(io, "SometimesBigInt(", value(x), ")")
end
function value(x::SometimesBigInt)::Union{Int, BigInt}
x.value[]
end
function Base.:(*)(x::SometimesBigInt, y::SometimesBigInt)
xv, yv = value(x), value(y)
if xv isa Int && yv isa Int
zv, overflowed = mul_with_overflow(xv, yv)
if overflowed
zv = big(xv) * big(yv)
end
else
zv = xv * yv
end
SometimesBigInt(zv)
end

Okay, now let’s benchmark multiplication in the case where we have a 1% chance of overflow:

nums = (1:9..., 10^10)
xs = rand(nums, 1000) # 10% chance of getting 10^10
ys = rand(nums, 1000)
# for any element of xs .* ys we have 1% chance of overflow
function bench(xs, ys)
sbigxs = SometimesBigInt.(xs)
sbigys = SometimesBigInt.(ys)
bigxs = big.(xs)
bigys = big.(ys)
print("Int mul: ")
@btime $xs .* $ys
print("SomeTimesBig mul: ")
@btime $sbigxs .* $sbigys
print("BigInt mul: ")
@btime $bigxs .* $bigys
nothing
end
julia> bench(xs, ys)
Int mul: 515.380 ns (1 allocation: 7.94 KiB)
SomeTimesBig mul: 22.607 μs (1274 allocations: 27.97 KiB)
BigInt mul: 114.618 μs (3001 allocations: 54.81 KiB)

So we’re 42x slower than regular (overflowing) Int multiplication and 4x faster than making the entire array BigInt.

If we make it a 0% chance of overflow, we see the base overhead of SometimesBig relative to Int:

I think given these benchmarks, there’s a case to be made for this sort of approach.

It would be better for performance to only store an Int and a Bool flag telling you whether to interpret that Int as a number or a pointer to a bigint, (that way SometimesBigInt would be an isbits type), but I don’t know enough about protecting pointers from GC to do that.

I’ve been thinking the same thing for some years, for integers and for decimal floating point - one thing would be to not use BigInt, but rather a Vector allocated with Base.StringVector (i.e. low memory overhead, only sizeof(Ptr).
Currently, because there’s no way of having Julia’s GC look at a value and decide what type (of a union type) it is (for example, using the bottom bits of a pointer to determine what type of pointer, or a to store an integer, or several characters, in the upper bits), I think one way would be to have a struct with two parts, one a Int, and the other a String that is set to a known value if the Int needs to be used, otherwise the String can hold the vector of chunks of the big int (or decimal)).

I did a quick test of the approach I described, and it works out to be twice as fast as SomeTimesBigInt,
and only about a 12% penalty over using BigInt (instead of 2.34x)

It certainly works for the rtype=BigInt and rtype=fmpz (for the last one with the 2 additional definitions I give above). I thought the whole point of your type was to switch to BigInt when meeting overflow.
The error message suggests that you don’t handle an occuring overflow. Or perhaps you do not have the correct promotion rule. You should have

promote_type(yourtype, Int)=your_type
promote_type(yourtype,BigInt)=BigInt # yourtype would also do