Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #2681 > unrolled thread
| Started by | Thomas Scrace <tom@scrace.org> |
|---|---|
| First post | 2011-04-20 14:21 +0100 |
| Last post | 2011-04-21 12:09 -0700 |
| Articles | 14 on this page of 94 — 20 participants |
Back to article view | Back to comp.lang.c
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
Page 5 of 5 — ← Prev page 1 2 3 4 [5]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2011-04-20 16:11 +0100 |
| Message-ID | <0.5761d5ad606fde7f41a9.20110420161150BST.87r58xhs95.fsf@bsb.me.uk> |
| In reply to | #2687 |
Thomas Scrace <tom@scrace.org> writes:
> On Wed, 20 Apr 2011, Scott Fluhrer wrote:
>
>>
>> "Thomas Scrace" <tom@scrace.org> wrote in message
>> news:alpine.LFD.2.02.1104201414030.21950@bowman...
>>
>> There is some sort of comparison operator in there, one would assume. If
>> not, how did your code know it went through the entire range?
>
> Yes, sorry. I do use >/< operators.
>
> The code is as follows:
>
> signed long slmax()
> {
> signed long s;
> signed long temp;
> for (s = 0, temp = -1; s > temp; ++s, ++temp) {
> ;
> }
> return temp;
> }
>
> It's the same for all the other types, the only difference is the types.
>
> As you can see (and as I now see) in the case of an signed long it
> will cycle around and around infinitely.
It's not obvious to me. I'd expect this loop to terminate on most
current C implementations.
Integer overflow is undefined behaviour so, in theory, anything can
happen when s reaches LONG_MAX. In fact, the compiler is permitted to
work out that this is inevitable and may therefore replace your code
with anything that it pleases. Of course they won't. What will happen
in a very large number of cases is that s will wrap from LONG_MAX to
LONG_MIN and the loop will end.
You may be seeing what I am seeing. On my machine long is 64 bits and I
calculate that, at the speed my machine can run this loop, it won't end
for about 340 years.
> For the unsigned long this
> was of course not a problem. For signed shorts and signed ints it was
> not a problem because I could use a larger type (long) for the temp
> variable.
>
> I did not realise that signed types behaved this way.
I am not 100% sure that what you've deduced about your code is true. I
am pretty sure that you've missed that fact that this code is undefined
by the rules of the language.
--
Ben.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2011-04-20 08:14 -0700 |
| Message-ID | <3424a29f-facc-4605-bc3d-b6b9d6c22366@r4g2000prm.googlegroups.com> |
| In reply to | #2687 |
On Apr 20, 5:28 pm, Thomas Scrace <t...@scrace.org> wrote:
> On Wed, 20 Apr 2011, Scott Fluhrer wrote:
>
> > "Thomas Scrace" <t...@scrace.org> wrote in message
> >news:alpine.LFD.2.02.1104201414030.21950@bowman...
>
> > There is some sort of comparison operator in there, one would assume. If
> > not, how did your code know it went through the entire range?
>
> Yes, sorry. I do use >/< operators.
>
> The code is as follows:
>
> signed long slmax()
> {
> signed long s;
> signed long temp;
> for (s = 0, temp = -1; s > temp; ++s, ++temp) {
> ;
> }
> return temp;
>
> }
>
> It's the same for all the other types, the only difference is the types.
>
> As you can see (and as I now see) in the case of an signed long it will cycle
> around and around infinitely. For the unsigned long this was of course not a
> problem. For signed shorts and signed ints it was not a problem because I could
> use a larger type (long) for the temp variable.
>
> I did not realise that signed types behaved this way.
>
Signed types have undefined behaviour on overflow. Normally they just
wrap like unsigned types from maximium to minimum. But other
behaviours are possible.
[toc] | [prev] | [next] | [standalone]
| From | Thomas Scrace <tom@scrace.org> |
|---|---|
| Date | 2011-04-20 16:24 +0100 |
| Message-ID | <alpine.LFD.2.02.1104201619090.22217@bowman> |
| In reply to | #2689 |
On Wed, 20 Apr 2011, Malcolm McLean wrote: >> > Signed types have undefined behaviour on overflow. Normally they just > wrap like unsigned types from maximium to minimum. But other > behaviours are possible. > Well, it seems as if you and Ben might be right, because I just amended the code to take advance of the wrapping behaviour, and the loop still is not terminating. It is rather strange, because when I do: LONG_MAX + 1L I get LONG_MIN. But a loop that increments a signed long from 0 until it becomes negative does not appear to end. I can't really understand this, because I can get to ULONG_MAX in a matter of a few seconds in the same fashion. -- Thomas Scrace <tom@scrace.org>
[toc] | [prev] | [next] | [standalone]
| From | Thomas Scrace <tom@scrace.org> |
|---|---|
| Date | 2011-04-20 17:09 +0100 |
| Message-ID | <alpine.LFD.2.02.1104201705550.22217@bowman> |
| In reply to | #2690 |
Well, I just added a print statement to the loop so I could see what was happening. It is definitely not looping around, it is just going really slowly. I did a very rough timing, and it took about a minute to count to 4 million. By comparison, with an unsigned long it took just a few seconds to max out at 9223372036854775807. So, the wrapping does not seem to be the issue. I am at a loss as to how to explain why the speed is so dramatically different. -- Thomas Scrace <tom@scrace.org>
[toc] | [prev] | [next] | [standalone]
| From | Thomas Scrace <tom@scrace.org> |
|---|---|
| Date | 2011-04-20 17:19 +0100 |
| Message-ID | <alpine.LFD.2.02.1104201718400.22217@bowman> |
| In reply to | #2692 |
On Wed, 20 Apr 2011, Thomas Scrace wrote: > > By comparison, with an unsigned long it took just a few seconds to > max out at 9223372036854775807. Sorry, I meant 18446744073709551615. -- Thomas Scrace <tom@scrace.org>
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <kst-u@mib.org> |
|---|---|
| Date | 2011-04-20 12:09 -0700 |
| Message-ID | <ln1v0w68ov.fsf@nuthaus.mib.org> |
| In reply to | #2693 |
Thomas Scrace <tom@scrace.org> writes:
> On Wed, 20 Apr 2011, Thomas Scrace wrote:
>> By comparison, with an unsigned long it took just a few seconds to
>> max out at 9223372036854775807.
>
> Sorry, I meant 18446744073709551615.
(That's 2**64-1.)
That's implausible; there must be something else going on.
If your computer can increment a 64-bit long in 1 nanosecond
(1 GHz), it would take it over 500 years to iterate from 0
to 18446744073709551615. You can tweak the numbers slightly
(maybe your computer is faster than that, maybe it can do multiple
increments per clock cycle, etc.), but not enough to reduce the
time to a few seconds.
You said you added a print statement to the loop, and it took about
a minute to count to 4 million. (BTW, this would be a lot easier if
you had kept that context in your followup.) The print statement is
going to take orders of magnitude longer than a simple increment;
a minute to generate 4 million lines of output is plausible.
The overhead of formatting the output string is going to be
substantial, and even that is likely to be swamped by the time it
takes to physically generate the output.
My best guess is that you're actually iterating over a 32-bit range.
That takes about 6 seconds on my system (with no ouput in the loop).
(A sufficiently clever compiler might also optimize away the loop,
but then it would take no perceptible time, not "just a few seconds".)
Post the code (with no print stastements in the loop) that
"took just a few seconds". Please post the complete compilable
and runnable program. Before the loop starts, have it print the
relevent values from your <limits.h>, e.g.:
#include <limits.h>
...
printf("INT_MAX = %d\n", INT_MAX);
printf("UINT_MAX = %u\n", UINT_MAX);
printf("LONG_MAX = %ld\n", LONG_MAX);
printf("ULONG_MAX = %lu\n", ULONG_MAX);
If this doesn't solve the mystery, we might consider looking at the
generated assembly code, but we're not there yet.
--
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"
[toc] | [prev] | [next] | [standalone]
| From | Thomas Scrace <tom@scrace.org> |
|---|---|
| Date | 2011-04-20 21:39 +0100 |
| Message-ID | <alpine.LFD.2.02.1104202130210.22217@bowman> |
| In reply to | #2700 |
On Wed, 20 Apr 2011, Keith Thompson wrote:
> Thomas Scrace <tom@scrace.org> writes:
>> On Wed, 20 Apr 2011, Thomas Scrace wrote:
>>> By comparison, with an unsigned long it took just a few seconds to
>>> max out at 9223372036854775807.
>>
>> Sorry, I meant 18446744073709551615.
>
> (That's 2**64-1.)
>
> That's implausible; there must be something else going on.
>
> If your computer can increment a 64-bit long in 1 nanosecond
> (1 GHz), it would take it over 500 years to iterate from 0
> to 18446744073709551615. You can tweak the numbers slightly
> (maybe your computer is faster than that, maybe it can do multiple
> increments per clock cycle, etc.), but not enough to reduce the
> time to a few seconds.
>
> You said you added a print statement to the loop, and it took about
> a minute to count to 4 million. (BTW, this would be a lot easier if
> you had kept that context in your followup.) The print statement is
> going to take orders of magnitude longer than a simple increment;
> a minute to generate 4 million lines of output is plausible.
> The overhead of formatting the output string is going to be
> substantial, and even that is likely to be swamped by the time it
> takes to physically generate the output.
>
> My best guess is that you're actually iterating over a 32-bit range.
> That takes about 6 seconds on my system (with no ouput in the loop).
> (A sufficiently clever compiler might also optimize away the loop,
> but then it would take no perceptible time, not "just a few seconds".)
>
Hi Keith.
I posted the relevant function in a previous post, but I will reproduce it here:
> signed long slmax()
> {
> signed long s;
> signed long temp;
> for (s = 0, temp = -1; s > temp; ++s, ++temp) {
> ;
> }
> return temp;
> }
The function is the same for the unsigned longs, except with the types of the
two counter variables changed to unsigned. Scott Fluhrer pointed out that the
explanation for the supernaturally fast enumeration of the 64bit longs was in
the
temp = -1
assignment. Because temp is an unsigned variable in the unsigned functions this
actually ended up taking the value of ULONG_MAX, and the loop immediately
terminated. The reason I did not realise the error was that I was looking for it
to return ULONG_MAX; I just thought it was doing it in a different fashion.
So, mystery solved! It's amazing how these apparently simple K&R exercises can
lead to learning a lot more about the language than you initially expect.
Thanks,
Tom
--
Thomas Scrace <tom@scrace.org>
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <kst-u@mib.org> |
|---|---|
| Date | 2011-04-20 15:01 -0700 |
| Message-ID | <lnoc404m6p.fsf@nuthaus.mib.org> |
| In reply to | #2706 |
Thomas Scrace <tom@scrace.org> writes:
> On Wed, 20 Apr 2011, Keith Thompson wrote:
>> Thomas Scrace <tom@scrace.org> writes:
>>> On Wed, 20 Apr 2011, Thomas Scrace wrote:
>>>> By comparison, with an unsigned long it took just a few seconds to
>>>> max out at 9223372036854775807.
>>>
>>> Sorry, I meant 18446744073709551615.
>>
>> (That's 2**64-1.)
>>
>> That's implausible; there must be something else going on.
>>
>> If your computer can increment a 64-bit long in 1 nanosecond
>> (1 GHz), it would take it over 500 years to iterate from 0
>> to 18446744073709551615. You can tweak the numbers slightly
>> (maybe your computer is faster than that, maybe it can do multiple
>> increments per clock cycle, etc.), but not enough to reduce the
>> time to a few seconds.
>>
>> You said you added a print statement to the loop, and it took about
>> a minute to count to 4 million. (BTW, this would be a lot easier if
>> you had kept that context in your followup.) The print statement is
>> going to take orders of magnitude longer than a simple increment;
>> a minute to generate 4 million lines of output is plausible.
>> The overhead of formatting the output string is going to be
>> substantial, and even that is likely to be swamped by the time it
>> takes to physically generate the output.
>>
>> My best guess is that you're actually iterating over a 32-bit range.
>> That takes about 6 seconds on my system (with no ouput in the loop).
>> (A sufficiently clever compiler might also optimize away the loop,
>> but then it would take no perceptible time, not "just a few seconds".)
>>
>
> I posted the relevant function in a previous post, but I will reproduce it here:
>
>> signed long slmax()
>> {
>> signed long s;
>> signed long temp;
>> for (s = 0, temp = -1; s > temp; ++s, ++temp) {
>> ;
>> }
>> return temp;
>> }
>
> The function is the same for the unsigned longs, except with the types of the
> two counter variables changed to unsigned. Scott Fluhrer pointed out that the
> explanation for the supernaturally fast enumeration of the 64bit longs was in
> the
>
> temp = -1
>
> assignment. Because temp is an unsigned variable in the unsigned functions this
> actually ended up taking the value of ULONG_MAX, and the loop immediately
> terminated. The reason I did not realise the error was that I was looking for it
> to return ULONG_MAX; I just thought it was doing it in a different fashion.
>
> So, mystery solved! It's amazing how these apparently simple K&R exercises can
> lead to learning a lot more about the language than you initially expect.
I'm glad you solved the mystery, but for future reference:
Yes, you posted the function, but you didn't post a complete program,
nor did you post the actual function that exhibited the problem. A
description of your actual code, even if it's accurate, isn't nearly as
useful as an exact copy (as in copy-and-paste) of your code. We can't
guess what details you've left out, either accidentally or because you
assumed they were unimportant.
Here's the kind of thing I was asking for:
#include <stdio.h>
#include <limits.h>
unsigned long slmax(void)
{
unsigned long s;
unsigned long temp;
for (s = 0, temp = -1; s > temp; ++s, ++temp) {
;
}
return temp;
}
int main(void)
{
unsigned long result;
printf("ULONG_MAX = %lu\n", ULONG_MAX);
printf("Calling slmax()\n");
result = slmax();
printf("After slmax()\n");
return 0;
}
Output:
ULONG_MAX = 4294967295
Calling slmax()
After slmax()
And you told us this took "a few seconds" to run. On my system, the
time it takes to run is literally too short to measure (well, to measure
conveniently). That's a *huge* difference, and it led me to a
completely icorrect conclusion.
Recommended reading:
<http://www.catb.org/~esr/faqs/smart-questions.html>.
Again, I'm glad you solved the problem, but I hope this advice will be
useful next time you want to ask a question here. And please don't
think I'm picking on you (I'm not) or beating a dead horse (well, I
probably am).
--
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"
[toc] | [prev] | [next] | [standalone]
| From | Thomas Scrace <tom@scrace.org> |
|---|---|
| Date | 2011-04-21 11:16 +0100 |
| Message-ID | <alpine.LFD.2.02.1104211114240.24017@bowman> |
| In reply to | #2710 |
On Wed, 20 Apr 2011, Keith Thompson wrote: > Recommended reading: > <http://www.catb.org/~esr/faqs/smart-questions.html>. > > Again, I'm glad you solved the problem, but I hope this advice will be > useful next time you want to ask a question here. And please don't > think I'm picking on you (I'm not) or beating a dead horse (well, I > probably am). Thanks Keith, I'll bear that in mind. -- Thomas Scrace <tom@scrace.org>
[toc] | [prev] | [next] | [standalone]
| From | "Scott Fluhrer" <sfluhrer@ix.netcom.com> |
|---|---|
| Date | 2011-04-20 13:06 -0400 |
| Message-ID | <1303319339.805970@sj-nntpcache-3.cisco.com> |
| In reply to | #2687 |
"Thomas Scrace" <tom@scrace.org> wrote in message
news:alpine.LFD.2.02.1104201524110.22103@bowman...
> On Wed, 20 Apr 2011, Scott Fluhrer wrote:
>
>>
>> "Thomas Scrace" <tom@scrace.org> wrote in message
>> news:alpine.LFD.2.02.1104201414030.21950@bowman...
>>
>> There is some sort of comparison operator in there, one would assume. If
>> not, how did your code know it went through the entire range?
>
> Yes, sorry. I do use >/< operators.
>
> The code is as follows:
>
> signed long slmax()
> {
> signed long s;
> signed long temp;
> for (s = 0, temp = -1; s > temp; ++s, ++temp) {
> ;
> }
> return temp;
> }
>
> It's the same for all the other types, the only difference is the types.
Looking at this code, the problem is not with the signed types, but the
unsigned.
When you make the s and temp unsigned, then in the first iteration:
s = 0
temp = ULONG_MAX (because that's what you get when you assign -1 to an
unsigned long)
So, s > temp is false, and so you exit immediately.
For signed types, this doesn't happen; you'll continue looping until s goes
beyond LONG_MAX, and the increment invokes undefined behavior. However, I
expect that you're not actually getting this far. Are longs 64 bits on this
platform? If it is, then this will take a *long* time (9223372036854775808
iterations; even if each iteration takes one picosecond (!), we're talking
about over 100 days).
>
> As you can see (and as I now see) in the case of an signed long it will
> cycle around and around infinitely. For the unsigned long this was of
> course not a problem. For signed shorts and signed ints it was not a
> problem because I could use a larger type (long) for the temp variable.
>
> I did not realise that signed types behaved this way.
>
> Thomas Scrace <tom@scrace.org>
[toc] | [prev] | [next] | [standalone]
| From | Thomas Scrace <tom@scrace.org> |
|---|---|
| Date | 2011-04-20 18:16 +0100 |
| Message-ID | <alpine.LFD.2.02.1104201813200.22217@bowman> |
| In reply to | #2697 |
On Wed, 20 Apr 2011, Scott Fluhrer wrote: > > "Thomas Scrace" <tom@scrace.org> wrote in message > news:alpine.LFD.2.02.1104201524110.22103@bowman... >> On Wed, 20 Apr 2011, Scott Fluhrer wrote: >> >>> >>> "Thomas Scrace" <tom@scrace.org> wrote in message >>> news:alpine.LFD.2.02.1104201414030.21950@bowman... >>> >> It's the same for all the other types, the only difference is the types. > > Looking at this code, the problem is not with the signed types, but the > unsigned. > > When you make the s and temp unsigned, then in the first iteration: > s = 0 > temp = ULONG_MAX (because that's what you get when you assign -1 to an > unsigned long) > So, s > temp is false, and so you exit immediately. > > For signed types, this doesn't happen; you'll continue looping until s goes > beyond LONG_MAX, and the increment invokes undefined behavior. However, I > expect that you're not actually getting this far. Are longs 64 bits on this > platform? If it is, then this will take a *long* time (9223372036854775808 > iterations; even if each iteration takes one picosecond (!), we're talking > about over 100 days). > Right. This makes sense. Yes, we are talking 64 bits. I was not recognising the problem with the unsigned variables, because they do in fact produce the desired result, just not in the way I intended! Thanks a lot for your help. -- Thomas Scrace <tom@scrace.org>
[toc] | [prev] | [next] | [standalone]
| From | gordonb.bfd7y@burditt.org (Gordon Burditt) |
|---|---|
| Date | 2011-04-21 11:22 -0500 |
| Message-ID | <wsmdnYali-xaxC3QnZ2dnUVZ_o2dnZ2d@posted.internetamerica> |
| In reply to | #2681 |
> In K&R there is an exercise to compute the range of possible values for each C > type. In doing this I have written two functions that are identical, except for > the fact that one uses signed long ints, and the other uses unsigned long ints. > I have found that the function that uses the unsigned ints completes in a few seconds, > while the signed version takes so long that I have never had the patience to > wait for it to end. The only operators I am using on the variables are increment > and decrement. It is quite possible on a modern machine (or even relatively ancient ones, like the Radio Shack Model I) that the machine instructions used for signed increment and unsigned increment are the same, bit-for-bit and in performance. The same applies to signed and unsigned add and subtract, for operands of the same size. C doesn't guarantee that, but it's fairly common. Two's complement representation makes it possible to do signed and unsigned operations with the same machine instruction (this does not work, though, with multiply and divide) without telling the CPU which one it's doing. If you are doing loops, you are also doing comparisons, assuming the loops eventually exit. Are you sure you are making the same number of trips through the loop in each case? > Is there a difference in performance between these types? It's difficult for there to be a performance difference on machines where the same instruction is used for both. Some machines use "condition codes" set by a math operation and used by a conditional branch, which can sometimes avoid a specific instruction for comparison against zero, and avoid needing a dozen comparison instructions differing by what to compare for. These results *are* different for signed and unsigned operation. The signed/unsigned increment, decrement, add, and subtract instructions simply set more "condition codes", with different flags used for signed and unsigned results. (The "carry" flag can also be considered "unsigned less than". A "zero" or "equal" flag is, of course, usable for both signed and unsigned operations). A different form of conditional branch is used based on the comparison being made and the signedness of the types. > Is this restricted to > long ints, or is there a general difference between all signed/non-signed C > types? > Could this be something compiler or processor specific? *ANY* performance difference is always compiler and processor specific. C does not require performance. I believe what you are seeing is a program bug, not a performance difference. > I am using GCC on > the x86 platform (intel core i5).
[toc] | [prev] | [next] | [standalone]
| From | Thomas Scrace <tom@scrace.org> |
|---|---|
| Date | 2011-04-21 19:27 +0100 |
| Message-ID | <alpine.LFD.2.02.1104211916360.25760@bowman> |
| In reply to | #2744 |
On Thu, 21 Apr 2011, Gordon Burditt wrote: >> In K&R there is an exercise to compute the range of possible values for each C >> type. In doing this I have written two functions that are identical, except for >> the fact that one uses signed long ints, and the other uses unsigned long ints. >> I have found that the function that uses the unsigned ints completes in a few seconds, >> while the signed version takes so long that I have never had the patience to >> wait for it to end. The only operators I am using on the variables are increment >> and decrement. > > > I believe what you are seeing is a program bug, not a performance difference. Well it turned out that you are correct. I have discussed this in previous posts, but, briefly, I had a bug that caused the function to give me the result I was looking for, but using a method I was not expecting. The reason was that I was initiating a loop by assinging -1 to an unsigned type. This meant that the variable immediately had the max value, and the loop exited without looping through all the possible values of the unsigned type (which is what I thought it was doing). From my perspective this meant that the program was looping through a large number of values extremely quickly in comparison with the signed version of the function, which was extremely slow (it actually *was* looping through all the values). I have posted the full version of the program I ended up with in a previous message if you are interested. Thanks for the information - it was very interesting. -- Thomas Scrace <tom@scrace.org>
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <kst-u@mib.org> |
|---|---|
| Date | 2011-04-21 12:09 -0700 |
| Message-ID | <lnvcy72zht.fsf@nuthaus.mib.org> |
| In reply to | #2752 |
Thomas Scrace <tom@scrace.org> writes:
> On Thu, 21 Apr 2011, Gordon Burditt wrote:
>>> In K&R there is an exercise to compute the range of possible values for each C
>>> type. In doing this I have written two functions that are identical, except for
>>> the fact that one uses signed long ints, and the other uses unsigned long ints.
>>> I have found that the function that uses the unsigned ints completes in a few seconds,
>>> while the signed version takes so long that I have never had the patience to
>>> wait for it to end. The only operators I am using on the variables are increment
>>> and decrement.
>>
>>
>> I believe what you are seeing is a program bug, not a performance difference.
>
> Well it turned out that you are correct. I have discussed this in previous
> posts, but, briefly, I had a bug that caused the function to give me the
> result I was looking for, but using a method I was not expecting.
>
> The reason was that I was initiating a loop by assinging -1 to an unsigned type.
> This meant that the variable immediately had the max value, and the loop exited
> without looping through all the possible values of the unsigned type (which is
> what I thought it was doing).
>
> From my perspective this meant that the program was looping through a large
> number of values extremely quickly in comparison with the signed version of the
> function, which was extremely slow (it actually *was* looping through all the
> values).
>
> I have posted the full version of the program I ended up with in a previous
> message if you are interested.
>
> Thanks for the information - it was very interesting.
This program makes some non-portable assumptions, but it should work as
expected on any system you're likely to encounter.
#include <stdio.h>
int main(void)
{
const unsigned char uchar_max = -1;
const signed char schar_max = uchar_max / 2u;
const unsigned short ushrt_max = -1;
const signed short shrt_max = ushrt_max / 2u;
const unsigned int uint_max = -1;
const signed int int_max = uint_max / 2u;
const unsigned long ulong_max = -1;
const signed long long_max = ulong_max / 2ul;
const unsigned long long ullong_max = -1;
const signed long long llong_max = ullong_max / 2ull;
printf("schar_max = %20d\n", schar_max);
printf("uchar_max = %20u\n", (unsigned)uchar_max);
printf("shrt_max = %20d\n", shrt_max);
printf("ushrt_max = %20u\n", (unsigned)ushrt_max);
printf("int_max = %20d\n", int_max);
printf("uint_max = %20u\n", uint_max);
printf("long_max = %20ld\n", long_max);
printf("ulong_max = %20lu\n", ulong_max);
printf("llong_max = %20lld\n", llong_max);
printf("ullong_max = %20llu\n", ullong_max);
return 0;
}
It's reliable for the unsigned types; -1 converted to any unsigned type
always yields the maximum value of that type.
For the signed types, it simply assumes that the maximum value is half
the maximum value of the corresponding signed type (with truncating
division); for example, if USHRT_MAX is 65535, it assumes SHRT_MAX is
32767. This is likely to be true even on systems that don't use
2's-complement. It will break down only if corresponding signed and
unsigned types have different numbers of padding bits. (Most or all
modern systems have no padding bits.)
Computing the minimum value for signed types is less straightforward.
It's likely to be either -FOO_MAX-1 (2's-complement) or -FOO_MAX
(1s'-complement or sign-and-magnitude), and you can (99%-reliably)
determine which representation is used by type-punning (e.g., set
the signed member of a union to -1 and see what value the unsigned
value takes on). This will fail if a system uses 2's-complement
but chooses to make the minimum representable value a trap
representation.
Of course it's easier just to use <limits.h>, but perhaps this kind of
technique could be useful for someone *implementing* <limits.h>.
--
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"
[toc] | [prev] | [standalone]
Page 5 of 5 — ← Prev page 1 2 3 4 [5]
Back to top | Article view | comp.lang.c
csiph-web