Thread: unrolling strategies

You can do more than one iteration in a template instance... You could have a version that unrolls 10 copies inline, for instance, then multiply that out to get a lower template depth.

Loop unrolling is done to some degree by both by the compiler, and at run time by the processor, so make sure to profile to see if your changes actually make a difference.

Beware that if you unroll too much, the result won't fit in L1 cache any more. A branch in cache is likely to be less expensive than cache misses.

Also bear in mind that in some architectures with branch prediction, the cost of a successful guess is close to zero.

As ever, it is probably a good idea to start with a baseline of "simple" code which you can profile and benchmark. For one thing, optimisers are the most effective when the programmer isn't being too "clever" with the code.

Ad-hoc hackery without a consistent approach to measuring the result won't get you anywhere.

It is also important that you understand all the options a modern compiler has, before starting on your own hatchet jobs on the code.
Optimize Options - Using the GNU Compiler Collection (GCC)
Eg.

-fno-guess-branch-probability
Do not guess branch probabilities using heuristics. GCC will use heuristics to guess branch probabilities if they are not provided by profiling feedback (-fprofile-arcs). These heuristics are based on the control flow graph. If some branch probabilities are specified by `__builtin_expect', then the heuristics will be used to guess branch probabilities for the rest of the control flow graph, taking the `__builtin_expect' info into account. The interactions between the heuristics and `__builtin_expect' can be complex, and in some cases, it may be useful to disable the heuristics so that the effects of `__builtin_expect' are easier to understand.
The default is -fguess-branch-probability at levels -O, -O2, -O3, -Os.

When it comes to dealing with matricies you should make your code work smarter, not harder. It depends on what you're doing with those matricies, but there are algorithms out there that can perform multiplications quicker for example.
Loop unrolling gives you diminishing returns. The more you unroll, the less it is worth it. I suspect that in your polynomial case that the only reason you might have gotten anywhere near such an improvement is that you were unrolling multiple levels of nested loops, so the improvements compound. For such a large matrix though, I don't expect such massive unrolling to make that much improvement.

Originally Posted by m37h0d

hmm...the polynomials were definitely singly-looped.

the difference was essentially between:

Code:

double evaluate(double x)
{
    double result=0;
    for(int i=0;i<N;++i)
    {
        result+=pow(x,i)*coeff[i];
    }
    return result;
}

and

Code:

double eval(doublex)
{
    return x*x*x+polynomial<3>::coefficient+x*x+polynomial<2>::coefficient+x*polynomial<1>::coefficient+polynomial<0>::coefficient;
}

Oh that explains it! I wasn't going to say it but more than a 2x improvement through loop unrolling is next to impossible, so yeah I figured something was up. It turns out that probably 99% of the speed improvement you got there was from not using the very slow pow function! (well the speed of pow with an integer exponent does somewhat vary amoung compilers)
Aside from the obvious bug there with a few + instead of * in that code, you could make that even faster by avoiding a lot of multiplications, if you do it like this:

Code:

double eval(doublex)
{
    return x*(x*(x*polynomial<3>::coefficient+polynomial<2>::coefficient)+polynomial<1>::coefficient)+polynomial<0>::coefficient;
}

Only 3 multiplies!

Now you know that the speed improvement had not so much to do with loop unrolling, perhaps you'll reconsider loop unrolling at all with your matrix stuff huh!

Moving multiplies and adds around like that needs to be done with care, because it can yield very different results when the order of magnitude of the operands varies significantly.