counting down or up is faster

S

sololoquist

#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
 
T

Tom St Denis

sololoquist said:
#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
 
S

santosh

sololoquist said:
#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.
 
J

junky_fellow

#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>
 
J

Jack Klein

#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".
 
T

Tor Rustad

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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top