Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #2808

Re: Performance of signed vs unsigned types

Show all headers | View raw

On 04/22/2011 08:33 PM, Michael Press wrote:
> In article <iostlt$6u4$1@dont-email.me>,
>  James Kuyper <jameskuyper@verizon.net> wrote:
> 
>> On 04/22/2011 05:22 PM, Michael Press wrote:
>>> In article <iorvdl$pg6$1@dont-email.me>,
>>>  James Kuyper <jameskuyper@verizon.net> wrote:
>>>
>>>> On 04/22/2011 12:33 AM, Michael Press wrote:
...
> I know that the set int is finite, so eventually x cannot grow
> any larger. Call it overflow if it pleases you.

The fact that x cannot grow any larger is not the issue. The fact that
your code attempts to calculate x+step when it's mathematical value is
too large to be stored in an int is an an issue, and overflow is the
term for that situation. It's not about pleasing me, the term is used by
the standard itself.

...
>> If you don't have any idea which way your code will branch at it's if()
>> statements, how can you have any confidence in it's ability to produce
>> the desired results, whatever those might be?
> 
> I expect to get consistent results from a+b and a<b. 

That's yet another unjustified assumption, if a+b overflows. As
indicated below, the fact that it's unjustified is more important than I
had originally thought.

>>>> A fully conforming implementation could return, as the result for any
>>>> int expression that overflows, the current value stored in register 7,
>>>> which might happen to contain the machine address of 'x'. I suppose that
>>>> your program could produce the expected result on such an
>>>> implementation, but it's pretty unlikely to do so.
>>>
>>> Basically I assume. 
>>> addition and multiplication are closed on int,
>>
>> Which is also not guaranteed. However, the implementation I described
>> which always returns the contents of register 7 does not violate closure
>> of int under addition and multiplication; 
> 
> An implementation that always returns register 7, 
> or only when !( x < x + step).\

Sorry, my first statement was that it returns the value stored in
register 7 "for any int expression that overflows". My second statement
didn't include that qualifying clause, which may have caused confusion -
in particular, I can't make sense of several of your next few paragraphs
- that may be due to this confusion.

Note that what the comparison operator is comparing, when x+step
overflows, is the value of x and the value stored in register 7; the
comparison can be either true or false, depending upon what's in
register 7. There's no necessary relationship between x+step overflowing
and the value that results from the comparison expression.

> If the implementation always returns register 7,
> then register 7 always contains INT_MAX.

There's no such requirement. There are, in fact, no applicable
requirements when x+step overflows; that's what "undefined behavior" means.

> ... Does the
> standard require that INT_MAX exist?

It requires that a conforming implementation provide a definition for
INT_MAX in that expands into a constant expression of type int. That
rules out, among other things, the possibility that INT_MAX might change
during the execution of the program.

>> yet I doubt that your program
>> would work properly on such an implementation.
> 
> I do not see why not. 
> Machine returns contents of register 7. 
> Therefore register 7 contains INT_MAX,

That does not follow.

> or else it register 7 < x and the program 
> keeps plugging away, eventually adding 1 successively. 

It wasn't until I sat down to answer this message that I took a really
close look at the program you wrote; I knew that it depended upon
undefined behavior, which guarantees that is non-portable; but I had not
previously realized how robust it was. Your program's correct behavior
depends on upon an assumption, and one that's not guaranteed to be true
by the standard; but it's an a far weaker assumption than I had thought
it was: it assumes that the result of an int expression that overflows
is an valid int value.

A constant value doesn't prevent your program from working, regardless
of what that value is. A random value doesn't prevent it from working,
though the process gets a little slower. The absolute worst case
behavior occurs when an overflowing x+step expression always has a value
of x+1. If int happens to be a 64-bit type, that behavior would make
your program take an absurdly long time determining the value of INT_MAX
- but it would still eventually determine it.

I wish I'd done that analysis earlier, so I wouldn't have wasted my time
arguing about what the possible values of x+step are.

The code is still not portable, because the result of an int expression
that overflows is not restricted to valid int values. Keith has already
given an example based upon real-life exposure to a system that used
64-bit hardware to emulate 48-bit integers; on such an implementation,
your code would end up setting x to 2^63-1, rather than the correct
value of 2^48-1. Since x does not have a valid int value, there are no
requirements on what value the printf() expression would print out when
x == 2^63-1.

The alternative is not simply having your program blow up. Other,
subtler possibilities allowed by the fact that the behavior of your
program is undefined include:
1. (y = x+step) > x might return true, even though y is actually less
than x.
2. (y = 2*step) > step might return true, even though y is actually less
than step; in particular, y might be negative, causing step to become
negative.
3. step might also, arbitrary, become negative for no particularly good
reason other than the fact that the behavior is undefined.
4. The lines of your program might start executing in an arbitrary
order, unrelated to the order that's required when the behavior is
actually defined by the standard.

I should have brought up these other possibilities in the first place; I
apologize for wasting your time on irrelevant possibilities.

>> So you made a total of at least five assumptions not guaranteed to be
>> true by the C standard, in code posted as a response to my assertion
>> that  "most of the ways I can think of for computing the range of a
>> signed type are subject to serious portability issues.". I will grant
>> you that you did not label your code as a counter-example to that
>> assertion, but if it was not so-intended, what was the point of posting
>> that code?
> 
> The only assumption I know to be violated is closure of addition.
> The code can be made to work using only addition. 
> Tell me which implementations bomb on overflow.
> I will be content to avoid them. 

That you choose to avoid them does not make your code portable, if it
won't work as intended on those implementations.

> If the implementation does not bomb on overflow
> what prevents my program from returning INT_MAX.

See above. The 64-bit/48-bit implementation Keith mentioned is probably
the single most plausible alternative behavior that would actually
prevent your program from printing INT_MAX, without bombing.

-- 
James Kuyper

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Performance of signed vs unsigned types Thomas Scrace <tom@scrace.org> - 2011-04-20 14:21 +0100
  Re: Performance of signed vs unsigned types James Kuyper <jameskuyper@verizon.net> - 2011-04-20 09:49 -0400
    Re: Performance of signed vs unsigned types Thomas Scrace <tom@scrace.org> - 2011-04-20 15:21 +0100
    Re: Performance of signed vs unsigned types Peter Nilsson <airia@acay.com.au> - 2011-04-20 15:34 -0700
      Re: Performance of signed vs unsigned types Thomas Scrace <tom@scrace.org> - 2011-04-21 17:57 +0100
        Re: Performance of signed vs unsigned types Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-04-21 19:26 +0100
    Re: Performance of signed vs unsigned types Michael Press <rubrum@pacbell.net> - 2011-04-20 21:45 -0700
      Re: Performance of signed vs unsigned types James Kuyper <jameskuyper@verizon.net> - 2011-04-21 06:20 -0400
        Re: Performance of signed vs unsigned types Michael Press <rubrum@pacbell.net> - 2011-04-21 13:54 -0700
          Re: Performance of signed vs unsigned types James Kuyper <jameskuyper@verizon.net> - 2011-04-21 18:50 -0400
            Re: Performance of signed vs unsigned types Michael Press <rubrum@pacbell.net> - 2011-04-21 16:16 -0700
              Re: Performance of signed vs unsigned types James Kuyper <jameskuyper@verizon.net> - 2011-04-21 19:27 -0400
                Re: Performance of signed vs unsigned types Michael Press <rubrum@pacbell.net> - 2011-04-21 17:24 -0700
                Re: Performance of signed vs unsigned types James Kuyper <jameskuyper@verizon.net> - 2011-04-21 21:00 -0400
                Re: Performance of signed vs unsigned types Michael Press <rubrum@pacbell.net> - 2011-04-21 21:33 -0700
                Re: Performance of signed vs unsigned types Thomas Scrace <tom@scrace.org> - 2011-04-22 08:22 +0100
                Re: Performance of signed vs unsigned types Michael Press <rubrum@pacbell.net> - 2011-04-22 14:25 -0700
                Re: Performance of signed vs unsigned types James Kuyper <jameskuyper@verizon.net> - 2011-04-22 09:21 -0400
                Re: Performance of signed vs unsigned types Michael Press <rubrum@pacbell.net> - 2011-04-22 14:22 -0700
                Re: Performance of signed vs unsigned types James Kuyper <jameskuyper@verizon.net> - 2011-04-22 17:58 -0400
                Re: Performance of signed vs unsigned types Michael Press <rubrum@pacbell.net> - 2011-04-22 17:33 -0700
                Re: Performance of signed vs unsigned types James Kuyper <jameskuyper@verizon.net> - 2011-04-23 09:01 -0400
                Re: Performance of signed vs unsigned types Michael Press <rubrum@pacbell.net> - 2011-04-23 14:07 -0700
                Re: Performance of signed vs unsigned types James Kuyper <jameskuyper@verizon.net> - 2011-04-23 18:14 -0400
                Re: Performance of signed vs unsigned types Michael Press <rubrum@pacbell.net> - 2011-04-25 11:42 -0700
                Re: Performance of signed vs unsigned types James Kuyper <jameskuyper@verizon.net> - 2011-04-25 22:34 -0400
                Re: Performance of signed vs unsigned types gordonb.nw63u@burditt.org (Gordon Burditt) - 2011-04-26 10:59 -0500
                Re: Performance of signed vs unsigned types "madamemandm@yahoo.com" <madamemandm@yahoo.com> - 2011-04-22 07:55 -0700
                Re: Performance of signed vs unsigned types Noob <root@127.0.0.1> - 2011-04-22 17:03 +0200
                Re: Performance of signed vs unsigned types Keith Thompson <kst-u@mib.org> - 2011-04-22 08:42 -0700
                Re: Performance of signed vs unsigned types Michael Press <rubrum@pacbell.net> - 2011-04-22 14:15 -0700
                Re: Performance of signed vs unsigned types Keith Thompson <kst-u@mib.org> - 2011-04-22 15:23 -0700
                Re: Performance of signed vs unsigned types Michael Press <rubrum@pacbell.net> - 2011-04-22 17:37 -0700
                Re: Performance of signed vs unsigned types Seebs <usenet-nospam@seebs.net> - 2011-04-23 02:46 +0000
                Re: Performance of signed vs unsigned types Michael Press <rubrum@pacbell.net> - 2011-04-23 14:04 -0700
                Re: Performance of signed vs unsigned types Barry Schwarz <schwarzb@dqel.com> - 2011-04-23 14:28 -0700
                Re: Performance of signed vs unsigned types Michael Press <rubrum@pacbell.net> - 2011-04-25 11:43 -0700
                Re: Performance of signed vs unsigned types Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-04-23 23:38 +0100
                Re: Performance of signed vs unsigned types Michael Press <rubrum@pacbell.net> - 2011-04-25 11:46 -0700
                Re: Performance of signed vs unsigned types Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-04-25 22:43 +0100
                Re: Performance of signed vs unsigned types Seebs <usenet-nospam@seebs.net> - 2011-04-24 11:34 +0000
                Re: Performance of signed vs unsigned types Michael Press <rubrum@pacbell.net> - 2011-04-25 11:47 -0700
                Re: Performance of signed vs unsigned types Keith Thompson <kst-u@mib.org> - 2011-04-25 12:32 -0700
                Re: Performance of signed vs unsigned types Michael Press <rubrum@pacbell.net> - 2011-04-25 20:25 -0700
                Re: Performance of signed vs unsigned types Keith Thompson <kst-u@mib.org> - 2011-04-26 07:45 -0700
                Re: Performance of signed vs unsigned types lawrence.jones@siemens.com - 2011-04-24 23:50 -0400
                Re: Performance of signed vs unsigned types Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-04-25 02:13 -0700
                Re: Performance of signed vs unsigned types Ian Collins <ian-news@hotmail.com> - 2011-04-25 21:36 +1200
                Re: Performance of signed vs unsigned types Michael Press <rubrum@pacbell.net> - 2011-04-25 11:48 -0700
                Re: Performance of signed vs unsigned types lawrence.jones@siemens.com - 2011-04-25 16:32 -0400
                Re: Performance of signed vs unsigned types Keith Thompson <kst-u@mib.org> - 2011-04-25 15:22 -0700
                Re: Performance of signed vs unsigned types Michael Press <rubrum@pacbell.net> - 2011-04-25 20:32 -0700
                Re: Performance of signed vs unsigned types "io_x" <a@b.c.invalid> - 2011-04-26 09:42 +0200
                Re: Performance of signed vs unsigned types Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-04-26 12:04 +0100
                Re: Performance of signed vs unsigned types Keith Thompson <kst-u@mib.org> - 2011-04-26 08:15 -0700
                Re: Performance of signed vs unsigned types Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-04-26 08:35 -0700
                Re: Performance of signed vs unsigned types Keith Thompson <kst-u@mib.org> - 2011-04-26 08:52 -0700
                Re: Performance of signed vs unsigned types Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-04-26 09:15 -0700
                Re: Performance of signed vs unsigned types Keith Thompson <kst-u@mib.org> - 2011-04-26 10:22 -0700
                Re: Performance of signed vs unsigned types gordonb.s68qo@burditt.org (Gordon Burditt) - 2011-04-26 19:59 -0500
                Re: Performance of signed vs unsigned types "madamemandm@yahoo.com" <madamemandm@yahoo.com> - 2011-04-27 14:15 -0700
                Re: Performance of signed vs unsigned types "io_x" <a@b.c.invalid> - 2011-04-28 12:15 +0200
                Re: Performance of signed vs unsigned types Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-04-28 03:26 -0700
                Re: Performance of signed vs unsigned types Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-04-28 12:09 +0100
                Re: Performance of signed vs unsigned types James Kuyper <jameskuyper@verizon.net> - 2011-04-28 08:03 -0400
                Re: Performance of signed vs unsigned types Seebs <usenet-nospam@seebs.net> - 2011-04-28 16:44 +0000
                Re: Performance of signed vs unsigned types Gordon Burditt <gordon@hammy.burditt.org> - 2011-04-29 05:42 -0500
                Re: Performance of signed vs unsigned types Michael Press <rubrum@pacbell.net> - 2011-04-25 20:27 -0700
                Re: Performance of signed vs unsigned types Ian Collins <ian-news@hotmail.com> - 2011-04-26 15:30 +1200
                Re: Performance of signed vs unsigned types Michael Press <rubrum@pacbell.net> - 2011-04-26 00:14 -0700
                Re: Performance of signed vs unsigned types Ian Collins <ian-news@hotmail.com> - 2011-04-26 20:23 +1200
                Re: Performance of signed vs unsigned types Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-04-26 04:17 -0700
                Re: Performance of signed vs unsigned types Ike Naar <ike@sverige.freeshell.org> - 2011-04-22 06:46 +0000
                Re: Performance of signed vs unsigned types James Kuyper <jameskuyper@verizon.net> - 2011-04-22 09:37 -0400
                Re: Performance of signed vs unsigned types Michael Press <rubrum@pacbell.net> - 2011-04-25 11:49 -0700
              Re: Performance of signed vs unsigned types Keith Thompson <kst-u@mib.org> - 2011-04-22 09:09 -0700
                Re: Performance of signed vs unsigned types "madamemandm@yahoo.com" <madamemandm@yahoo.com> - 2011-04-22 09:46 -0700
                Re: Performance of signed vs unsigned types Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-04-22 20:21 +0100
  Re: Performance of signed vs unsigned types "Scott Fluhrer" <sfluhrer@ix.netcom.com> - 2011-04-20 10:06 -0400
    Re: Performance of signed vs unsigned types Thomas Scrace <tom@scrace.org> - 2011-04-20 15:28 +0100
      Re: Performance of signed vs unsigned types Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-04-20 16:11 +0100
      Re: Performance of signed vs unsigned types Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-04-20 08:14 -0700
        Re: Performance of signed vs unsigned types Thomas Scrace <tom@scrace.org> - 2011-04-20 16:24 +0100
          Re: Performance of signed vs unsigned types Thomas Scrace <tom@scrace.org> - 2011-04-20 17:09 +0100
            Re: Performance of signed vs unsigned types Thomas Scrace <tom@scrace.org> - 2011-04-20 17:19 +0100
              Re: Performance of signed vs unsigned types Keith Thompson <kst-u@mib.org> - 2011-04-20 12:09 -0700
                Re: Performance of signed vs unsigned types Thomas Scrace <tom@scrace.org> - 2011-04-20 21:39 +0100
                Re: Performance of signed vs unsigned types Keith Thompson <kst-u@mib.org> - 2011-04-20 15:01 -0700
                Re: Performance of signed vs unsigned types Thomas Scrace <tom@scrace.org> - 2011-04-21 11:16 +0100
      Re: Performance of signed vs unsigned types "Scott Fluhrer" <sfluhrer@ix.netcom.com> - 2011-04-20 13:06 -0400
        Re: Performance of signed vs unsigned types Thomas Scrace <tom@scrace.org> - 2011-04-20 18:16 +0100
  Re: Performance of signed vs unsigned types gordonb.bfd7y@burditt.org (Gordon Burditt) - 2011-04-21 11:22 -0500
    Re: Performance of signed vs unsigned types Thomas Scrace <tom@scrace.org> - 2011-04-21 19:27 +0100
      Re: Performance of signed vs unsigned types Keith Thompson <kst-u@mib.org> - 2011-04-21 12:09 -0700

csiph-web