数据结构

缓存行对 C++ 性能的影响有多大？实测告诉你 面试题：“遍历 vector 比遍历 list 快多少倍？"——答案不是 2 倍，是 10~100 倍。原因只有一个字：缓存。 故事：为什么 vector 存 20 个 HTTP 头比 unordered_map 还快 开发 Hical Web 框架时，我面临一个选择：HTTP 请求头用什么容器存？ 直觉说 unordered_map<string, string> 查找 O(1)，肯定比 vector<pair<string, string>> 的 O(n) 快。但实测结果打脸——vector 线性扫描 20 个头部，比 unordered_map 哈希查找还快 40%。 原因就是 cache line。这篇文章讲清楚这件事。 一、CPU 缓存：被忽视的性能悬崖 1.1 速度鸿沟 你的程序跑在 CPU 上，但数据存在内存里。两者之间有一道巨大的速度鸿沟： 1 2 3 4 5 6 7 8 9 10 11 ┌──────────┐ │ CPU 寄存器│ ~0.3 ns (1 cycle) ├──────────┤ │ L1 Cache │ ~1 ns (3-4 cycles) 32-48 KB / 核 ├──────────┤ │ L2 Cache │ ~4 ns (10-12 cycles) 256 KB-1 MB / 核 ├──────────┤ │ L3 Cache │ ~12 ns (30-40 cycles) 8-32 MB / 共享 ├──────────┤ │ 主内存 │ ~60-100 ns (150-300 cycles) └──────────┘ 关键数字：L1 和主内存的延迟差 100 倍。 ...