Arithmetic overflow checking

T

tm

On 7/7/2011 5:51 PM, Peter Duniho wrote:
...


Not necessarily. I assumed a couple of decades ago that array index
checking would be impossibly inefficient, but it seems to work fine in
Java.

And in other languages, like Pascal, Ada and Seed7, as well.
I suspect that having integer range types would be a major help.
When I'm working out whether an int can overflow, I often think in terms
of the ranges of inputs to calculations. A compiler would be able to
tell that adding a digit to a digit always fits in the range [0,18].

I think there are two things:

1. range checks (like value fits in [0,18]).
2. check if an 32-bit (or 8-bit, 16-bit, 64-bit, ...)
computation overflows.

In the 1. case a compiler could generate code that does
the computation and checks the range afterwards.
In the 2. case a computation could result in wrong data,
because the overflow was silently ignored. In this case
either some checks must be done before the computation or
the overfow condition is recognized during or after the
computation. In an ideal world the hardware would do this.

A CPU could (in theory) easily recognize the overflow
and generate an interrupt. This way normal computations
(without overflow) would have no extra cost. AFAIK
commonly used CPUs do not have this possibility. They
have some FLAG, which is set when an overflow occurred.
But there is no possibility to cause an interrupt, when
the overflow FLAG is set. So code, which checks for
overflow, must check this flag after every computation.
Needless to say: Normal computations (without overflow)
are slowed down by this checks.

Because of this slow down most compilers and virtual
machines (AFAIK inluding the JVM) have no overflow
checking.

In other words: A missing hardware feature:

Trigger interupt when overflow flag is set.

Causes compilers and JVMs to omit overflow checks.


Greetings Thomas Mertes

--
Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.
 
T

tm

C integer arithmetic is always modulo M, for some large M (like 2**32 or 2**64).
So the concept of overflow does not apply.


Not all CPUs detect integer arithmetic overflow. Not all CPUs signal integer
arithmetic problems.

And popular CPUs, which do detect integer overflow, do not
trigger an interupt. This makes zero overhead overflow
detection impossible.

So software suffers because hardware / CPU designers want
to save a transistor...


Greetings Thomas Mertes

--
Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.
 
E

Eric Sosman

In C the array size is not part of the type or value, so there is nothing to
check.

No; the size (element count) is part of an array's type. Your
compiler will confirm this for you by issuing a diagnostic for

char matrix[5][7]; /* five char[7] arrays */
char (*nine)[9]; /* pointer to char[9] */
nine = matrix; /* point it at the first char[7] */
C integer arithmetic is always modulo M, for some large M (like 2**32 or 2**64).
So the concept of overflow does not apply.

This is true only for `unsigned' integer arithmetic. Signed
integer arithmetic is in fact vulnerable to overflow.
 
M

Malcolm McLean

     This is true only for `unsigned' integer arithmetic.  Signed
integer arithmetic is in fact vulnerable to overflow.
All arithmetic is vulnerable to overflow. The question is whether the
system reports and error or gives wrong results. Sometimes wrong
results are better than errors, for instance in video games, but only
rarely.
 
D

David Lamb

[...]
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.

I've used machines that raised overflow traps "for free," ....
(The machines I speak of were from forty-odd years ago

When microprocessors started to arrive on the scene, a lot of old-timey
hardware folks said they'd forgotten 30+ years of hardware design. When
operating systems for computers based on said processors came out, a lot
of old-timey software folks said they'd forgotten 30+ years of operating
system design. We seem to still be suffering the consequences.
 
J

Joshua Cranmer

C integer arithmetic is always modulo M, for some large M (like 2**32 or 2**64).
So the concept of overflow does not apply.

That is only true for unsigned integers; signed integer overflow is
undefined.
 
P

Phil Carmody

One might even say that array types are characterized by their
element type and by the number of elements in the array.
extern char s[];

That's not an array, that's a promise that somewhere else there's
an array.

Phil
 
M

Martin Gregorie

[...]
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.

I've used machines that raised overflow traps "for free," ...
(The machines I speak of were from forty-odd years ago

When microprocessors started to arrive on the scene, a lot of old-timey
hardware folks said they'd forgotten 30+ years of hardware design. When
operating systems for computers based on said processors came out, a lot
of old-timey software folks said they'd forgotten 30+ years of operating
system design. We seem to still be suffering the consequences.

That happened not once, but twice.

The first great leap backward was the minicomputer era, when the likes of
the PDP-8 arrived with a single user, single tasking OS reminiscent of
early computers, except they generally had teletypes instead of banks of
switches and flashing lights. By then the better mainframes were multi-
user, multitasking beasts.

Then the first microcomputers arrived in the mid/late '70s. By this time
the better minis had multi-tasking operating systems, but micros had re-
implemented the earliest mini OSes - CP/M was near as dammit a copy of
the old PDP-8 OS (RSTS?) from the late 60s - and the earliest micros even
had switches and flashing lights (KIM-1, IMSAI 8080). By 1980 the minis
were running UNIX but the latest and greatest micros had - drumroll - MS-
DOS!
 
M

Martin Gregorie

On 08/07/2011 12:30 AM, Eric Sosman wrote:
On 7/7/2011 8:51 PM, Peter Duniho wrote:
[...]
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.

I've used machines that raised overflow traps "for free,"
...
(The machines I speak of were from forty-odd years ago

When microprocessors started to arrive on the scene, a lot of
old-timey hardware folks said they'd forgotten 30+ years of hardware
design. When operating systems for computers based on said processors
came out, a lot of old-timey software folks said they'd forgotten 30+
years of operating system design. We seem to still be suffering the
consequences.

That happened not once, but twice.

The first great leap backward was the minicomputer era, when the likes
of the PDP-8 arrived with a single user, single tasking OS reminiscent
of early computers, except they generally had teletypes instead of
banks of switches and flashing lights. By then the better mainframes
were multi- user, multitasking beasts.

Then the first microcomputers arrived in the mid/late '70s. By this
time the better minis had multi-tasking operating systems, but micros
had re- implemented the earliest mini OSes - CP/M was near as dammit a
copy of the old PDP-8 OS (RSTS?) from the late 60s - and the earliest
micros even had switches and flashing lights (KIM-1, IMSAI 8080). By
1980 the minis were running UNIX but the latest and greatest micros had
- drumroll - MS- DOS!
Only twice? Aren't you forgetting "smart" phones. One of the great
advances in Android is (Drum roll!) multitasking!!!
They don't count since, unlike minis and micros, their builders didn't
retreat to the techno-stone age, ignore progress made to date, and build
primitive OS by rubbing (metaphorical) sticks together.

AFAIK all smartphones started an a more advanced level because they
inherited better operating systems. IIRC these all originated on
electronic memo pads such as Psion, HP and Palm Pilot made, and were all
a lot more advanced than the likes of RSTS, CP/M, Flex09, etc. Leastwise,
I don't think you can consider Symbian and whatever MS was calling the
iPAQ OS at that stage any more primitive than the contemporary versions
of MacOS, OS/2 or even Windows, though admittedly they were rather behind
UNIX and its distant relations such as OS-9/68K.
 
K

Keith Thompson

Malcolm McLean said:
All arithmetic is vulnerable to overflow. The question is whether the
system reports and error or gives wrong results. Sometimes wrong
results are better than errors, for instance in video games, but only
rarely.

All arithmetic that's intended to model (a subset of) the real
numbers with the usual mathematical operations is vulnerable to
overflow. (Even arbitrary-precision packages can run out of memory.)

But C unsigned arithmetic, for example *doesn't* model normal real
arithmetic; it models arithmetic modulo 2**N and is not vulnerable
to overflow. (Wraparound is not overflow; it yields the correct
wrapped result.)
 
M

markspace

Only twice? Aren't you forgetting "smart" phones. One of the great
advances in Android is (Drum roll!) multitasking!!!


If you're counting smart phones and MS-DOS, then you have to count
Apple's first MacOS, which used co-operative multi-tasking. I.e., any
error by any program in the system and the whole thing would just break.
This went on for nearly two decades iirc.

There's probably others we should count. 8-3 filenames,
case-insensitive file systems, weird mapping schemes for disc usage
based on a "maximum" storage size of say about 256kB (not kidding),
Apple's "innovative" data/resource fork file-scheme--I won't call it a
file-system--still causing pain to this day, and any other number of
"quick" or "new" kludges based on the idea of limited resources or
limited time to market.

All right up there with "saving" time or complexity not giving the user
a choice of hardware detection for integer overflow *coughjava*.
 
G

Gene Wirchenko

[snip]
In other words: A missing hardware feature:

Trigger interupt when overflow flag is set.

Causes compilers and JVMs to omit overflow checks.

No, it does not. Coupled with the idea of speed at all costs,
yes.

I think the safe option should be on by default. If you really
need the speed, then you can make the decision to override.

Most of the time, the speed is not required. I will take
slightly slower, correct results over fast, possibly wrong results.

Sincerely,

Gene Wirchenko
 
G

Gene Wirchenko

Gene Wirchenko said:
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:

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.

And the subsystem that the error was in was neded for the Ariane
4 but not for the Ariane 5. Software reuse ended up biting hard.

I have read a lot about that incident, though not as much as
about the THERAC-25 fiasco.

Sincerely,

Gene Wirchenko
 
G

Gene Wirchenko

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

And as if it excuses it. There is a reason why we have specs. It
is to specify desired behaviour, not be a straitjacket forevermore.
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? :)
Exactly.

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.

I would rather have it the other way around. Safety first. Make
the option on by default. If someone really needs the additional
speed and judges the risk is acceptable, then that person can flip the
switch and maybe get sued into the ground if he gets it wrong.

Sincerely,

Gene Wirchenko
 
J

Joshua Cranmer

I would rather have it the other way around. Safety first. Make
the option on by default. If someone really needs the additional
speed and judges the risk is acceptable, then that person can flip the
switch and maybe get sued into the ground if he gets it wrong.

The problem with arithmetic overflow is that it's not really adding any
safety. Sure, having 2^30 + 2^30 be a value less than 0 is wrong, but
often times the 2^30 value in the first place is just as wrong. Not to
mention that sometimes people fake unsigned integer types, in which case
2 - 1 is an invalid value--how is the compiler supposed to know that
this value is really an unsigned value? Note that this would break,
e.g., java.util.Arrays.binarySearch.

What you really need is checked ranges, not automatic overflow checking.
 
M

Malcolm McLean

     Most of the time, the speed is not required.  I will take
slightly slower, correct results over fast, possibly wrong results.
The game keeps on changing.

For instance modern space invaders are slowed down by the need to
normalise their vectors for lighting. Most of the rest of the code is
either handled by special rasterisers, or is insignificant in the
larger scheme of things. However they used to crawl about the screen
unless you pulled all the layers of indirection and gift-wrapping and
bounds checking away.
 
G

Gene Wirchenko

The game keeps on changing.

For instance modern space invaders are slowed down by the need to
normalise their vectors for lighting. Most of the rest of the code is
either handled by special rasterisers, or is insignificant in the
larger scheme of things. However they used to crawl about the screen
unless you pulled all the layers of indirection and gift-wrapping and
bounds checking away.

As someone once asked on a newsgroup that I follow, "How fast do
you want your wrong answers?"

Sincerely,

Gene Wirchenko
 
G

Gene Wirchenko

The problem with arithmetic overflow is that it's not really adding any
safety. Sure, having 2^30 + 2^30 be a value less than 0 is wrong, but
often times the 2^30 value in the first place is just as wrong. Not to
mention that sometimes people fake unsigned integer types, in which case
2 - 1 is an invalid value--how is the compiler supposed to know that
this value is really an unsigned value? Note that this would break,
e.g., java.util.Arrays.binarySearch.

What you really need is checked ranges, not automatic overflow checking.

We need both. Either one would catch the problem above, but some
situations are vulnerable to only one.

Going off the end of a small array would be caught by bounds
checking and not overflow checking.

Averaging a set of numbers with a sum too big would be caught by
overflow checking and not bounds checking.

Sincerely,

Gene Wirchenko
 
J

Joshua Cranmer

On Mon, 11 Jul 2011 10:30:26 -0700, Joshua Cranmer
Averaging a set of numbers with a sum too big would be caught by
overflow checking and not bounds checking.

What I advocated would basically be a "checked integer": every operation
is guaranteed to have a result between [min, max]; if not, it throws an
exception.
 
T

tm

[snip]
In other words: A missing hardware feature:
 Trigger interupt when overflow flag is set.
Causes compilers and JVMs to omit overflow checks.

     No, it does not.  Coupled with the idea of speed at all costs,
yes.

     I think the safe option should be on by default.  If you really
need the speed, then you can make the decision to override.

     Most of the time, the speed is not required.  I will take
slightly slower, correct results over fast, possibly wrong results.

It is not always necessary to pay for correct results
with a slowdown.

Correct results can be computed without any slowdown,
when the CPU is able to trigger an overflow interupt.

A slowdown would only happen when an overflow occurs.
Computations without overflow would run at full speed.


Greetings Thomas Mertes

--
Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,899
Latest member
RodneyMcAu

Latest Threads

Top