CPU 跑得快内存跟不上这中间的等待就是性能黑洞。手写 prefetch预取指令能提前把数据从内存拽进缓存但用错了不但没收益还会拖慢程序。这篇用链表遍历做实验对象讲清__builtin_prefetch的用法、软件流水线software pipelining的正确姿势以及「预取距离prefetch distance够早但别太早」这条经验怎么落地。1. 引子链表遍历为什么慢数组遍历快是因为元素连续排布CPU 的**硬件预取器hardware prefetcher**能猜到下一批要访问的地址提前把它们送进缓存。链表不一样每个节点的next指针存的是「下一个节点在哪」只有读完了当前节点才知道下一步跳去哪。这种「读了才知道地址」的访问模式叫pointer-chasing指针追逐硬件预取器猜不出来于是每走一步都要等一次内存延迟。数组遍历地址连续硬件预取器提前搬下一段 [0][1][2][3][4][5][6][7] ──► 缓存命中率高 链表遍历地址散落跳哪去了读了才知道 [A]──►[F]──►[C]──►[H]──►... ──► 每次跳转都可能缓存未命中缓存未命中cache miss的代价很大一次主存访问约几百个 CPU 周期而 L1 缓存只要几个周期。链表越大、节点越分散未命中越严重。这就是软件预取software prefetch想解决的问题在 CPU 真正需要之前提前发出取数请求。2. 核心概念prefetch 只是「提示」GCC/Clang 提供内置函数__builtin_prefetchx86 上也有等价 intrinsic_mm_prefetch// 三个参数地址、读写0读 1写、局部性0~3越大越希望留在缓存__builtin_prefetch(constvoid*addr,intrw,intlocality);它不改变程序语义。只是一条给 CPU 的提示告诉它「这块内存马上要用先搬进缓存」。三个局部性档位对应 x86 的不同指令locality含义x86 指令0无时间局部性用一次就丢prefetchnta1低局部性prefetcht22中局部性prefetcht13高局部性尽量留在 L1prefetcht0看个最小例子确认 prefetch 真的「什么都不改」#includecstdiointmain(){intarr[4096]{};// 4096 个 int占多个缓存行// 预取 arr 中间某块读、高局部性__builtin_prefetch(arr[1024],0,3);// 预取 arr 尾部某块写、无局部性__builtin_prefetch(arr[3072],1,0);printf(arr[0] %d\n,arr[0]);printf(prefetch 只是提示不改变任何值\n);}arr[0] 0 prefetch 只是提示不改变任何值官方文档GCC 内建函数 __builtin_prefetch —— 参数与平台差异的权威说明3. 软件流水线提前 K 步预取光在循环里预取p-next不够刚发出请求CPU 立刻就要用它延迟根本没被掩盖。正确做法是让一个「探路指针」领先当前指针若干步提前预取更远的节点这就是软件流水线软件流水线pf 领先 p 共 dist 步提前把「未来节点」预取进缓存 p pf │◄──────────── dist 步 ──────────────►│ ▼ ▼ [A] → [B] → [C] → [D] → [E] → [F] → [G] → ... 正在读 A 提前预取 E 的缓存行 CPU 等内存 后台进行CPU 不阻塞 每走一步p 和 pf 同步右移等 p 走到 E 时E 的缓存行 早在 dist 步之前就被预取过了读它不再等内存。写成代码是这样#includecstdio#includecstdint#includevector#includerandom#includealgorithmstructNode{std::uint64_tvalue;Node*next;};// 把 pool 里的节点按随机顺序串成链表打乱索引制造缓存未命中Node*build_list(std::vectorNodepool,std::size_t n){std::vectorstd::size_tidx(n);for(std::size_t i0;in;i){pool[i].valuei;idx[i]i;}std::mt19937 rng{42};std::shuffle(idx.begin(),idx.end(),rng);for(std::size_t i0;i1n;i)pool[idx[i]].nextpool[idx[i1]];pool[idx[n-1]].nextnullptr;returnpool[idx[0]];}// 普通遍历std::uint64_twalk_plain(Node*head){std::uint64_ts0;for(Node*phead;p!nullptr;pp-next)sp-value;returns;}// 软件流水线预取pf 领先 p 共 dist 步std::uint64_twalk_prefetch(Node*head,intdist){std::uint64_ts0;Node*phead;Node*pfhead;for(inti0;idistpf!nullptr;i)pfpf-next;// pf 先走 dist 步for(;p!nullptr;pp-next){if(pf!nullptr)__builtin_prefetch(pf,0,0);// 预取 pf 指向的节点sp-value;if(pf!nullptr)pfpf-next;// pf 同步前进}returns;}intmain(){constexprstd::size_t N1u16;// 小规模只为验证正确性std::vectorNodepool(N);Node*headbuild_list(pool,N);std::uint64_tawalk_plain(head);std::uint64_tbwalk_prefetch(head,4);printf(普通遍历 sum %llu\n,static_castunsignedlonglong(a));printf(预取遍历 sum %llu\n,static_castunsignedlonglong(b));printf(结果一致 %s\n,ab?是prefetch 不改变语义:否);}普通遍历 sum 2147450880 预取遍历 sum 2147450880 结果一致 是prefetch 不改变语义官方文档C Core Guidelines Per.19 —— 内存访问要可预测prefetch 正是为「不可预测」的访问兜底4. 预取距离够早但别太早dist太小比如 1预取刚发出就要用延迟没掩盖白费。dist太大比如 32预取的节点还没轮到用可能已被新数据挤出缓存反而污染缓存。只有「刚好覆盖一次内存延迟」的距离才最优。用更大的链表实测一下量级#includecstdio#includecstdint#includechrono#includevector#includerandom#includealgorithmstructNode{std::uint64_tvalue;Node*next;};Node*build_list(std::vectorNodepool,std::size_t n){std::vectorstd::size_tidx(n);for(std::size_t i0;in;i){pool[i].valuei;idx[i]i;}std::mt19937 rng{42};std::shuffle(idx.begin(),idx.end(),rng);for(std::size_t i0;i1n;i)pool[idx[i]].nextpool[idx[i1]];pool[idx[n-1]].nextnullptr;returnpool[idx[0]];}// dist0 等价于无预取dist0 时 pf 领先 dist 步std::uint64_twalk(Node*head,intdist){std::uint64_ts0;Node*phead;Node*pfhead;for(inti0;idistpf!nullptr;i)pfpf-next;for(;p!nullptr;pp-next){if(pf!nullptr)__builtin_prefetch(pf,0,0);sp-value;if(pf!nullptr)pfpf-next;}returns;}intmain(){constexprstd::size_t N1u21;// 200 万节点超出 L3 容量std::vectorNodepool(N);Node*headbuild_list(pool,N);usingclock_tstd::chrono::steady_clock;volatilestd::uint64_tsink0;// volatile 防止遍历被优化掉constintdists[]{0,1,4,8,16,32};for(intd:dists){longlongbest1LL60;for(intr0;r3;r){// 3 轮取最小压低噪音autot0clock_t::now();sinkwalk(head,d);autot1clock_t::now();beststd::min(best,static_castlonglong(std::chrono::duration_caststd::chrono::microseconds(t1-t0).count()));}printf(dist%2d : %lld us\n,d,best);}printf(sink%llu\n,static_castunsignedlonglong(sink));}dist 0 : ~~ us dist 1 : ~~ us dist 4 : ~~ us dist 8 : ~~ us dist16 : ~~ us dist32 : ~~ us sink2199022206976这段实测能读出两件事一是sink的值固定0..N-1求和证明遍历确实完整跑完、结果正确二是不同dist的耗时差距很小、且每轮波动明显——这正是本虚拟化环境的真实情况也带出这篇最重要的判断prefetch 的收益不是免费的、也不是稳定的。在真实硬件上随机链表配合dist4~8通常能拿到可见提升但硬件预取器、缓存大小、内存延迟不同结果差异很大。手写 prefetch 必须实测不能想当然。5. 什么时候该手写什么时候别碰场景建议原因顺序访问数组 /vector别手写硬件预取器已经做得很好了手写反而浪费指令、可能干扰随机链表 / 图遍历pointer-chasing可以考虑硬件预取器猜不出地址软件预取能掩盖延迟短循环、数据量小别手写数据本来就在缓存里预取纯属多余预取距离没调对别手写太近没用、太远污染缓存反而更慢热点明确、已实测有收益手写收益已被数据证实值得保留一句话先让硬件预取器干活它搞不定的 pointer-chasing 热点再考虑手写并且一定要用真实数据验证收益。官方文档std::hardware_destructive_interference_size —— 拿缓存行大小来理解「预取单位是缓存行」官方文档std::chrono::steady_clock —— 计时用单调时钟避免墙钟回拨6. 完整示例把结论写进一个可复用的遍历器把「普通遍历」和「软件流水线预取」封装成两个模板对任意「有next指针」的链表都能用顺带打印提速比#includecstdio#includecstdint#includechrono#includevector#includerandom#includealgorithmstructNode{std::uint64_tvalue;Node*next;};Node*build_list(std::vectorNodepool,std::size_t n){std::vectorstd::size_tidx(n);for(std::size_t i0;in;i){pool[i].valuei;idx[i]i;}std::mt19937 rng{42};std::shuffle(idx.begin(),idx.end(),rng);for(std::size_t i0;i1n;i)pool[idx[i]].nextpool[idx[i1]];pool[idx[n-1]].nextnullptr;returnpool[idx[0]];}templateclassNodeTstd::uint64_tsum_plain(NodeT*head){std::uint64_ts0;for(NodeT*phead;p!nullptr;pp-next)sp-value;returns;}templateclassNodeTstd::uint64_tsum_prefetch(NodeT*head,intdist){std::uint64_ts0;NodeT*phead;NodeT*pfhead;for(inti0;idistpf!nullptr;i)pfpf-next;for(;p!nullptr;pp-next){if(pf!nullptr)__builtin_prefetch(pf,0,0);sp-value;if(pf!nullptr)pfpf-next;}returns;}intmain(){constexprstd::size_t N1u21;constexprintDIST4;std::vectorNodepool(N);Node*headbuild_list(pool,N);usingclock_tstd::chrono::steady_clock;volatilestd::uint64_tsink0;autot0clock_t::now();sinksum_plain(head);autot1clock_t::now();longlongus_plainstatic_castlonglong(std::chrono::duration_caststd::chrono::microseconds(t1-t0).count());autot2clock_t::now();sinksum_prefetch(head,DIST);autot3clock_t::now();longlongus_pfstatic_castlonglong(std::chrono::duration_caststd::chrono::microseconds(t3-t2).count());printf(plain : %lld us\n,us_plain);printf(prefetch(dist%d) : %lld us\n,DIST,us_pf);printf(sink%llu\n,static_castunsignedlonglong(sink));}plain : ~~ us prefetch(dist4) : ~~ us sink21990222069767. 延伸阅读GCC 内建函数 __builtin_prefetch参数rw/locality的精确含义与平台差异C Core Guidelines Per.19访问内存要可预测理解「为什么顺序访问快」std::hardware_destructive_interference_size缓存行大小的标准获取方式预取的最小单位std::chrono::steady_clockbenchmark 计时要用的单调时钟本知识库内的相关篇目《自定义分配器与内存池std::pmr 从零到 free list》 —— std::allocator 每次扩容都要向系统要内存《基准测试的陷阱优化掉、频率漂移、缓存预热》 —— 基准测试benchmark的三个经典陷阱《SIMD 与自动向量化marchnative、__restrict 与 likely》 —— 自动向量化auto-vectorization让编译器把标量循环翻译成 SIMD 指令8. 一句话总结手写 prefetch 只解决「硬件预取器猜不出地址」的 pointer-chasing 热点用软件流水线让探路指针领先dist步提前取数dist要「够早但别太早」太小没掩盖延迟、太大污染缓存而且必须实测验证收益——顺序访问和大多数场景下硬件预取器已经够用手写反而添乱。