Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Unsigned integer wrapping on overflow

Reply
Thread Tools

Unsigned integer wrapping on overflow

 
 
Juha Nieminen
Guest
Posts: n/a
 
      08-28-2010
joe <(E-Mail Removed)> wrote:
> Wouldn't it be better if unsigned integers saturated upon overflow
> instead of wrapping?


Would make implenting a linear congruential generator harder.

What would be possible is that if the operation overflows, the upper
bits go to a second variable. This could even be made optional in the
language (in other words, when you declare the integral variable, you
use some special keyword or syntax which tells the compiler that this
is the kind of variable which, on overflow, should spill the upper bits
to this another variable).
 
Reply With Quote
 
 
 
 
tni
Guest
Posts: n/a
 
      08-28-2010
On 2010-08-28 17:42, Juha Nieminen wrote:
> The performance hit would be quite drastic. Every single operation you
> do with an integer would have to be followed by a conditional jump, which
> the CPU might or might not guess correctly (if it doesn't, a really severe
> penalty follows).


Not really. Generally (if there is no branch prediction data), backward
jumps are predicted as taken, forward jumps as not taken. By structuring
the code right (overflow should be very rare), there should be very
little penalty. Somebody actually implemented that (IIRC on x86) and the
performance penalty wasn't bad (a couple %).
 
Reply With Quote
 
 
 
 
joe
Guest
Posts: n/a
 
      08-28-2010
Öö Tiib wrote:
> On 28 aug, 03:47, "joe" <(E-Mail Removed)> wrote:
>> Öö Tiib wrote:
>>> On 28 aug, 01:59, "joe" <(E-Mail Removed)> wrote:
>>>> Öö Tiib wrote:
>>>>> On 27 aug, 22:28, "joe" <(E-Mail Removed)> wrote:
>>>>>> Wouldn't it be better if unsigned integers saturated upon
>>>>>> overflow instead of wrapping? I'm thinking from an overflow
>>>>>> detection point of view and using "overflow" to mean either
>>>>>> overflow or underflow. Detection could be done in a called
>>>>>> function then if desired, if one is willing to give up the
>>>>>> maximum unsigned value for a given width integer in select
>>>>>> cases, which sounds very reasonable to me.

>>
>>>>> You are not forced to use arithmetic provided by language. You can
>>>>> easily make your own numeric classes and their operations.

>>
>>>> Like MS's SafeInt, I know. But if it was built-in to the low level,
>>>> there wouldn't be a need for those kinds of things. If people are
>>>> doing it in programmer-land, then surely the compiler could do it
>>>> more efficiently? And it doesn't have to be one way or the other, a
>>>> new set of safe primitive integers could be added for those who
>>>> want to use them.

>>
>>>>> Also it is
>>>>> simple to throw together a static code analysis tool that warns on
>>>>> usage of any language-provided operations outside of such
>>>>> wrappers. I do not suggest it ... but C++ is easy to use as sort
>>>>> of language construction kit from that viewpoint.

>>
>>>>> Then you can use (one or several) inbuilt values as "invalid
>>>>> value", "missing value", "overflow value", "underflow value" etc.

>>
>>>> At a pretty big performance hit no doubt (considering that integers
>>>> are the most primitve things).

>>
>>> Integer arithmetics are cheap.

>>
>> Until you box them.

>
> Your overflow handling does not add less overhead on machine code
> level. Additionally that is on common case unnecessary overhead,
> because variables that are in danger to overflow their physical limits
> are of too small type anyway. Usual int variable is within smaller
> limits than int32_t or even int16_t has. Additionally the platforms
> where size of int16_t and int is same are becoming more and more
> exotic each year. Some people find that unsigned variable has
> underflow limit too near to its actual lower limit so even advocate
> against using unsigned types. Handling the real limits gives lot more
> bang for the buck.


That may make more sense for certain domain value types but for the
general concept of integer, I don't think so. The scenario I was thinking
of was something like malloc which will accept any unsigned integer. Well
how can malloc know if the caller really wanted 4+ billion bytes or if a
negative number was passed? If integers saturated instead of wrapped,
malloc could disallow the value 1 less than the maximum unsigned 32-bit
int (on a 32-bit platform) and use the maximum value as a detection of
overflow/underflow.

>
>>> Most int values in software can
>>> consider itself overflown far below 2 billions. Some int variable
>>> can consider itself overflowing as low as 300 other at 2000,
>>> depending what it means. Red-black tree with depth 300 does not
>>> perhaps fit into internet.



 
Reply With Quote
 
joe
Guest
Posts: n/a
 
      08-28-2010
tni wrote:
> On 2010-08-28 17:42, Juha Nieminen wrote:
>> The performance hit would be quite drastic. Every single
>> operation you do with an integer would have to be followed by a
>> conditional jump, which the CPU might or might not guess correctly
>> (if it doesn't, a really severe penalty follows).

>
> Not really. Generally (if there is no branch prediction data),
> backward jumps are predicted as taken, forward jumps as not taken. By
> structuring the code right (overflow should be very rare), there
> should be very little penalty. Somebody actually implemented that
> (IIRC on x86) and the performance penalty wasn't bad (a couple %).


Intriguing. I want, I want. OK, it's a contest then (are you listening
GCC and VC++?): first one to implement the "alternative set of integers"
(aka, "safe integers") extension, wins! Actually, I think I like the
VS IDE too much to jump to GCC just for that.


 
Reply With Quote
 
joe
Guest
Posts: n/a
 
      08-28-2010
tni wrote:
> On 2010-08-28 0:42, Sprechen sie von C++ wrote:
>> "joe" <(E-Mail Removed)> wrote in message
>> news:9lUdo.101194$(E-Mail Removed)...
>>> Wouldn't it be better if unsigned integers saturated upon overflow
>>> instead of wrapping? I'm thinking from an overflow detection point
>>> of view and using "overflow" to mean either overflow or underflow.
>>> Detection could be done in a called function then if desired, if one
>>> is willing to give up the maximum unsigned value for a given width
>>> integer in select cases, which sounds very reasonable to me.

>
> IMO, well-defined overflow (that you get with unsigned) is at least as
> useful as saturation.


(From another post I just made
"The scenario I was thinking
of was something like malloc which will accept any unsigned integer. Well
how can malloc know if the caller really wanted 4+ billion bytes or if a
negative number was passed? If integers saturated instead of wrapped,
malloc could disallow the value 1 less than the maximum unsigned 32-bit
int (on a 32-bit platform) and use the maximum value as a detection of
overflow/underflow."

Now, in that context, please explain how wrapping "is at least as useful
as saturation".

> But an additional mechanism that saturates or
> throws on overflow would certainly be extremely useful.


I was thinking an alternative set of integers. (I have only been thinking
about unsigned integers in this whole thread).

>
>> The basic types map directly to the CPU instructions. So given the
>> CPU supports wraparound to allow for multi-precision calculations
>> that is why it rolls over.

>
> But the funny thing is, you can't even implement that efficiently in
> that so-called systems programming language C (and C++).
>
>> When that happens the CPU asserts the overflow bit so
>> that code can increment the higher order word.

>
> Given that pretty much every CPU out there does have an overflow flag,
> you should really have some way to access it.


It would, then/now, appear that there are many possibilities. Just the
saturating characteristic would make me a happy camper though (not that I
know all of the ramifications of what I am asking for).


 
Reply With Quote
 
joe
Guest
Posts: n/a
 
      08-28-2010
Juha Nieminen wrote:
> joe <(E-Mail Removed)> wrote:
>> Wouldn't it be better if unsigned integers saturated upon overflow
>> instead of wrapping?

>
> Would make implenting a linear congruential generator harder.


Again, I suggested that it not be either/or, but rather both: an
additional alternative set of integers available to the programmer to use
if he wanted to. Mix-n-match as you wish.

>
> What would be possible is that if the operation overflows, the upper
> bits go to a second variable. This could even be made optional in the
> language (in other words, when you declare the integral variable, you
> use some special keyword or syntax which tells the compiler that this
> is the kind of variable which, on overflow, should spill the upper
> bits to this another variable).


Sounds less than transparent.


 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      08-28-2010
On Aug 27, 8:28 pm, "joe" <(E-Mail Removed)> wrote:
> Wouldn't it be better if unsigned integers saturated upon
> overflow instead of wrapping?


It would be "better" (for some suitable definition of better) if
all types triggered some sort of hardware trap on overflow. (The
"undefined behavior" of signed integral types and floating point
types on overflow is designed to allow that.) Practically
speaking, however, this would result in significantly slower
programs on most platforms (or would require significantly more
intelligent compilers to get close to current performance).

Why undefined behavior is not the case for unsigned integral
types is somewhat of a mystery. I'm guessing that it is due to
some pre-standard code counting on wrapping.

--
James Kanze
 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      08-28-2010
On Aug 27, 11:42 pm, "Sprechen sie von C++" <(E-Mail Removed)> wrote:
> "joe" <(E-Mail Removed)> wrote in message


> news:9lUdo.101194$(E-Mail Removed)...


> > Wouldn't it be better if unsigned integers saturated upon
> > overflow instead of wrapping? I'm thinking from an overflow
> > detection point of view and using "overflow" to mean either
> > overflow or underflow. Detection could be done in a called
> > function then if desired, if one is willing to give up the
> > maximum unsigned value for a given width integer in select
> > cases, which sounds very reasonable to me.


> The basic types map directly to the CPU instructions. So given
> the CPU supports wraparound to allow for multi-precision
> calculations that is why it rolls over.


Whether they map directly to CPU instructions or not depends on
the implementation. I know of at least one implementation with
compiler options to turn off compatilibity when mapping int to
unsigned int, because of the runtime overhead the required
mapping created.

> When that happens the CPU asserts the overflow bit so that
> code can increment the higher order word.


You can't access the carry or overflow flags from C/C++ anyway,
so you're stuck. When doing multi-precision calculations, you
can't use the largest size available; you have to use one less.
(Which means that if you want maximum speed, you have to use
assembler, where you can access the condition code.)

--
James Kanze
 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      08-28-2010
On Aug 28, 4:42 pm, Juha Nieminen <(E-Mail Removed)> wrote:
> joe <(E-Mail Removed)> wrote:
> > But the compiler can interrogate the overflow bit and do
> > what it wants, yes? What the performance hit would be I
> > don't know.


> The performance hit would be quite drastic. Every single
> operation you do with an integer would have to be followed by
> a conditional jump, which the CPU might or might not guess
> correctly (if it doesn't, a really severe penalty follows).


That is, of course, is pure speculation. Compilers have become
quite good at optimizing this sort of stuff, and figuring out in
advance whether the expression can actually overflow or not.
How much it would actually cost, once the compiler got through
optimizing, is anybodies guess. Studies with array bounds
checking (a much more limited aspect of the same thing) have
found only limited performance loss.

Historically, too, some machines have done this sort of thing in
hardware. In practice, today, we have a chicken and egg
problem: modern machines don't bother, since modern languages
don't require it, and in some cases, even forbid it, and modern
languages don't require it, because they're afraid of the
performance hit. (On the other hand, on some modern machines,
floating point is practically as fast as integral arithmetic.
And floating point units typically do check for overflow,
including when storing back into an int.)

--
James Kanze
 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      08-28-2010
On Aug 28, 4:59 pm, tni <(E-Mail Removed)> wrote:
> On 2010-08-28 17:42, Juha Nieminen wrote:
>
> > The performance hit would be quite drastic. Every single operation you
> > do with an integer would have to be followed by a conditional jump, which
> > the CPU might or might not guess correctly (if it doesn't, a really severe
> > penalty follows).

>
> Not really. Generally (if there is no branch prediction data), backward
> jumps are predicted as taken, forward jumps as not taken. By structuring
> the code right (overflow should be very rare), there should be very
> little penalty. Somebody actually implemented that (IIRC on x86) and the
> performance penalty wasn't bad (a couple %).


Intel had, at least at one point in the past, an into
instruction, which triggered a hardware trap if the overflow bit
was set in the status register. Presumably, branch prediction
would always assume this one as not being taken. (But I have no
idea of the performance of this on modern chips, or even if it
still exists.)

--
James Kanze
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
(int) -> (unsigned) -> (int) or (unsigned) -> (int) -> (unsigned):I'll loose something? pozz C Programming 12 03-20-2011 11:32 PM
Re: Unsigned Integer Overflow on Multiplication and Division Keith Thompson C Programming 2 05-13-2010 08:48 PM
Re: Unsigned Integer Overflow on Multiplication and Division Eric Sosman C Programming 1 05-13-2010 08:18 PM
Unsigned integer overflow detection Raymond C++ 8 08-20-2007 06:44 PM
unsigned integer overflow behaviour bartek C++ 3 02-06-2004 09:47 PM



Advertisments