Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Keith Thompson <kst-u@mib.org> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Performance of signed vs unsigned types |
| Date | 2011-04-22 09:09 -0700 |
| Organization | None to speak of |
| Message-ID | <lnipu62rot.fsf@nuthaus.mib.org> (permalink) |
| References | (2 earlier) <rubrum-D8EBF4.21450020042011@news.albasani.net> <iop0dp$ivo$1@dont-email.me> <rubrum-005E59.13544421042011@news.albasani.net> <ioqcbo$irj$1@dont-email.me> <rubrum-49C519.16165221042011@news.albasani.net> |
Michael Press <rubrum@pacbell.net> writes:
> In article <ioqcbo$irj$1@dont-email.me>,
> James Kuyper <jameskuyper@verizon.net> wrote:
>> On 04/21/2011 04:54 PM, Michael Press wrote:
>> > In article <iop0dp$ivo$1@dont-email.me>,
>> > James Kuyper <jameskuyper@verizon.net> wrote:
>> >
>> >> On 04/21/2011 12:45 AM, Michael Press wrote:
>> >>> In article <iomoa5$vfr$1@dont-email.me>,
>> ...
>> >>> $ cat try.c
>> >>> #include <stdio.h>
>> >>>
>> >>> int
>> >>> main(void)
>> >>> {
>> >>> int x;
>> >>> int y;
>> >>> int step;
>> >>>
>> >>> x = step = 1;
>> >>> for (; step != 0;)
>> >>> {
>> >>> if ((y = x + step) > x)
>> >>> {
>> >>> x = y;
>> >>> if ((y = 2 * step) > step)
>> >>> step = y;
>> >>> }
>> >>> else
>> >>> {
>> >>> step /= 2;
>> >>> }
>> >>> }
>> >>> printf("Maximum int = %d = %#x.\n", x, x);
>> >>> return 0;
>> >>> }
>> >>
>> >> That's one example of precisely what I was talking about. As soon as x >
>> >> INT_MAX - step, the expression x+step has undefined behavior; as soon as
>> >> step > INT_MAX/2, the expression 2*step has undefined behavior. The
>> >> above code seems to rely upon the unportable assumption that the actual
>> >> behavior in each of those cases will be to produce a result that is
>> >> negative. That's very common behavior, but it's not guaranteed by the
>> >> standard. That's what I meant by "serious portability issues".
>> >
>> > Does not assume it goes negative.
>>
>> By assuming that adding two positive ints, or multiplying a positive int
>> by 2, will produce a negative result when the operation overflows
>
> No, it does not.
It certainly makes *some* assumption(s) not guaranteed by the standard.
Specifically, it appears to assume that, where step is a positive
int value, evaluating (x + step) will yield a value less than x if
and only if the mathematical result of (x + step) exceeds INT_MAX.
Again, as James wrote in text that you snipped, there are probably
other sets of assumptions that would also make the program work.
But there is no set of assumptions that make the program work that
cannot be violated by a conforming implementation. In other words,
there can be conforming C implementation on which your program does
*not* print "Maxmum int = " followed by the correct value of INT_MAX.
For example, if signed integer overflow causes the program to terminate,
then your program won't print anything.
Another example: Suppose a CPU provides 64-bit integer registers,
with addition and comparison working correctly for all 64-bit values,
but with multiplication and division working correctly only for
up to, say, 48-bit values. The C implementation chooses to store
ints in 64 bits, but to make INT_MAX 2**47-1 -- i.e., an int has
16 padding bits. It doesn't generate additional code to check for
overflow, since the behavior is undefined anyway. For operands and
results in the range INT_MIN..INT_MAX, all operations work correctly.
But the conditions
INT_MAX + 1 > INT_MAX
and
INT_MAX + INT_MAX > INT_MAX
will both be true.
The above is based on my very faulty recollection of the Cray T90 and
similar machines. It's probably incorrect in some significant ways,
but it is, I believe, a conforming hypothetical implementation. As I
recall, long was also stored in 64 bits, but without the padding
bits, making multiplication and division more expensive because
the compiler had to generate extra code to get correct results.
In general, without either access to <limits.h> or assumptions
about operations whose behavior is undefined, I don't believe it's
possible to determine the correct value for INT_MAX in portable C.
A contrived example: You could take a conforming implementation
with, say, 32-bit 2's-complement ints with no padding bits or
trap representations, and INT_MAX==2**31-1, and create a second
implementation that's identical *except* that INT_MAX==2**30-1 and
INT_MIN==-2**30. Arithmetic on int values would continue to work
exactly the same way, but the implementation woud simply choose
not to define the behavior of any int operations that yield values
exceeding the new tighter bounds.
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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