Faster for() loops?

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
Hi Folks,http://www.abarnett.demon.co.uk/tutorial.html#FASTFOR Page
states:for( i=0;  i<10;  i++){ ... }i loops through the values
0,1,2,3,4,5,6,7,8,9 If you don't care about the order of the loop counter,
you can do this instead: for( i10%; i--; ) { ... }Using this code, i loops
through the values 9,8,7,6,5,4,3,2,1,0, and the loop should be faster. This
works because it is quicker to process "i--" as the test condition, which
says "is i non-zero? If so, decrement it and continue.". For the original
code, the processor has to calculate "subtract i from 10. Is the result
non-zero? if so, increment i and continue.". In tight loops, this make a
considerable difference.
How far it holds true.. in the light of modern optimizing compilers? and
will it make a significant difference in case of embedded systems???

Thanks,
-Neo
"Do U really think, what U think real is really real?"



Re: Faster for() loops?
Hi,

[...] In tight loops, this make a
Quoted text here. Click to load it

There is nothing like an experiment to test a theory. I just tried with
AVRGCC

void countDown(void){
    int i;
    for(i10%; i!=0; i--) doSomething();
}
void countUp(void){
    int i;
    for(i=0;i<10;i++) doSomething();
}

The generated code is

000000ce <countDown>:
}

void countDown(void){
       ce:    cf 93           push    r28
       d0:    df 93           push    r29
    int i;
    for(i10%; i!=0; i--) doSomething();
       d2:    ca e0           ldi    r28, 0x0A    ; 10
       d4:    d0 e0           ldi    r29, 0x00    ; 0
       d6:    0e 94 5d 00     call    0xba
       da:    21 97           sbiw    r28, 0x01    ; 1
       dc:    e1 f7           brne    .-8          ; 0xd6
       de:    df 91           pop    r29
       e0:    cf 91           pop    r28
       e2:    08 95           ret

000000e4 <countUp>:
}
void countUp(void){
       e4:    cf 93           push    r28
       e6:    df 93           push    r29
       e8:    c9 e0           ldi    r28, 0x09    ; 9
       ea:    d0 e0           ldi    r29, 0x00    ; 0
    int i;
    for(i=0;i<10;i++) doSomething();
       ec:    0e 94 5d 00     call    0xba
       f0:    21 97           sbiw    r28, 0x01    ; 1
       f2:    d7 ff           sbrs    r29, 7
       f4:    fb cf           rjmp    .-10         ; 0xec
       f6:    df 91           pop    r29
       f8:    cf 91           pop    r28
       fa:    08 95           ret

Counting down instead of up saves one whole instruction. It could make a
difference I suppose.

However, the compiler cannot optimise as well if anything in the loop
depends on the value of 'i'.


void countDown(void){
    int i;
    for(i10%; i!=0; i--) doSomething(i);
}
void countUp(void){
    int i;
    for(i=0;i<10;i++) doSomething(i);
}

Becomes

void countDown(void){
       ce:    cf 93           push    r28
       d0:    df 93           push    r29
    int i;
    for(i10%; i!=0; i--) doSomething(i);
       d2:    ca e0           ldi    r28, 0x0A    ; 10
       d4:    d0 e0           ldi    r29, 0x00    ; 0
       d6:    ce 01           movw    r24, r28
       d8:    0e 94 5d 00     call    0xba
       dc:    21 97           sbiw    r28, 0x01    ; 1
       de:    d9 f7           brne    .-10         ; 0xd6
       e0:    df 91           pop    r29
       e2:    cf 91           pop    r28
       e4:    08 95           ret

000000e6 <countUp>:
}
void countUp(void){
       e6:    cf 93           push    r28
       e8:    df 93           push    r29
    int i;
    for(i=0;i<10;i++) doSomething(i);
       ea:    c0 e0           ldi    r28, 0x00    ; 0
       ec:    d0 e0           ldi    r29, 0x00    ; 0
       ee:    ce 01           movw    r24, r28
       f0:    0e 94 5d 00     call    0xba
       f4:    21 96           adiw    r28, 0x01    ; 1
       f6:    ca 30           cpi    r28, 0x0A    ; 10
       f8:    d1 05           cpc    r29, r1
       fa:    cc f3           brlt    .-14         ; 0xee
       fc:    df 91           pop    r29
       fe:    cf 91           pop    r28
      100:    08 95           ret

This time there are a whole 2 extra instructions. I don't think this is
such a big deal. Unrolling the loop would give a better result.

cheers,

Al

Re: Faster for() loops?

Quoted text here. Click to load it

Many micros have a decrement jmp if zero (or non zero) machine instruction
so a decent optimising compiler should know this and use it in count down
to zero loops. Counting up often needs a compare followed by a jmp zero (or
non zero) which will be a tad slower.

Ian


Re: Faster for() loops?
Quoted text here. Click to load it

The answer is "implementation-dependent".

A major advantage of writing in C is that you can, if you choose, write
understandable, maintainable code. This kind of hand-optimisation has the
opposite effect. If you really need to care about exactly how many
instruction cycle a loop takes, code it in assembly language. Otherwise, for
the sake of those that come after you, please write your C readably and
leave the compiler to do the optimisation. These days, most compilers can
optimise almost as well as you can, for most "normal" operations.

Regards,
--
Peter Bushell
http://www.software-integrity.com /



Re: Faster for() loops?

Quoted text here. Click to load it

Question: How can I optimise code better than the compiler?
Answer: If you ask, then you can't.

Re: Faster for() loops?
Quoted text here. Click to load it
Regardless of the performance issue, I'd like to point out that after
for( i10%; i--; ) finishes, i will have the value -1, since the
decrement is performed even if i is zero. This is counterintuitive, so
it's worth noting. It also means the following is not equivalent:

for (i = 10; i != 0; --i)

Since here one less decrement is performed. Incidentally, my
compiler/platform generates better code with this version -- it compares
i to -1 in the other, which is no better than comparing it to 10! If you
want to count down, I suggest writing what you mean and separating the
test and decrement parts -- it has the added bonus of making things more
readable. The rest is best left to the compiler.

S.

Re: Faster for() loops?
Neo wrote On 09/25/05 23:41,:
Quoted text here. Click to load it

Unroll it completely.


Re: Faster for() loops?

Quoted text here. Click to load it

It may or not save a couple of assembly language instructions, (of
course depending on the compiler and processor used,) but I doubt this
"noptimization" will make any noticeable change in the performance of
a program, unless your code consist mainly of empty for() loops.

What impact can a minuscule reduction in the time required to decide
if the loop has ended or not have, if the body of the loop, for
example, call functions that format a CAN message, deliver it, wait
for a response, retry if there were errors or timeouts, decode the
response, store the values in a serial EEPROM, and based on them start
a few motors, open pneumatic valves, optionally sending an email
message to Katmandu.

That is not an optimization, but a total waste of time. Read the first
example in "Elements of programming style" and learn...

Roberto Waltman

[ Please reply to the group, ]
[ return address is invalid. ]

Re: Faster for() loops?
Quoted text here. Click to load it

What if the difference is between fitting into memory and not?





Re: Faster for() loops?
Quoted text here. Click to load it

The subject line was "faster for() loops", not "smaller and/or more
memory efficient for() loops"

If you must shoehorn code into a microcontroller memory that is one
size too small, you do what you need to do.
But I would look somewhere else first:
* Are there libraries including code that will never be used?
* Is there common code that could be factored into functions?
* Are there text messages that could be shortened?
* Are there any compiler options that could produce smaller code?
* Is there a better compiler available?
* If the problem is RAM, can smaller data types be used, (pack
structures, use char instead of int for small values, etc.)
* etc.

[Dropping x-post to comp.lang.c]


Roberto Waltman

[ Please reply to the group, ]
[ return address is invalid. ]

Re: Faster for() loops?
I think I disagree.

If you can fit something into a cheaper processor model because you save a
couple of bytes by changing 1 or two loops, then you are not in trouble
anymore.


Quoted text here. Click to load it



Re: Faster for() loops?

Don't top post. Replies belong after the text you are replying to.

Quoted text here. Click to load it

Don't include peoples signatures unless you are commenting on them.

 > I think I disagree.
 >
 > If you can fit something into a cheaper processor model because you
 > save a couple of bytes by changing 1 or two loops, then you are not in
 > trouble anymore.

I'll be more explicit then. EVERY SINGLE TIME I have come across a
system where people have tried to squeeze the code in believing it will
just about fit (either size or speed) one of the following has happened:

1) Customer required a subsequent change which proved to be impossible
    unless the card was redesigned because there was no space for the new
    code.
2) A bug fix requires some additional code and oops, there is no more
    space.
3) By the time all the required stuff was added that the person who
    thought it would only just fit had forgotten it did NOT fit by a mile
    so it did not even come close to meeting the customers requirements
4) It turned out there were massive savings to be had else where because
    of higher level problems allowing me to save far more space/time than
    you could possibly save by such micro-optimisations.

Only with the third of those possibilities was it possible to meet the
requirements using the existing hardware, and meeting the requirements
involved fixing the algorithms or doing large scale changes where the
coding was just plain atrocious.

So my experience is that it is never worth bothering with such
micro-optimisations.
--
Flash Gordon
Living in interesting times.
We've slightly trimmed the long signature. Click to see the full one.
Re: Faster for() loops?
OK, point taken.  Although, when working with very small memories, it can
make all the difference if a byte can be saved here and there.  Afterall, 50
such 'optimisations' could amount to 10% of the total memory available.  I'm
not necessarily suggesting this should be done from day 1, but have found it
useful just to get a feel for what the compiler works best with.

Quoted text here. Click to load it



Re: Faster for() loops?

Quoted text here. Click to load it

[snip]
 
Quoted text here. Click to load it


You need to get the other point, the one about not top-posting.



Brian

Re: Faster for() loops?
prick.

Quoted text here. Click to load it



Re: Faster for() loops?
Quoted text here. Click to load it

I'm going to make one and only one attempt to make this clear to you.
It's arguably more than you deserve, but if you improve your posting
habits it will benefit all of us.  If not, we can achieve the same
benefit by killfiling you -- which I'm sure many people already have.

We don't discourage top-posting because we like to enforce arbitrary
rules.  We do so because top-posting makes articles more difficult to
read, especially in an environment like this one where bottom-posting
is a long-standing tradition.  (In other words, top-posting in an
environment where it's commonly accepted is ok; top-posting where it's
not commonly accepted makes *your* article more difficult to read
because we have to make an extra effort to read a different format.)

Usenet is an asynchronous medium.  Parent articles can arrive after
followups, or not arrive at all.  It's important for each individual
article to be readable by itself, from top to bottom, providing as
much context as necessary from previous articles.  It's not reasonable
to expect your readers to jump around within your article to
understand what you're talking about.

Quoting one of CBFalconer's sig quotes:

A: Because it fouls the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

See also <http://www.caliburn.nl/topposting.html .

I'm giving you good advice.  You can believe me and follow it, or you
can ignore it and never be taken seriously here again.  It's your
call.

--
Keith Thompson (The_Other_Keith) snipped-for-privacy@mib.org  <http://www.ghoti.net/~kst
San Diego Supercomputer Center             <*>  <http://users.sdsc.edu/~kst
We've slightly trimmed the long signature. Click to see the full one.
Re: Faster for() loops?

Quoted text here. Click to load it

<big snip>

Quoted text here. Click to load it

See http://alpage.ath.cx/toppose/toppost.htm as well.

Thanks,

Al



Re: Faster for() loops?

Quoted text here. Click to load it

Oops. I can't spell.

Make that http://alpage.ath.cx/toppost/toppost.htm

Al

Re: Faster for() loops?
On Wed, 28 Sep 2005 12:24:54 +1000, in comp.lang.c , Al Borowski

Quoted text here. Click to load it

For what its worth, arguments based on threading are bunk. Thread
members  arrive out-of-order, not at all, and disappear from servers.

And arguments based on catering for cretinous users who're too thick
to snip are hardly likely to impress smart people...

I slightly agree with your conclusions tho. I'd modify (1) and (2) as
follows

1) Top Post (and totally remove the old message) if you are only
making 1 brief point which has no relation to any of the old message.
And then ask yourself why the hell you're replying to this post with
an irrelevant remark.

2) otherwise middle post

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html
We've slightly trimmed the long signature. Click to see the full one.
Re: Faster for() loops?
[...]
Quoted text here. Click to load it

Top-posting is posting new text *above* any quoted text; if there is
no quoted text, it's not top-posting (or at best it's a degenerate
case that could as easily be called bottom-posting or middle-posting).
What you're describing is, or should be, simply posting a new article.

Quoted text here. Click to load it

--
Keith Thompson (The_Other_Keith) snipped-for-privacy@mib.org  <http://www.ghoti.net/~kst
San Diego Supercomputer Center             <*>  <http://users.sdsc.edu/~kst
We've slightly trimmed the long signature. Click to see the full one.

Site Timeline