Почему существует различие между временем выполнения для одного и того же кода массивов?

Question

Если я запустил следующую программу и затем запустил ее снова после замены i и j на sum+=arr[i][j], время выполнения сильно отличается, т. Е. 9,8 с по сравнению с 2,7 с до смены. Я просто не могу понять, почему это так. Может кто-нибудь, пожалуйста, дайте мне понять, почему это так?

#include<iostream>
#include<time.h>
using namespace std;

int main()
{
    int long sum=0;
    int size = 1024;
    clock_t start, end;
    double msecs;
    start = clock();

    int **arr = new int*[size];
    for (int i = 0; i < size; i++) 
    {
        arr[i] = new int[size];
    }

    for(int kk=0; kk<1000; kk++) 
    {
        sum = 0;
        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size ; j++)
            {
                sum += arr[i][j];
            }
        }
    }

    end = clock();  
    msecs = ((double) (end - start)) * 1000 / CLOCKS_PER_SEC;
    cout<<msecs<<endl<<endl;

    return 0;
}

Answer 1

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

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

Скажем, ваши данные размещены в памяти как:

  0  1  2  3  4  5  6  7  8  9 
 10 11 12 13 14 15 16 17 18 19
 20 21 22 23 24 25 26 27 28 29

Когда ваша программа должна прочитать, скажем, данные с надписью 0, он читает всю строку:
0 1 2 3 4 5 6 7 8 9

Так что, когда вам нужны данные с пометкой 1, он уже находится в кеше, и ваша программа работает быстрее.

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

Короче говоря, чтение из памяти является дорогостоящим, это способ оптимизации операций чтения для экономии времени.