counting down or up is faster

Discussion in 'C Programming' started by sololoquist, Nov 20, 2006.

  1. sololoquist

    sololoquist Guest

    #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
     
    sololoquist, Nov 20, 2006
    #1
    1. Advertising

  2. sololoquist

    Tom St Denis Guest

    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
     
    Tom St Denis, Nov 20, 2006
    #2
    1. Advertising

  3. sololoquist

    santosh Guest

    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.
     
    santosh, Nov 20, 2006
    #3
  4. sololoquist

    Guest

    On Nov 20, 4:41 pm, "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?


    <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, 2006
    #4
  5. sololoquist

    Jack Klein Guest

    On 20 Nov 2006 03:41:22 -0800, "sololoquist"
    <> wrote 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/~ajo/docs/FAQ-acllc.html
     
    Jack Klein, Nov 20, 2006
    #5
  6. sololoquist

    Tor Rustad Guest

    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
     
    Tor Rustad, Nov 20, 2006
    #6
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. SirPoonga
    Replies:
    2
    Views:
    815
    Ben Strackany
    Jan 7, 2005
  2. Ulf Nordlund

    Counting down faster when looping?

    Ulf Nordlund, Feb 7, 2005, in forum: Java
    Replies:
    26
    Views:
    874
    Walter Mitty
    Feb 9, 2005
  3. Matt Chwastek
    Replies:
    6
    Views:
    545
    Michael Angelo Ravera
    Nov 20, 2006
  4. Bash

    Counting down to cookie expiration

    Bash, Feb 9, 2005, in forum: Javascript
    Replies:
    0
    Views:
    96
  5. edwardfredriks

    counting up instead of counting down

    edwardfredriks, Sep 6, 2005, in forum: Javascript
    Replies:
    6
    Views:
    235
    Dr John Stockton
    Sep 7, 2005
Loading...

Share This Page