Разница в производительности развертки цикла C ++ (Project Euler)
У меня есть вопрос по поводу вопроса Project Euler и оптимизации с использованием циклического развертывания.
Описание проблемы:
2520 — это наименьшее число, которое можно разделить на каждое из чисел от 1 до 10 без остатка. Какое наименьшее положительное число равномерно делится на все числа от 1 до 20?
Решение:
#include <iostream>
#include <limits.h>
#include <stdio.h>
#include <time.h>
using namespace std;
int main() {
clock_t startTime = clock();
for (int i = 1; i < INT_MAX; i++)
{
bool isDivisible = true;
//CODE BLOCK #1
/*for (int j = 2; j <= 20; j++)
{
if ( i % j != 0)
{
isDivisible = false;
break;
{
}*/
//CODE BLOCK #2
/*if (i % 2 != 0 || i % 3 != 0 ||
i % 4 != 0 || i % 5 != 0 ||
i % 6 != 0 || i % 7 != 0 ||
i % 8 != 0 || i % 9 != 0 ||
i % 10 != 0 || i % 11 != 0 ||
i % 12 != 0 || i % 13 != 0 ||
i % 14 != 0 || i % 15 != 0 ||
i % 16 != 0 || i % 17 != 0 ||
i % 18 != 0 || i % 19 != 0 ||
i % 20 != 0 )
isDivisible = false;*/
if (isDivisible)
{
cout << "smallest: " << i << endl;
cout << "Ran in: " << clock() - startTime << " cycles" << endl;
break;
}
}
return 0;
}
Теперь, комментируя CODE BLOCK # 1 или CODE BLOCK # 2, я получаю правильный ответ (232792560). Однако CODE BLOCK # 2 намного быстрее, чем CODE BLOCK # 1.
БЛОК КОДА № 1: 3 580 000 циклов (я только добавил разрыв в БЛОК КОДА № 1, и он работает намного быстрее. Однако все же значительно медленнее, чем составной оператор IF.)
КОД БЛОКА № 2: 970 000 циклов
Кто-нибудь знает, почему может возникнуть такая огромная разница в производительности?
Решение
С использованием || означает, что, как только одно из них верно, остальные условия не вычисляются. Это было бы эквивалентно циклу:
for (int j = 2; j <= 20; j++)
{
if ( i % j != 0){
isDivisible = false;
break;
}
}
Если вы попробуете это, вы обнаружите, что разрыв во времени выполнения сократился. Любые другие различия могут быть отнесены к издержкам цикла, но с включенной оптимизацией в вашем компиляторе, я подозреваю, что они будут работать с той же скоростью (или, по крайней мере, иметь гораздо больше похожего времени).
РЕДАКТИРОВАТЬ О новой разнице в производительности:
Существует много оптимизированных способов проверки делимости чисел на константы, например, для N любая сила 2 i % N != 0 можно заменить на i & (N-1)другие тоже существуют и не так очевидны.
Компилятор знает множество этих маленьких трюков и, вероятно, во втором блоке кода может оптимизировать большинство, если не все эти проверки делимости (поскольку они записаны непосредственно вами), в то время как в первом блоке кода он должен решить развернуть сначала циклы, а затем замените переменную цикла константами, прежде чем можно будет даже рассуждать о различных проверках.
Возможно, это различие способствует лучшему оптимизированному коду в блоке 2, чем в блоке 1.
Другие решения
3 580 000 против 970 000 — это не только издержки цикла
В вашем последнем ядре похоже, что вы хотели, чтобы блок Up, Down и square сохранялся между другим циклом, но эти блоки являются «краткими» локальными, поэтому содержащиеся в них данные не разделяются между ветвями. К сожалению, ваш подход не сработает, даже если они будут разделены между филиалами.
В вашем внутреннем цикле текущий раунд цикла использует данные, которые были рассчитаны в предыдущем раунде. Распараллеливание таких циклов не совсем тривиально, а иногда и вовсе невозможно. В вашем случае, простым решением было бы использование атомарных операторов для увеличения счетчиков Up и Down, но это было бы неэффективно, потому что атомарные операторы вызывают неявную сериализацию операций.
Вероятно, вам следует заняться решением этой проблемы с помощью существующих параллельных примитивов, таких как префиксные суммы, которые уже были оптимизированы. Например, те, что в CUB или Thrust.