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

Question

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

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 ключевое слово (или его эквивалент).

Прежде всего, вам нужен размотчик, который принимает функцию в качестве аргумента и выполняет ее 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 цикл для любой функции, принимающей один аргумент, являющийся счетчиком итераций цикла. Например, мы можем вычислить сумму чисел от 0 до 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 переменная (захваченная по ссылке) вместо этого она стала в несколько раз медленнее.

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