Как развернуть короткий цикл в C++

Мета-программирование C ++ рекурсивно.

Подумайте о своей проблеме с точки зрения рекурсии. Реализуйте терминальные и нетерминальные случаи.

Ваш конечный случай может быть либо 0, либо 1. Пропускайте лимиты как параметры шаблона. Используйте структуру / класс, потому что они допускают частичную специализацию и другие полезные вещи:

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];
    }
};

Вы, вероятно, сможете сделать что-то вроде следующего. В зависимости от вашего компилятора и настроек оптимизации, которые вы используете, вы можете получить желаемый эффект.

Имейте в виду, что для небольших объектов, таких как char, он может быть медленнее, чем std :: copy или memcpy , и что для больших объектов стоимость цикла, вероятно, будет ниже. в любом случае быть незначительным по сравнению с копиями, происходящими в данный момент.

#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;
}

Важно понимать, что компилятор очень умен, и что обман его для разворачивания циклов с использованием метапрограммирования шаблонов, вероятно, отбросит вас назад и продвинет вперед .

Чтобы получить максимальную отдачу от ваших оптимизаций: следите за разборкой. Надеюсь, это научит вас чему-то большему, чем просто использовать шаблоны для решения проблемы.

И обратите внимание, как сказал Йоханнес: если компилятор видит, что вы выполняете цикл фиксированное количество раз (или фиксированное кратное количество раз, как переменная 4x), он может создать код, очень близкий к оптимальному.

В нем не используются шаблоны, и это не "полное" разворачивание, но вы можете частично развернуть цикл примерно так:

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;
    }
}

Теперь в этом конкретном примере дополнительные вычисления, вероятно, перевесят преимущества от разворачивания только четырех элементов за раз. Вы должны получать все большую выгоду от увеличения количества элементов внутри верхнего цикла (во всей функции замените 4 на то количество элементов, которое вы копируете внутри каждой итерации с ручным разворачиванием).

template <int begin, int end> struct copy_;

template <int end> struct copy_<end, end> {
  template <typename T> static void execute(T& a, T& b)
  {
    a[end] = b[end];
  }
};

template <int begin, int end> struct copy_<begin, end> {
  template <typename T> static void execute(T& a, T& b)
  {
    a[begin] = b[begin];
    copy_<begin+1, end>::execute(a, b);
  }
};

template <int begin, int how_many> struct copy {
  template <typename T> static void execute(T& a, T& b)
  {
    copy_<begin, begin+how_many-1>::execute(a, b);
  }
};

copy<2, 3>::execute(a, b);

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

template <class InputIterator>
vector(InputIterator, InputIterator)

Creates a vector with a copy of a range.