integer arithmetic overflow

[StefanKarpinski]

To deal with integer arithmetic overflow we do the following:

1. add checked integer arithmetic intrinsics named checked_add, checked_mul, etc.
2. have a compiler switch that uses these everywhere.
3. write a @check_overflow macro that transforms an expression to turn * into checked_mul and + into checked_add, etc., but only in the expression — called functions are on their own.

[StefanKarpinski]

Note that by "compiler switch", I just mean a command-line option that choses between different sets of definitions for core integer arithmetic. Kind of awesome that that's all this takes to change the way core arithmetic works.

[timholy]

Is this still relevant, or does the commit fix it?

FYI, I recently added a "morebits" function to make it easier to write code that avoids integer multiplication overflow (used in nextprod and prevprod), not sure whether this was a good idea or not.

[pao]

The commit 54e40e3 appears to address (1), but not (2) or (3).

[ViralBShah]

There are also those who would prefer saturation arithmetic instead of overflow. At least that's what Matlab users get.

[ViralBShah]

Can we do this without a compiler switch? At the risk of code bloat, how about a SafeInt type?

[JeffBezanson]

There are multiple features here; the purpose of the switch is to instrument all code for debugging. If you know ahead of time that certain numbers or certain operations need to handle overflow somehow, then you want a separate mechanism for that.

[werediver]

Please, clarify whether the following behaviour is related to this issue or should be reported as a new one:

julia> 2^50, (2^50)*(2^50), 2^100
(1125899906842624,0,0)

But

julia> 1/0
Inf

It's rather confusing, isn't it?

julia> versioninfo()
Julia Version 0.2.1
Commit e44b593* (2014-02-11 06:30 UTC)
Platform Info:
  System: Windows (x86_64-w64-mingw32)
  WORD_SIZE: 64
  BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY)
  LAPACK: libopenblas
  LIBM: libopenlibm

Thanks.

[andreasnoack]

Int/Int isn't integer division. It promotes to floats, 1/1=1.0.

[mbauman]

That behavior is very much intentional and working as intended. Julia currently always uses native machine arithmetic. This issue is to allow some sort of command-line or compilation switch to change that behavior, but native arithmetic will almost certainly always be the default.

There's a very good explanation in the documentation on why Julia uses native machine integer arithmetic. It discusses this very clearly.

The behavior of 1/0 is orthogonal to this. Inf is infinity in a floating point representation, but 2^100 is not a floating point number; integer exponentiation always returns an integer.

[werediver]

@mbauman, thanks for your explanations. The FAQ is also great. Now I understand,the behavior is adequate.

[quinnj]

At JuliaCon, part of the presentation on Speed vs. Correctness discussed integer overflow and there were some interesting ideas thrown around such as:

# a @checked macro that would expose the LLVM overflow flag for an arithmetic operation
ans, flag = @checked 1 + 1

# alternatively, it could be used around a whole block of code that would indicated
# if *any* of the code in the block set the LLVM overflow flag
flag = @checked begin
  # lots of various
  # arithmetic operations here
end

[ScottPJones]

@Keno Where does that checked_mul live?
I'm interested in using a checked version of the arithmetic, because for certain financial and medical applications, I think doing unchecked arithmetic can be legally dangerous. That's also where decimal arithmetic is frequently necessary... correctness is much more important than raw speed.
(round(.70*.05*100) shows a very simple case where binary arithmetic can get you in trouble with the tax man...)

[PallHaraldsson]

@ScottPJones "I'm interested in using a checked version of the arithmetic, because for certain financial and medical applications, I think doing unchecked arithmetic can be legally dangerous."

This issue is only about integer overflows. Should be easy enough to do as a separate type (BigInt is also an option), that could be built out of regular integers (or even from below or binary floating point..):

See also:

https://github.com/stevengj/DecFP.jl

[Seems you have to call xchk to check for overflow to get it thrown. [I'm not sure, I think ordinary binary floating point may be similar.]]

This one is arbitrary precision.. so you wouldn't get overflows.. only possibly out-of-memory errors:
https://github.com/tinybike/Decimals.jl/blob/master/README.md

[johnmyleswhite]

@PallHaraldsson: Please do not comment on issues like this to offer your two cents. You are e-mailing dozens of people unnecessarily.

[eschnett]

I recently got bitten several times by accidental integer overflow. I implemented @fastmath in the past, and my first idea for implementing @checked would be along the same lines, throwing InexactError if things go wrong. Is this still a good idea?

My motivation is:

• Do something now, without waiting for efficient LLVM intrinsics
• Safety first, I'm willing to pay a speed penalty for this
• By default, don't change the current behaviour
• I don't want to rewrite code, so SafeInt etc. wouldn't work for me

[StefanKarpinski]

@eschnett, are you saying you want something dynamically scoped? I don't think we can do that right now because there are legitimate usages of overflow, e.g. the classic >>> midpoint trick see also http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html. Arguably, addition with intentional overflow should be a separate operator so that we can distinguish these cases.

[eschnett]

@StefanKarpinski No, I'm thinking of static scoping. The @checked macro would convert operations in its argument e.g. from * to checked_mul. This is how @fastmath is implemented -- I think that's different from @inbounds which sets a global codegen flag.

Over time, I can also imagine explicitly annotating all places where overflow is expected and harmless; this would then allow using a command-line option to switch over all of Julia.

[JeffBezanson]

What, if anything, should we do for 1.0 here? Seems like it can be moved out of the milestone.

[timholy]

Seems like some folks want a way to turn this on for all arithmetic operations, which formerly might have meant a new startup flag julia --check-overflow. But now that #265 is fixed, it theoretically seems like this could be solved which a package (and thus removed from the 1.0 milestone), though I note that

eval(Base, quote
     (+)(x::T, y::T) where {T<:BitInteger} = checked_add(x, y)
     end)

results in a StackOverflow due to the use of an increment in tuple iteration/destructuring. I suspect it could be resolved by having tuple iteration call an intrinsic directly, but that's just a guess. Clearly the package would have to be structured with care.

[StefanKarpinski]

What you really need to support this is a way to express that you really want to do overflowing arithmetic, e.g. in the classic (lo + hi) >>> 1 computation in binary search or quicksort. However, that seems like a feature that can be added post 1.0 as can a hypothetical --arithmetic-overflow=[wrap|error] option (or a package). It might be a good idea to turn checking on by default during testing like Rust does; that would entail carefully going through Base Julia and using intentionally wrapping overflow in the places where we mean it, of course.

[JeffBezanson]

Seems like we're unlikely to change the default behavior, and the rest of the ideas here can be new features, even in packages --- a @check_overflow macro, a wrapper type that provides checked arithmetic, a way to annotate operations expected to overflow, together with options for enabling checking everywhere else for testing.

[ronisbr]

Just one question:

How difficult / feasible / sensible is to implement the following:

Add a macro so that every integer operation that will overflow has their arguments promoted to a Integer representation with a higher bit number before execution?

So, if I am using in my code things like:

f = C1*Δt^2 + C2*Δt^3

where the user can pass a very big integer number to Δt, then I can add this safe measurement to avoid incorrect computations.

[StefanKarpinski]

It's easy but all your code will be very slow.

[mbauman]

There's a package that does the opposite — SaferIntegers.jl. It adds overflow checks and errors. It also has a macro to convert literals to "safe" integers that error on overflow (@safeints) — but its docstring is a little confusing since it hasn't been totally updated (it may be helpful to know that it is a modified version of https://github.com/stevengj/ChangePrecision.jl, so that's why there's stuff about floating point there).

[oscardssmith]

This seems closable.