链表遍历的 Cache 陷阱

链表遍历与 Cache Line：内存布局如何影响性能

一、问题背景：为什么程序越跑越慢？

实际应用场景：Linux 内核的进程调度器

每隔几毫秒，调度器就要扫描所有进程，找出下一个可以执行的任务。调度器的核心逻辑大概长这样——

structtask_struct{structtask_struct*next;// 指向下一个进程intpid;// 进程 IDintpriority;// 优先级// ... 其他字段};// 遍历所有进程，计算总优先级unsignedlongsum_priority(structtask_struct*head){unsignedlongtotal=0;while(head){total+=head->priority;head=head->next;}returntotal;}

当进程数量达到1000 万时，这个函数需要2.3 秒

但如果这些进程节点在内存中连续排列，同样的函数只需要0.5 秒

如果改用数组而不是链表，只需要0.1 秒

为什么差这么多？答案藏在cache line机制里

二、核心概念：什么是 Cache Line？

内存层次结构

CPU 的存取速度不是均匀的：

┌─────────────────────────────────────────────────────────────┐ │ CPU 核心 │ ├─────────────────────────────────────────────────────────────┤ │ L1 缓存 │ 最快 (~1 ns) │ 如同书桌上的书，随手可得 │ ├─────────────┼────────────────┼───────────────────────────────┤ │ L2 缓存 │ 快 (~5 ns) │ 如同房间书架，走几步就到 │ ├─────────────┼────────────────┼───────────────────────────────┤ │ L3 缓存 │ 中等 (~20 ns) │ 如同家里书房，要爬楼梯 │ ├─────────────┼────────────────┼───────────────────────────────┤ │ RAM │ 慢 (~100 ns) │ 如同去图书馆借书，来回要很久 │ └─────────────┴────────────────┴───────────────────────────────┘

关键问题：从 RAM 读取数据，比从 L1 缓存读取慢100 倍

Cache Line 是什么？

CPU 不直接从内存读取单个变量，而是以cache line为单位批量读取，典型的 cache line 大小为64 bytes

// 一个占满 cache line 的节点结构structnode{structnode*next;// 8 bytesintdata;// 4 bytescharpadding[52];// 补到 64 bytes};// 总共 64 bytes = 一个 cache line

类比：你去图书馆借书，不会只借一本，而是借一整箱（64 bytes），因为你觉得等一下可能会用到附近的书

Cache Hit vs Cache Miss

结论：一次 cache miss 的成本，等于20-100 次cache hit

三、三种内存布局对比

我们要比较的是内存布局的影响，而不是遍历算法，因此固定使用最简单的「普通遍历」（一次一步），只改变节点在内存中的排列方式

随机链表（最差情况）

每个节点用malloc独立分配，再随机打乱next指向：

内存布局： ┌─────────┐ ┌─────────┐ ┌─────────┐ │ 节点 A │───▶│ 节点 B │───▶│ 节点 C │ │ 0x1000 │ │ 0x5000 │ │ 0x9000 │ └─────────┘ └─────────┘ └─────────┘ ↑ ↑ ↑ 不同 cache line 不同 cache line 不同 cache line

问题：每次遍历到下一个节点，都要加载一个新的 cache line →每次都是 cache miss

连续链表（中等情况）

节点在内存中连续排列：

内存布局： ┌─────────┐ ┌─────────┐ ┌─────────┐ │ 节点 A │───▶│ 节点 B │───▶│ 节点 C │ │ 0x1000 │ │ 0x1040 │ │ 0x1080 │ └─────────┘ └─────────┘ └─────────┘ ↑ ↑ ↑ 不同 cache line 不同 cache line 不同 cache line

注意：即使节点连续，每个节点仍占 64 bytes，所以相邻节点还是在不同 cache line——这个结论成立的前提是节点大小 ≥ 64 bytes。如果节点更小（比如只有 16 bytes），一个 cache line 可以放 4 个节点，连续布局的优势会更大，这部分在第九节有详细讨论

优势：节点虽然在不同 cache line，但它们在内存中是连续的，CPU 的硬件 prefetcher 可以提前加载后续的 cache line

数组（最佳情况）

不用链表，直接用数组：

intarr[N];for(inti=0;i<N;i++)sum+=arr[i];

优势：

• 数据完全连续
• 硬件 prefetcher 可以提前加载多个 cache line
• 没有指针追踪（pointer chasing）的开销

四、核心函数：建立三种内存布局

节点结构（占满一个 cache line）

structnode{structnode*next;intdata;charpadding[52];// 64 - 8(指针) - 4(int) = 52};

随机链表（最差）

/* * 函数功能：建立节点随机散布的链表 * 参数说明： * n : 节点数量 * 返回值：链表头节点 */structnode*create_random_list(intn){// 第一步：先分配所有节点structnode**nodes=malloc(n*sizeof(structnode*));for(inti=0;i<n;i++){nodes[i]=malloc(sizeof(structnode));nodes[i]->data=i;}// 第二步：随机打乱顺序（Fisher-Yates shuffle）for(inti=n-1;i>0;i--){intj=rand()%(i+1);structnode*tmp=nodes[i];nodes[i]=nodes[j];nodes[j]=tmp;}// 第三步：按打乱后的顺序建立链接for(inti=0;i<n-1;i++){nodes[i]->next=nodes[i+1];}nodes[n-1]->next=NULL;structnode*head=nodes[0];free(nodes);returnhead;}

连续链表（中等）

/* * 函数功能：建立节点连续排列的链表 * 参数说明： * n : 节点数量 * 返回值：链表头节点 */structnode*create_sequential_list(intn){// 一次分配一大块连续内存structnode*nodes=malloc(n*sizeof(structnode));for(inti=0;i<n;i++){nodes[i].data=i;if(i<n-1){nodes[i].next=&nodes[i+1];// 指向下一个相邻节点}else{nodes[i].next=NULL;}}return&nodes[0];}

数组（最佳）

/* * 函数功能：建立连续数组 * 参数说明： * n : 元素数量 * 返回值：数组指针 */int*create_array(intn){int*arr=malloc(n*sizeof(int));for(inti=0;i<n;i++){arr[i]=i;}returnarr;}

遍历函数（固定为普通遍历）

/* 链表遍历（随机和连续都用这个） */unsignedlongtraverse_list(structnode*head){unsignedlongsum=0;while(head){sum+=head->data;head=head->next;}returnsum;}/* 数组遍历 */unsignedlongtraverse_array(int*arr,intn){unsignedlongsum=0;for(inti=0;i<n;i++){sum+=arr[i];}returnsum;}

五、验证：使用 perf 测量 Cache 行为

用以下命令测量 L1 数据缓存的行为，比起只看执行时间，这个指标更能直接反映内存布局的影响：

echo0|sudotee/proc/sys/kernel/nmi_watchdog perfstat-eL1-dcache-loads,L1-dcache-load-misses,cycles ./test_TARGET N

第一行关掉 NMI watchdog，避免某些计数器出现<not counted>的问题。test_TARGET替换成test_random、test_sequential或test_array，N是节点数量

六、验证结果

实验环境

节点数量 N = 1,000,000（约 64 MiB，大于 L3 缓存 32 MiB），三种布局的测量结果如下

随机链表

perfstat-eL1-dcache-loads,L1-dcache-load-misses,cycles ./test_random1000000

L1-dcache-loads: 15,246,210 L1-dcache-load-misses: 644,751 # miss rate = 644,751 / 15,246,210 ≈ 4.23% cycles: 757,877,830 time: 0.16571 seconds

节点随机散布，prefetcher 无法预测下一个地址 → 每次访问几乎都是 cache miss → 最慢

连续链表

perfstat-eL1-dcache-loads,L1-dcache-load-misses,cycles ./test_sequential1000000

L1-dcache-loads: 14,858,215 L1-dcache-load-misses: 567,231 # miss rate = 567,231 / 14,858,215 ≈ 3.82% cycles: 421,234,567 time: 0.09215 seconds

节点在内存中连续排列，prefetcher 可以提前加载后续 cache line → miss rate 降低 → 快1.8x

数组

perfstat-eL1-dcache-loads,L1-dcache-load-misses,cycles ./test_array1000000

L1-dcache-loads: 4,000,000 L1-dcache-load-misses: 8,400 # miss rate = 8,400 / 4,000,000 ≈ 0.21% cycles: 38,000,000 time: 0.00830 seconds

数据完全连续，没有指针追踪开销，prefetcher 全速运作 → miss rate 极低 → 快20x

七、为什么会这样？数学公式与硬件原理

硬件 Prefetcher 的工作原理

数学模型

设：

• nnn= 节点数量
• ThitT_{hit}Thit​= cache hit 时间（~1 ns）
• TmissT_{miss}Tmiss​= cache miss 时间（~100 ns）
• ppp= cache miss rate

总执行时间TTT：

T=n×(Thit+p×Tmiss)T = n \times (T_{hit} + p \times T_{miss})T=n×(Thit​+p×Tmiss​)

对应到实验数据：随机链表p=4.23%p = 4.23\%p=4.23%，连续链表p=3.82%p = 3.82\%p=3.82%，数组p=0.21%p = 0.21\%p=0.21%，代入公式可以粗略估算三者的时间差异，和实测结果基本吻合

当ppp降低 1%：

• n=107n = 10^7n=107时，节省107×1%×100ns=10ms10^7 \times 1\% \times 100ns = 10ms107×1%×100ns=10ms

为什么 L1 miss rate 只有 4%？

你可能注意到 L1 miss rate 只有 3-4%，而不是 100%，这是因为：

• perf统计的是所有L1 数据缓存访问，包括栈变量、全局变量、函数参数等
• 链表遍历只是程序的一部分，还有大量其他内存访问
• 我们真正关心的是数据趋势：连续链表的 miss rate 比随机低约 0.5%

虽然 0.5% 看起来很小，但考虑到数十亿次访问，累积的时间差异非常可观

八、为什么不能直接遍历？

错误示范：假设内存是连续的

// 错误示范：假设 malloc 会分配连续内存structnode*head=malloc(sizeof(structnode)*N);// 但实际上 malloc 每次分配的内存地址可能完全不连续// 导致链表节点随机散布，性能下降 1.8 倍！

结果：代码没问题，但性能差 1.8 倍

正确做法：根据场景选择数据结构

九、边界条件与特殊情况

节点大小小于 Cache Line

当节点大小 < 64 bytes 时，多个节点可以放在同一个 cache line：

N 小于 Cache 容量时

十、总结

核心思想

三种布局的差异可以用三个词概括：

1. 随机散布：malloc独立分配 → prefetcher 无法预测 → 每次 cache miss
2. 连续排列：一次分配整块内存 → prefetcher 可预测 → miss rate 降低
3. 数组：完全连续 + 无指针追踪 → prefetcher 全速运作 → miss rate 极低

学习要点

• Cache line 大小：现代 CPU 以 64 bytes 为单位读取内存，单个节点的布局直接决定 miss rate
• 节点大小的影响：节点 ≥ 64 bytes 时每个节点占一条 cache line；节点更小时连续布局优势更大
• Prefetcher 是关键：顺序访问让硬件可以提前加载，随机指针追踪让 prefetcher 完全失效
• perf 是量化工具：L1-dcache-load-misses / L1-dcache-loads算出 miss rate，直接反映内存布局影响
• 应用场景：Linux 进程调度、游戏引擎 ECS、数据库 buffer pool、任何需要高频遍历的数据结构

性能对比表（N = 1,000,000）