[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.c

Performance of signed vs unsigned types

Thomas Scrace

4/20/2011 1:22:00 PM

93 Answers

James Kuyper

4/20/2011 1:50:00 PM

0

On 04/20/2011 09:21 AM, Thomas Scrace wrote:
> Hi all,
>
> 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.
>
> Is there a difference in performance between these 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? I am using GCC on
> the x86 platform (intel core i5).

The most important differences between unsigned and signed types are not
in their performance, but their behavior.
I'm not familiar with the exercise you're referring to, I only have a
copy of the first edition of K&R, which might not even have that
exercise (I didn't find it in a quick glance through the book).

The easiest way to determine the limits of the C types is to use the
macros from <limits.h>, but I presume that would defeat the point of the
exercise. There as safe and quite trivial methods of computing the range
of an unsigned type, but most of the ways I can think of for computing
the range of a signed type are subject to serious portability issues.
What do you expect the following function to do?

#include <limits.h>

long next_after_last(void)
{
return LONG_MAX + 1L;
}

Your answer to that question is likely to be closely related to the
reason your program is stuck.
--
James Kuyper

Scott Fluhrer

4/20/2011 2:07:00 PM

0


"Thomas Scrace" <tom@scrace.org> wrote in message
news:alpine.LFD.2.02.1104201414030.21950@bowman...
> Hi all,
>
> 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.

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?

>
> Is there a difference in performance between these 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?

Questions about performance are *always*
compiler/processor/phase-of-the-moon specific.

On the other hand, on most platforms, signed longs and unsigned longs
generally perform fairly similarly. My guess (given that I haven't seen
your code) is that your code had a bug in it which caused it to infinite
loop on a signed type, but not an unsigned type.

> I am using GCC on the x86 platform (intel core i5).
>
> Thanks,
>
> Tom
>
>
> --
> Thomas Scrace <tom@scrace.org>


Thomas Scrace

4/20/2011 2:21:00 PM

0

Thomas Scrace

4/20/2011 2:29:00 PM

0

Ben Bacarisse

4/20/2011 3:12:00 PM

0

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.

Malcolm McLean

4/20/2011 3:14:00 PM

0

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.

Thomas Scrace

4/20/2011 3:24:00 PM

0

Thomas Scrace

4/20/2011 4:10:00 PM

0

Thomas Scrace

4/20/2011 4:20:00 PM

0

Scott Fluhrer

4/20/2011 5:07:00 PM

0


"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>