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


 

Forums >

comp.lang.c

efficient or clever way

dr.oktopus

6/6/2011 8:29:00 AM

Hello,
walking an array is a common construct in programming.
In C language, I see two common practises.

1:

for (p = array, pend = array + size ; p < pend ; ++p)
/* do something */

2:

count = size;
p = array;
while (count--) {
/* do something here */
++p;
}

In complex contests, keeping a count variable could
be more readable (IMO) than having a variable acting
as a sentinel for the array bound (I'm speking of pieces
of codes where array navigation is not from the start
to the end, or inside Duff's devices, for example).
My question is: is this code really inefficient than
first approach (since it has to dec a variable every
cycle, more than test it) or current cpus could handle a sort
of decrement and test instr that do it all at the same time?
Thanks,
wily
15 Answers

China Blue Veins

6/6/2011 9:12:00 AM

0

> My question is: is this code really inefficient than
> first approach (since it has to dec a variable every
> cycle, more than test it) or current cpus could handle a sort
> of decrement and test instr that do it all at the same time?

Think of it these terms: the difference is maybe one cycle per loop, or a few
more if it goes to cache. Your post has been propagated on millions of computers
using a considerable number of cycles worldwide. In all likelihood the possible
savings from a correct answer will never be more than fraction of the cost of
asking the question.

For code like this far more energy will be spent on other people trying to
figure out why you did that than actually executing it. So you should choose the
clearest, most obvious coding.

The place where you should put your work are in things like converting an O(n^2)
program to O(n log n) or even O(n). These kinds of changes are more likely to
have a long term pay off.

Compilers are good at scrubbing out extraneous cycles from the code you wrote.
They're really bad at rewriting an algorithm to save an order of
complexity--that's for humans to do.

--
I remember finding out about you, | I survived XYZZY-Day.
Everyday my mind is all around you,| I'm whoever you want me to be.
Looking out from my lonely room |Annoying Usenet one post at a time.
Day after day. | At least I can stay in character.

Chris H

6/6/2011 11:51:00 AM

0

In message <chine.bleu-C1538A.02122706062011@news.eternal-
september.org>, China Blue Angels <chine.bleu@yahoo.com> writes
>> My question is: is this code really inefficient than
>> first approach (since it has to dec a variable every
>> cycle, more than test it) or current cpus could handle a sort
>> of decrement and test instr that do it all at the same time?
>
>Think of it these terms: the difference is maybe one cycle per loop, or a few
>more if it goes to cache. Your post has been propagated on millions of
>computers
>using a considerable number of cycles worldwide. In all likelihood the
>possible
>savings from a correct answer will never be more than fraction of the cost of
>asking the question.

I like that thought.

>Compilers are good at scrubbing out extraneous cycles from the code you wrote.
>They're really bad at rewriting an algorithm to save an order of
>complexity--that's for humans to do.

This is also true....

I find a lot of programmers spend time shaving cycles off functions
whereas the problem is the higher level design.

--
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\ Chris Hills Staffs England /\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/

pete

6/6/2011 12:22:00 PM

0

dr.oktopus wrote:
>
> Hello,
> walking an array is a common construct in programming.
> In C language, I see two common practises.
>
> 1:
>
> for (p = array, pend = array + size ; p < pend ; ++p)
> /* do something */
>
> 2:
>
> count = size;
> p = array;
> while (count--) {
> /* do something here */
> ++p;
> }
>
> In complex contests, keeping a count variable could
> be more readable (IMO) than having a variable acting
> as a sentinel for the array bound (I'm speking of pieces
> of codes where array navigation is not from the start
> to the end, or inside Duff's devices, for example).
> My question is: is this code really inefficient than
> first approach (since it has to dec a variable every
> cycle, more than test it) or current cpus could handle a sort
> of decrement and test instr that do it all at the same time?
> Thanks,
> wily

It all depends on the cpu.
Comparing two variables against each other
may or may not be slower
than a decrement plus a comparison against constant zero.

A decrement plus a comparison against constant zero,
is a single instruction in Microchip assembly.

--
pete

cri

6/6/2011 3:14:00 PM

0

On Mon, 6 Jun 2011 01:29:11 -0700 (PDT), "dr.oktopus"
<blindwilly@freeonline.zzn.com> wrote:

>Hello,
>walking an array is a common construct in programming.
>In C language, I see two common practises.
>
>1:
>
>for (p = array, pend = array + size ; p < pend ; ++p)
>/* do something */
>
>2:
>
>count = size;
>p = array;
>while (count--) {
>/* do something here */
>++p;
>}
>
>In complex contests, keeping a count variable could
>be more readable (IMO) than having a variable acting
>as a sentinel for the array bound (I'm speking of pieces
>of codes where array navigation is not from the start
>to the end, or inside Duff's devices, for example).
>My question is: is this code really inefficient than
>first approach (since it has to dec a variable every
>cycle, more than test it) or current cpus could handle a sort
>of decrement and test instr that do it all at the same time?

In ye olde days of yore the second form would have been more efficient
than the first. Decrement, increment, and test against zero are all
much simpler instructions, than the compare of two pointers, which
requires a subtraction. Many machines had a one instruction decrement
and test against zero. In these days with modern machines and modern
compilers it's almost certainly a wash. If there is a difference it
could be either way.

All of that said, I would write your second form like this:

for (count=size,p=array;count--;++p) {/* body */}

Keith Thompson

6/6/2011 4:36:00 PM

0

"dr.oktopus" <blindwilly@freeonline.zzn.com> writes:
> walking an array is a common construct in programming.
> In C language, I see two common practises.
>
> 1:
>
> for (p = array, pend = array + size ; p < pend ; ++p)
> /* do something */
>
> 2:
>
> count = size;
> p = array;
> while (count--) {
> /* do something here */
> ++p;
> }

There's also this:

const size_t array_len = sizeof array / sizeof array[0];
for (size_t i = 0; i < array_len; i ++) {
/* do something with array[i] */
}

An optimizing compiler is likely to generate equally good code for
any of them.

--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.ne...
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Kleuskes & Moos

6/6/2011 6:38:00 PM

0

On Jun 6, 1:50 pm, Chris H <ch...@phaedsys.org> wrote:
> In message <chine.bleu-C1538A.02122706062...@news.eternal-
> september.org>, China Blue Angels <chine.b...@yahoo.com> writes
>
> >> My question is: is this code really inefficient than
> >> first approach (since it has to dec a variable every
> >> cycle, more than test it) or current cpus could handle a sort
> >> of decrement and test instr that do it all at the same time?
>
> >Think of it these terms: the difference is maybe one cycle per loop, or a few
> >more if it goes to cache. Your post has been propagated on millions of
> >computers
> >using a considerable number of cycles worldwide. In all likelihood the
> >possible
> >savings from a correct answer will never be more than fraction of the cost of
> >asking the question.
>
> I like that thought.

"premature optimization is the root of all evil", Donald Knuth.

But i might steal the above quote, too.

Voice Of Truth

6/6/2011 6:49:00 PM

0

pete wrote:

> It all depends on the cpu.
> Comparing two variables against each other
> may or may not be slower
> than a decrement plus a comparison against constant zero.
>
> A decrement plus a comparison against constant zero,
> is a single instruction in Microchip assembly.


Pete, your answers are always as short as irritating. You must be
a great pole in the ass for everyone. Just for once at least, take your
answer and put it up your ass (and you are still lucky 'cause it's short).

Keith Thompson

6/6/2011 6:56:00 PM

0

Voice Of Truth <oops@uhm.wow> writes:
> pete wrote:
>> It all depends on the cpu.
>> Comparing two variables against each other
>> may or may not be slower
>> than a decrement plus a comparison against constant zero.
>>
>> A decrement plus a comparison against constant zero,
>> is a single instruction in Microchip assembly.
>
> Pete, your answers are always as short as irritating. You must be
> a great pole in the ass for everyone. Just for once at least, take your
> answer and put it up your ass (and you are still lucky 'cause it's short).

I found pete's response to be accurate, informative, and to the point.

You, on the other hand, appear to have a posting history consisting of
this one unjustified insult. You're not getting off to a good start.

--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.ne...
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Voice Of Truth

6/6/2011 6:59:00 PM

0

Keith Thompson wrote:

> I found pete's response to be accurate, informative, and to the point.
>
> You, on the other hand, appear to have a posting history consisting of
> this one unjustified insult. You're not getting off to a good start.

Love you Keith, as brother of course.

pete

6/6/2011 11:11:00 PM

0

Voice Of Truth wrote:

> Pete, your answers are always as short as irritating.

sfsort is my latest microoptimization of
a Leapfrogging Samplesort function
with a qsort type interface.

http://www.springerlink.com/content/p705645...

/* BEGIN sfsort.h */

#ifndef H_SFSORT_H
#define H_SFSORT_H

#include <stddef.h>

void sfsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));

#endif

/* END sfsort.h */



/* BEGIN sfsort.c */

#include "sfsort.h"

static void sfrog(size_t s1,
size_t ss,
unsigned char *A,
size_t u,
size_t size,
int (*compar)(const void *, const void *));

void
sfsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
size_t s;

if (nmemb > 1) {
for (s = 1; nmemb - s > s; s += s + 1) {
sfrog(0, s - 1, base, s + s, size, compar);
}
sfrog(0, s - 1, base, nmemb - 1, size, compar);
}
}

static void
sfrog(size_t s1, size_t ss,
unsigned char *A, size_t u, size_t size,
int (*compar)(const void *, const void *))
{
if (s1 - ss != 1) {
if (u > ss) {
unsigned char *p1, *p2, *end, swap;
const size_t sm = (ss - s1) / 2 + s1;
const size_t sms = sm * size;
size_t j = (u + 1) * size;
size_t i = ss * size;

do {
i += size;
} while (j > i && compar(A + sms, A + i) > 0);
do {
j -= size;
} while (j > i && compar(A + j, A + sms) > 0);
while (j > i) {
p1 = A + j;
p2 = A + i;
end = p2 + size;
do {
swap = *p1;
*p1++ = *p2;
*p2++ = swap;
} while (p2 != end);
do {
i += size;
} while (j > i && compar(A + sms, A + i) > 0);
do {
j -= size;
} while (j > i && compar(A + j, A + sms) > 0);
}
if (j == i) {
j -= size;
}
i = ss * size;
if (j > i) {
end = A + sms;
p1 = A + j + size;
p2 = A + i + size;
do {
swap = *--p2;
*p2 = *--p1;
*p1 = swap;
} while (p2 != end);
j /= size;
i = sm + j - ss + 1;
sfrog(s1, sm - 1, A, i - 2, size, compar);
} else {
j = ss;
i = sm + 1;
}
sfrog(i, j, A, u, size, compar);
}
} else {
sfsort(A + s1 * size, u - ss, size, compar);
}
}

/* END sfsort.c */


--
pete