Зачем нужен доступ к двумерному массиву быстрее, чем доступ к 1-му массиву?

Question

У меня есть две программы, скомпилированные с g ++ и исполняемые на linux. Программа 1 создает 2D массив, а затем измеряет, сколько времени требуется, чтобы получить доступ ко всем его элементам 100000 раз:

#include <time.h> 
#include <iostream> 

int main() 
{ 
    clock_t time; 
    int i, y, x; 

    int matrix[9][9]{{ 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, 30, 31, 32, 33, 34, 35}, 
        {36, 37, 38, 39, 40, 41, 42, 43, 44}, 
        {45, 46, 47, 48, 49, 50, 51, 52, 53}, 
        {54, 55, 56, 57, 58, 59, 60, 61, 62}, 
        {63, 64, 65, 66, 67, 68, 69, 70, 71}, 
        {72, 73, 74, 75, 76, 77, 78, 79, 80}}; 

    time = clock(); 

    for (i = 0; i < 100000; i++) 
    { 
    for (x = 0; x < 9; x++) 
    { 
     for (y = 0; y < 9; y++) 
     { 
     matrix[x][y]; 
     } 
    } 
    } 

    time = clock() - time; 
    std::cout << "Clicks:  " << time << std::endl; 
    std::cout << "Time taken: " << (double) time/CLOCKS_PER_SEC << "s" << std::endl; 
} 

Программа 2 создает 1D массив, а также измеряет, сколько времени требуется, чтобы получить доступ ко всем его элементам 100000 раз :

#include <time.h> 
#include <iostream> 

int main() 
{ 
    clock_t time; 
    int i, j; 

    int vector[81] = { 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, 30, 31, 32, 33, 34, 35, 
        36, 37, 38, 39, 40, 41, 42, 43, 44, 
        45, 46, 47, 48, 49, 50, 51, 52, 53, 
        54, 55, 56, 57, 58, 59, 60, 61, 62, 
        63, 64, 65, 66, 67, 68, 69, 70, 71, 
        72, 73, 74, 75, 76, 77, 78, 79, 80}; 

    time = clock(); 

    for (i = 0; i < 100000; i++) 
    { 
    for (j = 0; j < 81; j++) 
    { 
     vector[j]; 
    } 
    } 

    time = clock() - time; 
    std::cout << "Clicks:  " << time << std::endl; 
    std::cout << "Time taken: " << (double) time/CLOCKS_PER_SEC << "s" << std::endl; 
} 

После выполнения программы 1 мой выход:

Clicks:  8106 
Time taken: 0.008106s 

После выполнения программы 2 мой вывод:

Clicks:  15958 
Time taken: 0.015958s 

Насколько я понимаю, 1D-массив хранится в непрерывном блоке памяти. Аналогично, строки статического 2D-массива хранятся в смежных блоках памяти. И наоборот, строки динамического массива 2d могут не храниться в смежных блоках памяти. Если это так, то программа 2 должна быть как минимум схожа по скорости с программой 1, поэтому мой вопрос заключается в том, почему программа 1 будет значительно быстрее, чем программа 2?

Answer 1

петли, вероятно, будут удалены (вид оптимизации) компилятором, потому что

1. Вы на самом деле ничего не делали в петлях.

2. Матрица может рассматриваться как массив const.

3. программа 1 быстрее, чем программы 2. (: <)

Чтобы увидеть происходит ли удаление в код во время компиляции, вы можете увеличить самую внешнюю петлю в 100 раз, и убедиться в том время, необходимое для выполнения, значительно увеличивается (не обязательно точным 100 раз).

Если это правда, вы можете предотвратить такую ​​оптимизацию, выполнив некоторые фактические работы в цикле (вычислите сумму и не забудьте распечатать ее впоследствии) и внесите некоторые «непредсказуемые» изменения в вашу матрицу, например:

srand(10); 
for (int i=0; i<9; ++i) { 
    matrix[i][i] = rand()%100; 
} 

И далее, компилятор может проводить некоторые другие оптимизации для вашего кода, например, расширить свою петлю, даже адрес элемента, который вы посещаете (они больше не рассчитывается во время выполнения), вы можете предотвратить это при этом время выполнения циклов «непредсказуемо»:

#include <chrono> 
#include <iostream> 
#include <cstdlib> 

int array[100]; 
int array2[10][10]; 

int64_t Sum1D(int len) { 
    int64_t sum = 0; 
    for (int i=0; i<100000; ++i) { 
    for (int j=0; j<len; ++j) { 
     sum += array[j]; 
    } 
    } 
    return sum; 
} 

int64_t Sum2D(int len1, int len2) { 
    int64_t sum = 0; 
    for (int i=0; i<100000; ++i) { 
    for (int j=0; j<len1; ++j) { 
     for (int k=0; k<len2; ++k) 
     sum += array2[j][k]; 
    } 
    } 
    return sum; 
} 

int main() 
{ 
    for (int i=0; i<100; ++i) { 
    array[i] = rand(); 
    array2[i%10][i/10] = rand(); 
    } 

    auto time = std::chrono::steady_clock::now(); 

    //int64_t sum = Sum1D(100); 
    int64_t sum = Sum2D(10,10); 

    auto duration = std::chrono::steady_clock::now()-time; 
    std::cout << sum << "!" << duration.count() << std::endl; 

    return 0; 
} 

, что в итоге делает программу 1 медленнее, чем program2.(:>)

Answer 2

Вот что я нашел:

1. Если вы на самом деле использовать значения, то время выполнения почти то же самое, например, изменить matrix[x][y]; к matrix[x][y] += 1; и vector[j]; к vector[j] += 1;

   >  Clicks:  28519 
   >  Time taken: 0.028519s 
   

   и

   >  Clicks:  29941 
   >  Time taken: 0.029941s 
   

2. Без указанных изменений, оптимизации при компиляции, g++ -O3 <filename>.cpp, это приводит то же время, получил тот же следующий вывод для обеих программ:.

   $/a.out

   >  Clicks:  2 
   >  Time taken: 2e-06s 
   

Итак, вы указываете на оптимизацию компилятора.