3. 数据局部性优化：时间局部性与空间局部性、循环交换与数据重排、缓存行对齐

好，咱们接着聊内存带宽。前面几章我讲了带宽瓶颈在哪，也讲了怎么用工具去定位。但说实话，工具只能告诉你「这里慢了」，真正要解决问题，还得靠代码层面的优化。

这一章，我重点聊聊数据局部性。说白了，就是怎么让CPU缓存更高效地工作。你想想看，CPU从缓存读数据，延迟只有几个纳秒；从主存读，几十甚至上百纳秒。这差距，就是性能的分水岭。

3.1 时间局部性与空间局部性

这两个概念，教科书上讲得挺玄乎。我用自己的话给你翻译一下：

时间局部性：刚用过的数据，很快还会再用。比如循环里的累加变量。
空间局部性：刚用过的数据附近的数据，很快也会被用到。比如数组的连续访问。

嗯，就这么简单。但实际代码里，很多人会忽略这两点。

一个典型的反面例子：

// 糟糕的访问模式 - 跳跃访问
int sum = 0;
for (int i = 0; i < N; i++) {
    sum += data[i * STRIDE];  // STRIDE很大，比如1024
}

这种写法，每次访问都跳到很远的地方。缓存根本没法预取，每次都得从主存读。我见过有人用这种模式处理稀疏矩阵，性能直接掉到十分之一。

那怎么改？很简单，把数据排紧凑。比如用结构体数组代替数组结构体，或者把热点数据单独拎出来。

我的经验： 做图像处理时，我习惯把像素的R、G、B分量分开存成三个连续数组。这样处理单通道时，空间局部性极好。比用结构体数组快30%以上。

3.2 循环交换与数据重排

这是我最常用的优化手段。很多性能问题，其实就是循环顺序不对。

看个例子：

// 坏写法 - 按列访问
for (int j = 0; j < COLS; j++) {
    for (int i = 0; i < ROWS; i++) {
        sum += matrix[i][j];  // 每次跳一行
    }
}

// 好写法 - 按行访问
for (int i = 0; i < ROWS; i++) {
    for (int j = 0; j < COLS; j++) {
        sum += matrix[i][j];  // 连续访问
    }
}

为什么会这样？因为C/C++里二维数组是按行存储的。按行访问，就是连续内存访问，缓存行利用率接近100%。按列访问，每次都要跨过一整行，缓存行里只取一个元素，剩下的全浪费了。

我曾经在一个项目中，把矩阵乘法里的循环顺序调了一下，性能提升了4倍。当时同事都惊呆了。其实原理就这么简单。

注意： 循环交换不是万能的。如果数据本身就不连续，比如链表，那怎么交换都没用。这时候得考虑数据重排。

数据重排，就是把不连续的数据，重新组织成连续的内存块。比如：

// 原始数据 - 分散在不同对象里
struct Particle {
    float x, y, z;
    float vx, vy, vz;
    float mass;
    int type;
};

// 重排后 - 把x坐标单独拿出来
float* x_positions = new float[N];
for (int i = 0; i < N; i++) {
    x_positions[i] = particles[i].x;
}

这样，当你只需要处理x坐标时，就能连续访问了。嗯，这就是所谓的「面向数据设计」的核心思想。

3.3 缓存行对齐

缓存行是CPU缓存的最小单位，通常是64字节。如果你的数据跨了两个缓存行，那访问一次就得读两次内存。这太亏了。

怎么避免？对齐。

// 对齐到64字节边界
struct alignas(64) CacheLineAligned {
    int data[16];  // 正好64字节
};

// 或者用预处理器指令
struct __attribute__((aligned(64))) MyStruct {
    // ...
};

我个人习惯在定义热点数据结构时，都加上对齐属性。尤其是多线程场景下，还能避免伪共享（False Sharing）问题。

伪共享的例子：

struct Counter {
    int a;  // 线程1修改
    int b;  // 线程2修改
};  // 如果a和b在同一个缓存行，两个线程互相拖累

// 解决方案：填充到不同缓存行
struct alignas(64) Counter {
    int a;
    char padding[60];  // 填充到64字节
    int b;
};

我曾经在一个高并发服务里，就是因为没注意这个，性能死活上不去。加上填充后，吞吐量直接翻倍。

小技巧： 可以用 std::hardware_destructive_interference_size（C++17）来获取当前平台的缓存行大小，不用硬编码64。

知识体系总览

下面这张图，是我自己总结的数据局部性优化框架。你可以对照着检查自己的代码：

嗯，这张图基本把这一章的核心内容都串起来了。你写代码的时候，可以对照着看看，自己的数据访问模式属于哪一类，有没有优化的空间。

最后说一句：数据局部性优化，不是银弹。但它是最低成本、最高回报的优化手段之一。很多时候，改几行代码，性能就能翻倍。何乐而不为呢？

📚 课程目录

3. 数据局部性优化：时间局部性与空间局部性、循环交换与数据重排、缓存行对齐

3.1 时间局部性与空间局部性

3.2 循环交换与数据重排

3.3 缓存行对齐

知识体系总览