Loop unrolling question. Does this make sense?

[John Edwards]

Hello,

I have sort of a newbie question. I'm trying to optimize a loop by
breaking it into two
passes.

Example:

for(i = 0; i < max; i++)
{
do this
and this
}

(The value of max is not known)

I want to change it to this:

for(i = 0; i < max /2; i++)
{
do this
and this
}
for(i = max /2; i < max; i++)
{
do this
and this
}


Does this make sense and will I get anything out of it?

[Victor Bazarov]

Re: Loop unrolling question. Does this make sense?

"John Edwards" <sales@caselear ning.com> wrote...[color=blue]
> I have sort of a newbie question. I'm trying to optimize a loop by
> breaking it into two
> passes.
>
> Example:
>
> for(i = 0; i < max; i++)
> {
> do this
> and this
> }
>
> (The value of max is not known)
>
> I want to change it to this:
>
> for(i = 0; i < max /2; i++)
> {
> do this
> and this
> }
> for(i = max /2; i < max; i++)
> {
> do this
> and this
> }
>
>
> Does this make sense and will I get anything out of it?[/color]

No, you will not. You might be able to get something out of

if (max & 1)
{
do this
and this
}
for (i = 0; i < max/2; ++i)
{
do this
and this
do this
and this
}

Of course, if 'do this and this' uses 'i' somehow, it may not
be worth unrolling, since any arithmetic will chew up any time
you save by unrolling.

Victor

[Sam Holden]

Re: Loop unrolling question. Does this make sense?

On Sun, 06 Jul 2003 20:06:24 GMT, John Edwards <sales@caselear ning.com> wrote:[color=blue]
> Hello,
>
> I have sort of a newbie question. I'm trying to optimize a loop by
> breaking it into two
> passes.
>
> Example:
>
> for(i = 0; i < max; i++)
> {
> do this
> and this
> }
>
> (The value of max is not known)
>
> I want to change it to this:
>
> for(i = 0; i < max /2; i++)
> {
> do this
> and this
> }
> for(i = max /2; i < max; i++)
> {
> do this
> and this
> }
>
>
> Does this make sense and will I get anything out of it?[/color]

Not really and it will run slower.

Loop unrolling looks like:

for(i=0;i<max;i +=2)
{
do this
and this
do this
and this
}

If i is more than just a loop counter, then the i+=2 might change to ++i
with a ++i inside the loop body as well.

Of course this will do awful things for an odd length max, and two instances
of the loop body isn't going to achieve much (especially when the check for
odd max overhead is added).

Don't even think of unrolling a loop until the loop has been shown to
actually be contributing to unsatisfactory performance. And then benchmark
before and after, since you can slow things down (by a lot if the code of
the body (and loop overhead) now doesn't fit in cache on architectures
which have such things - which I suspect is almost all architectures in
which you would be trading code space for code speed in that direction).

--
Sam Holden

[Victor Bazarov]

Re: Loop unrolling question. Does this make sense?

"John Edwards" <sales@caselear ning.com> wrote...[color=blue]
> So what you're saying is that unless they are using 'i', it may not be[/color]
worth[color=blue]
> it?[/color]

No, I said exactly the opposite.
[color=blue]
>
> 'Do this & that' is actually doing writes for vector graphics.
>
>
>
>
>
> "Victor Bazarov" <v.Abazarov@att Abi.com> wrote in message
> news:vgh0t5ilp2 4j9c@corp.super news.com...[color=green]
> > "John Edwards" <sales@caselear ning.com> wrote...[color=darkred]
> > > I have sort of a newbie question. I'm trying to optimize a loop by
> > > breaking it into two
> > > passes.
> > >
> > > Example:
> > >
> > > for(i = 0; i < max; i++)
> > > {
> > > do this
> > > and this
> > > }
> > >
> > > (The value of max is not known)
> > >
> > > I want to change it to this:
> > >
> > > for(i = 0; i < max /2; i++)
> > > {
> > > do this
> > > and this
> > > }
> > > for(i = max /2; i < max; i++)
> > > {
> > > do this
> > > and this
> > > }
> > >
> > >
> > > Does this make sense and will I get anything out of it?[/color]
> >
> > No, you will not. You might be able to get something out of
> >
> > if (max & 1)
> > {
> > do this
> > and this
> > }
> > for (i = 0; i < max/2; ++i)
> > {
> > do this
> > and this
> > do this
> > and this
> > }
> >
> > Of course, if 'do this and this' uses 'i' somehow, it may not
> > be worth unrolling, since any arithmetic will chew up any time
> > you save by unrolling.
> >
> > Victor
> >
> >[/color]
>
>[/color]

[Artie Gold]

[OT] Re: Loop unrolling question. Does this make sense?

John Edwards wrote:[color=blue]
> Hello,
>
> I have sort of a newbie question. I'm trying to optimize a loop by
> breaking it into two
> passes.
>
> Example:
>
> for(i = 0; i < max; i++)
> {
> do this
> and this
> }
>
> (The value of max is not known)
>
> I want to change it to this:
>
> for(i = 0; i < max /2; i++)
> {
> do this
> and this
> }
> for(i = max /2; i < max; i++)
> {
> do this
> and this
> }
>
>
> Does this make sense and will I get anything out of it?
>[/color]

Unfortunately, you seem not to have a real understanding of what loop
unrolling is. May I refer you to the following link?

http://users.chariot.net.au/~matty/ultra/optcat/Loop_Unrolling.html

BTW -- your question is really not topical here (as, at its heart, it is
not a question about the C++ language).

Your compiler may have an optimization option to unroll loops (see your
documentation); in any event, micro-optimizations at the source code
level should only be performed if you have empirically determined (by,
e.g. profiling) that a particular piece of code is causing a bottleneck.

HTH,
--ag


--
Artie Gold -- Austin, Texas



----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---

[Thomas Matthews]

Re: Loop unrolling question. Does this make sense?

John Edwards wrote:[color=blue]
> Hello,
>
> I have sort of a newbie question. I'm trying to optimize a loop by
> breaking it into two
> passes.
>
> Example:
>
> for(i = 0; i < max; i++)
> {
> do this
> and this
> }
>
> (The value of max is not known)
>
> I want to change it to this:
>
> for(i = 0; i < max /2; i++)
> {
> do this
> and this
> }
> for(i = max /2; i < max; i++)
> {
> do this
> and this
> }
>
>
> Does this make sense and will I get anything out of it?[/color]

The standard technique of loop unrolling is to
repeat the statements inside the loop and adjusting
the counter; not to repeate the loops.

The goal is to divide the cost (overhead) of updating
and comparing the indices over the cost of the statements.
For example, repeating the inner block twice will reduce
the overhead cost by 1/2.

Be aware that the number of iterations must be evenly
divisible by the number of statement repetitions.

Guide to Optimization
---------------------
1. Don't. Get the program working correctly first.
2. Don't. Use a profiler and analyze the program execution.
The 80/20 rule states that 80% of the program's execution
occurs in 20% of the code.
3. Review function designs. A lot of execution gain can
be obtained at the design level. Remove unused functions,
operations, data and code. Simplify repetitive operations.
Don't process data unless required to do so (lazy processing).
4. Inline function calls for small sized functions. If the
content of the function is smaller or slightly larger than
the overhead of the function call, inline it.
5. Factor out constant expressions and statements from loops.
6. Review floating point operational costs. Some processors
choke on fp operations, some have no extra cost. If there
is a penalty (or additional cost) keep everything as integers
until the last moment.
7. Unroll loops, if you have the code space.
8. Replace function contents with assembly language. Write
the assembly language function to take advantage of any
special (helpful) processor features, such as pipelining
or caches.

--
Thomas Matthews

C++ newsgroup welcome message:

http://www.slack.net/~shiva/welcome.txt

C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.l earn.c-c++ faq:

http://www.raos.demon.uk/acllc-c++/faq.html

Other sites:
http://www.josuttis.com -- C++ STL Library book