Почему существует различие между временем выполнения для одного и того же кода массивов?
Если я запустил следующую программу, а затем запустил ее снова после замены 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;
}
Решение
Это связано с пространственная местность. Когда вашей программе требуются некоторые данные из памяти, процессор считывает не только эти конкретные данные, но и соседние данные. Итак, на следующей итерации, когда вам нужен следующий набор данных, он уже находится в вашем кэше.
В другом случае ваша программа не может использовать пространственную локальность, поскольку вы не читаете соседние данные в последовательных итерациях.
Скажем, ваши данные размещены в памяти как:
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, он уже находится в кеше, и ваша программа работает быстрее.
Наоборот, если вы читаете данные по столбцам, это вам не поможет, каждый раз, когда вы получаете ошибку в кеше, и процессору снова приходится читать память.
Короче говоря, чтение из памяти является дорогостоящим, это способ оптимизации операций чтения для экономии времени.
Другие решения
Других решений пока нет …