Блог

Я тестирую два почти идентичных кода с небольшой разницей в одном из циклов for . Первый использует три цикла для итерации индексов y , z , x в то время как второй повторяет x , z , y .

Мой вопрос в том, почему разница во времени пользователя и времени настенных часов? Это из-за расположения памяти в одном коде и в другом?

test_1.c:

 #define N 1000

// Matrix definition
long long int A[N][N],B[N][N],R[N][N];

int main()
{
    int x,y,z;
    char str[100];

/*Matrix initialization*/ 
    for(y=0;y<N;y  ) 
        for(x=0;x<N;x  )
        {
            A[y][x]=x;
            B[y][x]=y;
            R[y][x]=0;
        }
/*Matrix multiplication*/
    for(y=0;y<N;y  )
        for(z=0;z<N;z  ) 
            for(x=0;x<N;x  ) 
            {
                R[y][x] = A[y][z] * B[z][x];
            }   
exit(0);
}
  

Разница во втором коде (test_2.c) находится в последнем цикле for:

 for(x=0;x<N;x  )
    for(z=0;z<N;z  ) 
        for(y=0;y<N;y  ) 
        {
            R[y][x] = A[y][z] * B[z][x];
        } 
  

Если я напечатаю /user/bin/time -v ./test_1, я получу следующую статистику:

 Command being timed: "./test_1"
User time (seconds): 5.19
System time (seconds): 0.01
Percent of CPU this job got: 99%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:05.22
  

В то время как /user/bin/time -v ./test_2 дает следующую статистику:

 Command being timed: "./test_2"
User time (seconds): 7.75
System time (seconds): 0.00
Percent of CPU this job got: 99%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:07.76
  

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

Если вам нужна аналогия с реальным миром, представьте, что вы разносите листовки по 10 разным дорогам (A-J), каждая из которых имеет номера домов 1-10. Вы могли бы доставить A1, A2, A3…A10, B1, B2, B3…B10 и т.д. … или вы могли бы доставить A1, B1, C1 … J1, A2, B2, C2 … и т.д. Очевидно, что первый способ будет более эффективным. Это то же самое, что и в компьютерной памяти — более эффективно обращаться к памяти «рядом» с памятью, к которой вы недавно обращались, чем прыгать.