c - 二维矩阵的哪种表示更快

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

如果您的问题（以及相应的解决方案）需要二维数组，则只需使用二维数组：M[a][b]。

您必须记住，无论如何，内存都是线性寻址的。多维数组的概念只是在线性内存之上实现的一层。

如今，编译器已经高度优化，因此它们在“线性化”二维数组方面会比你做得更好。此外，如果您这样做，代码将更难以编写和维护。

Answer 3

您可以使用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

---

这意味着第二个代码比第一个代码花费更多时间。