Как реализовать развертывание цикла 2 во время выполнения в целях оптимизации
Рассмотрим некоторый код, который должен выполняться многократно где-то от 1 до 1 000 000 раз, и что количество повторов неизвестно во время компиляции. Насколько я понимаю, развертывание цикла будет незначительной оптимизацией, учитывая большое количество циклов, и будет оптимизировать только до max_unrolls, указанного во время компиляции. Идея, которую я придумала, состоит в том, чтобы реализовать бинарный (или базовый 2) частичный цикл развертывания, который по существу выполняет some_function многократно столько раз, сколько указано во время выполнения. Я придумал некоторый код, чтобы продемонстрировать идею, сокращенная версия показана ниже. Метод, используемый в приведенном ниже коде, имеет ряд проблем с точки зрения удобства использования.
- Это требует, чтобы кодер вручную скопировал развертывание базы 2, по существу, скопировал развертывание 2 ^ n-1 раз.
- Это также необходимо сделать заново для каждой новой функции, которая должна использовать этот метод.
мой вопрос это тройной. Во-первых, я что-то упускаю, компилятор уже достаточно умен, чтобы сделать это сам? Во-вторых, каков эффективный способ реализации этого, чтобы можно было сравнить его со стандартом? 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 */
}
Решение
Вы можете легко реализовать что-то подобное с помощью шаблонов C ++. Обратите внимание, что вы все еще находитесь в зависимости от вашего компилятора: нет гарантии, что все вызовы функций будут встроены. Если это не так, вы можете попробовать использовать __forceinline ключевое слово (или его эквивалент).
Прежде всего, вам нужен unroller который принимает функцию в качестве аргумента и выполняет ее К раз в полностью развернутом цикле. Вызов функции должен быть встроенным, поэтому вы должны использовать функторные объекты вместо указателей функций или 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 переменная (захваченная по ссылке) вместо этого она стала в несколько раз медленнее.
Так что, если вы действительно одержимы производительностью, я предлагаю использовать макросы для развертывания цикла, они абсолютно не увеличивают накладные расходы.
Другие решения
Других решений пока нет …