gcc: Optimization levels and templates

Analyzing the assembly output for template devices can be a bit discouragging at times, specially when we spend hours trying to tune a mean looking template class only to find out the compiler is not able to reduce it's value like we expected. But hold on, before throwing all your templates away you might want to figure out why they are not optimized.

Let's start with a simple example: a template device to return the next power of 2:

template <int n, long curr_pow, bool stop>
struct Impl_Next_POW2 {
    static const bool is_smaller = n < curr_pow;
    static const long next_pow = _Next_POW2<n, curr_pow*2, is_smaller>::pow;
    static const long pow = is_smaller? curr_pow : next_pow;
};

template <int n, long curr_pow>
struct Impl_Next_POW2<n, curr_pow, true> {
    // This specializtion is important to stop the expansion
    static const long pow = curr_pow;
};

template <int n>
struct Next_POW2 {
    // Just a wrapper for _Next_POW2, to hide away some
    // implementation details
    static const long pow = _Next_POW2<n, 1, false>::pow;
};

Gcc can easily optimize that away, if you compile with "g++ foo.cpp -c -S -o /dev/stdout" you'll just see the whole thing is replaced by a compile time constant. Let's make gcc's life a bit more complicated now:

template <int n, long curr_pow, bool stop>
struct Impl_Next_POW2 {
    static long get_pow() {
        static const bool is_smaller = n < curr_pow;
        return is_smaller?
                    curr_pow :
                    _Next_POW2<n, curr_pow*2, is_smaller>::get_pow();
    }
};

template <int n, long curr_pow>
struct Impl_Next_POW2<n, curr_pow, true> {
    static long get_pow() {
        return curr_pow;
    }
};

template <int n>
struct Next_POW2 {
    static long get_pow() {
        return _Next_POW2<n, 1, false>::get_pow();
    }
};

Same code but instead of using plain static values we wrap everything in a method. Compile with "g++ foo.cpp -c -S -fverbose-asm -o /dev/stdout | c++filt" and you'll see something like this now:

main:
    call    Next_POW2<17>::get_pow()

Next_POW2<17>::get_pow():
    call    _Next_POW2<17, 1l, false>::get_pow()

_Next_POW2<17, 1l, false>::get_pow():
    call    _Next_POW2<17, 2l, false>::get_pow()

_Next_POW2<17, 2l, false>::get_pow():
    call    _Next_POW2<17, 4l, false>::get_pow()

_Next_POW2<17, 4l, false>::get_pow():
    call    _Next_POW2<17, 8l, false>::get_pow()

_Next_POW2<17, 8l, false>::get_pow():
    call    _Next_POW2<17, 16l, false>::get_pow()

_Next_POW2<17, 16l, false>::get_pow():
    call    _Next_POW2<17, 32l, false>::get_pow()

_Next_POW2<17, 32l, false>::get_pow():
    movl    $32, %eax    #, D.2171

What went wrong? It's very clear for us the whole thing is just a chain of calls which could be replaced by the last one, however that information is now only available if you "inspect" the body of each function, and this is something the template instanciator (at least in gcc) can't do. Luckily you just need to enable optimizations, -O1 is enough, to have gcc output the reduced version again.

Keep it in mind for the next time you're optimizing your code with template metaprogramming: some times the template expander needs some help from the optimizer too.