缓存友好的 Map：flat_map 与 unordered_flat_map 对比 STL

现代 CPU 的运行速度比主存快数百倍。一次缓存未命中会让核心停顿数百个周期等待数据。这种不对称使得缓存友好性——而非渐近复杂度——成为小数据集上数据结构性能的主导因素。

std::map 和 std::unordered_map 是基于节点的容器：每个元素单独堆分配。boost::container::flat_map 和 boost::unordered_flat_map 用连续存储替代节点，牺牲插入速度换取缓存局部性。本文在冷缓存条件下对四种容器做 benchmark，解释为什么 flat 变体在交易系统常见的读多写少、小数据集场景下能赢。

---

四种容器

std::map — 红黑树

每个元素是一个堆分配的节点，包含 pair<const Key, Value>，加上三个子/父指针和一个颜色位。查找需要 O(log N) 次指针追踪，每次都可能触发缓存未命中，因为节点散落在堆上。

         [50]           ← 节点：{key, value, left, right, parent, color}
        /    \
      [30]   [70]       ← 每个节点：独立的堆分配
      / \     / \
    [10][40][60][90]    ← 遍历 = 指针追踪 = 缓存未命中

节点大小：sizeof(pair) + 3 × sizeof(ptr) + 1 → 64 位平台上通常 48–80 字节/节点，其中只有 key 和 value 是有效载荷。

boost::container::flat_map — 有序数组

元素以 pair<Key, Value> 连续存储在有序数组中。查找是二分搜索（O(log N)），但每次探测访问的是连续数组中缓存行对齐的元素——CPU 预取器可以预测访问模式。

[10][30][40][50][60][70][90]   ← 连续的 pair 数组
   ↑ 二分搜索探测点            ← 内存连续 → 可预取

没有每元素开销。插入需要移动元素（最坏 O(N)），对 POD 类型来说是 memmove。

std::unordered_map — 链式哈希表

每个桶是一个链表，元素是堆分配的节点。哈希冲突时分配新节点并链接。查找平均 O(1)，但沿链遍历意味着在散落的节点间指针追踪。

bucket[0]: → [K1,V1] → [K5,V5] → nullptr
bucket[1]: → nullptr
bucket[2]: → [K3,V3] → nullptr
bucket[3]: → [K7,V7] → [K2,V2] → [K9,V9] → nullptr

每个节点是独立的堆分配。桶数组本身是连续的，但元素不是。

boost::unordered_flat_map — 开放寻址哈希表

元素直接存储在桶数组中。冲突时，二次探测搜索下一个空槽。没有链、没有每元素指针、没有独立分配。

bucket[0]: [K1,V1]
bucket[1]: [空]
bucket[2]: [K3,V3]
bucket[3]: [K7,V7]    ← 探测序列：3,4,7,12,21...
bucket[4]: [K2,V2]    ← （二次探测偏移）
bucket[5]: [K9,V9]
bucket[6]: [K5,V5]
bucket[7]: [空]

整个哈希表是一块连续内存。遍历是线性扫描，遇到空槽跳过。

---

内存布局对比

关键洞察是指针密度。数据结构中的每个指针都是一个潜在的缓存未命中，因为跟踪它意味着跳到任意地址。

容器	每元素开销	指针追踪	连续性
std::map	3 个指针 + 颜色位	有（树遍历）	无
std::unordered_map	1 个指针 + 桶间接	有（链遍历）	仅桶数组
flat_map	无	无（索引运算）	完全
unordered_flat_map	无	无（探测运算）	完全

以 flat_map 为例，N=100 个 pair<uint64_t, PodValue<64>>（每个 72 字节），整个数据结构只有 100 × 72 = 7,200 字节——完全在 L1 缓存（32 KiB）内。二分搜索最多触碰 log2(100) ≈ 7 条缓存行。

同样的数据在 std::map 中，每个节点约 128 字节（72 载荷 + 48 开销 + 对齐），散落在堆上。7 层树遍历可能触碰 7 条缓存行，分布在 7 个不同的 4 KiB 页中，没有任何空间局部性。

---

Benchmark 方法论

要复现真实性能，需要模拟冷缓存场景，而不是大多数朴素 benchmark 产生的暖缓存数字。G:\flat_map 项目实现了 5 项控制：

1. 独占 CPU 核心

在 Linux 上用 cset 隔离核心：

cset set -c 2-63 -s system
cset set -c 0-1 -s benchmark
cset proc -m -k -f root -t system
echo 0 > /sys/devices/system/cpu/cpu1/online
cset proc -s benchmark -e ./flat_map_bench

消除其他进程的调度抖动。

2. rdtscp 周期级精确计时

rdtscp 指令读取 CPU 时间戳计数器，带隐式序列化。Benchmark 用它测量单个操作，而非批量平均：

inline uint64_t rdtsc_start() {
    unsigned int aux;
    return __rdtscp(&aux);
}

inline uint64_t rdtsc_end() {
    unsigned int aux;
    _mm_lfence();           // 序列化后再读
    return __rdtscp(&aux);
}

结束测量前的 lfence 确保所有先前指令已退休。

3. 每次测量前淘汰缓存

CacheEvictor 分配 2× L3 缓存大小的缓冲区，随机遍历每条缓存行。随机（非顺序）访问模式防止 CPU 缓存替换策略保留旧数据：

class CacheEvictor {
    // 2× L3 大小缓冲区
    void evict() {
        const size_t total_lines = buf_size_ / 64;
        for (size_t i = 0; i < 10 * total_lines; ++i) {
            size_t idx = dist(rng_) * 64;
            sink += *reinterpret_cast<uint64_t*>(buf_ + idx);
        }
    }
};

模拟容器最近未被访问的”冷缓存”场景——在管理数千个小 map 实例的服务器应用中很常见。

4. 固定种子随机数据

用 std::mt19937_64 生成数据，种子固定（42）。确保：

• 各次运行的 key 分布相同
• 公平对比：std::map 的树形和 std::unordered_map 的冲突链长度是确定的

5. Google Benchmark 手动计时

for (auto _ : state) {
    evictor.evict();
    uint64_t t0 = rdtsc_start();
    // ... 被测操作 ...
    uint64_t t1 = rdtsc_end();
    state.SetIterationTime(static_cast<double>(t1 - t0));
}

UseManualTime() 让 Google Benchmark 使用 rdtscp 测量的周期数，而非挂钟时间。

---

Benchmark 参数

参数	取值	理由
键类型	uint64_t、std::string（4–16 字符）	整型和短字符串是最常见的两种键
值大小	8、32、64、128 字节	从小结构体到中等对象
元素数量	10、50、100、500、1000	聚焦小数据集
值类型	POD、non-POD	POD 允许 memcpy/memmove；non-POD 需要逐元素拷贝

所有结果为每次操作的 CPU 周期数，冷缓存条件下测量。

---

测试结果

插入性能

整型键，PodValue<64>：

N	map	unordered_map	flat_map	unordered_flat_map
10	~1,400	~1,100	~800	~600
50	~9,000	~7,000	~4,500	~2,800
100	~20,000	~15,000	~11,000	~5,500
500	~130,000	~90,000	~280,000	~28,000
1000	~300,000	~190,000	~900,000	~55,000

小数据集（N ≤ 100，值 ≤ 64 字节）下，flat_map 插入比 map 和 unordered_map 都快。原因：flat_map 的有序数组插入是对一小块连续内存做 memmove，对 POD 类型极快。基于节点的容器必须为每次插入做堆分配。

超过交叉点（N ≈ 100–500）后，flat_map 的 O(N) 移位占主导，性能急剧下降。

字符串键，PodValue<64>：

字符串键把交叉点推得更低。字符串比较比整型比较慢，且 pair<string, ValType> 不再是 POD——flat_map 必须逐个移动元素而非 memmove。相比 map 和 unordered_map 的优势缩小甚至消失。

关键结论： flat_map 插入只在整型键 + POD 值 + 小数据集时有竞争力。unordered_flat_map 插入在所有情况下都占优。

查找性能

整型键：

N	map	unordered_map	flat_map	unordered_flat_map
10	~400	~250	~150	~120
50	~700	~280	~250	~130
100	~900	~300	~350	~140
500	~1,300	~350	~800	~160
1000	~1,600	~400	~1,000	~170

flat_map 查找始终比 map 快 40–100%。二分搜索触碰的是连续缓存行，预取器可以预测；map 的树遍历是一串指针追踪的缓存未命中。

小数据集（N ≤ 100，值 ≤ 64 字节）下，flat_map 甚至比 unordered_map 快。unordered_map 的哈希计算加链遍历的开销，比在 L1 内连续数组上做 7 次二分搜索探测还大。

unordered_flat_map 查找在所有情况下最快：一次哈希计算加上连续数组中的短探测序列。

字符串键：

字符串键缩小了 flat_map 对 unordered_map 的优势，因为字符串比较比整型比较慢。二分搜索最多做 log2(N) 次字符串比较，每次可能比较多字符。但 flat_map 仍始终优于 map。

遍历性能

容器	每元素周期（N=100，整型键，PodValue<64>）
std::map	~120
std::unordered_map	~80
flat_map	~4
unordered_flat_map	~5

这是最戏剧性的结果。flat_map 和 unordered_flat_map 的遍历比基于节点的容器快 20–30 倍。原因是纯顺序访问：预取器远远走在遍历循环前面，让流水线不断获得数据。基于节点的容器每个元素需要一次指针解引用，预取器无法工作。

这个结论不受数据集大小、值大小或键类型的影响。对连续内存的顺序访问永远比指针追踪快。

POD vs non-POD

固定 N=100，Size=128，整型键：

容器	POD 插入	non-POD 插入	变慢幅度
std::map	基准	~慢 10%	节点分配占主导
std::unordered_map	基准	~慢 15%	节点分配占主导
flat_map	基准	~慢 60–80%	memmove → 逐元素移动
unordered_flat_map	基准	~慢 40–50%	rehash 拷贝 → 逐元素移动

POD vs non-POD 主要影响 flat 容器的插入性能。值类型为 POD 时，flat_map 的插入移位和 unordered_flat_map 的 rehash 可以使用 memcpy/memmove——对整块做一次 SIMD 优化操作。值类型为 non-POD 时（自定义拷贝/移动构造函数），每个元素必须单独移动。

查找和遍历性能不受 POD vs non-POD 影响：这些操作不拷贝或移动元素。

---

为什么冷缓存很重要

micro-benchmark 中一个常见错误是测量暖缓存性能：在紧循环中运行操作数千次后取平均。这给出偏低的数字，因为前几次迭代后整个数据结构已在 L1 缓存中。

在真实应用中——尤其是交易系统——情况不同：

1. 多实例。 管理数千用户连接的服务器可能有数千个小 map 实例。当用户 #8472 的请求到达时，该用户的 map 已经毫秒没被访问——被其他 8,471 个 map 从缓存中淘汰了。

2. 上下文切换。 即使在专用核心上，OS 也可能调度内核工作（定时器中断、softirq、RCU 回调），淘汰用户的缓存行。

3. 交错的数据路径。 交易系统可能先在一个 map 中查找合约，然后立即在另一个 map 中查找对手方。第二次查找把第一个 map 从缓存中淘汰。

冷缓存场景是小型、频繁创建的 map 的真实场景。暖缓存数字是乐观的上界。

---

memcpy 的优势

flat_map 在小数据集上的秘密武器是 memmove/memcpy。向 POD 类型的有序数组插入时，尾部元素的移位编译为单条 rep movsb 或 SIMD 拷贝：

// flat_map 插入（简化）
auto pos = std::lower_bound(data.begin(), data.end(), key);
data.insert(pos, {key, value});  // 对 POD 类型调用 memmove

N=100 个 PodValue<64>（每个 72 字节），移动 50 个元素是 memmove 3,600 字节——在 x86 上约 50 ns 的单次操作。相比之下，std::map 的插入：分配节点（可能调用 malloc），链接到树中，再平衡（2–3 次指针写入加一次旋转）。光是 malloc 在争用锁时就要数百纳秒。

这个优势在以下情况下消失：

• 值类型为 non-POD（逐元素移动代替 memmove）
• 数据集大到移位触碰 L1/L2 之外的缓存行
• 字符串键使 lower_bound 的比较开销变大

---

实用选型指南

数据集小（N < 100）？
├── 是
│   ├── 读多写少？
│   │   ├── 是 → 需要有序性？
│   │   │   ├── 是 → flat_map（查找比 map 快 2–3 倍）
│   │   │   └── 否 → unordered_flat_map（全面最快）
│   │   └── 否（写多）
│   │       └── unordered_flat_map（O(1) 均摊插入）
│   └── 值类型是 POD？
│       ├── 是 → flat_map 插入仍有竞争力
│       └── 否 → flat_map 插入退化；优先用 unordered_flat_map
└── 否（N ≥ 100）
    ├── 需要有序性？
    │   ├── 是 → std::map（flat_map 插入是 O(N)）
    │   └── 否 → unordered_flat_map
    └── 需要遍历？
        └── flat_map 或 unordered_flat_map（遍历快 20 倍）

约束

两种 flat 变体都要求元素是可拷贝和可移动的——它们直接存储元素，而非通过指针。这意味着不能直接存储 std::unique_ptr 等 move-only 类型（用 std::shared_ptr 包装或用指针作为值类型）。

unordered_flat_map 不允许设置 max_load_factor——它使用内部策略决定何时 rehash。这通常没问题，但意味着无法像 std::unordered_map 那样精确控制内存/性能权衡。

C++23：std::flat_map

C++23 将 std::flat_map 和 std::flat_multimap 引入标准库，基于 Boost 的设计。接口与 std::map 几乎一致，迁移成本很低。截至 2026 年初，主流标准库实现（libc++、libstdc++、MSVC STL）已有部分或完整支持。

---

参考

• flat_map 性能调研: https://zhuanlan.zhihu.com/p/661418250
• Boost.Container flat_map: https://www.boost.org/doc/libs/1_83_0/doc/html/container/non_standard_containers.html
• Boost.Unordered 开放寻址容器: https://www.boost.org/doc/libs/1_83_0/libs/unordered/doc/html/unordered.html
• C++23 std::flat_map 提案 (P0429R9): https://wg21.link/P0429
• Intel 64 与 IA-32 优化参考手册: https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html
• Tessil 哈希表 benchmark: https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html