Блог

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

 #include <cstring>
#include <chrono> 
#include <iostream> 

#define NLOOPS 10

void doWorkFast(int total, int *write, int *read)
{
    for (int j = 0; j < NLOOPS; j  ) {
        for (int i = 0; i < total; i  ) {
            write[i] = read[i]   i;
        }
    }
}

void doWorkSlow(int total, int *write, int *read, int innerLoopSize)
{
    for (int i = 0; i < NLOOPS; i  ) {
        for (int j = 0; j < total/innerLoopSize; j  ) {
            for (int k = 0; k < innerLoopSize; k  ) {
                write[j*k   k] = read[j*k   k]   j*k   k;
            }
        }
    }
}


int main(int argc, char *argv[])
{
    int n = 1000000000;
    
    int *heapMemoryWrite = new int[n];
    int *heapMemoryRead = new int[n];
    

    for (int i = 0; i < n; i  )
    {
        heapMemoryRead[i] = 1;
    }

    std::memset(heapMemoryWrite, 0, n * sizeof(int));   

    auto start1 = std::chrono::high_resolution_clock::now();

    doWorkFast(n,heapMemoryWrite, heapMemoryRead);
    

    auto finish1 = std::chrono::high_resolution_clock::now();  
    auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(finish1 - start1); 

    for (int i = 0; i < n; i  )
    {
        heapMemoryRead[i] = 1;
    }

    std::memset(heapMemoryWrite, 0, n * sizeof(int));

    auto start2 = std::chrono::high_resolution_clock::now();
    
    doWorkSlow(n,heapMemoryWrite, heapMemoryRead, 10);


    auto finish2 = std::chrono::high_resolution_clock::now();  
    auto duration2 = std::chrono::duration_cast<std::chrono::microseconds>(finish2 - start2); 

    std::cout << "Small inner loop:" << duration1.count() << " microseconds.n" << 
                 "Large inner loop:" << duration2.count() << " microseconds." << std::endl; 

    delete[] heapMemoryWrite;
    delete[] heapMemoryRead;
}
 

Глядя на две функции DoWork *, для каждой итерации мы считываем одни и те же адреса, добавляем одно и то же значение и записываем на одни и те же адреса. Я понимаю, что в doWorkSlow реализации мы выполняем еще одну или две операции для разрешения j*k k , однако я думаю, что разумно предположить, что относительно времени, необходимого для загрузки / сохранения для чтения и записи в память, вклад во время этих операций незначителен.

Тем не менее, doWorkSlow это занимает примерно в два раза больше времени (46,8 с) по сравнению с doWorkFast (25,5 с) на моем i7-3700 с использованием g --version версии 7.5.0. Хотя на ум приходят такие вещи, как предварительная выборка кэша и прогнозирование ветвлений, у меня нет хорошего объяснения, почему doWorkFast это намного быстрее, чем doWorkSlow . У кого-нибудь есть понимание?

Спасибо

Глядя на две функции DoWork *, для каждой итерации мы считываем одни и те же адреса, добавляем одно и то же значение и записываем на одни и те же адреса.

Это неправда!

В doWorkFast вы индексируете каждое целое число постепенно, как array[i] .

 array[0]
array[1]
array[2]
array[3]
 

В doWorkSlow вы индексируете каждое целое число как array[j*k k] , которое перескакивает и повторяется.

j Например, когда равно 10, и вы выполняете итерацию k с 0 и далее, вы получаете доступ

 array[0]    // 10*0 0
array[11]   // 10*1 1
array[22]   // 10*2 2
array[33]   // 10*3 3
 

Это не позволит вашему оптимизатору использовать инструкции, которые могут работать со многими соседними целыми числами одновременно.