abs behavior incorrect/not documented correctly

[gajjanag]

Currently (at least on 0.3.11, have checked master docs but not implementation), abs does not behave in a mathematically correct manner: abs(typemin(Int)) == typemin(Int) on my Linux x86-64 machine.

This problem plagues the C standard library abs(), llabs(), etc as well due to subtle asymmetry in 2's complement arithmetic. The C standard leaves behavior on INT_MIN, etc undefined, and this is fortunately documented, though easily missed by many programs.

I thus see 2 possible approaches:

1. Follow the C standard behavior, give no guarantee for abs(typemin), and document it.
2. Do something special with typemin, and document it.

[jiahao]

Duplicate of #5796 - we decided not to special case typemin.

Agreed that typemin is a special case worth documenting. Would you be willing to open a pull request updating the docs?

[gajjanag]

I have tried contributing to Julia in the past, and the pain (build failures, configuration issues, buggy packages, etc) has been too much of a barrier to me. I could write more on this topic, but I think http://danluu.com/julialang/ summarizes the state very well. I may do this within a few months, but since the fix is trivial, it may be easier for a regular contributor to do it before then.

[simonbyrne]

Sorry that you've experienced trouble with such things. The incredibly large scope of Julia, and all the platforms that it tries to support (multiple OSes, 32/64 bit/ARM, lots of dependencies), coupled with the fact that it is under active development mean that things are bound to break occasionally (though hopefully only on the master branch). But please do open issues if you experience such problems.

[nalimilan]

Build failures have been pretty rare for quite a long time here. Anyway, you can make a PR to change the docs without even building Julia (actually, you can even make it from GitHub, though somebody will have to run a script afterwards).

[MichaeLeroy]

Probably the best place to document this behavior is in the Overflow behavior subsection of the manual. I had planned to draft something up and show it here, giving @gajjanag a fair opportunity to make the pull request prior to doing so myself. However, I found a wrinkle that may merit some further discussion and a decision before proceeding with this change.

EDIT--I've withdrawn this thought, feel free to ignore the following:

The wrinkle is documented in the next subsection, Division errors. Namely that integer division of typemin(Int) by -1, throws a DivideError. Indeed:

julia> x = typemin(Int)
-9223372036854775808

julia> div(x, -1)
ERROR: DivideError: integer division error
 in div at ./int.jl:79

julia> -x
-9223372036854775808

julia> abs(x)
-9223372036854775808

It strikes me as inconsistent to have -x yield a definite result whereas div(x, -1) results in an error. And I felt rather silly at the prospect of adding text to the manual to indicate that, in effect,
-typemin(Int) === typemin(Int)
and this is good, only to have the manual say in the next paragraph that
div(typemin(Int), -1)
is erroneous.

I suggest that div be fixed so that
div(typemin(Int), -1) == typemin(Int)
and that the documentation be updated accordingly along with the update to describe abs(typemin(Int)).

I've made a first attempt to do this myself but didn't quite make it. And I thought it wise to bring this point up for consideration before putting too much work into a change that may not be well received.

Here is what I've done so far. It looked to me as if the div(typemin(Int), -1) exception is thrown by some explicit code in intrinsics.cpp. I tried eliminating the clause that I thought throws the division by -1 exception:

        t = den->getType();
        raise_exception_unless(builder.CreateICmpNE(den, ConstantInt::get(t,0)),
                               prepare_global(jldiverr_var), ctx);
        return builder.CreateUDiv(JL_INT(x), den);

After building with this change, I had hoped to see:

julia> div(typemin(Int), -1)
-9223372036854775808

However, I still get the DivideError. Perhaps, I've failed to build properly, traced back the the wrong function, or have misread the code. I'll give it further thought. Meanwhile, any suggestions, advice or opinions are welcome.

[gajjanag]

I noticed another issue: overflow errors with abs, etc can propagate. For instance, the gcd function can trigger the behavior as it calls abs. This is not documented, and documenting just abs is insufficient: a client of gcd can't (and should not) expect to read abs to learn about gcd's overflow behavior.

Thus, this issue is not at all a simple one, and a clean solution goes well beyond my level of expertise or energy for this. I hence defer it to others interested in this. Maybe as a start, the label on this can be changed: I doubt this issue is an "intro issue" anymore, since it requires significant work to fully and cleanly address.

[MichaeLeroy]

@gajjanag so far I've seen nothing that can't be grasped by understanding the policy that Julia's integer arithmetic is modular and that certain operations promote their types. I'm satisfied that this policy represents an appropriate balance between performance and safety.

Prompted by your comment on gcd, I attempted to find a situation where that function behaves pathologically. From the few tests that I performed, It seems OK:

julia> gcd(typemin(Int), 6)
2

julia> gcd(typemin(Int), 291)
1

julia> gcd(typemin(Int), typemin(Int))
-9223372036854775808

Can you provide a specific example of problematic gcd behavior not covered by the "integer arithmetic is modular" policy? I'm always curious about the limitations of my tools.

I'd rather see div(typemin(Int), -1) == typemin(Int). Sure a decision on and implementation of this is not an Intro issue, but I'm trying to implement this behavior for the sake of learning. At worst, I play around a bit and at the end of the day have do a git reset --hard to my copy of Master, having learned at least something but failing to contribute much.

[gajjanag]

@MichaeLeroy sorry for not being clear enough. Per the docs, gcd always returns "Greatest common (positive) divisor (or zero if x and y are both zero)." This is clearly being violated by your third example. It is fundamentally due to the fact that abs(typemin(Int)) == typemin(Int).

[MichaeLeroy]

@gajjanag I'd put that third example into the category of proper modular arithmetic, so it is not a violation of the "integer arithmetic is modular arithmetic" policy, and it has exactly the right value. I think that we both agree that gcd(x, x) is abs(x) so if one accepts that abs(typemin(Int)) == typemin(Int) the third example is OK. I'm comfortable with this situation.

[gajjanag]

@MichaeLeroy I don't agree, simply because of your documentation claiming it is positive, which is clearly incorrect above. If you claim it is abs(x), it needs to be documented. For me it is very clear and simple: a function's behavior needs to be documented correctly and concisely with no "edge cases" missing out. I am thus not comfortable with this situation, but I won't fix it myself.

Personally, I don't mind a gcd that gave a value that is either positive or negative. But whatever solution gets adopted, it must be documented correctly.

[MichaeLeroy]

I withdraw my suggestion that div(typemin(Int), -1) be fixed to yield typemin(Int) rather than throwing a DivideError. It looks as if there may be a practical problem to discarding the exception for this condition for sdiv_int in intrinsics.cpp. I called my modified sdiv_int directly and got apparently nonsensical results:

julia> Base.sdiv_int(typemin(Int), -1)
140388018659888

So there may be good reason to keep the current behavior of div even though it is slightly at odds with the concept that in Julia integer arithmetic is modular.

[MichaeLeroy]

@gajjanag I'm sorry if I gave the wrong impression. I'm not arguing that the documentation can't or shouldn't be improved on this point. I'm merely saying that I think that it is perfectly reasonable that abs(typemin(Int)) yields typemin(Int) (because abs(typemin(Int)) == typemax(Int) + 1).

Please do have a go at modifying the manual and generating a pull request. I'll refrain from any such action for a decent interval to give you the first crack at closing this issue.

My opinion is that it is sufficient to clarify and amplify the Overflow behavior subsection and that we need not add notes to each of the math functions that like gcd and affected by this behavior. But you should do as you see fit.

[MichaeLeroy]

@gajjanag Have you read the manual's FAQ on Integer Arithmetic? There is a great deal of helpful information there on the rationale for and consequences of making integer arithmetic modular arithmetic. From my perspective, referencing this FAQ entry in the Overflow behavior is a good way to resolve this issue.

[gajjanag]

@MichaeLeroy: I read it, and although it is a great entry, it is by no means sufficient in terms of documentation. For instance, it is not at all clear why gcd needs to behave absurdly exactly on typemin(T) as one of the inputs, other 0, or both typemin(T) etc (I may even have missed some even after a single look at the code). How can a client of gcd expect to get that information from the FAQ entry? The only way he/she or other code can get such information is by digging into the source code currently. This is why I say the problem is not a simple one.

All the FAQ does is a "general caveat". It tells nothing about specific functions and where they can trigger weird, unexpected behavior.

[timholy]

Matlab:

>> x = int64(-9223372036854775808)

x =

 -9223372036854775808

>> class(x)

ans =

int64

>> abs(x)

ans =

  9223372036854775807

>> -abs(x) == x

ans =

     0

>> abs(x) == -x

ans =

     1

>> help abs
 ABS    Absolute value.
    ABS(X) is the absolute value of the elements of X. When
    X is complex, ABS(X) is the complex modulus (magnitude) of
    the elements of X.

    See also SIGN, ANGLE, UNWRAP, HYPOT.

    Other functions named abs:
       duration/abs
       sym/abs

No documentation explaining what, mathematically speaking, is clearly a confusing situation.

@gajjanag, I think this is the kind of situation where it's either incumbent upon you to contribute a resolution, or to learn to live with the fact that numbers are represented with bits that are only approximations of mathematical objects and that these corner cases are just going to be weird one way or another.

[StefanKarpinski]

Yikes, that Matlab behavior is bananas. Having abs(typemin(Int)) == typemin(Int) is weird but at least it's internally consistent. Once again, modular integer arithmetic for integers seems to be a much better choice than saturating arithmetic since at least there's a ring homomorphism from ℤ to ℤ/2⁶⁴ℤ.

[MichaeLeroy]

@gajjanag I certainly appreciate your position and see the value of having documentation that is exacting in calling out dangerous edge case behavior. However, exhaustively calling out edge cases on all functions may be impractical (perhaps impossible). Also a manual where each function's documentation is loaded down with caveats or tabulations of failure call-outs would arguably be quite user hostile, more confusing, and difficult to maintain than the current situation. Perhaps, I'm being unfair, making a straw man of your point. If so, could you set me right in my understanding?

[StefanKarpinski]

I think this is worth mentioning in the documentation of abs.

[timholy]

Or perhaps linking to a longer explanation about overflow and corner cases. Explaining this properly isn't exactly short, and I'd hate for the important stuff to get overwhelmed by material needed to explain what is literally one case out of 2^64.

[MichaeLeroy]

I like the idea of addressing some of the general documentation weaknesses that @gajjanag has called out. But I'd like to do so in a manner that is readable, practical and maintainable. It seems to me that the best place to do so is in the code, using the new Documentation facilities. If so, perhaps the thing to do is to close this issue with general improvements to the manual's documentation of integer overflow issues and to generate as a separate issue or strategy for the improvement of Julia function documentation. (Perhaps such a policy exists, I'm very new in my Julia development efforts and haven't yet read myself in on all of the development manuals.)

The FAQ Entry does a great job of explaining why Julia uses modular integer arithmetic. As @timholy suggests, a more detailed discussion of the consequences of this behavior may be in order. Does it make sense to make this discussion a separate FAQ entry rather than messing around with an already well written section on the rationale? @gajjanag I imagine that you'd not be completely satisfied with such a solution, but are you interested writing/collaborating on such a FAQ entry. I may be too comfortable with the integer arithmetic is modular situation to do a great job of explaining its pitfalls.

[gajjanag]

I think it may help if I explain where I am coming from, and how I found this out. I mostly work with C, where such integer overflow issues are often undefined behavior. There, these things can be security vulnerabilities, e.g if the abs() return is then used in some arithmetic to index a buffer. As such, I am quite paranoid about these things, and highly appreciate the fact that man abs on my system gives me this caveat, which is easily missed: after all it is a classic off by one and is an artifact of the standard two's complement behavior. I have been involved with FFmpeg lately on fixing and improving their gcd function, auditing abs usage (and replacing judiciously with a "negative abs" which is always safe), etc.

I currently do not actively use Julia, but have done so in the past and may do so again in the future. I highly appreciate the Julia project, and am interested in helping out by pointing out these things as possible improvements. As for the exact solution, due to my current lack of investment in Julia, and my general lack of time for these things, I am afraid I can't be of much use.

I see good ideas on this thread, and @MichaeLeroy above in particular has a solution that although not ideal in my view, is a very solid first step.

[StefanKarpinski]

Since we check that array accesses are within bounds, this is not nearly such a problem in Julia.

[MichaeLeroy]

@gajjanag thanks for your input and also for providing the background that you bring to this issue. BTW, I imagine that any improvements that you might be able to bring to Julia's gcd would be received with interest. For example, an improved gcd might help with issue #11522.

This issue and #12989 point to seemingly contradictory missions for Julia's documentation. On the one hand to layout all of the gory details, caveats and limitations of an object and on the other to provide a very compact hint as to what this object is. Ideally the documentation can be structured to make it suitable for either purpose (and others besides). That's the point that I was getting at when I suggested that there ought to be a strategy for Julia's documentation. I'm not claiming that there is no such strategy, I've only just begun to learn the documentation system in the hope of seeing this strategy or of contributing to its development if the Julia community agrees that having such documentation is a good idea.

Based on what's been said here, I'll take a crack at writing a FAQ section on integer overflow to supplement the existing one on why integer arithmetic is modular. I'll provide links to these FAQ sections in basic numbers section of the manual. I'll also suggest an update to the in-code documentation for abs, warning of its surprising behavior for typemin(T<:Signed). This may take me some time, but I'll try to get out PRs within a week. Meanwhile if someone else feels like jumping on this problem, go for it. I'm not possessive of issues.

[tkelman]

Sounds great @MichaeLeroy, thanks in advance.

[ScottPJones]

There are checked_add, checked_sub etc. functions to handle this sort of case, why not a checked_abs?

[StefanKarpinski]

+1 to checked_abs

On Thursday, October 29, 2015, Scott P. Jones [email protected]
wrote:

There are checked_add, checked_sub etc. functions to handle this sort of
case, why not a checked_abs?

—
Reply to this email directly or view it on GitHub
#13549 (comment).

[MichaeLeroy]

+1 to checked_abs as well. Thanks @ScottPJones for pointing out the availability of these overflow trapped functions. I'll mention them in the integer overflow FAQ entry that I've agreed to write. It is nice to know that such functions are available, but I hope that their use is quite rare and carefully considered.

[MichaeLeroy]

I made an attempt at a checked_abs implementation and, crudely I'm afraid, checked its performance;

julia> function checked_abs{T<:Signed}(x::T)
           x == typemin(T) && throw(OverflowError())
           abs(x)
       end
checked_abs (generic function with 1 method)

julia> checked_abs(typemin(Int))
ERROR: OverflowError()
 in checked_abs at none:2

julia> @time (for i in 1:10^7; abs(rand(-10^8:10^8)) end)
  0.422180 seconds

julia> @time (for i in 1:10^7; abs(rand(-10^8:10^8)) end)
  0.496745 seconds

julia> @time (for i in 1:10^7; checked_abs(rand(-10^8:10^8)) end)
  0.495338 seconds

julia> @time (for i in 1:10^7; checked_abs(rand(-10^8:10^8)) end)
  0.506031 seconds

I'm concerned that this test is dominated by data generation rather than the calls to abs/checked_abs. I suspect that better testing is needed to properly characterize the performance penalty imposed by checked_abs. Suggestions?

If I hear no objections or advice to the contrary, I'll add this implementation of checked_abs to the PR that I'm working on to provide in-code documentation of abs overflow behavior. I'm rather new to the Julia development business, so I'm a bit slow yet on the mechanics of github, and this work may take more time than I'd like.

[ScottPJones]

for benchmarking, I think it works better to put all the looping and the function into a function, and you may need to take care to pull out a value, so that it isn't all optimized away.
Also, I think here you might just be testing the performance of rand().

[MichaeLeroy]

@ScottPJones thanks for your advice on benchmarking, it certainly helped me to get to more reasonable tests. I did have to play around to get something that worked, examining @code_native outputs to avoid the optimization while trying to minimize overhead.

function abstester{T<:Signed}(n::T)
    s = zero(T)
    for i in -n:n
        s = abs(i)
    end
    s
end

function cabstester{T<:Signed}(n::T)
    s = zero(T)
    for i in -n:n
        s = checked_abs(i)
    end
    s
end

julia> @time abstester(10^7);
  0.016153 seconds (6 allocations: 192 bytes)

julia> @time abstester(10^7);
  0.014489 seconds (6 allocations: 192 bytes)

julia> @time abstester(10^7);
  0.016904 seconds (6 allocations: 192 bytes)

julia> @time cabstester(10^7);
  0.028860 seconds (6 allocations: 192 bytes)

julia> @time cabstester(10^7);
  0.030721 seconds (6 allocations: 192 bytes)

julia> @time cabstester(10^7);
  0.031251 seconds (6 allocations: 192 bytes)

So there is a significant if not brutal penalty to using checked_abs versus abs.

[ScottPJones]

Thanks! Personally, if you need checked arithmetic (which I may), that penalty does not look so bad, and I'm sure can be improved on later - the important thing is you can submit a PR with that function (and we'll pray TPTB will bless it 😄 ) Good Job! 👍

[MichaeLeroy]

@ScottPJones I appreciate your help and encouragement. Real life intrudes, so I can't get the PR done right now, but I'll give it a shot the next time I have a bit of time.

[StefanKarpinski]

It's very hard to make something that might raise an exception as fast as a few integer ops, so I wouldn't hold out much hope for making this that much faster.

[tkelman]

Is #13841 sufficient to close this?

[MichaeLeroy]

In addition to #13841, I've committed to writing a FAQ entry on Integer overflow to complement the already existing entry on native arithmetic. The focus on the new entry will be on how to cope with integer arithmetic. I hope to get this done by the end of the week. I'm more than happy to hear suggestions about what should be included in this entry, and this thread may be a good place for that to happen. But if it makes sense instead to close the issue and open a fresh one focused on this task, that would work for me as well.

I'll try to seed/provoke some discussion around this FAQ entry by commenting with a simple outline in the next day or so. I'm hardly an expert on the topic, which doesn't deter me but does make me somewhat cautious, interested in advice, and open to correction.

[StefanKarpinski]

Sounds like a great contribution. I look forward to reading it!

[MichaeLeroy]

My work to provide an additional overflow FAQ entry is dragging on a bit, mostly because I had to put in some study to avoid too many ignorant pronouncements. I've gotten a basic grasp of the issue (I hope) and created an overflow_research repository to facilitate work on a draft (which is the README there).

The draft is getting somewhat beyond the outline stage. Feel free to have a look and comment here regarding suggestions, complaints, criticisms, or exposes of my ignorance. In broad outline, the questions are addressed are:

• Why Does Julia Wrap on Integer Overflow, Isn't that a Problem? (the overall question)
• Isn't Wrapping Dangerous (learning from C)? (In C yes, but not so much in Julia)
• What are the Advantages of Wrapped Overflow? (performance, especially ease of optimization)
• How Can One Cope with Wrapped Overflow? (intrinsics, testing and documentation, gotchas)
• Are there any Alternatives to Simple Trap or Wrap? (yes but perhaps inappropriate for a FAQ)
• Some references I've used (informal at this point)

I'll be off the grid for much of this weekend and otherwise engaged early next week. So don't be shocked if I fail to respond promptly to any comments or if development on this stalls until the middle of next week.

[goelakash]

This issue could be closed now I think.