[RFC] What is the integer overflow story in Julia?

[LilithHafner]

For simple operations (e.g. +, *, -) we do modular arithmetic and do not warn on overflow.
For complex operations, we sometimes check for intermediate overflow (lcm, getindex, binomial) and sometimes do not, (isapprox, lcm)

I'd like a clear, documented, policy of when we let overflow happen, when we throw, and when we make sure to avoid it with widen or similar.

The first step is to come up with the policy. Current documentation is quite limited. Ideas?

[stevengj]

See also #21600.

[JeffreySarnoff]

Regarding a policy for the treatment of integer overflow.

It is easier to make the case for treating unsigned bitstypes as modular values (permitting operations to wraparound either way) than to make a compelling case for treating signed bitstypes as modular values. Many uses of unsigned bitstypes are designed with a reliance on the presence of unchecked wraparound.

It is rare to design an algorithm that requires unchecked wraparound for signed bitstypes. The only common rationale for allowing signed bitstypes to wrap (over or under) is that provides accelerated throughput and the associated simplification of instruction flow is easier to optimize.

Integer Wraparound is #14 on the 2023 CWE list of Top 25 Most Dangerous Software Weaknesses

CWE™ is a community-developed list of software and hardware weakness types. It serves as a common language, a measuring stick for security tools, and as a baseline for weakness identification, mitigation, and prevention efforts.
(The Mitre Corporation underwrites CWE™)

[nhz2]

I think of Int64 as the 64 least significant bits of a hypothetical BigInt sign extended.

Therefore, I believe the following equality should hold for all basic integer operations, or they should
throw an error or have some warning in their docstring.

op(x::Int64, y::Int64) == op(big(x), big(y)) % Int64

For example, one case where the above equality doesn't work is with ^:

1 ^ -2 == 1.0
Int64(1) ^ Int64(-2) == 1
big(1) ^ big(-2) throws a DomainError.

But I guess this is okay because the docstring for ^ says it has special behavior when using Int literals.

Though I'm not sure why big(1) ^ big(-2) errors here.

[PallHaraldsson]

one case where the above equality doesn't work is with ^:

1 ^ -2 == 1.0
Int64(1) ^ Int64(-2) == 1

That's because arguably Integer ^ Integer should in general be Float64 (if not Rational), one of few flaws in Julia (only exception when b of a ^ b is Unsigned, then I can argue for the status quo), for the same reason Integer / Integer is Float64 (the fast approximation of Rational), which is a good decision.

Such a decision would have averted overflows or (costly software) checks (and is only done at parser time for constants), and I would like to see it changed for Julia 2.0 (see other issue on it, and what can be done for 1.x, let's not discuss this here). Insisting on Int result (for Signed b), is arguably faulty math, and I don't think many would rely on that very much. Then we wouldn't need to warn:

tonyhffong/Lint.jl#271

This is one reason I want 2.0, to break (but in a good way), this integer result, most or all would be better off, I don't think ^ is very much used anyway for integers except for Unsigned in number theory and wouldn't be affected.

big(1) ^ big(-2) throws a DomainError.

Since negative power gives a fraction, in general not an integer, why you should do (and only the above for positive power):

julia> BigFloat(1) ^ BigFloat(-2)
1.0

It is easier to make the case for treating unsigned bitstypes as modular values

Right. And since you need to opt into them, work harder, I would supported them not checking for overflows. For (Signed) Integer you could actually have avoided any possibility of overflows, and thus checks. If just e.g. Int32 * Int32 -> Int64 (fast; no checks) and Int64 * Int64 -> Int128 (not as fast, nor for subsequent math, why I would prefer Int32 the default in Julia, also on 64-bit platforms...).

[nhz2]

That makes sense for Julia 2.0, but in general, BigInt should be better supported. Almost every math function that works with Int inputs should work with BigInt inputs. This is definitely not the case now, so when I try and switch from Int to BigInt to avoid overflow, I typically end up getting a bunch of other errors.

[adienes]

I would say basically only arithmetic or bit-twiddling operators should allow unchecked overflow; all other functions should check internally when there is danger

[adienes]

probably to the annoyance of viewers of the issue tracker, I've been finding & attempting to fix several bugs related to internal overflow lately, and here's my latest idea for an extremely minimal documented policy:

suppose there is some function foo: T -> T so for simplicity just say T is some integral domain and foo is type stable. and say it has some potential for overflow

function foo(input)
    intermediate = bar(input)
    return final(intermediate)
end

and the "correct" behavior is described in the documentation of foo by some statement F. there may be some inputs x where due to internal overflow, it is difficult or cumbersome or simply not possible to make foo(x) == F(x). I propose:

• documentation is mandatory if foo(x) != F(x) without error.
• throwing an OverflowError or falling back to a slower implementation is always allowed
• if foo(x) != F(x) without a specific note in the docs for foo, that is considered a bug
• type stability should generally be assumed, so if foo chooses to widen as its "slow fallback" this should be documented

I think this is actually pretty close to empirical status quo, since it allows for many judgement calls about when to error vs be slow vs just return the wrong thing. but what it changes is when the wrong thing can be returned this must be documented. All arithmetic operations already have such a warning in the documentation, and I don't think there are actually all that many more functions that intentionally behave this way (although there are some)

applying the example to some open issues / PRs:

• clear up several more inconsistencies among gcd , gcdx and invmod #59678 gcd family chooses Error (not always OverflowError, but close enough) so no documentation needed
• nextpow(2, x) is incorrect for large numbers #45880 (comment) nextpow2 needs to be fast, so it wants license to return the wrong thing. this is fine but must be documented
• DateTime arithmetic should not have wraparound behavior #50930 DateTime should choose one of slow fallback or error, as it's rarely performance critical

if there is support for this policy I'm happy to make a PR to the docs. obviously it doesn't even address when to widen vs error vs documentation hazard sign, and I don't know if there really can be a unified / consistent / generic policy for that since it's so context-dependent, but I think this is at least better than nothing.

[LilithHafner]

In the case where foo(x) != F(x), I see a distinction based on weather F(x) is representable as an object of type T. If it is, then we should strongly prefer to return F(x) and anything else is a bug (or should be documented, therefore redefining F). In the case where F(x) is not representable (e.g. *(::Int, ::Int)), returning F(x)%T for bit integer types is very standard and may warrant a mention but not a warning in each docstring.

TL;DR Overflow in internals is distinctly worse than rounding/truncating/coercing the final result to fit into a type stable return type.