By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,497 Members | 2,497 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 454,497 IT Pros & Developers. It's quick & easy.

Loop optimization

P: n/a
Hi,
I have two versions of a loop. I want to know which one is more
efficient. and is there any way to make it even more efficient?

1- for (i = 0; str[i++] != '\0';) ;

2- for (i = 0; str[] != '\0'; ++i) ;

Nov 21 '05 #1
Share this Question
Share on Google+
25 Replies


P: n/a
the second loop statement should be read as:

for (i = 0; str[i] != '\0'; ++i) ;

sorry for inconvenience.

Haroon

Nov 21 '05 #2

P: n/a
"haroon" <ha***********@gmail.com> wrote in message
news:11**********************@z14g2000cwz.googlegr oups.com...
I have two versions of a loop. I want to know which one is more
efficient. and is there any way to make it even more efficient?

1- for (i = 0; str[i++] != '\0';) ;
2- for (i = 0; str[] != '\0'; ++i) ;


It depends on the compiler, amongst other things. It would not surprise me
if exactly the same code was generated for both (ie both were equally
efficient).

Alex
Nov 21 '05 #3

P: n/a

haroon wrote:
the second loop statement should be read as:

for (i = 0; str[i] != '\0'; ++i) ;

sorry for inconvenience.

Haroon


C language standard says nothing about efficiency, so
not a lot to say here. You can test them on your machine and
see which is faster. The two loops end up with i at different
values, so perhaps "which does what you want" would be
a better place to start. That said, the standard strlen
MIGHT be faster, as it may use platform specific tricks
(fancy assembly instructions for determining string length?)
not available in standard C.

-David

Nov 21 '05 #4

P: n/a
haroon wrote:

the second loop statement should be read as:

for (i = 0; str[i] != '\0'; ++i) ;


In that case, I believe that Alex Fraser
has said all that there is to say on this matter.

--
pete
Nov 21 '05 #5

P: n/a
haroon wrote:
Hi,
I have two versions of a loop. I want to know which one is more
efficient. and is there any way to make it even more efficient?

1- for (i = 0; str[i++] != '\0';) ;

2- for (i = 0; str[] != '\0'; ++i) ;


Version 2 is more efficient, because it won't compile
and will therefore consume no time at all in execution.

More seriously, your question is ill-posed. If we
correct the second version by changing `str[]' to `str[i]'
(I'm just guessing, but it's your error that forces me to
make the guess), observe that the two loops do not perform
the same task. Since they perform different tasks, it is
senseless to ask about their relative efficiency. Which
is more efficient: A bicycle or a banana?

Personally, I don't think I'd write either loop. On
the supposition that `str' is a `char' array containing a
string (or is a pointer to the start of a string), I'd more
likely write

i = strlen(str) + 1; /* version 1 */
i = strlen(str); /* version 2, corrected */

.... depending on the desired outcome. I'd do so even though
there's no guarantee that strlen() is more efficient than
your loops, because it is surpassingly unlikely that the
calculation of a string length is the bottleneck in the
program. If it does turn out to be the bottleneck, you'll
discover that only by measurement -- and the measurement (and
whatever improvements might be possible) will be specific to
the particular C implementation you're using at the moment.

--
Eric Sosman
es*****@acm-dot-org.invalid
Nov 21 '05 #6

P: n/a
On 2005-11-21, haroon <ha***********@gmail.com> wrote:
Hi,
I have two versions of a loop. I want to know which one is more
efficient. and is there any way to make it even more efficient?

1- for (i = 0; str[i++] != '\0';) ;

2- for (i = 0; str[] != '\0'; ++i) ;


There's no particular reason to think either would be more or less
efficient.

Now, one which might more plausibly be more efficient would be

char *s = str; while(*s++) ... ;

but that depends a lot on what you're doing.
Nov 21 '05 #7

P: n/a
haroon <ha***********@gmail.com> wrote:
1- for (i = 0; str[i++] != '\0';) ; 2- for (i = 0; str[i] != '\0'; ++i) ;


To add to Alex's comments, the second version is easier to read than
the first.

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.
Nov 21 '05 #8

P: n/a
I believe this would be ok:

unsigned int i = 0;
for( ; str[i]; ++i)

Depends on CPU, what instructions are built-in and whether your
compiler has unrolled the loop.

Have you declared 'i' as unsigned?
http://www.abarnett.demon.co.uk/tutorial.html#INTEGERS

Maybe use prefix, even though this means to references to i:
http://www.tantalon.com/pete/cppopt/...refixOperators
haroon wrote:
the second loop statement should be read as:

for (i = 0; str[i] != '\0'; ++i) ;

sorry for inconvenience.

Haroon


Nov 21 '05 #9

P: n/a
Sorry: for( ; str[i] != '\0'; ++i)
If this is what you intend.

carl wrote:
I believe this would be ok:

unsigned int i = 0;
for( ; str[i]; ++i)

Depends on CPU, what instructions are built-in and whether your
compiler has unrolled the loop.

Have you declared 'i' as unsigned?
http://www.abarnett.demon.co.uk/tutorial.html#INTEGERS

Maybe use prefix, even though this means to references to i:
http://www.tantalon.com/pete/cppopt/...refixOperators
haroon wrote:
the second loop statement should be read as:

for (i = 0; str[i] != '\0'; ++i) ;

sorry for inconvenience.

Haroon


Nov 21 '05 #10

P: n/a
David Resnick wrote:

haroon wrote:
the second loop statement should be read as:

for (i = 0; str[i] != '\0'; ++i) ;
The two loops end up with i at different
values, so perhaps "which does what you want" would be
a better place to start.


I missed that point when I read the code.
Good job!

--
pete
Nov 21 '05 #11

P: n/a
it is more efficient with pointer
haroon schrieb:
Hi,
I have two versions of a loop. I want to know which one is more
efficient. and is there any way to make it even more efficient?

1- for (i = 0; str[i++] != '\0';) ;

2- for (i = 0; str[] != '\0'; ++i) ;


Nov 21 '05 #12

P: n/a
da******@gmail.com wrote:
it is more efficient with pointer
What is?
haroon schrieb:
Hi,
I have two versions of a loop. I want to know which one is more
efficient. and is there any way to make it even more efficient?

1- for (i = 0; str[i++] != '\0';) ;

2- for (i = 0; str[] != '\0'; ++i) ;


Oh, /that/. How do you know it's more efficient with pointers? You
certainly can't tell from the C standard.

--
Chris "another virtual machine" Dollin
missing tests don't fail.
Nov 21 '05 #13

P: n/a
haroon wrote
(in article
<11**********************@z14g2000cwz.googlegroups .com>):
Hi,
I have two versions of a loop. I want to know which one is more
efficient. and is there any way to make it even more efficient?

1- for (i = 0; str[i++] != '\0';) ;

2- for (i = 0; str[] != '\0'; ++i) ;


It depends. It always depends. On the compiler usually,
sometimes upon other factors beyond your control. The correct
answer is usually to allow the compiler to do the optimization
for you (by setting the appropriate flags for your target
platform) and choose the one that is most readable or easiest to
maintain.

In this particular case, I would personally opt for neither of
the above.
--
Randy Howard (2reply remove FOOBAR)
"The power of accurate observation is called cynicism by those
who have not got it." - George Bernard Shaw

Nov 21 '05 #14

P: n/a
da******@gmail.com wrote:
it is more efficient with pointer
1) You response belongs *under* the text you are replying to, not above.
2) Have you proved his by measuring the performance of the code
generated by *all* compilers?
3) It is easy for a compiler to translate from the array version to the
pointer version and so the pointer version is unlikely to produce a
faster executable.
4) Many compilers will produce the same code whether you use pointer
arithmetic or arrays.
haroon schrieb:
Hi,
I have two versions of a loop. I want to know which one is more
efficient. and is there any way to make it even more efficient?

1- for (i = 0; str[i++] != '\0';) ;

2- for (i = 0; str[] != '\0'; ++i) ;

--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.
Nov 21 '05 #15

P: n/a
carl wrote:
I believe this would be ok:
You reply belongs under the text you are replying to, not above.
unsigned int i = 0;
for( ; str[i]; ++i)
You can't put that in the middle of a code block.
Depends on CPU, what instructions are built-in and whether your
compiler has unrolled the loop.
True, what is most efficient depends on you compiler and *changes* from
one version to the next as they change the optimiser.
Have you declared 'i' as unsigned?
http://www.abarnett.demon.co.uk/tutorial.html#INTEGERS
I've yet to see a system where using unsigned integers was guaranteed to
be faster. Generally on 2s complement systems (i.e. almost all in
current production) the processor will do exactly the same in the same
amount of time whether i is signed or unsigned.
Maybe use prefix, even though this means to references to i:
http://www.tantalon.com/pete/cppopt/...refixOperators
That applies to objects in C++, not to simple integer variables in C (or
probably C++). Also, I would be surprised to see any vaguely modern
compiler (a version released within the last 10 years) that produced
different code for i++ and ++i when used on an integer in a void context
(i.e. the value of the expression is not used).
haroon wrote:
the second loop statement should be read as:

for (i = 0; str[i] != '\0'; ++i) ;

sorry for inconvenience.

Haroon

--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.
Nov 21 '05 #16

P: n/a
Flash Gordon wrote:
da******@gmail.com wrote:


<original post in order>
haroon schrieb:
Hi,
I have two versions of a loop. I want to know which one is more
efficient. and is there any way to make it even more efficient?

1- for (i = 0; str[i++] != '\0';) ;

2- for (i = 0; str[] != '\0'; ++i) ;



it is more efficient with pointer

1) You response belongs *under* the text you are replying to, not above.
2) Have you proved his by measuring the performance of the code
generated by *all* compilers?
3) It is easy for a compiler to translate from the array version to the
pointer version and so the pointer version is unlikely to produce a
faster executable.
4) Many compilers will produce the same code whether you use pointer
arithmetic or arrays.


I /think/ he may be referring to the fact that an int is being
incremented, so you are doing increment then pointer arithmetic,
rather than incrementing a pointer. Of course this is a common
idiom that may well get optimised out anyway.

--
imalone
Nov 21 '05 #17

P: n/a
Ian Malone wrote:
Flash Gordon wrote:
da******@gmail.com wrote:


<original post in order>
>> haroon schrieb:
>>
>>> Hi,
>>> I have two versions of a loop. I want to know which one is more
>>> efficient. and is there any way to make it even more efficient?
>>>
>>> 1- for (i = 0; str[i++] != '\0';) ;
>>>
>>> 2- for (i = 0; str[] != '\0'; ++i) ;
>>
>>

>
>

it is more efficient with pointer


1) You response belongs *under* the text you are replying to, not above.
2) Have you proved his by measuring the performance of the code
generated by *all* compilers?
3) It is easy for a compiler to translate from the array version to the
pointer version and so the pointer version is unlikely to produce a
faster executable.
4) Many compilers will produce the same code whether you use pointer
arithmetic or arrays.


I /think/ he may be referring to the fact that an int is being
incremented, so you are doing increment then pointer arithmetic,
rather than incrementing a pointer. Of course this is a common
idiom that may well get optimised out anyway.


Addendum: there's no way to tell from the code given whether str is
declared as a pointer or an array anyway.

--
imalone
Nov 21 '05 #18

P: n/a

Flash Gordon wrote:
Maybe use prefix, even though this means to references to i:
http://www.tantalon.com/pete/cppopt/...refixOperators


That applies to objects in C++, not to simple integer variables in C (or
probably C++). Also, I would be surprised to see any vaguely modern
compiler (a version released within the last 10 years) that produced
different code for i++ and ++i when used on an integer in a void context
(i.e. the value of the expression is not used).


Interesting, I thought the two did produce different code, isn't this
true:

prefix op {
x = x + 1;
return x;
}

postfix op {
int tmp = x;
x = x + 1;
return tmp;
}

What does 'void context' mean and does this change the above code?

I'm new to this and would like to know whether I just wasted loads of
time changing my postfix to prefix in a futile attempt at optimisation!
TIA

Nov 21 '05 #19

P: n/a
On 2005-11-21, carl <nw*****@googlemail.com> wrote:

Flash Gordon wrote:
> Maybe use prefix, even though this means to references to i:
> http://www.tantalon.com/pete/cppopt/...refixOperators


That applies to objects in C++, not to simple integer variables in C (or
probably C++). Also, I would be surprised to see any vaguely modern
compiler (a version released within the last 10 years) that produced
different code for i++ and ++i when used on an integer in a void context
(i.e. the value of the expression is not used).


Interesting, I thought the two did produce different code, isn't this
true:

prefix op {
x = x + 1;
return x;
}

postfix op {
int tmp = x;
x = x + 1;
return tmp;
}

What does 'void context' mean and does this change the above code?


it means there's nowhere to return to, so no need to return. both would
become x = x + 1;
Nov 21 '05 #20

P: n/a
Ian Malone wrote:
Flash Gordon wrote:
da******@gmail.com wrote:
<original post in order>
>> haroon schrieb:
>>
>>> Hi,
>>> I have two versions of a loop. I want to know which one is more
>>> efficient. and is there any way to make it even more efficient?
>>>
>>> 1- for (i = 0; str[i++] != '\0';) ;
>>>
>>> 2- for (i = 0; str[] != '\0'; ++i) ; it is more efficient with pointer

<snip>
2) Have you proved his by measuring the performance of the code
generated by *all* compilers?
3) It is easy for a compiler to translate from the array version to the
pointer version and so the pointer version is unlikely to produce a
faster executable.
4) Many compilers will produce the same code whether you use pointer
arithmetic or arrays.


I /think/ he may be referring to the fact that an int is being
incremented, so you are doing increment then pointer arithmetic,
rather than incrementing a pointer.


I'm sure that was what he meant.
Of course this is a common
idiom that may well get optimised out anyway.


That was part of what I meant in points 3 and 4.
--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.
Nov 21 '05 #21

P: n/a
carl wrote:
Flash Gordon wrote:
Maybe use prefix, even though this means to references to i:
http://www.tantalon.com/pete/cppopt/...refixOperators That applies to objects in C++, not to simple integer variables in C (or
probably C++). Also, I would be surprised to see any vaguely modern
compiler (a version released within the last 10 years) that produced
different code for i++ and ++i when used on an integer in a void context
(i.e. the value of the expression is not used).


Interesting, I thought the two did produce different code,


They do when you *use* the value.
isn't this
true:

prefix op {
x = x + 1;
return x;
}

postfix op {
int tmp = x;
x = x + 1;
return tmp;
}
About right, although there are some subtleties, like there being no
guarantee when the increment occurs.
What does 'void context' mean and does this change the above code?
That means that you are not using the value.

int main(void)
{
int y;
int x=0;
y = x++; /* using the value, so it matters */
y = ++x; /* using the value, so it matters */
x++; /* not using the value, so how can you tell which occurred? */
++x; /* How can you tell if this did the same as the above or not? */
}

The subtlety I mentioned is that the increment can actually happen at
any time before the next sequence point, so things line ++i + ++i are
undefined, i.e. anything can happen. Check the comp.lang.c FAQ for details.
I'm new to this and would like to know whether I just wasted loads of
time changing my postfix to prefix in a futile attempt at optimisation!


1st rule of optimisation: don't do it.

You are not ready for the other rules yet, so just obey the first one
and right code that works.
--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.
Nov 21 '05 #22

P: n/a
"carl" <nw*****@googlemail.com> writes:
Flash Gordon wrote:
> Maybe use prefix, even though this means to references to i:
> http://www.tantalon.com/pete/cppopt/...refixOperators


That applies to objects in C++, not to simple integer variables in C (or
probably C++). Also, I would be surprised to see any vaguely modern
compiler (a version released within the last 10 years) that produced
different code for i++ and ++i when used on an integer in a void context
(i.e. the value of the expression is not used).


Interesting, I thought the two did produce different code, isn't this
true:

prefix op {
x = x + 1;
return x;
}

postfix op {
int tmp = x;
x = x + 1;
return tmp;
}

What does 'void context' mean and does this change the above code?

I'm new to this and would like to know whether I just wasted loads of
time changing my postfix to prefix in a futile attempt at optimisation!


A "void context" is a context in which an expression is evaluated only
for its side effects, with the actual result of the expression being
ignored.

"i++" yields the (previous) value of i; as a side effect, i is incremented.

"++i" yields the value of i+1; as a side effect, i is incremented.

If the result is used as part of a larger expression, such as
x = i++;
the compiler may need to use a temporary to hold the previous value of
i -- but since "x = i++;" and "x = ++i;" aren't semantically
equivalent, there's not much point in comparing their performance.

If the result is discarded, as in a statement context:
i++;
++i;
the expression *theoretically* yields the same result as it would in
any other context, but any decent compiler will be smart enough to
take advantage of the fact that the result isn't used. If a compiler
generated significantly different code for "i++;" and "++i;", it's
probably a bug.

Note that the first and third expression in a "for" statement also
provide a void context, so
for (i = 0; i < 10; i++) { ... }
and
for (i = 0; i < 10; ++i) { ... }
are equivalent -- and many programmers won't even notice the
difference when reading the code.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 21 '05 #23

P: n/a
In article <11**********************@z14g2000cwz.googlegroups .com>,
"haroon" <ha***********@gmail.com> wrote:
Hi,
I have two versions of a loop. I want to know which one is more
efficient. and is there any way to make it even more efficient?

1- for (i = 0; str[i++] != '\0';) ;

2- for (i = 0; str[] != '\0'; ++i) ;


Call strlen () instead.
Nov 21 '05 #24

P: n/a
In article <ce************@news.flash-gordon.me.uk>,
Flash Gordon <sp**@flash-gordon.me.uk> wrote:
da******@gmail.com wrote:
it is more efficient with pointer


1) You response belongs *under* the text you are replying to, not above.
2) Have you proved his by measuring the performance of the code
generated by *all* compilers?
3) It is easy for a compiler to translate from the array version to the
pointer version and so the pointer version is unlikely to produce a
faster executable.
4) Many compilers will produce the same code whether you use pointer
arithmetic or arrays.


5) Many compilers will produce faster code for arrays :-)

Seriously, on many C implementations calculating the address of an array
element comes for free (on PowerPC and x86 implementations), and the
array + index version has only one variable (i) that needs to be updated
instead of two (pointer and i).

Apart from that, a good strlen () implementation could beat the loop by
a considerable factor.
Nov 21 '05 #25

P: n/a
In article <11**********************@g47g2000cwa.googlegroups .com>,
"carl" <nw*****@googlemail.com> wrote:
Flash Gordon wrote:
Maybe use prefix, even though this means to references to i:
http://www.tantalon.com/pete/cppopt/...refixOperators


That applies to objects in C++, not to simple integer variables in C (or
probably C++). Also, I would be surprised to see any vaguely modern
compiler (a version released within the last 10 years) that produced
different code for i++ and ++i when used on an integer in a void context
(i.e. the value of the expression is not used).


Interesting, I thought the two did produce different code, isn't this
true:

prefix op {
x = x + 1;
return x;
}

postfix op {
int tmp = x;
x = x + 1;
return tmp;
}

What does 'void context' mean and does this change the above code?


It means the situation where you throw away the result. Implicit:

i++;
++i;

or explicit:

(void) i++;
(void) ++i;

The first one means: "Take i, increase it by one, take the original
value, throw it away". The second one means "Take i, increase it by one,
take the new value, throw it away". Any decent compiler will not produce
any code for "take the original value, throw it away" or "take the new
value, throw it away", so the only thing that remains is "take i,
increase it by one" in both cases.
Nov 21 '05 #26

This discussion thread is closed

Replies have been disabled for this discussion.