面试题：C语言多维数组复杂访问及存储优化

Question

给定一个三维数组`int cube[2][3][4]`，现要求实现一个函数，该函数接收该三维数组指针，计算并返回数组中所有元素的和。同时，分析在这种多维数组访问中，怎样的内存访问模式有助于提高缓存命中率，从而优化性能。

Answer 1

#include <stdio.h>

// 计算三维数组所有元素和的函数
int sumOfCube(int (*cube)[3][4]) {
    int sum = 0;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 4; k++) {
                sum += cube[i][j][k];
            }
        }
    }
    return sum;
}

内存访问模式与缓存命中率分析

在多维数组访问中，以步长为1的顺序访问内存有助于提高缓存命中率，从而优化性能。对于三维数组int cube[2][3][4]，在内存中它是按行优先（C语言默认）的方式存储的。即cube[0][0][0]之后紧接着是cube[0][0][1]，然后是cube[0][0][2] ， cube[0][0][3]，接着是cube[0][1][0]等。

如果按如下顺序访问：

for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 3; j++) {
        for (int k = 0; k < 4; k++) {
            // 访问cube[i][j][k]
        }
    }
}

这种访问模式是步长为1的顺序访问，因为在内存中cube[i][j][k] 的下一个元素就是cube[i][j][k + 1]。缓存通常以缓存行（cache line）为单位从主存中读取数据，一个缓存行通常包含多个连续的内存地址。当程序访问cube[i][j][k]时，缓存会预取相邻的元素到缓存行中。如果下一个访问的元素恰好在这个缓存行中，就可以直接从缓存中读取，而不需要从主存中读取，这就提高了缓存命中率。

相反，如果访问顺序是跳跃式的，例如：

for (int i = 0; i < 2; i++) {
    for (int k = 0; k < 4; k++) {
        for (int j = 0; j < 3; j++) {
            // 访问cube[i][j][k]
        }
    }
}

这种访问模式不是步长为1的顺序访问，会导致缓存命中率降低，因为每次访问cube[i][j][k] 后，下一个访问的元素cube[i][j + 1][k] 可能不在当前缓存行中，需要从主存重新读取，从而降低了性能。