454,497 Members | 2,497 Online
+ 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
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" 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 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 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: 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: >> 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 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: >> 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 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" 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 San Diego Supercomputer Center <*> 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" 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 , Flash Gordon 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" 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.