数据局部性优化，C++内存布局技巧

编写缓存友好的C++代码需遵循以下要点：1. 利用时间局部性与空间局部性，如循环中复用变量和顺序访问数组；2. 优化数据结构布局，合并同类字段、减少填充、控制对齐方式；3. 调整循环访问模式，按内存布局顺序访问、分块处理；4. 使用缓存友好的容器与算法，如std::vector、std::sort、std::unordered_map等，并预分配内存以减少碎片。

写缓存友好的C++代码，关键在于理解数据局部性原理和内存布局优化。CPU缓存的速度远高于主存，但容量有限，如何让程序尽可能命中缓存，是提升性能的关键。

了解数据局部性：时间局部性和空间局部性

时间局部性是指如果一个数据被访问了，那么它在不久的将来很可能再次被访问；空间局部性则是指如果一个内存位置被访问了，那么其附近的数据也可能很快被用到。

举个例子：在一个循环中反复使用同一个变量，这就是利用了时间局部性；而遍历数组时，访问完当前元素后紧接着访问下一个相邻元素，则是利用了空间局部性。

编写代码时应尽量：

• 减少临时变量切换，复用已有数据（提高时间局部性）
• 按顺序访问内存中的结构体或数组（提高空间局部性）

合理设计数据结构的内存布局

C++中结构体或类的成员排列会影响缓存效率。默认情况下，编译器会做内存对齐优化，但这可能导致“内存空洞”，浪费缓存行空间。

比如下面这个结构体：

struct Example {
    char a;
    int b;
    char c;
};

在32位系统下，可能占用12字节（a占1，填充3，b占4，c占1，再填充3），其中6字节是填充内容，实际有效数据只有6字节。这会导致缓存行利用率低。

优化建议：

• 把相同类型或相近大小的字段放在一起，减少填充
• 避免把不常用的大字段放在频繁访问的对象中
• 使用alignas或#pragma pack控制对齐方式（需谨慎使用）

循环优化与访问模式

很多性能瓶颈出现在循环内部，尤其是嵌套循环中访问二维数组的方式是否合理。

假设有一个二维数组arr[ROWS][COLS]，如果我们按列优先访问（即外层循环遍历列，内层循环遍历行），就会破坏空间局部性，导致缓存命中率下降。

正确做法：

• 尽量让访问顺序与内存布局一致（行优先）
• 将最内层循环设计为连续访问内存的操作
• 对于大数组，可以考虑分块处理（tiling），让每次操作集中在较小的数据块上，提高缓存利用率

例如：

// 好的访问方式
for (int i = 0; i < ROWS; ++i)
    for (int j = 0; j < COLS; ++j)
        arr[i][j] += 1;

// 不推荐的方式
for (int j = 0; j < COLS; ++j)
    for (int i = 0; i < ROWS; ++i)
        arr[i][j] += 1;

使用缓存友好的容器和算法

STL容器如std::vector比std::list更缓存友好，因为前者内存连续，后者节点分散，容易导致缓存未命中。

同样，在算法选择上，也要考虑局部性。例如：

• std::sort通常比std::list::sort快，因为它能更好地利用缓存
• 使用reserve()预分配内存，避免频繁扩容带来的拷贝和碎片化
• 对于需要频繁查找的结构，使用std::unordered_map（哈希表）而非std::map（红黑树）通常更高效

基本上就这些。
缓存友好的代码不一定复杂，但需要从数据结构、访问顺序和内存布局等多个角度去思考。有时候只是调整一下字段顺序或者循环方式，就能带来明显的性能提升。