How to unroll a short loop in C++ using templates?

Question

I wonder how to get something like this

1 write

copy(a,b,2,3)

2 and then get,

a[2]=b[2]; 
a[3]=b[3];
a[4]=b[4];

I know that C #defines can't be used recursively to get that effect, so I suppose that template meta-programming is in place.

I know there is a boost library for that, but I only want that "simple" trick, and boost is too "messy".

Thank you

Answer 1

From http://www.sgi.com/tech/stl/Vector.html:

template <class InputIterator>
vector(InputIterator, InputIterator)

Creates a vector with a copy of a range. 

Does this do the job?

Answer 2

check this http://stackoverflow.com/questions/2380143/c-metaprograming-with-templates-versus-inlining

Answer 3

Andrey's link has all the details. You should be asking yourself, "Why do I want to do this? Do I think I'm smarter than the compiler when it comes to optimization?" (The answer is no.)

Answer 4

C++ meta-programming is recursive. Think of your problem in terms of recursion, implement terminal case and non-terminal cases. Your terminal case can be either 0 or one. pass limits as template parameters. use structure/class because they allow partial specialization and other neat things.

template<int from, int to>
struct copy {
static void apply(source, destination) {
  source[from] = destination[from];
  copy<from+1,to>:: apply(source, destination);
}
};

// terminal case
template<int from>
struct copy<from, from> {
static void apply(source, destination) {
  source[from] = destination[from];
}
};

Answer 5

You can probably do something like the following. Depending on your compiler and the optimziation settings that you use you may get the effect that you are looking for.

Be aware that for small objects like char it may well be slower than a std::copy or a memcpy and that for larger objects the cost of a loop is likely to be insignificant compared to the copies going on in any case.

#include <cstddef>

template<std::size_t base, std::size_t count, class T, class U>
struct copy_helper
{
    static void copy(T dst, U src)
    {
        dst[base] = src[base];
        copy_helper<base + 1, count - 1, T, U>::copy(dst, src);
    }
};

template<std::size_t base, class T, class U>
struct copy_helper<base, 0, T, U>
{
    static void copy(T, U)
    {
    }
};

template<std::size_t base, std::size_t count, class T, class U>
void copy(T dst, U src)
{
    copy_helper<base, count, T, U>::copy(dst, src);
}

template void copy<5, 9, char*, const char*>(char*, const char*);

#include <iostream>
#include <ostream>

int main()
{
    const char test2[] = "     , World\n";
    char test[14] = "Hello";

    copy<5, 9>(test, test2);

    std::cout << test;

    return 0;
}

Answer 6

The most straight forward solution to this is to write a loop where the start and end values are known

for(int i = 2; i <= 4; i++) {
  a[i]=b[i]; 
}

I think this is better than any sort of template/runtime-call mixture: The loop as written is completely clear to the compilers' optimizer, and there are no levels of function calls to dig through just to see what's going on.

Answer 7

It's important to realize that the compiler is very smart, and that tricking it to unroll loops using template metaprogramming will probably set you back further that it gets you forward.

To get the bottom out of your optimizations: keep an eye on the disassembly. This will hopefully teach you more than throwing templates at the problem.

And note, like Johannes said: if the compiler can see that you are running a loop for a fixed number of times (or a fixed multiple of times like 4x variable), it can create code very close to optimal.

Answer 8

It doesn't use templates and it's not a "complete" unrolling, but you can partially unroll the loop with something like this:

void copy (SomeType* a, SomeType* b, int start_index, int num_items) {
    int i = start_index;

    while (num_items > 4) {
            a[i+0] = b[i+0];
            a[i+1] = b[i+1];
            a[i+2] = b[i+2];
            a[i+3] = b[i+3];
            i += 4;
            num_items -= 4;
    }
    while (num_items > 0) {
            a[i] = b[i];
            ++i;
            --num_items;
    }
}

Now in this particular example, the extra computations involved will probably outweigh the benefits from only unrolling four elements at a time. You should get an increasing benefit from an increasing number of elements inside the top loop (throughout the function, replace 4 with however many elements you are copying inside each manually-unrolled iteration).

Answer 9

Obligatory reference to Duff's Device

Answer 10

Incidentally, the boost preprocessor library has something very similar to what you want: http://www.boost.org/doc/libs/1_37_0/libs/preprocessor/doc/examples/duffs_device.c