Arithmetic overflow checking

[markspace]

AFAIK, mainstream hardware (e.g. x86-compatible) doesn't include special
overflow-checking instructions as you're describing. I agree it's

Er, x86 and i32/64 certainly does. I just happen to be browsing their
hardware architecture documents last weak.

Not a single instruction to AddWithTrap, but a it does have a global
state register, and a test/branch instrution, so you just pair up an ADD
followed by a JO (Jump if Overflow) and that's it. Two easy
instructions paired together, and it works the same for MUL and SUB too.
(DIV can't overflow; think about it).

 

[Gene Wirchenko]

On Thu, 07 Jul 2011 17:51:06 -0700, Peter Duniho

[snip]

I would not worry about the "simple" or "efficient" criteria. IMHO, if
one is deciding to apply overflow checking to every computation, one has
already abandoned the hope of efficiency.

Not necessarily. If a rocket ends up being destroyed as a
result, having the computing go a bit slower to save having to build
another rocket would have been more efficient. Unfortunately, this is
not a made-up example. See:
http://en.wikipedia.org/wiki/Ariane_5_Flight_501
In the subsequent investigation, the cause of the problem was
recreated.

Turn on those run-time checks unless speed *REALLY* is of
paramount importance. It usually is not.

[snip]

Sincerely,

Gene Wirchenko

 

[Gene Wirchenko]

[snip]

I think the problem is more a matter of software knowing when overflow
should and should not be treated as an error.

     Exactly.  C does not do that sort of checking, and the meme has
spread widely.  I would much prefer to have things blow up when wrong
than not blow up.  It makes for smaller messes.

the problem with that statement is that it's not wrong for Java
primitive integer types to wrap around.

Java is designed to behave that way. That does not mean that it
is not wrong.

A garrot is designed to be a murder weapon. That it was designed
for that does not make any murder committed with a garrot any less
wrong.

It is, in fact, wrong for them to throw an overflow exception, as many
have pointed out in this thread.

It is designed to behave like that. That behaviour is often
wrong from the point of view of ensuring program correctness.

C allows wraparound with unsigned (which I wish Java had)
integers. An overflow with signed integers results in undefined
behaviour. C's semantics are better than those of Java in this
regard. They should be better: throw an error.

Sincerely,

Gene Wrichenko

 

[lewbloch]

[snip]
I think the problem is more a matter of software knowing when overflow
should and should not be treated as an error.
     Exactly.  C does not do that sort of checking, and the meme has
spread widely.  I would much prefer to have things blow up when wrong
than not blow up.  It makes for smaller messes.

the problem with that statement is that it's not wrong for Java
primitive integer types to wrap around.

     Java is designed to behave that way.  That does not mean that it
is not wrong.

It doesn't mean that it is wrong.

In fact, it does mean that it's not wrong. If you're working in Java,
to do differently from what the Java spec requires is wrong.

As others have pointed out, there's an awful lot of code that depends
on the documented, required behavior. For that code, to have overflow
exceptions would be wrong, doubly so because it would violate the
rules under which the code was developed.

     A garrot is designed to be a murder weapon.  That it was designed
for that does not make any murder committed with a garrot any less
wrong.

A useless analogy that adds no insight to the question of overflow
exceptions. There is no evidence that wrapping around overflow is
equivalent to a murder weapon other than your fanciful rhetoric.

     It is designed to behave like that.  That behaviour is often
wrong from the point of view of ensuring program correctness.

Much more often, in Java, the behavior is right from the point of view
of ensuring program correctness, because Java programs are written
with the required behavior in mind.

     C allows wraparound with unsigned (which I wish Java had)
integers.  An overflow with signed integers results in undefined
behaviour.  C's semantics are better than those of Java in this
regard.  They should be better: throw an error.

"should" is pretty useless here - Java should do what it's documented
to do.

There are programmatic workarounds for preventing wraparound, and no
doubt there are errors that arise from the lack of overflow exception
trapping, just as there would be errors possible from its presence.
You have a personal preference to trap overflow exceptions, which you
like to present as an absolute rule for all programmers. that doesn't
make your personal preference better, just yours. You've offered no
objective evidence that your preference would be better for anyone
besides yourself; others here have offered evidence that to change
Java's behavior would cause more errors than your idea would fix.

I fully support your right to have a personal preference.

 

[rop rop]

the problem with that statement is that it's not wrong for Java
primitive integer types to wrap around.

It is, in fact, wrong for them to throw an overflow exception, as many
have pointed out in this thread.

Hi Lew,

Yes, I am sure we all know that it IS 100% per the Java-spec -- no
need to point out that...

That being said, I personally think it must be one of the most epic
design errors in software-history, to DELIBERATELY design a
programming-language this way.
To me its like... WHAT THE H*** WERE THEY THINKING?

I mean, it's fine if you have an OPTION for users to turn off overflow-
checking, for performance reasons, or whatever other reason someone
can dream up.

BUT, to make it so difficult for users that (as far as I have been
googling up) after 15+years of Java-evolution and refinement, still
NOBODY has came up with a simple and robust way of including such an
extremely basic "feature" for a software-language.

I am a big fan of Java and the "echo-system" around it and all the fun
we're having with it every day -- this one being the only BIG
EXCEPTION I can think of.
What I would hope for is that, still, at some point in the future,
there will actually be an OPTION in the JVM to turn on overflow-
checking.
That way, it can be adopted by users who really value robust and bug-
free software, without breaking backwards compatibility with existing
code.

 

[rop rop]

Generally, as for performance, for the majority of typical industry-
apps today (web-app backed by a database) overflow-checking would have
completely negligible impact on performance.

In-memory-computations, today, typically has extremely little impact,
compared to database-accesses and sending data over network.

Only in number-crunching applications would it make any significant
difference.
(Incidentally, however, these are perhaps the ones where overflow-bugs
are the most likely to occur?)

 

[John B. Matthews]

On Thu, 07 Jul 2011 17:51:06 -0700, Peter Duniho

[snip]

I would not worry about the "simple" or "efficient" criteria. IMHO,
if one is deciding to apply overflow checking to every computation,
one has already abandoned the hope of efficiency.

Not necessarily. If a rocket ends up being destroyed as a result,
having the computing go a bit slower to save having to build another
rocket would have been more efficient. Unfortunately, this is not a
made-up example. See:

<http://en.wikipedia.org/wiki/Ariane_5_Flight_501>

In the subsequent investigation, the cause of the problem was
recreated.

Turn on those run-time checks unless speed *REALLY* is of paramount
importance. It usually is not.

The software was designed for one system but used in another system
without adequate testing. In particular,

s) It would have been technically feasible to include almost the entire
inertial reference system in the overall system simulations which were
performed. For a number of reasons it was decided to use the simulated
output of the inertial reference system, not the system itself or its
detailed simulation. Had the system been included, the failure could
have been detected.

The full report may be seen here:

<http://en.wikisource.org/wiki/Ariane_501_Inquiry_Board_report>

 

[Eric Sosman]

Er, x86 and i32/64 certainly does. I just happen to be browsing their
hardware architecture documents last weak.

Not a single instruction to AddWithTrap, but a it does have a global
state register, and a test/branch instrution, so you just pair up an ADD
followed by a JO (Jump if Overflow) and that's it. Two easy instructions
paired together, and it works the same for MUL and SUB too. (DIV can't
overflow; think about it).

I Am Curious, Ultraviolet: Even for Integer.MIN_VALUE / -1?

 

[markspace]

I Am Curious, Ultraviolet: Even for Integer.MIN_VALUE / -1?

Hmm, that was the description I read in the docs, or thought I read.
I'm not really sure what the hardware will do in that case. One way to
find out would be to try it.

 

[Nasser M. Abbasi]

Hi,

If I want to have arithmetic-overflow checking in all parts of an
application,
what is the most practical, simple, efficient way to achieve this?
Id like to clutter the code as little a possible...
Is there any way to instruct the JVM to include it?

What? You mean you guys do not have this in Java??

It is a compiler option in Ada GNAT/gcc compiler:

http://gcc.gnu.org/onlinedocs/gcc-4.3.5/gnat_ugn_unw/Run_002dTime-Checks.html

"`-gnato'
Enables overflow checking for integer operations. This causes
GNAT to generate slower and larger executable programs by adding
code to check for overflow (resulting in raising Constraint_Error as
required by standard Ada semantics)."

This is something that should be there in Java.

--Nasser

 

[Nasser M. Abbasi]

What? You mean you guys do not have this in Java??

It is a compiler option in Ada GNAT/gcc compiler:

http://gcc.gnu.org/onlinedocs/gcc-4.3.5/gnat_ugn_unw/Run_002dTime-Checks.html

"`-gnato'
Enables overflow checking for integer operations. This causes
GNAT to generate slower and larger executable programs by adding
code to check for overflow (resulting in raising Constraint_Error as
required by standard Ada semantics)."

This is something that should be there in Java.

--Nasser

sorry, I see now this is mentioned in this thread. I replied before
reading the full thread.

--Nasser

 

[markspace]

the CPU generates an interrupt
when the overflow occurs,

Ah, ok that's why I read that the DIV instruction didn't affect the OV
bit--it uses a different mechanism. Thanks!

 

[Tom Anderson]

I've used machines that raised overflow traps "for free," in
the sense that it was done by the hardware/firmware/microcode, just
like setting condition flags.

Flipping the mode bit that enabled or disabled traps for integer
arithmetic was relatively expensive, so programs tended to set it
one way or the other during initialization and then just leave it
alone. But it's not necessary to use a global bit to get this kind
of behavior: an instruction set might feature both an AddAndWrap and
an AddAndTrap instruction. True, that's not entirely free -- you
pay for extra decoding logic in the instruction pipeline, for example.
But the inefficiencies don't rise to the "abandon hope" level, IMHO.

Besides: What are the relative efficiencies of an error caught
and announced versus a wrong answer computed at great speed without
any indication that it's wrong?

(The machines I speak of were from forty-odd years ago and might be
dismissed as ancientry, but their lineal descendants are still being
made and sold. I don't know how today's editions deal with overflow,
but if you're curious you can write to the vendor. Their headquarters
are in Armonk, NY.)

In that case, i can tell you what they do: charge you extra for it.

tom

 

[Tom Anderson]

The problem is "as needed". How does an automated tool tell the
difference between code that depends on the standard arithmetic and code
for which overflow detection is appropriate?

I'd been thinking it could be something like the presence of an
@CheckForOverflow annotation on the method or class. To be clear, this
would definitely be a feature that the user would have to request, not
something that happened by surprise.

You do then have this question of whether code called from a
@CheckForOverflow also gets checked for overflow (as with strictfp) or
not. I think not, because existing code will not have been written with
overflow checking in mind, so it can't be assumed that it will work with
it on. This is a blow to reuse, but it's not the end of the world.

tom

 

[rop rop]

You do then have this question of whether code called from a
@CheckForOverflow also gets checked for overflow (as with strictfp) or
not. I think not, because existing code will not have been written with
overflow checking in mind, so it can't be assumed that it will work with
it on. This is a blow to reuse, but it's not the end of the world.

I also think not, in the general case...
But you could also have an annotation argument, like

@CheckForOverflow(allTheWayDown=true)
or
@CheckForOverflow(allTheWayDown=false)

 

[Stefan Ram]

what is the most practical, simple, efficient way to achieve this?

Ok, so /given that Java has to be used/ it seems to be most
practical now, to call methods for arithmetic operations,
which include overflow checking. This looks ugly in the
source code without operator overloading, but requires the
least global preparation effort.

Another approach would be to statically prove that, under
the operating conditions given in a certain context,
overflow cannot occur (unless it is intended to occur) and
then write tests to verify this at run time.

Possibly, the discussion could gain some more insights,
if you could give a specific example of a program where such
an overflow checking would be used.

PS: We have a famous example of an overflow-related bug in
Java SE:

http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

. (Both an attempt to prove that an overflow cannot occur
in this method or carefully written test cases should have
revealed that there was a bug in this method.)

 

[Eric Sosman]

I also think not, in the general case...
But you could also have an annotation argument, like

@CheckForOverflow(allTheWayDown=true)
or
@CheckForOverflow(allTheWayDown=false)

I don't think the "true" variant would be workable, since it
pretty much forbids hashCode() calls. It probably also forbids
loading any classes, so you'd need to ensure that everything "all
the way down" was pre-loaded; that's going to be extremely hard
with plug-in architectures.

But if you're so interested in the topic, why don't you grab
the sources and go hack on them for a while? I expect the account
of your experiences would be a lot more interesting than idle
speculation is.

 

[Stanimir Stamenkov]

Wed, 6 Jul 2011 22:28:50 +0200, /Tom Anderson/:

using a library or a set of functions by convention is error-prone,

The set of library functions would just address the requirement of
not cluttering the code. The error-proneness is usually addressed
by writing appropriate unit tests which verify the code is dealing
with overflow situations in expected manner.

 

[markspace]

I also think not, in the general case...
But you could also have an annotation argument, like

@CheckForOverflow(allTheWayDown=true)
or
@CheckForOverflow(allTheWayDown=false)

I did a quick check of the C# variant when it was mentioned here, and
this is how they do it:

int result = checked( a + b - c );

In other words is a key word. Since Java can't really do this easily,
I'd be in favor of using an existing key word and extending it. For
example, the key word "try" can't ever appear currently as a class name
or package name in any program, so we could do this:

int result = try.checked( a + b - c );

Which at least makes sense to me as one reads the code; i.e., it's
literate programming. One could, I suppose, also extend the syntax
where an annotation can be used, but this might have side effects also.
For example, it might be hard to support these new user defined
annotations in the general case.

 

[lewbloch]

What? You mean you guys do not have this in Java??

It is a compiler option in Ada GNAT/gcc compiler:

http://gcc.gnu.org/onlinedocs/gcc-4.3.5/gnat_ugn_unw/Run_002dTime-Che...

"`-gnato'
     Enables overflow checking for integer operations. This causes
GNAT to generate slower and larger executable programs by adding
code to check for overflow (resulting in raising Constraint_Error as
required by standard Ada semantics)."

This is something that should be there in Java.

Ada was mentioned upthread as a language with the feature. Not only
we guys, but no one has this in Java, as the many posts upthread have
made quite clear. In fact, the Java language specification
specifically excludes trapping overflow in integer operations. As was
mentioned upthread by several folks. Lots of posters have expressed
the opinion that the feature should be present in some form in Java.
The discussion has now progressed to the form such a feature could
take without breaking Java and all the Java programs out there. Some
of the suggestions seem to be viable.