Как реализовать разворот цикла 2-го цикла во время выполнения в целях оптимизации

Question

Рассмотрите некоторый код, который нужно выполнить повторно в любом месте от 1 до 1000 000 раз, а количество повторений неизвестно во время компиляции. Я понимаю, что разворачивание цикла будет незначительной оптимизацией, учитывая большое количество циклов, и будет оптимизироваться только до max_unrolls, указанного во время компиляции. Идея, которую я придумал, состоит в том, чтобы реализовать двоичный (или базовый 2) неполный цикл, который по существу выполняет несколько раз несколько раз, что указано во время выполнения. Я придумал некоторый код, чтобы продемонстрировать эту идею, сжатая версия показана ниже. Метод, используемый в приведенном ниже коде, имеет ряд проблем с точки зрения удобства использования.

1. Требуется, чтобы кодер вручную скопировал базу 2 разворота, по существу, скопировал разворот 2^n-1 раз.
2. Это также необходимо переделать для каждой новой функции, которая должна использовать этот метод.

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

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

inline void some_reapeated_function(int &function_parameter_1, int &function_parameter_2) 
{ 
    function_parameter_1 /= function_parameter_2; 
} 

// Function to be called when you need it to be unrolled. 
int runtime_unroll(unsigned int &no_of_loops, int &function_parameter_1, int &function_parameter_2) 
{ 
    std::vector<bool> binary_vector; 

    // Stores the number of loops in a binary representation in a vector. 
    binary_function.reserve(no_of_loops); 
    while(no_of_loops) 
    { 
     if (no_of_loops&1) 
      binary_vector.push_back(false); 
     else 
      binary_vector.push_back(true); 
     no_of_loops>>=1; 
    } 

    // If binary of no_of_loops contains a 2^0 execute once. 
    if (binary_vector[0]) 
    { 
     some_reapeated_function(function_parameter_1,function_parameter_2); 
    } 
    // If binary of no_of_loops contains a 2^1 execute twice. 
    if (binary_vector[1]) 
    { 
     some_reapeated_function(function_parameter_1,function_parameter_2); 
     some_reapeated_function(function_parameter_1,function_parameter_2); 
    } 
    //If binary of no_of_loops contains a 2^2 execute 4 times. 
    if (binary_vector[2]) 
    { 
     some_reapeated_function(function_parameter_1,function_parameter_2); 
     some_reapeated_function(function_parameter_1,function_parameter_2); 
     some_reapeated_function(function_parameter_1,function_parameter_2); 
     some_reapeated_function(function_parameter_1,function_parameter_2); 
    } 


    /* This example only covers from 1 to 2^3-1 or up to 7 unrolls. 
    This can continue depending on the number of repetitions needed and 
    could incorporate a for loop to continue after the loop has fully unrolled */ 
} 

Answer 1

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

Прежде всего, вам нужно unroller который принимает функцию в качестве аргумента и выполняет его K раз в полностью развернутом цикле. Вызов функции должен быть встроен, поэтому вам нужно использовать объекты-объекты вместо указателей функций или std::function -s, а тип функтора должен быть шаблоном. Сам самокат может быть реализован как рекурсивный цикл с помощью аргумента целочисленного шаблона. Поскольку функции в C++ не могут иметь частичную специализированную специализацию, мы должны сделать наш разворот классом шаблона. Вот пример кода:

// execute UnrollCnt times in unrolled fashion 
template<int UnrollCnt, class Functor> struct Unroller { 
    static inline void Run(int base, const Functor &func) { 
     func(base); 
     Unroller<UnrollCnt - 1, Functor>::Run(base + 1, func); 
    } 
}; 
template<class Functor> struct Unroller<0, Functor> { 
    static inline void Run(int base, const Functor &func) { 
    } 
}; 

С учетом разворота мы можем легко реализовать развернутый контур. Если у нас есть N итераций, то мы можем позвонить нашему оператору [N/K] раз, а затем выполнить несколько оставшихся вызовов, как обычно. Обратите внимание, что тип функтора все равно должен быть шаблоном. Вот код:

// execute with argument in range [begin, end) 
template<int UnrollCnt, class Functor> 
void UnrolledFor(int begin, int end, const Functor &func) { 
    // iterations with unrolling 
    int iter = begin; 
    for (; iter <= end - UnrollCnt; iter += UnrollCnt) 
     Unroller<UnrollCnt, Functor>::Run(iter, func); 
    // last iterations without unrolling 
    for (; iter < end; iter++) 
     func(iter); 
} 

Теперь мы можем назвать цикл UnrolledFor для любой функции, принимающей один аргумент, являющийся счетчик цикла Петли в.Например, мы можем вычислить сумму чисел от к N-1:

long long ans = 0; 
int main() { 
    int cnt = 0; 
    scanf("%d", &cnt); 
    int start = clock(); 
    // note: passing a lambda function here, requesting 8x unrolling 
    UnrolledFor<8>(0, cnt, [](int i) { 
     ans += i; 
    }); 
    int elapsed = clock() - start; 
    printf("%lld (%d pg)\n", ans, elapsed); 
    return 0; 
} 

Примечания однако, что руководство разворачивание может работать намного быстрее, так как толстый уровень абстракции здесь не является тривиальным, чтобы сократить для компилятора. Например, вот некоторые тайминги я наблюдаю за образец кода (с N = 2000000000):

With MSVC 2013 x64: 
1999999999000000000 (421 pg) // 8x unrolling, ans is global 
1999999999000000000 (1389 pg) // 1x unrolling, ans is global 
1999999999000000000 (4664 pg) // 8x unrolling, ans is local 
1999999999000000000 (1388 pg) // 1x unrolling, ans is local 
With MinGW GCC 5.1.0 x64: 
1999999999000000000 (1388 pg) // 1x unrolling, ans is global 
1999999999000000000 (1404 pg) // 8x unrolling, ans is global 
1999999999000000000 (1389 pg) // 1x unrolling, ans is local 
1999999999000000000 (1393 pg) // 8x unrolling, ans is local 

Как вы видите, только MSVC с глобальной переменной ans на самом деле выиграть от разворачивания. Но с местной переменной ans (зафиксированной ссылкой) она получила несколько раз медленнее.

Итак, если вы действительно одержимы производительностью, я предлагаю использовать макросы для разворачивания циклов, они не добавляют абсолютно никаких накладных расходов.