2. 局部性原理：时间局部性与空间局部性

说到内存访问优化，局部性原理是绕不开的核心。我做了这么多年性能优化，发现很多性能问题归根结底就是没用好这个原理。说白了，CPU 比内存快太多了，它大部分时间都在等数据。你如果能利用好局部性，就能让数据乖乖待在缓存里，程序自然就快了。

什么是局部性原理？

局部性原理其实就两个概念：时间局部性和空间局部性。我习惯这么理解——

• 时间局部性：刚用过的数据，很快还会再用。就像你写代码时频繁访问的循环变量。
• 空间局部性：刚用过的数据附近的数据，很快也会被用到。比如遍历数组时，相邻元素会被顺序访问。

你想想看，CPU 的缓存机制就是基于这个原理设计的。L1 缓存只有几十 KB，但命中率能到 90% 以上，靠的就是局部性。

时间局部性：别反复加载同一份数据

先看时间局部性。我遇到过不少新手，写循环时喜欢在每次迭代里重新计算一些固定值。比如这样：

// 糟糕的写法：每次循环都重新计算
for (int i = 0; i < 1000; i++) {
    int factor = computeExpensiveFactor();  // 每次循环都调用
    result[i] = data[i] * factor;
}

// 好的写法：只计算一次
int factor = computeExpensiveFactor();  // 只调用一次
for (int i = 0; i < 1000; i++) {
    result[i] = data[i] * factor;
}

嗯，这里要注意。第一个版本每次循环都调用 computeExpensiveFactor()，每次调用都会产生新的内存访问。而第二个版本只计算一次，后面循环里直接复用。这就是时间局部性的典型应用。

空间局部性：让数据挨着放

空间局部性更常见。我记得有一次优化一个图像处理程序，性能死活上不去。后来发现是数组访问顺序的问题。

看这个例子：

// 空间局部性差：按列访问
for (int j = 0; j < COLS; j++) {
    for (int i = 0; i < ROWS; i++) {
        matrix[i][j] = 0;  // 每次跳一行，缓存不友好
    }
}

// 空间局部性好：按行访问
for (int i = 0; i < ROWS; i++) {
    for (int j = 0; j < COLS; j++) {
        matrix[i][j] = 0;  // 连续访问，缓存友好
    }
}

为什么会这样？因为 C/C++ 里二维数组是按行存储的。按行访问时，matrix[i][0] 到 matrix[i][COLS-1] 在内存里是连续的。CPU 加载一个缓存行（通常 64 字节）时，会把相邻的几个元素一起带进来。按列访问就惨了，每次都要跳到下一行的同一列，缓存行里的其他数据全浪费了。

如何利用局部性写出高效代码？

我总结了几个实战技巧，你可以直接用到项目里：

1. 循环嵌套时，内层循环尽量访问连续内存。比如二维数组，让内层循环遍历列而不是行。
2. 结构体字段按访问频率排列。把经常一起访问的字段放在一起，减少缓存行浪费。
3. 使用局部变量代替全局变量。局部变量通常在栈上，访问速度快，而且更容易利用时间局部性。
4. 避免在热路径上使用指针跳转。链表、树这类结构空间局部性差，能换成数组就换数组。

一个完整的优化案例

来看一个实际例子。假设我们要计算两个数组的点积：

// 优化前：空间局部性差
float dot_product_bad(float* a, float* b, int n) {
    float sum = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i] * b[i];  // 两个数组交替访问
    }
    return sum;
}

// 优化后：利用空间局部性
float dot_product_good(float* a, float* b, int n) {
    float sum = 0;
    // 一次加载多个元素，利用缓存行
    for (int i = 0; i < n; i += 4) {
        float a0 = a[i], a1 = a[i+1], a2 = a[i+2], a3 = a[i+3];
        float b0 = b[i], b1 = b[i+1], b2 = b[i+2], b3 = b[i+3];
        sum += a0 * b0 + a1 * b1 + a2 * b2 + a3 * b3;
    }
    return sum;
}

第二个版本手动展开了循环，让 CPU 可以一次加载多个连续元素。虽然代码长了点，但性能提升很明显。我测试过，在数据量大的时候能快 20%-30%。

知识体系图

下面这张图总结了局部性原理的核心逻辑：

总结

局部性原理不是什么高深理论，它就是告诉我们：让数据访问模式符合硬件的缓存机制。时间局部性让你复用数据，空间局部性让你连续访问。这两招用好了，你的代码性能会有质的提升。

我个人的习惯是，写代码前先想想数据流。如果发现访问模式很随机，就停下来想想能不能重新组织数据。这比事后加各种优化技巧管用得多。