数组与缓存：O(1) 访问优化

优化数组以最小化缓存未命中

数组元素的顺序访问比随机访问快 7–10 倍，这是由于缓存内存的工作机制。一条 64 字节的 cache line 可以加载 16 个连续的 int，这样使用合适的遍历模式就能最大限度减少未命中。使用 perf stat 进行性能分析揭示了问题：在简单的包处理任务中，每 100 万条指令就有 45 万次 cache-misses，这表明数组使用方式欠佳。

访问步长对性能的影响

访问步长决定了 cache line 加载效率。步长为 1 时，所有 64 字节都能充分利用，预取器还能识别模式以加速获取。

int sum = 0;
for (int i = 0; i < 8; i++) {
    sum += array[i];
}

这样的序列处理 8 个元素需要 107 个时钟周期（每个元素 13.4 个周期）。通过索引的随机访问将成本提高到 800 个周期（每个元素 100 个周期）。

对 100 万元素数组的基准测试：

• 步长 1：1.2 ms（100% 缓存行利用率）
• 步长 2：1.3 ms（50% 利用率）
• 步长 4：1.5 ms
• 步长 8：2.1 ms
• 步长 16：3.8 ms（6.25% 利用率）
• 步长 64：8.5 ms

建议：步长 ≤8 个元素以获得可接受性能。lmbench lat_mem_rd 工具证实：小步长（128–512 字节）数据留在 L1（3–4 ns），大步长（64 KB）则推送到 DRAM（100+ ns）。

多维数组：遍历顺序至关重要

C 使用行优先顺序：一行中的元素在内存中连续存储。按行遍历确保顺序访问，而按列遍历则引入 16+ 字节的步长。

int matrix[4][4] = {
    {0, 1, 2, 3},
    {4, 5, 6, 7},
    {8, 9, 10, 11},
    {12, 13, 14, 15}
};

对于 1024×1024 矩阵，按行遍历需 12 ms，按列遍历需 45 ms（慢 3.75 倍）。

优化矩阵乘法

朴素的 ijk 顺序：

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        for (int k = 0; k < N; k++) {
            C[i][j] += A[i][k] * B[k][j];
        }
    }
}

问题：B[k][j] 按列读取（步长 N=1024，4096 字节）。ikj 顺序可修复：

for (int i = 0; i < N; i++) {
    for (int k = 0; k < N; k++) {
        int r = A[i][k];
        for (int j = 0; j < N; j++) {
            C[i][j] += r * B[k][j];
        }
    }
}

512×512 结果：ijk — 2450 ms，ikj — 680 ms（加速 3.6 倍）。

对于大矩阵——使用分块 BLOCK_SIZE=64：

for (int ii = 0; ii < N; ii += BLOCK_SIZE) {
    for (int jj = 0; jj < N; jj += BLOCK_SIZE) {
        for (int kk = 0; kk < N; kk += BLOCK_SIZE) {
            for (int i = ii; i < min(ii + BLOCK_SIZE, N); i++) {
                for (int k = kk; k < min(kk + BLOCK_SIZE, N); k++) {
                    int r = A[i][k];
                    for (int j = jj; j < min(jj + BLOCK_SIZE, N); j++) {
                        C[i][j] += r * B[k][j];
                    }
                }
            }
        }
    }
}

块适合放入 L1，并实现数据重用。对于 1024×1024：1800 ms（比朴素快 10 倍）。

AoS 与 SoA：数据组织

结构体数组 (AoS) 将粒子字段分组，但一条 cache line 包含未使用数据（37.5% 利用率）。

typedef struct {
    float x, y, z;
    float vx, vy, vz;
    float mass;
    int id;
} particle_t;

数组之结构体 (SoA) 按类型分离：

typedef struct {
    float x[1000], y[1000], z[1000];
    float vx[1000], vy[1000], vz[1000];
    float mass[1000];
    int id[1000];
} particles_t;

SoA 中的位置更新将缓存行利用率达到 100%。对 100 万粒子、1000 次迭代的基准测试：AoS — 2850 ms，SoA — 1200 ms（加速 2.4 倍）。

关键要点

• 顺序数组访问比随机访问减少 7 倍以上缓存未命中
• 访问步长 ≤8 个元素确保 >90% 缓存行利用率
• C 中的行优先顺序要求按行遍历；按列访问慢 3–4 倍
• 改变矩阵运算中的循环顺序可带来 3–4 倍加速
• SoA 在 SIMD 处理和频繁访问字段子集时优于 AoS

— Editorial Team