Почему позиция кода влияет на производительность в C ++?

Question

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

Производительность измеряется по времени выполнения с использованием библиотеки chrono .

vector< vector<float> > U(matrix_size, vector<float>(matrix_size,14));
vector< vector<float> > L(matrix_size, vector<float>(matrix_size,12));
vector< vector<float> > matrix_positive_definite(matrix_size, vector<float>(matrix_size,23));

for (i = 0; i < matrix_size; ++i) {         
   for(j= 0; j < matrix_size; ++j){
//Part II : ________________________________________
    float sum2=0;               
    for(k= 0; k <= (i-1); ++k){
      float sum2_temp=L[i][k]*U[k][j];
      sum2+=sum2_temp;
    }
//Part I : _____________________________________________
    float sum1=0;       
    for(k= 0; k <= (j-1); ++k){
      float sum1_temp=L[i][k]*U[k][j];
      sum1+=sum1_temp;
    }           
//__________________________________________
    if(i>j){
      L[i][j]=(matrix_positive_definite[i][j]-sum1)/U[j][j]; 
    }
    else{
       U[i][j]=matrix_positive_definite[i][j]-sum2;
    }   
   }
}

Я компилирую с g++ -O3 (GCC 7.4.0 в Intel i5 / Win10).Я изменил порядок части I и части II и получил более быстрый результат, если часть II выполнялась до части I. Что происходит?

Это ссылка на всю программу.

Answer 1

Я бы попробовал запустить обе версии с perf stat -d <app> и посмотреть, где разница в счетчиках производительности.

При тестировании производительности вы можете фиксировать частоту ЦП, чтобы она не влияла на ваши оценки.

---

Выравнивание циклов на 32-байтовой границе часто повышает производительность на 8-30%.См. Причины нестабильности производительности из-за размещения кода в X86 - Зия Ансари, Intel для получения более подробной информации.

Попробуйте скомпилировать код с помощью -O3 -falign-loops=32 -falign-functions=32 -march=native -mtune=native.

Answer 2

Запуск perf stat -ddd во время игры с предоставленной программой показывает, что основное различие между двумя версиями заключается в основном в предварительной выборке.

part II -> part I   and   part I -> part II (original program)
   73,069,502      L1-dcache-prefetch-misses

part II -> part I   and   part II -> part I (only the efficient version)
   31,719,117      L1-dcache-prefetch-misses

part I -> part II   and   part I -> part II (only the less efficient version)
  114,520,949      L1-dcache-prefetch-misses

nb: согласно проводнику компилятора, part II -> part I - этоочень похоже на part I -> part II.

Полагаю, что на первых итерациях с i part II почти ничего не делает, но итерации с j делают part I доступ U[k][j] в соответствии сшаблон, который облегчит предварительную выборку для следующих итераций по i.

Answer 3

Более быстрая версия аналогична производительности, которую вы получаете, перемещая петли внутри if (i > j).

if (i > j) {
    float sum1 = 0;
    for (std::size_t k = 0; k < j; ++k){
        sum1 += L_series[i][k] * U_series[k][j];
    }
    L_parallel[i][j] = matrix_positive_definite[i][j] - sum1;
        L[i][j] /= U[j][j];
}
if (i <= j) {
    float sum2 = 0;
    for (std::size_t k = 0; k < i; ++k){
        sum2 += L_series[i][k] * U_series[k][j];
    }
    U_parallel[i][j] = matrix_positive_definite[i][j] - sum2;
}

Так что я бы предположил, что в одном случае компилятор может выполнить это преобразование самостоятельно. Это происходит только в -O3 для меня. (1950X, msys2 / GCC 8.3.0, Win10)

Я не знаю, какая именно это оптимизация и какие условия должны быть выполнены для ее применения. Это не один из параметров , явно перечисленных для -O3 (-O2 + всех их недостаточно). Очевидно, он уже не делает этого, когда для счетчиков цикла используется std::size_t вместо int.