仅当节点连续分配且能预判10–20步内访问地址时才用__builtin_prefetch；参数选addr=&nodes[next_id]、rw=0、locality=3，确保地址合法，多线程中不解决竞争。
什么时候该用 __builtin_prefetch 加速 DFS？
DFS 本身是栈式访问、跳转剧烈的结构，缓存友好性差；但如果你的节点数据是连续分配的（比如数组模拟树、图的邻接表用 std::vector 存且已预留空间），且能预判「接下来大概率要访问哪个节点」，这时才值得手动 prefetch。盲目加反而增加指令开销、打乱 CPU 流水线。
- 预取只对「未来 10–20 次迭代内会读的内存」有效，太远的地址 prefetch 会被硬件丢弃
- 必须确保预取地址合法（不能是空指针、未分配内存、已释放对象）
- 多线程 DFS 中，prefetch 不同步、不原子，别指望它解决竞争
__builtin_prefetch 的参数怎么选才不翻车？
GCC/Clang 的 __builtin_prefetch 有三个参数：addr、rw、locality。DFS 场景下几乎只用读操作、局部性中等：
- 第一个参数必须是「你确定马上要读的指针」，比如
&nodes[next_id]，不是nodes[next_id].data（后者是值，不是地址） - 第二个参数写
0（读）就行，DFS 很少改节点元数据；写1（写）会触发写分配，反而拖慢 - 第三个参数推荐
3（高局部性，多级缓存都预取），0（无局部性）基本没用，1或2在 DFS 中收益不稳定
示例：
if (next_id < nodes.size()) {
__builtin_prefetch(&nodes[next_id], 0, 3);
dfs(next_id);
}
DFS 里 prefetch 放在哪一行最容易失效？
放在递归调用「之后」或「条件判断之前」是常见错误：
立即学习“C++免费学习笔记（深入）”；
- 放在
dfs(next_id);后面 → 编译器可能直接优化掉，或 prefetch 发生时函数已返回 - 放在
if (next_id 前 → 可能对非法 <code>next_idprefetch，触发段错误（尤其开启-fsanitize=address时）
正确位置是：检查通过后、实际解引用前，且尽可能靠近后续读操作。比如：
- 邻接表遍历中，prefetch 下一个
adj[u][i]对应的节点，而不是adj[u]本身 - 树 DFS 中，prefetch 子节点结构体首地址，而不是子节点某个字段的地址
为什么加了 prefetch 反而变慢？
最常见原因是「预取了根本不会用到的地址」：
- 图稀疏时，大量
next_id是无效值（比如 -1 或哨兵），却仍执行 prefetch - 使用指针数组（
Node** children）时，prefetch 了指针变量本身，而非它指向的内容 - 在 debug 模式（
-O0）下测试 —— 此时 prefetch 指令不被优化，但其他代码极慢，掩盖真实收益；必须用-O2或-O3测
另一个隐蔽问题是：某些 CPU（如部分 ARM Cortex）对频繁 prefetch 敏感，可能抢占 L1D 带宽。如果 DFS 节点小（
真正起作用的，永远是「你知道下一步大概率读哪块内存，而且这块内存还没进缓存」——不是所有 DFS 都满足这个前提。
