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

counting down or up is faster

P: n/a
#define COUNT_UP
#include <stdio.h>

#define N 10
int main()
{
int i;

#ifdef COUNT_UP
for (i = 0; i < N; i++)
#else
for (i = N; i 0; i--)
#endif
printf("hello \n");
}
assuming everything as same except the for loops and if variable i 's
usage has no problem with up or down counting which is faster?
does that depend on
1. incl or decl for a particular machine that too if they exist
2. whether there is usage of assembly stmt loop which counts using ecx
register for counting down even if it is there is it faster
I tried it by calling time() with N 1000 and result favoured UP but
then next time DOWN won.
i couldn't go any further. thanx for your time

Nov 20 '06 #1
Share this Question
Share on Google+
5 Replies


P: n/a
sololoquist wrote:
#ifdef COUNT_UP
for (i = 0; i < N; i++)
#else
for (i = N; i 0; i--)
#endif
printf("hello \n");
}
2. whether there is usage of assembly stmt loop which counts using ecx
register for counting down even if it is there is it faster
I tried it by calling time() with N 1000 and result favoured UP but
then next time DOWN won.
i couldn't go any further. thanx for your time
It's really up to the compiler. since N is known at compile time the
compiler may fully unroll the loop, since you never read i other than
in the for loop it may actually count down [or up] depending on the
platform...

With GCC 4.1.1 on my x86_64 box it does just that (with -O3
-fomit-frame-pointer). With "-O2" I get

movl $.LC0, %edi
decl %ebx
call puts
cmpl $-1, %ebx
jne .L2
popq %rbx
ret

for count down, and,

movl $.LC0, %edi
incl %ebx
call puts
cmpl $10, %ebx
jne .L9
popq %rbx
ret

For count up. Which for the benefit of others is basically the same
opcodes, just one version increments the other decrements.

In short, what you are talking about is a micro-optimization that
depends entirely on the compiler and platform. Some platforms like the
8051 like the decrement approach (DJNZ instruction) but others like the
x86 don't care.

Tom

Nov 20 '06 #2

P: n/a
sololoquist wrote:
#define COUNT_UP
#include <stdio.h>

#define N 10
int main()
{
int i;

#ifdef COUNT_UP
for (i = 0; i < N; i++)
#else
for (i = N; i 0; i--)
#endif
printf("hello \n");
}
assuming everything as same except the for loops and if variable i 's
usage has no problem with up or down counting which is faster?
Program optimisation and speed of code execution are not specified in
the C standard. All other things being equal, this will depend on the
relative speed of the implementation of post-increment and
post-decrement operators. There's likely to be no noticeble difference.

Nov 20 '06 #3

P: n/a


On Nov 20, 4:41 pm, "sololoquist" <excuse_me_who_a...@yahoo.co.in>
wrote:
#define COUNT_UP
#include <stdio.h>

#define N 10
int main()
{
int i;

#ifdef COUNT_UP
for (i = 0; i < N; i++)
#else
for (i = N; i 0; i--)
#endif
printf("hello \n");

}assuming everything as same except the for loops and if variable i 's
usage has no problem with up or down counting which is faster?
<OT>I believe the answer is implementation specific.
My answer is also implementation specific.
I have worked on ARM based board. I got some documents from the ARM
site
that describes how to write efficient programs.
That document says that "compare with zero" could be optimised and may
be faster in some cases (like down counting loops).

I am cutting and pasting that section from that document.

The loop termination condition can cause significant overhead if
written without caution.
You should always write count-down-to-zero loops and use simple
termination conditions.
Take the following two sample routines, which calculate n!. The first
implementation uses
an incrementing loop, the second a decrementing loop.
int fact1 (int n)
{ int i, fact = 1;
for (i = 1; i <= n; i++)
fact *= i;
return (fact);
}
int fact2 (int n)
{ int i, fact = 1;
for (i = n; i != 0; i--)
fact *= i;
return (fact);
}

The following code is produced:
fact1
MOV a3,#1
MOV a2,#1
CMP a1,#1
BLT |L000020.J5.fact1|
|L000010.J4.fact1|
MUL a3,a2,a3
ADD a2,a2,#1
CMP a2,a1
BLE |L000010.J4.fact1|
|L000020.J5.fact1|
MOV a1,a3
MOV pc,lr
fact2
MOVS a2,a1
MOV a1,#1
MOVEQ pc,lr
|L000034.J4.fact2|
MUL a1,a2,a1
SUBS a2,a2,#1
BNE |L000034.J4.fact2|
MOV pc,lr

You can see that the slight recoding of fact1 required to produce fact2
has caused the
original ADD/CMP instruction pair to be replaced a single SUBS
instruction. This is because
a compare with zero could be optimized away, as described in 5.2
Compares with zero
on page 11.
In addition to saving an instruction in the loop, the variable n does
not need to be saved
across the loop, so a register is also saved. This eases register
allocation, and leads to
more efficient code elsewhere in the function (two more instructions
saved).
This technique of initializing the loop counter to the number of
iterations required, and then
decrementing down to zero, also applies to while and do statements.
</OT>

Nov 20 '06 #4

P: n/a
On 20 Nov 2006 03:41:22 -0800, "sololoquist"
<ex****************@yahoo.co.inwrote in comp.lang.c:
#define COUNT_UP
#include <stdio.h>

#define N 10
int main()
{
int i;

#ifdef COUNT_UP
for (i = 0; i < N; i++)
#else
for (i = N; i 0; i--)
#endif
printf("hello \n");
}
assuming everything as same except the for loops and if variable i 's
usage has no problem with up or down counting which is faster?
Each of them is faster than the other.
does that depend on
1. incl or decl for a particular machine that too if they exist
No.
2. whether there is usage of assembly stmt loop which counts using ecx
register for counting down even if it is there is it faster
Most of the platforms I code in C for these days, and all of the ones
I write the most code for, don't have an "ecx".
I tried it by calling time() with N 1000 and result favoured UP but
then next time DOWN won.
i couldn't go any further. thanx for your time
The C standard does not care. Why do you?

Have you finished writing and testing a program that correctly meets
all its requirements, and then found it was too slow? If so, have you
used a profiler or other tool and identified this particular use of a
loop index to be one of the serious bottlenecks?

If so, then try setting N to 100,000 and running it each way 1000
times, and see if there is a statistically significant difference in
the times.

More likely you are worried about nothing. Wikipedia is not always
the best source for information, but their page on optimization looks
reasonable. See this page:

"http://en.wikipedia.org/wiki/Optimization_(computer_science)"

Pay particular attention to the sections titled "Bottlenecks", "When
to optimize", and "Quotes".

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://c-faq.com/
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html
Nov 20 '06 #5

P: n/a
sololoquist skrev:
#define COUNT_UP
#include <stdio.h>

#define N 10
int main()
{
int i;

#ifdef COUNT_UP
for (i = 0; i < N; i++)
#else
for (i = N; i 0; i--)
#endif
printf("hello \n");
}
[...]
I tried it by calling time() with N 1000 and result favoured
UP but then next time DOWN won.
time() measure the wallclock, while clock()
measure the CPU time!

:-)

Under a modern OS, you measured not only how much
time your program spent, but the kernel time, task
switches etc.

However, like others have told you... leave such
micro-optimizations to the C compiler, they are
normally quite good at it.

--
Tor

Nov 20 '06 #6

This discussion thread is closed

Replies have been disabled for this discussion.