Какое представление 2D-матрицы быстрее

Question

Какой путь быстрее и удобнее для компилятора / кэша, используйте M [a] [b] или M [a * b] при работе с матрицами?

Я пытался написать оба способа в проводнике компилятора в функцииэто распределяет, инициализирует и возвращает матрицу, но я не знаю ассемблера и сколько времени занимает каждая инструкция

int **M = malloc(sizeof(int*)*m)
for(i=0; i<m; ++i) {
  *M = malloc(sizeof(int)*n);
  for(int j = 0; j < n; ++j){
    M[j] = j;
  }

против

int *M = malloc(m*n*sizeof(int));
for(i = 0; i < m*n; ++i) M[i] = i;

Я ожидаю, что второй способ будет быстрее.

Answer 1

Код с вызовами malloc будет медленнее.Интересно, насколько быстрый доступ к конкретной ячейке

void foo(int * const * const M, const size_t x, const size_t y, const int val)
{
    M[x][y] = val;
}

void foo2(int * const M, const size_t x, const size_t y, const size_t rowsize, const int val)
{
    M[x + rowsize * y] = val;
}

https://godbolt.org/z/iv0VPV

foo:
        mov     rax, QWORD PTR [rdi+rsi*8]
        mov     DWORD PTR [rax+rdx*4], ecx
        ret
foo2:
        imul    rcx, rdx
        add     rcx, rsi
        mov     DWORD PTR [rdi+rcx*4], r8d
        ret

результат очевиден;

Answer 2

Вы можете использовать clock_t для отслеживания времени блока кода.

и вот ваш код после некоторых обновлений.

---

#include<stdio.h>
#include<time.h>

int main()
{
    int i = 0, j = 0;
    int m, n;
    scanf("%d %d", &m, &n);
    clock_t start, end;
    double time_used;
    start = clock();

    int **M = malloc(sizeof(int*)*m);

    for (i = 0; i < m; ++i) {
        *M = malloc(sizeof(int)*n);
        for (int j = 0; j < n; ++j) {
            M[j] = j;
        }
    }
        end = clock();
        time_used = ((double)(end - start)) / CLOCKS_PER_SEC;

        printf("Time used for fisrst code is : %f \n ", time_used);
        start = clock();
        M = malloc(m*n * sizeof(int));
        for (i = 0; i < m*n; ++i) M[i] = i;
        end = clock();
        time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
        printf("Time used for second code is : %f \n ", time_used);


        return 0;
}

и этот код выводится при вводе матрицы 10000 * 10000

---

Время, использованное для первого кода: 0,001000

---

Время, использованное для первого кода: 0,686000

---

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

Answer 3

Если вашей проблеме (и соответствующему решению) требуется двумерный массив, просто используйте двумерный массив: M [a] [b].

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

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