1. 数组遍历顺序优化

任务目标

本案例通过对比同一二维数组在行优先遍历与列优先遍历下的耗时差异，直观展示缓存局部性对程序性能的影响。C/C++二维数组在内存中按行连续存储，行优先遍历时相邻访问地址连续，缓存命中率高；列优先遍历则每次跳过一个完整行，导致缓存频繁失效。

环境与依赖

• 编译器：gcc/g++（需支持C++11或更高版本）
• 系统：Linux/macOS/Windows（WSL）均可
• 无第三方库依赖

完整实现代码

#include <iostream>
#include <chrono>
#include <vector>

const int N = 4096;  // 矩阵维度

// 行优先遍历：按行访问，内存连续
long long rowMajor(const std::vector<std::vector<int>>& mat) {
    long long sum = 0;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            sum += mat[i][j];
    return sum;
}

// 列优先遍历：按列访问，内存跳跃
long long colMajor(const std::vector<std::vector<int>>& mat) {
    long long sum = 0;
    for (int j = 0; j < N; ++j)
        for (int i = 0; i < N; ++i)
            sum += mat[i][j];
    return sum;
}

int main() {
    // 初始化二维矩阵
    std::vector<std::vector<int>> mat(N, std::vector<int>(N));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            mat[i][j] = i + j;

    // 预热（排除首次访问的冷启动影响）
    volatile long long warm = rowMajor(mat);

    // 行优先计时
    auto t1 = std::chrono::high_resolution_clock::now();
    long long sum1 = rowMajor(mat);
    auto t2 = std::chrono::high_resolution_clock::now();
    auto rowTime = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();

    // 列优先计时
    auto t3 = std::chrono::high_resolution_clock::now();
    long long sum2 = colMajor(mat);
    auto t4 = std::chrono::high_resolution_clock::now();
    auto colTime = std::chrono::duration_cast<std::chrono::milliseconds>(t4 - t3).count();

    // 输出结果（sum1==sum2用于验证正确性）
    std::cout << "行优先耗时: " << rowTime << " ms, sum=" << sum1 << "\n";
    std::cout << "列优先耗时: " << colTime << " ms, sum=" << sum2 << "\n";
    std::cout << "加速比: " << (double)colTime / rowTime << "x\n";
    std::cout << "结果一致: " << (sum1 == sum2 ? "是" : "否") << "\n";
    return 0;
}

编译与运行

g++ -O2 -std=c++11 cache_demo.cpp -o cache_demo
./cache_demo

验证方法与判定标准

• 正确性验证：程序输出“结果一致: 是”，说明两种遍历方式计算出的总和相同，排除了算法错误导致的性能偏差。
• 性能对比验证：观察输出中的“加速比”数值。由于行优先遍历利用缓存局部性，通常列优先耗时是行优先的3～10倍（具体倍数受CPU缓存大小、N值影响）。若加速比明显大于1，则证明缓存局部性优化有效。
• 可复现性说明：N=4096时矩阵约64MB（4096×4096×4字节），远超常见L3缓存（8～32MB），确保两种遍历方式均需访问主存，差异主要来自缓存行利用率而非数据量本身。

缓存访问模式示意

图中橙色块表示列优先遍历时实际访问的元素，灰色块为同缓存行中未被使用的数据。行优先遍历时每个缓存行加载的4个元素全部被使用，而列优先遍历时每个缓存行仅1个元素有效，导致缓存利用率降低至25%（假设缓存行64字节、int为4字节）。

常见问题

• 为什么需要预热？：首次访问矩阵时所有数据均不在缓存中，冷启动开销会掩盖两种遍历方式的真实差异。预热确保后续计时反映的是稳定状态下的缓存行为。
• N值如何选择？：N=4096时矩阵约64MB，确保超出CPU末级缓存容量。若N过小（如256），矩阵完全装入缓存，两种遍历方式差异会显著缩小。
• 编译器优化影响：使用-O2编译时，编译器可能自动优化循环。若需观察更明显的差异，可尝试-O0或增加矩阵访问的随机性（如sum += mat[i][j] * (i%2)）防止完全向量化。