链表遍历的 Cache 陷阱

链表遍历与 Cache Line内存布局如何影响性能一、问题背景为什么程序越跑越慢实际应用场景Linux 内核的进程调度器每隔几毫秒调度器就要扫描所有进程找出下一个可以执行的任务。调度器的核心逻辑大概长这样——structtask_struct{structtask_struct*next;// 指向下一个进程intpid;// 进程 IDintpriority;// 优先级// ... 其他字段};// 遍历所有进程计算总优先级unsignedlongsum_priority(structtask_struct*head){unsignedlongtotal0;while(head){totalhead-priority;headhead-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 hit数据已在缓存中~1-5 nsCache miss数据不在缓存要去 RAM 取~100 ns结论一次 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(inti0;iN;i)sumarr[i];优势数据完全连续硬件 prefetcher 可以提前加载多个 cache line没有指针追踪pointer chasing的开销四、核心函数建立三种内存布局节点结构占满一个 cache linestructnode{structnode*next;intdata;charpadding[52];// 64 - 8(指针) - 4(int) 52};随机链表最差/* * 函数功能建立节点随机散布的链表 * 参数说明 * n : 节点数量 * 返回值链表头节点 */structnode*create_random_list(intn){// 第一步先分配所有节点structnode**nodesmalloc(n*sizeof(structnode*));for(inti0;in;i){nodes[i]malloc(sizeof(structnode));nodes[i]-datai;}// 第二步随机打乱顺序Fisher-Yates shufflefor(intin-1;i0;i--){intjrand()%(i1);structnode*tmpnodes[i];nodes[i]nodes[j];nodes[j]tmp;}// 第三步按打乱后的顺序建立链接for(inti0;in-1;i){nodes[i]-nextnodes[i1];}nodes[n-1]-nextNULL;structnode*headnodes[0];free(nodes);returnhead;}连续链表中等/* * 函数功能建立节点连续排列的链表 * 参数说明 * n : 节点数量 * 返回值链表头节点 */structnode*create_sequential_list(intn){// 一次分配一大块连续内存structnode*nodesmalloc(n*sizeof(structnode));for(inti0;in;i){nodes[i].datai;if(in-1){nodes[i].nextnodes[i1];// 指向下一个相邻节点}else{nodes[i].nextNULL;}}returnnodes[0];}数组最佳/* * 函数功能建立连续数组 * 参数说明 * n : 元素数量 * 返回值数组指针 */int*create_array(intn){int*arrmalloc(n*sizeof(int));for(inti0;in;i){arr[i]i;}returnarr;}遍历函数固定为普通遍历/* 链表遍历随机和连续都用这个 */unsignedlongtraverse_list(structnode*head){unsignedlongsum0;while(head){sumhead-data;headhead-next;}returnsum;}/* 数组遍历 */unsignedlongtraverse_array(int*arr,intn){unsignedlongsum0;for(inti0;in;i){sumarr[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_arrayN是节点数量六、验证结果实验环境项目详情CPUAMD Ryzen 7 5700XL1 数据缓存256 KiB约 4,096 个节点L2 缓存4 MiB约 65,536 个节点L3 缓存32 MiB约 524,288 个节点系统Ubuntu 22.04.5 LTS, Linux 6.8.0编译器gcc 11.4.0,-O2节点数量 N 1,000,000约 64 MiB大于 L3 缓存 32 MiB三种布局的测量结果如下随机链表perfstat-eL1-dcache-loads,L1-dcache-load-misses,cycles ./test_random1000000L1-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_sequential1000000L1-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_array1000000L1-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 的工作原理访问模式Prefetcher 行为结果顺序访问数组检测到规律提前加载多个 cache line几乎无 miss连续指针连续链表检测到规律提前加载下一个节点miss 降低随机指针随机链表无法检测规律不预测每次都是 miss数学模型设nnn 节点数量ThitT_{hit}Thit​ cache hit 时间~1 nsTmissT_{miss}Tmiss​ cache miss 时间~100 nsppp cache miss rate总执行时间TTTTn×(Thitp×Tmiss)T n \times (T_{hit} p \times T_{miss})Tn×(Thit​p×Tmiss​)对应到实验数据随机链表p4.23%p 4.23\%p4.23%连续链表p3.82%p 3.82\%p3.82%数组p0.21%p 0.21\%p0.21%代入公式可以粗略估算三者的时间差异和实测结果基本吻合当ppp降低 1%n107n 10^7n107时节省107×1%×100ns10ms10^7 \times 1\% \times 100ns 10ms107×1%×100ns10ms为什么 L1 miss rate 只有 4%你可能注意到 L1 miss rate 只有 3-4%而不是 100%这是因为perf统计的是所有L1 数据缓存访问包括栈变量、全局变量、函数参数等链表遍历只是程序的一部分还有大量其他内存访问我们真正关心的是数据趋势连续链表的 miss rate 比随机低约 0.5%虽然 0.5% 看起来很小但考虑到数十亿次访问累积的时间差异非常可观八、为什么不能直接遍历错误示范假设内存是连续的// 错误示范假设 malloc 会分配连续内存structnode*headmalloc(sizeof(structnode)*N);// 但实际上 malloc 每次分配的内存地址可能完全不连续// 导致链表节点随机散布性能下降 1.8 倍结果代码没问题但性能差 1.8 倍正确做法根据场景选择数据结构场景推荐数据结构原因频繁插入/删除链表连续布局利用 prefetcher频繁遍历/查找数组最佳 cache 行为内存受限链表随机可接受灵活分配九、边界条件与特殊情况节点大小小于 Cache Line当节点大小 64 bytes 时多个节点可以放在同一个 cache line节点大小每个 cache line 节点数连续布局优势16 bytes4 个更大一次加载 4 个节点32 bytes2 个中等64 bytes1 个较小本文实验N 小于 Cache 容量时N与 cache 关系三种布局差异10⁴小于 L2差异不大10⁵大于 L2小于 L3开始出现差异10⁶大于 L3差异显著条件对性能的影响节点大小 64 bytes连续布局优势更大N L2 容量三种布局差异不大N L3 容量差异显著1.8x ~ 20x十、总结核心思想三种布局的差异可以用三个词概括随机散布malloc独立分配 → prefetcher 无法预测 → 每次 cache miss连续排列一次分配整块内存 → prefetcher 可预测 → miss rate 降低数组完全连续 无指针追踪 → 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内存布局L1 miss rate时间 (s)相对速度随机链表4.23%0.16571.0x连续链表3.82%0.09221.8x数组0.21%0.008320.0x