第5章内存访问模式

课程目录第5章内存访问模式

5. 内存访问模式：局部性原理与缓存预取

大家好，我是你们的讲师。今天我们来聊聊内存访问模式。这个话题，说白了就是「怎么让CPU少等一会儿」。

我刚开始做嵌入式开发时，写过一段图像处理代码。功能没问题，但跑起来慢得像蜗牛。我反复优化算法，效果甚微。后来一位老同事看了一眼，说：「你瞅瞅你的内存访问模式。」我这才意识到，很多时候瓶颈不在CPU，而在内存。

你想想看，CPU主频动辄几GHz，而内存访问延迟还在几十纳秒级别。这中间的鸿沟，全靠缓存来填。但缓存不是万能的——你得顺着它的脾气来。

5.1 局部性原理：两个核心概念

局部性原理，是缓存能工作的理论基础。它分两种：时间局部性和空间局部性。

5.1.1 时间局部性

时间局部性的意思是：如果一个数据被访问了，那么它在不久的将来很可能再次被访问。

举个最简单的例子：循环中的计数器。

int sum = 0;
for (int i = 0; i < 1000000; i++) {
    sum += i;
}

变量 i 和 sum 在每次循环中都被反复访问。这就是时间局部性在起作用。缓存会把这些频繁访问的数据留在身边，避免每次都去内存取。

我的经验： 我在优化一个实时音频处理库时，发现一个查找表被反复查询。我把它从全局变量改为 static const，并确保它对齐到缓存行。结果延迟降低了30%。说白了，就是让编译器知道这个数据「很热」，别把它换出去。

5.1.2 空间局部性

空间局部性的意思是：如果一个数据被访问了，那么它附近的数据很可能也会被访问。

缓存每次从内存取数据，不是只取一个字节，而是取一整块——这叫缓存行（cache line），通常是64字节。所以，如果你访问了数组的第一个元素，那么接下来的15个int（假设int是4字节）都会被一起加载到缓存里。

// 空间局部性好：顺序访问
int arr[1024];
int sum = 0;
for (int i = 0; i < 1024; i++) {
    sum += arr[i];
}

// 空间局部性差：跳跃访问
int sum2 = 0;
for (int i = 0; i < 1024; i += 64) {
    sum2 += arr[i];
}

第一个循环，每次访问都在同一个缓存行内连续推进，缓存命中率极高。第二个循环，每次跳过63个元素，几乎每次都要重新加载缓存行——这叫缓存行颠簸。

注意： 我曾经在调试一个矩阵乘法时，因为把内层循环的索引写反了（行优先 vs 列优先），导致性能差了10倍。原因就是空间局部性被破坏了。记住：C语言是行优先存储，遍历时尽量按行来。

5.2 如何利用缓存预取

缓存预取，是硬件和软件共同配合的一种技术。硬件会自动预测你接下来要访问哪些地址，提前把数据加载到缓存里。但硬件不是万能的——它只能识别规律性的访问模式。

5.2.1 硬件预取

现代CPU都有硬件预取器。它能识别出步长固定的访问模式，比如顺序遍历数组。但遇到随机访问、链表遍历、或者步长变化很大的情况，硬件预取就失效了。

我举个例子：

// 硬件预取友好：步长固定
for (int i = 0; i < N; i++) {
    process(data[i]);
}

// 硬件预取不友好：随机访问
for (int i = 0; i < N; i++) {
    process(data[random_index[i]]);
}

第一个循环，硬件预取器能轻松预测下一个地址。第二个循环，索引是随机的，硬件根本猜不到——这时候性能就会断崖式下跌。

5.2.2 软件预取

当硬件预取靠不住时，我们可以手动干预。GCC和Clang都提供了 __builtin_prefetch 这个内建函数。

// 软件预取示例
void process_linked_list(struct node *head) {
    struct node *curr = head;
    while (curr) {
        // 预取下一个节点
        __builtin_prefetch(curr->next, 0, 3);
        // 处理当前节点
        do_work(curr);
        curr = curr->next;
    }
}

参数说明：

第一个参数：要预取的地址
第二个参数：0表示读，1表示写
第三个参数：预取强度，0~3，3表示最积极

我的建议： 软件预取是一把双刃剑。用好了能提速，用不好反而会污染缓存。我一般只在链表遍历、树遍历这种「硬件预取无能为力」的场景下使用。而且一定要实测——不要凭感觉加预取。

5.3 实战：矩阵转置的优化

我们来看一个经典案例：矩阵转置。

// 原始版本：空间局部性差
void transpose_naive(int *src, int *dst, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dst[j * n + i] = src[i * n + j];
        }
    }
}

// 优化版本：分块 + 预取
void transpose_blocked(int *src, int *dst, int n) {
    const int BLOCK = 64;  // 缓存行大小
    for (int i = 0; i < n; i += BLOCK) {
        for (int j = 0; j < n; j += BLOCK) {
            // 处理一个块
            for (int ii = i; ii < i + BLOCK && ii < n; ii++) {
                for (int jj = j; jj < j + BLOCK && jj < n; jj++) {
                    dst[jj * n + ii] = src[ii * n + jj];
                }
            }
        }
    }
}

分块版本为什么快？因为它把访问限制在一个缓存行大小的块内，保证了空间局部性。原始版本每次写 dst 时都跨行跳跃，缓存行利用率极低。

    核心结论： 优化内存访问模式，本质上就是「让数据尽量在缓存里待着，别老往外跑」。时间局部性让你重用数据，空间局部性让你连续访问。两者结合，性能自然就上去了。

5.4 知识体系图

下面这张图总结了本章的核心逻辑：

5.5 避坑指南

最后，分享几个我踩过的坑：

不要迷信预取：我曾经在一个顺序遍历的循环里加了软件预取，结果性能反而下降了。因为硬件预取已经做得很好，软件预取只是多此一举。
注意缓存行伪共享：多线程环境下，如果两个线程频繁修改同一个缓存行里的不同变量，会导致缓存行在多个核心之间来回传递。解决办法是把变量按缓存行对齐，或者用填充（padding）隔开。
结构体布局很重要：把经常一起访问的字段放在结构体的开头，让它们落在同一个缓存行里。把不常用的字段往后放。

我曾经犯过的错： 有一次我优化一个网络包处理函数，把所有的统计计数器放在一个结构体里。结果多线程下性能惨不忍睹——就是因为伪共享。后来我把每个计数器单独对齐到64字节，性能直接翻倍。教训就是：多线程下，缓存行是共享资源，要小心对待。

好了，关于内存访问模式就讲到这里。记住一句话：让数据靠近CPU，让访问变得规律。这是缓存优化的核心，也是你写出高性能代码的基石。

📚 课程目录

5. 内存访问模式：局部性原理与缓存预取

5.1 局部性原理：两个核心概念

5.1.1 时间局部性

5.1.2 空间局部性

5.2 如何利用缓存预取

5.2.1 硬件预取

5.2.2 软件预取

5.3 实战：矩阵转置的优化

5.4 知识体系图

5.5 避坑指南