efficient or clever way

[dr.oktopus]

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

 

[Chris H]

In message <[email protected]

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.

 

[Keith Thompson]

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 */
}

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

 

[Kleuskes & Moos]

In message <[email protected]



I like that thought.

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

But i might steal the above quote, too.

 

[Keith Thompson]

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.

 

[Jorgen Grahn]

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;
}

Those are not common in my experience. Are you excluding the more
common forms because you believe they are less efficient?

1b:
for (Foo* p=array; p!=array+size; p++) { ... }

2b:
for (int i=0; i<size; i++) { ... }

I prefer 1b if the index is really irrelevant inside the loop. Mostly
because I use C++ a lot -- it's a common idiom there.

/Jorgen

 

[Anand Hariharan]

The place where you should put your work are in things like converting anO(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.

Do you know of instances where a program that had a quadratic
complexity was changed/rewritten to have a linear complexity?

- Anand

 

[Anand Hariharan]

Do you mean like Tarjan's strongly connected regions?

Thank you. Didn't know of either Tarjan's or Kosaraju's algorithm.

- Anand