Удивительное замедление при растворении вложенной петли

Question

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

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

k = 0;
for (int i=0;i<n;++i)
{
for (int j=0;j<n;++j)
{
index[k][0] = i;
index[k][1] = j;
}
} 

например:

#pragma omp for 
for (int i=0;i<n;++i)
{
for (int j=0;j<n;++j)
{
a[i][j] = 2.0*i+3.0;
}
}

превратился в

#pragma omp for 
for (int k=0;k<n;++k)
{
i = index[k][0];
j = index[k][1];
a[i][j] = 2.0*i+3.0;
}

К моему удивлению код замедлился вместо ускорения, и я не знаю почему?

Answer 1

Петли не дорогие.Это то, что вы делаете внутри цикла, это дорого.Вы создали новый цикл, который запускается i * j раз, поэтому вы в конечном итоге выполняете внутренний код столько же раз.Таким образом, вы не сохранили ничего, кроме незначительной суммы для накладных расходов внутреннего цикла.

Ваш новый код теперь обращается к памяти для каждой итерации.Память медленная.Намного медленнее, чем накладные расходы на циклы for, от которых вы избавились.

Вот почему ваша новая версия медленнее старой.