John said:
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?
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.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book