# Tonight I hated julia, REPL and overflows

**URL:** <https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884>\
**Category:** New to Julia\
**Tags:** integer-overflow\
**Created:** [February 20, 2020, 2:10am UTC](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884 "2020-02-20T02:10:21Z")\
**Posts on this page:** 20\
**Page:** 3

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [February 23, 2020, 12:17am UTC](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884/41 "2020-02-23T00:17:18Z")

</div>

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

```julia
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

```

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [February 23, 2020, 12:21am UTC](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884/42 "2020-02-23T00:21:12Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [February 23, 2020, 12:24am UTC](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884/43 "2020-02-23T00:24:44Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [February 23, 2020, 12:43am UTC](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884/44 "2020-02-23T00:43:26Z")

</div>

Errrr, a complicated expression is multiple expressions.

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [February 23, 2020, 12:47am UTC](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884/45 "2020-02-23T00:47:09Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [February 23, 2020, 12:52am UTC](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884/46 "2020-02-23T00:52:54Z")

</div>

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…

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [February 23, 2020, 1:47am UTC](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884/47 "2020-02-23T01:47:44Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [February 23, 2020, 9:29am UTC](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884/48 "2020-02-23T09:29:04Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [February 23, 2020, 10:07am UTC](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884/49 "2020-02-23T10:07:18Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![rfourquet](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rfourquet/32/3610_2.png) [@rfourquet](https://discourse.julialang.org/u/rfourquet)\
**Post date:** [February 23, 2020, 10:56am UTC](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884/50 "2020-02-23T10:56:14Z")

</div>

> [@Tamas\_Papp](#):
>
> It would be great if someone who has a need for this would create a package for this kind of approach as an experiment.

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`.

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [February 23, 2020, 1:16pm UTC](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884/51 "2020-02-23T13:16:28Z")

</div>

No not for each operation, for the whole complex expression.

---

<div class="post-metadata">

**Author:** ![abulak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abulak/32/28314_2.png) [@abulak](https://discourse.julialang.org/u/abulak)\
**Post date:** [February 23, 2020, 2:11pm UTC](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884/52 "2020-02-23T14:11:51Z")

</div>

this situation actually begs for a julian `Flint.jl` which everybody would benefit from.  
But I’m not going to open this can of worms 😉

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [February 23, 2020, 5:00pm UTC](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884/53 "2020-02-23T17:00:25Z")

</div>

Indeed, (after 2 definitions which seem missing in Nemo):

```julia
julia> Base.one(::Type{fmpq})=fmpq(1)
julia> Base.:/(a::fmpq,b::fmpq)=a//b
julia> @btime test_hm(Nemo.fmpz,45)
  79.831 ms (466004 allocations: 15.86 MiB)
true

```

which is 10 times faster than `BigInt`!

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [February 24, 2020, 7:01pm UTC](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884/54 "2020-02-24T19:01:27Z")

</div>

> [@Tamas\_Papp](#):
>
> 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.

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

```julia
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:

```julia
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`:

```julia
nums = (1:10...,) 
xs = rand(nums, 1000) 
ys = rand(nums, 1000) 

julia> bench(xs, ys)
 Int mul: 525.717 ns (1 allocation: 7.94 KiB)
 SomeTimesBig mul: 16.719 μs (1001 allocations: 23.56 KiB)
 BigInt mul: 113.401 μs (3001 allocations: 54.81 KiB)

```

and if we give it a 100% chance of overflowing, we see how much better off we would have been if we’d just used `BigInt` in the first place:

```julia
nums = ((10^10 .+ (1:10))...,) 
xs = rand(nums, 1000) 
ys = rand(nums, 1000) 

julia> bench(xs, ys)
 Int mul: 520.681 ns (1 allocation: 7.94 KiB)
 SomeTimesBig mul: 272.308 μs (9001 allocations: 164.19 KiB)
 BigInt mul: 116.686 μs (3001 allocations: 54.81 KiB)

```

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.

---

<div class="post-metadata">

**Author:** ![ScottPJones](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/scottpjones/32/146_2.png) [@ScottPJones](https://discourse.julialang.org/u/ScottPJones)\
**Post date:** [March 5, 2020, 6:26pm UTC](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884/55 "2020-03-05T18:26:03Z")

</div>

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)).

---

<div class="post-metadata">

**Author:** ![ScottPJones](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/scottpjones/32/146_2.png) [@ScottPJones](https://discourse.julialang.org/u/ScottPJones)\
**Post date:** [March 6, 2020, 1:55pm UTC](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884/56 "2020-03-06T13:55:09Z")

</div>

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)

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [March 6, 2020, 6:22pm UTC](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884/57 "2020-03-06T18:22:19Z")

</div>

Could you test the following code (inverting a Hilbert matrix)

```julia
function test_hm(rtype,rank)
  m=[rtype(1)//(n+m) for n in 1:rank, m in 1:rank]
  one(m)==m*inv(m)
end

```

For `rank=45` and `rtype=yourtype` (you need enough definitions so that `Rationals{yourtype}` work but that should be mostly automatic).

The best I got so far is the type `fmpz` of `Nemo`, which is 10 times faster than `rtype=BigInt`.

---

<div class="post-metadata">

**Author:** ![ScottPJones](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/scottpjones/32/146_2.png) [@ScottPJones](https://discourse.julialang.org/u/ScottPJones)\
**Post date:** [March 8, 2020, 2:07pm UTC](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884/58 "2020-03-08T14:07:09Z")

</div>

> [@Jean\_Michel](#):
>
> function test\_hm(rtype,rank) m=[rtype(1)//(n+m) for n in 1:rank, m in 1:rank] one(m)==m\*inv(m) end

I couldn’t get that to work, either with my type or yours - it gets the following error when I try it:

```julia
test_hm(SBig
ERROR: LoadError: OverflowError: 129997293855212511 * 3483 overflowed for type Int64
Stacktrace:
 [1] throw_overflowerr_binaryop(::Symbol, ::Int64, ::Int64) at ./checked.jl:154
 [2] checked_mul at ./checked.jl:288 [inlined]
 [3] - at ./rational.jl:264 [inlined]
 [4] generic_lufact!(::Array{Rational{Int64},2}, ::Val{true}; check::Bool) at /Users/scott/j/

```

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [March 9, 2020, 10:58am UTC](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884/59 "2020-03-09T10:58:21Z")

</div>

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

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

```

If you show your code I could try to debug it…

---

<div class="post-metadata">

**Author:** ![simeonschaub](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/simeonschaub/32/216566_2.png) [@simeonschaub](https://discourse.julialang.org/u/simeonschaub)\
**Post date:** [March 9, 2020, 11:15am UTC](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884/60 "2020-03-09T11:15:35Z")

</div>

I think you need to explicitely overload `Base.checked_mul` for this to work.

[Previous page](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884.md?page=2)

[Next page](https://discourse.julialang.org/t/tonight-i-hated-julia-repl-and-overflows/34884.md?page=4)
