如何优化内存访问模式缓存友好程序设计技巧-C++-PHP中文网

理解缓存层次与缓存行：现代cpu按缓存行（通常64字节）加载数据，一次未命中会加载整行；2. 利用空间局部性：使用连续存储结构如数组，按内存顺序访问数据，合理布局结构体成员以提高缓存利用率；3. 利用时间局部性：通过循环分块等技术使数据在缓存中被多次重用，减少主存访问；4. 避免伪共享：在多线程环境中，通过填充或对齐确保不同线程操作的变量不位于同一缓存行，防止频繁同步；5. 使用内存池：提升小对象分配的局部性并减少碎片；缓存友好性至关重要，因为cpu与内存间存在巨大速度差，缓存通过存储高频数据减少等待，若程序缺乏局部性将导致频繁缓存失效，极大降低性能，例如二维数组列优先遍历会引发大量未命中，而改为行优先可提升数倍性能，循环分块在矩阵乘法中可使性能提升近10倍，伪共享虽不引发逻辑错误但会因缓存行竞争导致性能急剧下降，需通过填充、对齐或局部变量化来规避。

如何优化内存访问模式缓存友好程序设计技巧

优化内存访问模式和设计缓存友好程序，核心在于让CPU能够更高效地利用其内部的缓存层级，最大化数据访问的局部性，从而大幅减少从慢速主内存读取数据的次数。这就像是把最常用的工具放在触手可及的地方，而不是每次都跑去工具箱深处翻找。

解决方案

要实现缓存友好，我们需要深入理解CPU缓存的工作原理，并在此基础上调整我们的数据结构和算法。这主要涉及以下几个方面：

理解缓存层次与缓存行： 现代CPU通常有L1、L2、L3多级缓存。数据不是按字节，而是按“缓存行”（通常64字节）为单位加载到缓存中的。一次缓存未命中，会导致整个缓存行的数据被加载。
利用空间局部性： 当程序访问内存中某个位置时，它很可能在短时间内访问其附近的数据。
- 连续存储： 优先使用数组或向量等连续存储的数据结构，而非链表。遍历数组时，按内存连续的顺序访问（例如，C/C++中二维数组按行遍历）。
- 结构体布局： 将经常一起访问的结构体成员放在一起，并考虑它们的大小，避免不必要的填充，确保一个缓存行能容纳更多有用数据。
利用时间局部性： 当程序访问某个数据项时，它很可能在短时间内再次访问该数据项。
- 循环优化： 调整循环嵌套顺序，使内层循环尽可能多地重用已加载到缓存中的数据。对于大型数据集，可以采用“循环分块”（Loop Tiling/Blocking）技术，将数据处理分解为小块，确保每个块都能在缓存中处理完成。
- 减少冗余计算： 避免在循环内部重复计算相同的值，将其提升到循环外部。
避免伪共享（False Sharing）： 在多线程编程中，如果不同线程修改了位于同一个缓存行但逻辑上不相关的变量，会导致缓存行在不同CPU核心间频繁失效和同步，严重影响性能。可以通过数据填充或对齐来规避。
内存池与自定义分配器： 对于频繁创建和销毁小对象的场景，使用内存池可以减少碎片，并提高新分配对象的局部性。

为什么缓存友好性对程序性能至关重要？

这其实是现代计算机体系结构中一个非常核心的问题。我们都知道，CPU的速度发展得飞快，但内存的速度却相对滞后。这种巨大的速度差异，就像是F1赛车（CPU）在等一辆自行车（内存）送零件。如果CPU每次执行指令都需要从慢速的主内存中获取数据，那么它大部分时间都会处于等待状态，性能自然上不去。

缓存，就是为了弥补这个速度鸿沟而存在的。它就像CPU旁边的一个高速小仓库，里面存放着CPU最可能需要的数据副本。当CPU需要数据时，它首先去缓存里找。如果数据在缓存里（缓存命中），那几乎是瞬间就能拿到；如果不在（缓存失效），CPU就得去主内存里取，这个过程耗时巨大，可能导致CPU停顿数百甚至上千个时钟周期。

我曾遇到一个看似简单的图像处理循环，在数据量稍大时性能急剧下降。最初以为是算法复杂度的问题，但深入分析后发现，仅仅是二维数组的遍历顺序不对，导致每次访问都引发缓存失效。将行优先改为列优先（对于C/C++数组），性能提升了数倍。那一刻我才真正体会到，缓存友好性不是锦上添花，而是决定程序能否高效运行的基石。现代CPU的预取机制、流水线技术，也都是基于数据局部性假设来工作的。

如何通过代码实践提升空间局部性？

提升空间局部性，本质上就是让程序在访问内存时，倾向于访问那些在物理地址上相邻的数据。

在C/C++中，二维数组的存储方式是行优先的。这意味着

arr[0][0]

登录后复制

、

arr[0][1]

登录后复制

、

arr[0][2]

登录后复制

是连续存储的，而

arr[0][0]

登录后复制

和

arr[1][0]

登录后复制

之间可能隔着一整行的数据。

考虑一个简单的二维数组遍历：

// 假设一个1000x1000的二维数组
int matrix[1000][1000];

// 糟糕的空间局部性：列优先遍历
for (int j = 0; j < 1000; ++j) {
    for (int i = 0; i < 1000; ++i) {
        matrix[i][j] = i + j; // 每次访问都跳到下一行，可能导致大量缓存失效
    }
}

// 良好的空间局部性：行优先遍历
for (int i = 0; i < 1000; ++i) {
    for (int j = 0; j < 1000; ++j) {
        matrix[i][j] = i + j; // 连续访问同一行的数据，充分利用缓存行
    }
}

登录后复制

在结构体设计上，我们也要有意识地将那些经常一起使用的成员变量放在一起。例如：

struct Point3D {
    double x;
    double y;
    double z;
    // ... 其他不常用或与坐标无关的成员
};

登录后复制

如果

x, y, z

登录后复制

总是作为一个整体被访问，将它们连续声明，它们很可能被加载到同一个缓存行中。避免在它们中间插入一个不相关的、很少访问的巨大数组，那会挤占缓存行宝贵的空间。

很多时候，我们写代码时只关注逻辑的正确性，却很少“俯瞰”数据在内存中是如何“躺着”的。这种对内存布局的敏感性，是优化性能的关键一步。

时间局部性在循环优化中扮演什么角色？

时间局部性是指，如果一个数据项被访问过，那么它很可能在不久的将来再次被访问。在循环优化中，我们就是要想方设法让CPU尽可能长时间地“持有”它已经加载到缓存中的数据，而不是频繁地去主内存“进货”。

堆友

Alibaba Design打造的设计师全成长周期服务平台，旨在成为设计师的好朋友

306

查看详情

最典型的应用就是“循环分块”（Loop Tiling或Loop Blocking），尤其是在矩阵乘法这种计算密集型任务中表现突出。

考虑一个简单的矩阵乘法

C = A * B

登录后复制

：

// 朴素的矩阵乘法
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];
        }
    }
}

登录后复制

在这个朴素的实现中，当

登录后复制

循环时，

A[i][k]

登录后复制

是连续访问的（空间局部性好），但

B[k][j]

登录后复制

的访问模式是跳跃的，每次都跳到

登录后复制

的下一行，导致大量的缓存失效。

通过循环分块，我们可以将大矩阵分成小块，使得在处理一个小块时，相关的A、B、C子矩阵都能尽量留在缓存中：

// 循环分块的矩阵乘法（简化示例，假设块大小为BS）
for (int ii = 0; ii < N; ii += BS) {
    for (int jj = 0; jj < N; jj += BS) {
        for (int kk = 0; kk < N; kk += BS) {
            for (int i = ii; i < std::min(ii + BS, N); ++i) {
                for (int j = jj; j < std::min(jj + BS, N); ++j) {
                    for (int k = kk; k < std::min(kk + BS, N); ++k) {
                        C[i][j] += A[i][k] * B[k][j];
                    }
                }
            }
        }
    }
}

登录后复制

这里，我们引入了额外的

ii, jj, kk

登录后复制

循环来迭代块。内层的

i, j, k

登录后复制

循环只处理当前小块的数据。这样，

A[i][k]

登录后复制

和

B[k][j]

登录后复制

在处理完一个

BS x BS

登录后复制

的块之前，有更大的机会停留在缓存中，从而大幅减少了缓存失效的次数。

曾经在优化一个科学计算库时，仅仅是引入了循环分块，就让一个核心的矩阵运算性能提升了近10倍。这种优化不仅仅是算法层面的精进，更是对硬件特性——特别是缓存行为——的深刻理解。那种“哦，原来如此！”的顿悟感，非常美妙。

伪共享（False Sharing）是什么？如何规避？

伪共享是一个在多线程并发编程中常见的性能陷阱，它与缓存行的工作方式紧密相关。

什么是伪共享？ 当多个CPU核心上的不同线程，各自独立地修改位于同一个缓存行（Cache Line）中的不同变量时，就会发生伪共享。即使这些变量在逻辑上互不相关，互不共享，但由于它们恰好落在同一个缓存行内，根据缓存一致性协议（如MESI），任何一个核心对该缓存行的修改，都会导致其他核心中对应的缓存行失效。为了保持数据一致性，这个缓存行需要在不同核心之间来回“弹跳”，频繁地进行同步和失效操作，这会产生大量的总线流量和缓存未命中，从而严重降低程序性能。

举个例子：假设一个缓存行大小是64字节。有两个线程

T1

登录后复制

和

T2

登录后复制

，它们分别操作

var1

登录后复制

和

var2

登录后复制

。如果

var1

登录后复制

和

var2

登录后复制

恰好都位于同一个64字节的缓存行内，并且

T1

登录后复制

只写

var1

登录后复制

，

T2

登录后复制

只写

var2

登录后复制

。

```
T1
```
登录后复制
修改
```
var1
```
登录后复制
，它所在的缓存行被标记为“独占”或“修改”。
```
T2
```
登录后复制
试图修改
```
var2
```
登录后复制
，发现它所在的缓存行已经被
```
T1
```
登录后复制
独占，
```
T2
```
登录后复制
必须请求
```
T1
```
登录后复制
将该缓存行写回主内存，然后
```
T2
```
登录后复制
再从主内存加载，并获取该缓存行的独占权。
```
T1
```
登录后复制
再次修改
```
var1
```
登录后复制
，又得重复上述过程。尽管
```
var1
```
登录后复制
和
```
var2
```
登录后复制
逻辑上不共享，但物理上的共享（同一个缓存行）导致了性能问题。

如何规避伪共享？ 主要的方法是确保不同线程独立操作的变量位于不同的缓存行。

数据填充（Padding）： 这是最常用的方法。在变量之间插入一些无用的填充字节，使其占用足够的空间，从而将相邻的变量推到不同的缓存行中。
```
struct Counter {
    long value;
    char padding[64 - sizeof(long)]; // 填充到缓存行大小
};

// 多个线程操作各自的Counter实例
Counter counters[NUM_THREADS];
```
登录后复制
通过这种方式，
```
counters[0].value
```
登录后复制
和
```
counters[1].value
```
登录后复制
将位于不同的缓存行，避免了伪共享。
数据对齐（Alignment）： 确保每个共享变量都从缓存行的起始地址开始。在C++11及以后，可以使用
```
alignas
```
登录后复制
关键字：
```
struct AlignedCounter {
    alignas(64) long value; // 确保value在64字节边界上对齐
};
```
登录后复制
局部变量化： 尽可能在线程内部使用局部变量，减少对共享变量的直接写入。在需要同步时，再将局部结果合并到共享变量中，减少共享的频率。