鸿雁自南人自北

Hash Table Benchmark

2026-06-13T15:27:44.000Z

这是一组关于 C++ 哈希表和哈希函数的benchmark。测试内容包括查询、插入、删除、遍历等操作，也覆盖了多种数据分布。

结果主要用来比较“哈希表 +哈希函数”这个组合在不同操作、不同数据类型、不同数据规模下的表现。实际选择时，可以根据自己的应用场景，在这些结果里找更合适的哈希表和哈希函数。

测试数据采集于 2022 至 2023 年（机器配置见下文），文章整理发布于 2026年。

阅读结果前须知

不同哈希表对 key的分布和操作类型都很敏感，同一个实现换一组数据后，性能排名就可能变化很大。换句话说，不存在一个哈希表在所有数据、所有操作上都是最快的。

选择哈希表时，比较好的做法是把数据特征、操作类型、业务要求和哈希函数一起考虑。

这个 benchmark主要测试一些常见数据分布下，哈希表不同操作的性能。不过，真实数据分布总可能和这里测试的数据有很大差别，不同场景对不同指标的要求也不一样。因此，最可靠的做法仍然是在真实应用里测试。

测试方法

测试项目

测试对象是不同哈希表和不同哈希函数的组合。对于每一种组合，测试插入、删除、查询（包括命中和未命中）以及遍历在不同数据上的性能。更详细的测试项目如下。

序号	测试项目	说明
1	预留空间后插入	插入 n 个元素前先调用 `map.reserve(n)`
2	不预留空间直接插入	不提前 reserve，直接插入 n 个元素
3	删除并插入	不断执行一次删除和一次插入，使 map 大小保持不变
4	查询表内已有 key（hit）	反复查询已经在表中的元素
5	查询表内不存在的 key（miss）	反复查询不在表中的元素
6	以 50% 概率查询到表内 key	反复查询一组 key，其中每个 key 有 50% 概率在表中
7	大 `max_load_factor` 下查询表内已有 key（hit）	与测试 4 相同，但先把 `max_load_factor` 设为 0.9 并rehash
8	大 `max_load_factor` 下查询表内不存在的 key（miss）	与测试 5 相同，但先把 `max_load_factor` 设为 0.9 并rehash
9	大 `max_load_factor` 下以 50% 概率查询到表内 key	与测试 6 相同，但先把 `max_load_factor` 设为 0.9 并rehash
10	遍历整张表	多次遍历整张哈希表
11	默认和较大 `max_load_factor` 下的堆内存占用与`load_factor`	记录测试 4 和测试 7 中构造 map 后的堆内存占用和`load_factor`

上面的项目里可以看到，几个查询测试会使用更大的max_load_factor。load_factor表示哈希表被填满的程度，max_load_factor 是 STL中控制其上界的 API。这样做是因为不同哈希表可能有不同的扩容策略和max_load_factor，即使元素数量一样，不同表也可能选择不同的load_factor，占用不同大小的内存。load_factor和内存占用会很大程度上影响查询性能，所以使用较小max_load_factor的哈希表，查询性能可能变好，也可能变差。另一方面，更高的load_factor 可能带来更高的冲突概率，从而降低查询性能。

另外，追求极限查询性能时往往要求哈希表尽量少占空间，以降低 cache miss率。当可用内存非常有限时，也可能更希望使用较高的load_factor。一个做法是设置更高的max_load_factor，然后 rehash；或者在主要构造过程之前就把max_load_factor 设大。

对上面每一种测试，都会测试吞吐和延迟（在测试平台满足延迟测试条件时）。吞吐测试的结果通常更有代表性，因为现代软件运行在流水线CPU上，几乎所有操作前后都会有其他指令，能够充分利用流水线。不过在一些特定场景下，延迟数据也很重要。这里的延迟测试结果主要供有特殊需求的场景参考，它本身有比较大的局限性。

测试数据

benchmark中使用的数据都是随机生成的，测试数据可以选择不同的随机种子。每种哈希表会在32 到 10^7 的不同数据规模下测试。

测试 key 包括不同分布的 64位整数，以及不同长度的字符串。详细的数据类型如下表。

序号	Key 类型	Value 类型	说明
1	只有若干分散 bit 位携带信息的 `uint64_t`	`uint64_t`	key 的特点是：只有某些位置上的 bit 可能为 1，其他 bit 都是0。对于大小为 n 的测试数据，最多有 ceil[log2(n)] 个固定位可能为 1。比如key 类型如果是 `uint8_t`（实际测试中是`uint64_t`），测试规模为 7，那么 key 会用`rng() & 0b10010001` 这样的方式生成。这类 bit分布可以比较全面地检查哈希表和哈希函数能否处理“有效信息只出现在特定 bit位置”的 key。
2	在 [0, UINT64_MAX] 上均匀分布的 `uint64_t`	`uint64_t`	key 在 [0, UINT64_MAX] 范围内服从均匀分布。
3	高位被 mask 掉的 `uint64_t`	`uint64_t`	高位 bit 被设为 0。对于大小为 n 的测试数据，最多有 ceil[log2(n)]个固定位可能为 1。比如 key 类型如果是 `uint8_t`（实际测试中是`uint64_t`），测试规模为 7，那么 key 会用`rng() & 0b00000111` 生成。
4	低位被 mask 掉的 `uint64_t`	`uint64_t`	低位 bit 被设为 0。对于大小为 n 的测试数据，最多有 ceil[log2(n)]个固定位可能为 1。比如 key 类型如果是 `uint8_t`（实际测试中是`uint64_t`），测试规模为 7，那么 key 会用`rng() & 0b11100000` 生成。
5	只有若干分散 bit 位携带信息的 `uint64_t`	56 bytes struct	key 的分布与数据 1 相同。payload 是 56 bytes 的结构体，使得`sizeof(std::pair)==64`。
6	最大长度为 12 的短字符串	`uint64_t`	key 是最大长度为 12的字符串，长度和字符都随机生成。编译器或标准库可能会使用 Small StringOptimization（SSO）。
7	固定长度为 12 的短字符串	`uint64_t`	key 是固定长度为 12 的字符串，字符随机生成。编译器或标准库可能会使用Small String Optimization（SSO）。
8	最大长度为 24 的中等长度字符串	`uint64_t`	key 是最大长度为 24 的字符串，长度和字符都随机生成。
9	固定长度为 24 的中等长度字符串	`uint64_t`	key 是固定长度为 24 的字符串，字符随机生成。
10	最大长度为 64 的长字符串	`uint64_t`	key 是最大长度为 64 的字符串，长度和字符都随机生成。
11	固定长度为 64 的长字符串	`uint64_t`	key 是固定长度为 64 的字符串，字符随机生成。

在 uint64_t 能表示的范围内，我们选择了几种不同分布作为key。uint64_t范围内的均匀随机整数最容易用伪随机数生成，但在真实场景中并不常见。

如果关心整数 key下的性能，强烈建议重点看第一组数据的结果，而不是第二组均匀随机分布的数据。第一组数据更能检查哈希表和哈希函数处理多样化模式的能力；均匀随机分布的测试，基本只能说明它们对均匀随机分布本身的处理能力。而真实数据里，很少有key 恰好在 [0, 2^63 - 1] 范围内均匀随机分布。

基于这个考虑，整数 key的分析主要关注第一组数据。为了让文章不至于太长，其余整数数据集（包括第二组均匀随机分布，以及高位、低位被mask 的数据）大多只在各测试文章的附录里给出图，不再展开分析。

字符串数据使用了不同字符集。对于定长字符串，其模式和第一组整数数据类似：只有某些位置上的bit 可能不同，其余 bit都是固定的。这个模式主要用来测试哈希函数的质量。

对于变长字符串，字符串中可以出现可打印字符的一个子集。

真实数据分布常常是有偏的。如果一种哈希函数和哈希表的组合只能处理一种分布，却不能处理其他分布，那么这个组合面对未知分布时就不够稳健。如果数据分布是提前知道的，则可以为这类数据选择最快且稳定的哈希表。

测试的哈希函数和哈希表

下面是测试中使用的哈希函数。

名称	类型	说明	链接
std::hash	Normal	由编译器/标准库实现；在 libc++ 和 libstdc++ 中，整数类型使用identity hash
absl::hash	Normal	Google 实现；使用 128-bit 乘法结果和 xor-shift	https://github.com/abseil/abseil-cpp
robin_hood::hash	Normal	对整数 key 使用 xor-shift、乘法、xor-shift；对字符串 key 类似`absl::hash`	https://github.com/martinus/robin-hood-hashing
xxHash_xxh3	Bytes	为字符串设计；整数类型测试中为了通过编译使用 identityhash，因此不会出现在整数 key 的结果中	https://github.com/Cyan4973/xxHash

最早的测试里还包含一些 seed hash function，也就是同时接收 key 和 seed作为参数的哈希函数。为了让测试对象更简单，后来删除了这些哈希函数，并且所有哈希表都使用无seed 版本。

整数 key 的测试不会展示 xxHash_xxh3 的结果。早期版本的absl::Hash 在 arm64 平台和 x86-64平台上行为不一致，导致在某些数据集上表现很差。因此以前还放过一个uint128_mul::hash 作为对照，它和 x86-64 平台上的absl::Hash 类似。新版 absl::Hash已经修复了这个问题，所以这里删除了 uint128_mul::hash。

下面列出测试的哈希表。这里有些哈希表依赖“好的”哈希函数才能正常工作，也就是哈希函数需要在不均衡key 上也尽量生成均匀分布的 hashvalue。如果用了不具备这种性质的哈希函数（比如 identityhash），这些哈希表的性能可能会明显下降。这些哈希表可能默认 key 的 hashvalue已经在输出范围内均匀分布，因此要求哈希函数具有比较好的均匀性或扩散性。

这里的含义是，“好的”哈希函数往往比最简单的哈希函数（identityhash）复杂，需要更多指令才能完成计算。有些哈希表并不依赖很好的哈希函数，也许是因为它们自己会对hash value再做一次混淆来改善均匀性。对于这样的哈希表，哈希函数越简单越好，最好就是identity hash。因此比较时应该始终比较“哈希表 +哈希函数”的组合，而不是固定哈希函数比较哈希表，或者固定哈希表比较哈希函数。

测试的哈希表如下。

名称	是否需要好的哈希函数	说明	链接
std::unordered_map	No*	由 STL 实现；libc++ 和 libstdc++ 的实现可能不同。
ska::flat_hash_map	No	非常快且简单；使用 robin hood hash；每个元素有`alignof(value_type)` 的内存开销；需要较小的`load_factor`	https://github.com/skarupke/flat_hash_map
ska::bytell_hash_map	No	比 `ska::flat_hash_map`略慢，但每个元素只多一字节内存开销	https://github.com/skarupke/flat_hash_map
absl::flat_hash_map	Yes	使用 SIMD 和 metadata；查询不存在 key时很快；每个元素多一字节内存开销	https://abseil.io/about/design/swisstables
absl::node_hash_map	Yes	比 `absl::flat_hash_map` 慢，但 rehash后不会让指针失效	https://github.com/abseil/abseil-cpp
tsl::robin_map	Yes	使用 robin hood hash 的快速哈希表；内存开销不低于`ska::flat_hash_map`	https://github.com/Tessil/robin-map
emhash::HashMap7	Yes	lookup hit 操作很快	https://github.com/ktprime/emhash
fph::DynamicFphMap	No	动态完美哈希表（perfect hash table）：构造时为这组 key生成几乎无冲突的映射，查询几乎不需要探测，所以查询非常快但插入慢；每个元素有2~8 bit 的内存开销	https://github.com/renzibei/fph-table
fph::MetaFphMap	No	使用 metadata 的动态 perfect hash table；在 lookup miss 场景下好于`fph::DynamicFphMap`	https://github.com/renzibei/fph-table
robin_hood::unordered_flat_map	Yes	使用 robin hood hash 的哈希表	https://github.com/martinus/robin-hood-hashing
ankerl::unordered_dense_map	Yes	把元素存在 dense array 中；遍历最快；内存占用紧凑	https://github.com/martinus/unordered_dense

* 注：在测试的 libc++ 和 libstdc++ 版本中，libc++的实现需要好的哈希函数，而 libstdc++ 没有这个要求。如果使用std::hash，libc++ 在大小为 2 的幂时性能可能很差。

粗略看一下就会发现，上面很多哈希表为了追求速度，都使用了 robin hoodhashing 技术。

实验和结果

这个 benchmark 的代码在 https://github.com/renzibei/hashtable-bench。

测试平台

平台 1：Intel Xeon E-2388G CPU @ 3.20 GHz，最高 boost 到 5.1GHz；x86-64；Rocket Lake。

平台 2：M1 Max Macbook Pro 16 inch, 2021；arm64；Firestorm。

由于 arm64 平台（M1 Max）缺少高精度的时间戳计数器，延迟只在 x86-64平台上测试（AMD CPU 在使用 TSC 测延迟时也会有一些问题，所以延迟只测试Intel CPU）。另外，对于 x86-64平台，也做了一些设置来保证测试结果稳定，包括：

使用 taskset 命令设置 CPU core affinity
关闭超线程
在 /etc/default/grub 的 GRUB_CMDLINE_LINUX中加入 isolcpus= 和 rcu_nocbs= 来隔离核心
关闭部分省电选项，包括禁用 ondemand systemdservice，并在 grub command line 中设置 idle=poll 和intel_idle.max_cstate=0
关闭 timer tick interrupt，重新编译内核并设置CONFIG_NO_HZ_FULL=y，同时在 grub command line 中设置nohz_full=
其他一些降低系统延迟抖动的设置，可以参考 https://rigtorp.se/low-latency-guide/

这些设置在 macOS 上无法完成。不过 macOS上不测操作延迟，所以影响不大。

结果

吞吐数据会用每次操作的平均时间表示。图中展示不同数据规模下的平均单次操作时间，时间越短，性能越好。

延迟数据由于篇幅限制，在大多数测试中只展示 99分位延迟。这个指标可以帮助观察哈希表的最坏时间复杂度和长尾延迟，但它甚至还不足以反映真正的最坏情况。对于有长尾特征的分布，0.99、0.999、0.9999分位的值都可能差别很大。如果应用对实时性和尾延迟有严格要求，比如游戏或高频交易，那么这类指标值得重点关注。

如果某项测试耗时过长，就会被记为 timeout，并把时间设为0；这样的数据点不会画出来。

可以点击图例中的标签，隐藏或显示特定哈希表和哈希函数对应的数据线。

结果按照数据类型和操作类型分成下面几组。

结论

简单说，没有一个哈希表适合所有workload。应该选哪一个，取决于主要操作是什么、key长什么样、以及可用内存有多少。如果查询占主导，并且表构造一次后主要用于查询，那么perfect hash table fph::DynamicFphMap 很难被超过；如果 miss很常见，fph::MetaFphMap也值得考虑，代价是构造较慢。对于插入和查询混合的一般用途，absl::flat_hash_map搭配 absl::Hash是一个快速、紧凑且稳健的默认选择；ska::flat_hash_map在数据还留在 cache里时最快；如果频繁遍历，ankerl::unordered_dense_map是更该优先考虑的选择。std::unordered_map在大多数测试中都偏慢，主要价值是指针稳定性。

更完整的选择理由，以及各测试和各 workload 下的对比，可以看分析与结论。

局限

资源独占

测试中，测试程序几乎可以独占所有计算机资源，尤其是 cache资源。这在实际应用中相对少见。真实应用里，其他进程和任务可能会占用一部分cache。因此在实际场景中，应该预期可用 cache 会更少。

warm cache 与 cold memory

测试中既没有做 warmup，也没有专门测试 cold start场景。这里会在一段数据范围内反复测试某个操作很多次。因此，当操作次数远大于数据量时，可以认为大多数操作访问的是warm cache；当操作次数小于数据量时，大多数操作访问的是 coldmemory。在测试中受限于测试时间，数据量较小时，操作次数会远大于数据量；数据量较大时，操作次数会等于数据量。

庞大的测试空间

测试空间至少包含：

1	\|hash table set\| x \|hash function set\| x \|data sets\| x \|operation set\| x \|hardware platform set\| x \|compiler set\|

可以看到，可测试空间相当大。任何一个哈希表集合或哈希函数集合的增加，都会明显增加测试工作量。受时间和资源限制，这里只探索了一部分组合，还有许多组合和空间没有测试。

因此，如果要为某个具体用途选择最合适的哈希表和哈希函数，仍然应该在实际应用场景里做真实测试。

后记

这个 hash table benchmark 系列前后拖了至少四年。第一版数据 2022年就有了，当时 M1 Max 还是很新的 CPU，现在 M5都出来了。之所以花了这么长时间，是因为整理这么多图表和分析实在太繁琐了。我大概2022 年到 2023年间就完成了主体文章的撰写，但是很多收尾工作因为懒一直没做。并且由于这件事一直拖着，博客也陷入了head-of-line blocking的境地：总想着“我还没有完成这个系列的文章”，于是一直没有更新其他文章。

这几年里，很多东西都变了。CPU 更新了很多代，也有了一些新的 hashfunction / hash table 面世， LLM技术也在这段时间飞速发展。这些博客里讲的很多东西可能已经有些过时了。只能感叹一句，逝者如斯夫，不舍昼夜。

不管这个评测系列的文章质量如何，我决定结束迭代，就此发出吧。

Hash Table Benchmark - 12 byte 字符串查询

2026-06-13T13:55:00.000Z

这一篇测试 12 byte 字符串 key 下的查询性能。

点击图例中的标签，可以隐藏或显示图中对应哈希表和哈希函数的数据线。

这一篇测试三种情况下哈希表的查询性能：

查询表中存在的 key（命中，successful find）。
查询表中不存在的 key（未命中，unsuccessful find）。
查询有 50% 概率在表中的 key。

测试里有两种 key：定长 12 byte 的字符串，以及最长 12 byte的变长字符串。

和整数测试不同，字符串 key 的查询会把很大一部分时间花在哈希函数和 key比较上：整个字节序列都要算一遍哈希，命中时还要把候选 slot里的字节和查询的 key逐字节比较。这让哈希函数的选择比在整数测试中重要得多。这里测试了四个哈希函数：std::hash、absl::Hash、robin_hood::hash 和xxHash_xxh3；其中 xxh3专为字节序列设计，所以对那些查询开销主要花在哈希函数上的表，它往往最快。第二个字符串特有的因素是小字符串优化（SSO）：12字节的 std::string会内联存放在字符串对象内部，因此没有单独的堆分配，访问这些字符也不需要解引用指针。定长变体让每个key 恰好 12 字节，而变长（max length）变体下 key 长度在 12字节以内浮动，这也会触发哈希和比较代码里依赖长度的分支。下面每张图默认显示每个表最快的那个哈希函数（点击图例可以展开其余）；吞吐图同时给出Xeon E-2388G 和 M1 Max 的结果，延迟只在 Xeon 上测试。

吞吐

查询表中存在的 key（命中）

使用默认 max_load_factor

:

命中查询时，表需要计算 hash、找到 slot，然后真正把查询的 12个字节和存储的 key 比较，所以每个表都要付出完整的“哈希 + 比较”代价。在Xeon E-2388G 上，只要工作集还在 cache 里，perfect hash 的fph::DynamicFphMap 最快：搭配xxHash_xxh3，它在 1,024 个元素时一次命中约 6.5 ns，32,768时约 8.4 ns，领先于所有常规的表。这正是 fph 发挥优势的区间，因为它的最小perfect hash 保证 key 在第一次探测就落到自己的 slot上，唯一的一次访存就是它读取的那个 slot。当表的大小超过 L3 cache后，情况反转：一旦查询变成访存受限，反而是那些探测序列短、访问局部性好的表占优。在10^7 个元素时， tsl::robin_map 和ska::flat_hash_map（都搭配 xxh3）以约 42 ns 领先，而fph::DynamicFphMap 慢到 57 ns，metadata 更重的fph::MetaFphMap 慢到 64 ns，因为 perfect hash table把元素铺在更稀疏的数组上，规模一大就更容易 cache miss。

这里哈希函数的选择最为关键。对大多数开放寻址和 perfect hash的表，xxHash_xxh3是最佳哈希函数，因为它们的查询循环主要被对 12 字节做哈希所主导；而SwissTable 风格的 emhash::hash_map7 和ska::bytell_hash_map 反而和 absl::Hash搭配最好。基于节点的表一旦离开 cache 就明显落后：在 10^7时，absl::node_hash_map 达到 107 ns，std::unordered_map 达到 118ns，每次查询在哈希之外还要追一个堆上节点的指针。

M1 Max 上的情况类似，但曲线更平。由于 cache 更大，SwissTable家族的表在大规模下领先（在 10^7 时，emhash::hash_map7 和ska::bytell_hash_map 约为 60-66ns）；而且在这个平台上，好几个表最优的哈希是 absl::Hash而不是 xxh3，这反映了它针对 Arm做了调优。基于节点的表依然垫底（std::unordered_map 在 10^7时约 200 ns）。

下面的变长（max length）变体表现几乎一样：所有 key 仍然都满足SSO、上限是 12字节，长度变化几乎不改变哈希和比较的代价，所以排名和数值都和定长情况吻合。较大max_load_factor 的图把元素排得更密，这在大规模下对 cache驻留略有帮助，但会拉长探测序列，整体排名不变。

:

使用较大 max_load_factor

:

查询表中不存在的 key（未命中）

使用默认 max_load_factor

:

未命中比命中代价更低，因为大多数表只靠 metadata就能排除查询，根本不用比较那 12 个字节。这正是fph::MetaFphMap 明显领先的地方：它每个 slot 的 metadata让它只需一次 metadata 检查就能回答“不存在”，所以在 Xeon 上，它在 1,024个元素时一次未命中约 3.6 ns，并且一直到 1.2M 个元素都保持在 10 ns以内（9.65 ns），远远甩开其他表。即使在 10^7 时它变成 DRAM 受限、上升到30.7 ns，也仍能和最好的 SwissTable表竞争（absl::flat_hash_map 为 25.1ns，r_h::unordered_flat_map 为 29.0 ns）。robin hood 风格的tsl::robin_map 和 ska::flat_hash_map 在 cache区间则慢得多（32,768 到 200,000 时为 16-26ns），因为它们的回移（backward-shift）探测必须走过一连串 slot，才能断定key 不存在。

由于未命中省掉了完整的逐字节比较，哈希函数在这里的影响略小一些，很多表的最佳选择变成了absl::Hash 而不是 xxh3。基于节点的std::unordered_map 在大规模下仍然最慢（10^7 时 110ns），因为即使是未命中也要先哈希，再遍历一个 bucket 的节点链。在 M1 Max上排名一致，只是绝对数值更小：fph::MetaFphMap 一直到 1.2M个元素都能在 4-6 ns 内回答未命中，10^7 时也只有 18.6ns，曲线也最稳定。

变长（max length）变体和较大 max_load_factor的图重复了同样的规律；唯一能看出的变化是：更密的大 load factor 让 robinhood 的探测串略微变长，使它们与基于 metadata 和 SwissTable的表之间的差距进一步拉大。

:

使用较大 max_load_factor

:

查询有 50% 概率在表中的 key

使用默认 max_load_factor

:

50% 命中的 workload把命中和未命中混在一起，所以它介于前两种情况之间，排名也随之变化。在Xeon 上，SwissTable 风格的 absl::flat_hash_map 和r_h::unordered_flat_map （都搭配xxh3）现在在中小规模领先，1,024 时约 6 ns，32,768 时约 13-14 ns，fph::MetaFphMap 紧贴其后；perfect hash table不再像纯命中时那样在 cache区间占据压倒性优势，因为有一半查询是未命中，而基于 metadata的表能用很低的代价处理这些查询。在 10^7 时，robin hood系的表又凭借访存局部性领先（tsl::robin_map 43.5ns，ska::flat_hash_map 44.4 ns），而std::unordered_map 落后到 119.5 ns。

M1 Max 上，r_h::unordered_flat_map 和absl::flat_hash_map在大多数规模下排第一，曲线照例更平；各表最优的哈希是 xxh3 和absl::Hash 混合。和之前一样，变长变体和较大max_load_factor 的图遵循同样的规律，没有定性变化。

:

使用较大 max_load_factor

:

延迟

P99 延迟图（仅 Xeon）展示的是查询时间分布的长尾：单次查询的 99分位，它主要由探测路径上最坏的 cache miss 和 TLB miss 决定。当工作集超过L3 cache 后，每个表的长尾都会跳到几百纳秒，因为最慢的那 1%查询现在要走一次完整的 DRAM 往返。

查询表中存在的 key（命中）

使用默认 max_load_factor

:

命中时，长尾取决于最坏情况下探测序列要碰多少条 cache line。在 cache内， fph::DynamicFphMap 和 fph::MetaFphMap的长尾最低（1,024 时约 21 ns，32,768 时约 36-37ns），因为它们的单次探测保证把最坏情况限得很紧。一旦表溢出到 DRAM，几个flat 表的长尾收敛到 460-560 ns 这一带，其中r_h::unordered_flat_map 和 absl::flat_hash_map在 10^7 时最好（约 527 和 557 ns）。基于节点的表自始至终长尾最重（10^7时 absl::node_hash_map 680ns，std::unordered_map 795 ns），因为一次查询既可能在bucket 数组上 cache miss，又可能在它指向的节点上再次 miss。

:

使用较大 max_load_factor

:

查询表中不存在的key（未命中）

使用默认 max_load_factor

:

未命中的长尾最能体现 fph::MetaFphMap 的 metadata优势：它的 P99 极其平坦，从 1,024 到 200,000 个元素只有 16-35 ns，1.2M时也只有 59.5 ns，而此时其他每个表都已经爬到几百纳秒。由于未命中靠一次metadata 读取就能定论，最坏情况很少需要第二条 cacheline，所以直到表大到连 DRAM 中常驻的页都放不下，长尾才会飙升（10^7 时482 ns）。robin hood 系的 tsl::robin_map 和ska::flat_hash_map 则相反，在 200,000 个元素时就已经跳到约412ns，因为一次最坏未命中要走过很长的探测串。std::unordered_map的长尾再次最重（10^7 时 905 ns）。

:

使用较大 max_load_factor

:

查询有 50% 概率在表中的 key

使用默认 max_load_factor

:

由于有一半查询命中，长尾由更费时的命中路径主导：flat 的 SwissTable 表r_h::unordered_flat_map 和 absl::flat_hash_map保持最好的 P99（1,024 时约 23 和 22 ns，10^7 时升到 527 和 534ns）。fph::MetaFphMap不再有它在纯未命中时那种平坦的优势，因为这个 workload里命中的那一半仍然需要逐字节比较，还可能多读一条 cache line。基于节点的std::unordered_map 的长尾又一次最重（10^7 时 850ns）。变长变体和较大 max_load_factor的附录图遵循同样的规律。

:

使用较大 max_load_factor

:

← 返回 Hash Table Benchmark目录

Hash Table Benchmark - 24 byte 字符串查询

2026-06-13T13:55:00.000Z

这一篇测试 24 byte 字符串 key 下的查询性能。

点击图例中的标签，可以隐藏或显示图中对应哈希表和哈希函数的数据线。

这一篇测试三种情况下哈希表的查询性能：

查询表中存在的 key（命中，successful find）。
查询表中不存在的 key（未命中，unsuccessful find）。
查询有 50% 概率在表中的 key。

测试里有两种 key：定长 24 byte 的字符串，以及最长 24 byte的变长字符串。

24 字节的 key 已经越过了小字符串优化（SSO）的边界：这个长度的std::string 不再能内联存放（libstdc++ 最多内联 15字节），所以定长 24 字节的 key全部分配在堆上，查询必须先解引用一个指针才能取到 key的字节，再去做哈希或比较。这在 12-byte 那篇讨论过的“哈希 +比较”代价之上，又让每个 key 几乎必然多一次 cachemiss，也让定长和变长两个变体表现得相当不同：在变长 24 字节的情况下，很多key 短到能内联，从而省掉这次额外的间接访问。这里测试的哈希函数仍是std::hash、absl::Hash、robin_hood::hash和 xxHash_xxh3；由于每个 key要处理的字节更多，针对字节优化的 xxh3现在几乎对每个表都胜出。每张图显示每个表最优的哈希；吞吐图同时给出 XeonE-2388G 和 M1 Max 的结果，延迟只在 Xeon 上测试。

吞吐

查询表中存在的 key（命中）

使用默认 max_load_factor

:

和 12-byte 测试相比，有两点值得注意。第一，在 Xeon 上xxHash_xxh3 现在几乎是每个表的最佳哈希函数，因为 key更长，哈希在整体工作中占的比重更大，xxh3在字节吞吐上的优势就显出来了。第二，所有表都更慢，彼此也挤得更近：由于每个定长24 字节的 key 都在堆上，一次命中既要对 24字节做哈希，又要追一个指针去取存储的字符来做比较。在 Xeon 上，robin hood风格的 ska::flat_hash_map 和tsl::robin_map（xxh3）在大规模下领先，10^7 时约 115ns，其余 flat 表与它们相差 15-20 ns以内；std::unordered_map 是主要的例外，达到 192 ns。在cache 内（1,024 个元素），fph::DynamicFphMap 和ankerl::unordered_dense_map 最快，约 11.5-12ns，在访存流量主导之前，perfect hash table又一次得益于它的单次探测保证。

M1 Max 把各个表区分得更清楚：perfect hash 的fph::DynamicFphMap 和 fph::MetaFphMap（xxh3）在中等规模领先（32,768 时为 15.5 和 16.9ns），并一直保持在前列直到 10^7 （125.7 和 139.0 ns），这得益于 M1 的大cache 让它们更稀疏的数组驻留得更久。 std::unordered_map再次垫底（10^7 时 208 ns）。

下面的变长（maxlength）变体明显更快，小规模下往往只要一半左右的时间（比如 Xeon 上tsl::robin_map 在 1,024 时约 6.8 ns，而定长是 18.6ns），正是因为大多数变长 24 字节的 key都短到能内联，省掉了堆上的解引用。较大 max_load_factor的图排名不变，只是排得更密一些。

:

使用较大 max_load_factor

:

查询表中不存在的 key（未命中）

使用默认 max_load_factor

:

和 12 字节时一样，未命中代价更低，而 fph::MetaFphMap领先，因为它的 metadata能在不解引用堆指针、也不比较任何字节的情况下排除一个不存在的 key。在Xeon 上，它在 1,024 时回答一次定长 24 字节的未命中约 6 ns，32,768 时为10.6 ns，领先于 SwissTable 系的表（absl::flat_hash_map 11.6ns，absl::node_hash_map 12.0 ns），并一直到 10^7都最快（69.8 ns）。robin hood 系的表在中等规模再次落后（32,768 时tsl::robin_map 24.6 ns，ska::flat_hash_map25.1 ns），原因是它们的探测串更长。在 M1 Max 上这个 metadata优势更大：fph::MetaFphMap 一直到 200,000 个元素都能在4.7-9.5 ns 内回答未命中， 10^7 时也只有 40.5 ns，远远甩开其他表。

变长（max length）变体排名一致，只是绝对数值更小，因为很多 key留在内联；在 M1 Max 上，fph::MetaFphMap 一直到 1.2M个元素都低到只有 9-11 ns。较大 max_load_factor的图同样符合这一规律。

:

使用较大 max_load_factor

:

查询有 50% 概率在表中的 key

使用默认 max_load_factor

:

混合 workload 落在两者之间：在 Xeon 上，SwissTable 系的absl::flat_hash_map 和r_h::unordered_flat_map（xxh3）以及fph::MetaFphMap 都在第一梯队，1,024 时约 8.6-10.2 ns，10^7时大约 105-117 ns，std::unordered_map 落后到 187ns。由于有一半查询是未命中、根本不会碰堆上存储的字节，依赖 metadata的表在这里比纯命中时表现更好。M1 Max 上仍是同一批 flat表在前列，曲线照例更平。变长变体和较大 max_load_factor的附录图遵循同样的规律。

:

使用较大 max_load_factor

:

延迟

P99 延迟图（仅 Xeon）刻画的是最慢的 1% 查询。24字节的堆布局让这些长尾比 12 字节时更重，因为一次慢查询可能同时在 slot数组、堆上存储的 key 字节，以及页表上都发生 cache miss。

查询表中存在的 key（命中）

使用默认 max_load_factor

:

对定长 24 字节的命中，长尾陡升并收敛：到 10^7 时每个 flat 表都落在750-830 ns 这一带，其中r_h::unordered_flat_map（xxh3）最好，750ns，std::unordered_map 最差， 930 ns。从 cache内区间跳上来的幅度很大，长尾从 1,024 时约 50 ns，到 32,768时就已经升到几百纳秒，因为此时最坏情况的查询必然会在堆上存储的 key 上cache miss。变长（max length）变体的长尾明显更低（比如 10^7 时大约535-695 ns），因为内联的短 key 为这些查询省掉了那次额外的堆 miss。

:

使用较大 max_load_factor

:

查询表中不存在的key（未命中）

使用默认 max_load_factor

:

在未命中路径上，基于 metadata 的表在 cache内长尾最低：fph::MetaFphMap 和ankerl::unordered_dense_map 一直到 32,768 都保持在约 22-51ns，而 robin hood 系的表在那里就已经飙过 145 ns。到 10^7时，各表长尾再次汇合到 600-700 ns 区间。更说明问题的是变长 24字节变体：那里长尾在很长一段范围内都保持很低（即使在 200,000个元素时，领先者也接近 130 ns）才开始上升，因为大多数不存在的 key都能从内联数据里被排除，不必碰堆。这说明延迟长尾不只取决于哈希表算法，也取决于SSO 边界。

:

使用较大 max_load_factor

:

查询有 50% 概率在表中的 key

使用默认 max_load_factor

:

由于有一半查询命中，长尾由更费时的命中路径决定，定长 24 字节的曲线在10^7 时收敛到 740-980 ns 这一带，r_h::unordered_flat_map最好，745 ns，std::unordered_map 最差，980ns。fph::MetaFphMap 在纯未命中时享有的 metadata优势在这里被稀释了，因为命中的那一半仍要付出堆解引用和逐字节比较的代价。和之前一样，变长变体和较大max_load_factor 的附录图遵循同样的规律。

:

使用较大 max_load_factor

:

← 返回 Hash Table Benchmark目录

Hash Table Benchmark - 64 byte 字符串查询

2026-06-13T13:55:00.000Z

这一篇测试 64 byte 字符串 key 下的查询性能。

点击图例中的标签，可以隐藏或显示图中对应哈希表和哈希函数的数据线。

这一篇测试三种情况下哈希表的查询性能：

查询表中存在的 key（命中，successful find）。
查询表中不存在的 key（未命中，unsuccessful find）。
查询有 50% 概率在表中的 key。

测试里有两种 key：定长 64 byte 的字符串，以及最长 64 byte的变长字符串。

64 字节时，每个定长 key都远远超过了小字符串优化（SSO）的上限，所以它们全都存放在堆上，查询必须先解引用一个指针才能取到字符，再去做哈希或比较。现在一个key 就有四条 cache line那么大，这使得哈希函数的开销在整个查询中占了主导：把完整的 64字节算一遍哈希，比 slot 的下标运算耗时得多。因此，针对字节吞吐做了优化的xxHash_xxh3，在本测试中几乎都是两台机器上各个表的最佳哈希函数；而各种表布局之间的差距也缩小了，因为它们都要付出同样大的哈希和指针追逐代价。定长64 字节和变长 64 字节两个变体的区别仍然在于：变长 key里包含许多短的、可以走 SSO的字符串，能省掉堆上的间接访问。吞吐图同时给出 Xeon E-2388G 和 M1 Max的结果；延迟只在 Xeon 上测试。

吞吐

查询表中存在的 key（命中）

使用默认 max_load_factor

:

由于对 64 字节做哈希占了主导，整个梯队比短 key测试时更挤在一起，但排名仍然有参考价值。在 Xeon 上，perfect hash 的fph::DynamicFphMap 和fph::MetaFphMap（xxh3）在 cache 内最快（1,024 时约 16.4 和16.8 ns，32,768 时 54.6 和 56.5ns），靠的是它们的单次探测保证——即便哈希开销很大，这一点依然重要。在10^7 时它们仍处于前列（152.7 和 163.5 ns），但探测串短的 robin hood 系tsl::robin_map 和 ska::flat_hash_map追了上来（151.7 和 152.2 ns）。这里每个表最优的哈希都是 xxh3。基于节点的std::unordered_map 明显落后， 246.7 ns，在本就开销很大的key 解引用之上，还要再多一次对堆上节点的解引用。

M1 Max 上 perfect hash table领先得更明显，fph::DynamicFphMap 在整个范围内都最快（32,768时 15.5 ns，10^7 时 112.7 ns），这得益于 M1 的大 cache让它稀疏的数组驻留得更久。 std::unordered_map再次垫底，184.5 ns。

下面的变长（max length）变体明显更快，比如tsl::robin_map 在 1,024 时一次命中约 9.9 ns，而定长 64字节是 18.4 ns，因为可走 SSO 的短 key 既避开了堆解引用，也省掉了对完整64 字节做哈希的代价。较大 max_load_factor的图排名不变，只是排得更密。

:

使用较大 max_load_factor

:

查询表中不存在的 key（未命中）

使用默认 max_load_factor

:

未命中又一次是 fph::MetaFphMap 脱颖而出的场景：它的metadata让它在不解引用堆上存储的字符、也不比较任何字节的情况下就排除一个不存在的key，所以在 Xeon 上，它在 1,024 时领先（8.2 ns），32,768 时 16.9ns，并一直到 10^7 都最快（95.5 ns）。SwissTable 系的absl::flat_hash_map 和ankerl::unordered_dense_map 紧随其后，而 robin hood 系的tsl::robin_map 和 ska::flat_hash_map在中等规模因探测串更长而落后（32,768 时 41.6 和 43.1ns）。在这里，避免完整的 64 字节比较非常重要，所以那些靠一个 tag字节就能短路的 metadata 和 SwissTable 方案明显领先。M1 Max 放大了这个metadata 优势： fph::MetaFphMap 一直到 200,000 个元素都能在5.9-18 ns 内回答未命中，10^7 时也只有 54.2ns。std::unordered_map 在两台机器的大规模下都最慢（10^7 时Xeon 231 ns，M1 125 ns）。

变长（max length）变体排名一致，只是数值更小；较大max_load_factor 的图也符合这一规律。

:

使用较大 max_load_factor

:

查询有 50% 概率在表中的 key

使用默认 max_load_factor

:

混合 workload 介于两者之间。在 Xeon上，absl::flat_hash_map、r_h::unordered_flat_map 和fph::MetaFphMap（都用 xxh3）都在第一梯队，1,024 时约11.7-12 ns，10^7 时 137-148 ns，std::unordered_map 落后到235 ns。在 M1 Max 上， fph::MetaFphMap在大多数规模下最快（32,768 时 22.8 ns，10^7 时 104.2 ns），因为 workload里未命中的那一半正好发挥了它 metadata的长处，而命中的那一半仍然受益于它的单次探测布局。变长变体和较大max_load_factor 的附录图遵循同样的规律。

:

使用较大 max_load_factor

:

延迟

P99 延迟图（仅 Xeon）展示长尾。64 字节的 key分配在堆上，一次最坏情况的查询可能在 slot 数组、key 的堆缓冲区和页表上都cache miss，所以这里的长尾是三个字符串测试中最重的。

查询表中存在的 key（命中）

使用默认 max_load_factor

:

对定长 64 字节的命中，长尾急剧收敛：从 1,024 时约 67-92 ns，到 32,768时就跳到 550-620 ns，再到 10^7 时画出来的表大约落在 830-955 ns，其中r_h::unordered_flat_map （xxh3）排在最前，830ns，absl::node_hash_map 是它们中最慢的，955 ns。std::unordered_map 还要更慢，但它的长尾超出了图表 1,000 ns的显示上限（10^7 时约 1,025ns），所以没有画在这里。早期那段陡升，反映的是一旦缓冲区放不进 cache，对key 字节的堆访问就必然 miss。变长（maxlength）变体的长尾更低（领先的表在 32,768 时大约 290-330 ns，而定长是550 以上），因为内联的短 key 为许多未命中的查询省掉了这次访问。

:

使用较大 max_load_factor

:

查询表中不存在的key（未命中）

使用默认 max_load_factor

:

在未命中路径上，fph::MetaFphMap 在 cache内保持最低的长尾（1,024 时 24.8 ns，32,768 时 105.6 ns），因为它的metadata 不必碰堆上存储的 key 字节就能定下未命中，ankerl::unordered_dense_map 次之。robin hood系的表最早急剧上升，32,768 时就超过 400 ns。变长 64字节变体把长尾飙升的拐点大幅推后，领先者在 32,768 时仍保持在 52-62 ns左右，因为大多数不存在的 key 都短到能从内联数据里被排除。和 24字节时一样，这说明 SSO 边界对延迟长尾的影响不亚于哈希表算法本身。

:

使用较大 max_load_factor

:

查询有 50% 概率在表中的 key

使用默认 max_load_factor

:

由于有一半查询命中，长尾由更费时的命中路径主导，定长 64字节的大多数曲线在 10^7 时聚在 805-890 ns 这一带（许多表集中在 805-845ns 附近，其中 fph::MetaFphMap 最高，约 890ns）；std::unordered_map 又一次超出图表 1,000 ns的显示上限（约 1,065 ns），没有画出。fph::MetaFphMap在纯未命中时享有的 metadata优势在这里被稀释了，因为命中的那一半仍然需要堆解引用和 64字节比较。变长变体和较大 max_load_factor的附录图遵循同样的规律。

:

使用较大 max_load_factor

:

← 返回 Hash Table Benchmark目录

Hash Table Benchmark - 分析与结论

2026-06-13T13:55:00.000Z

这篇把前面 benchmark 的结果完整梳理一遍，涵盖整数和字符串 key、小value 和大 value，并讨论针对具体的 workload该怎么选哈希表和哈希函数。

没有最好的哈希表

这组 benchmark 覆盖了插入、删除、查询（命中、未命中，以及 50%混合）和遍历。测试在多种分布的整数 key、以及 12、24、64 字节的字符串 key上进行，value 分别为 8 字节和 56 字节（因此存储的 pair 为 16 或 64字节），规模从 32 一直到 10^7 个元素，跑在两台差别很大的机器上——IntelXeon E-2388G（Rocket Lake）和 Apple M1Max。在这么多变化中始终成立的一条经验是：没有哪个组合能一直最快——快慢会随workload 中占主导的操作、key 的类型和分布、value 的大小、表相对于 cache的大小，以及平台而变。

第二条值得先讲的经验是：哈希表和哈希函数必须一起选。有些表假定哈希已经把key均匀打散，一旦不是这样就会严重退化；另一些表自己会做混淆，因此更适合搭配计算代价尽可能低的哈希。因此每张图比较的都是表 + 哈希 的组合，而不是孤立地比较表。

查询

查询往往是大家最关心的操作，也是表的设计最能体现差异的地方。一次查询可以拆成三部分：计算哈希、把它映射到slot，以及加载并比较 key。哪一部分占主导，取决于 key的类型，以及表里有多少数据能放进 cache。

整数 key

对整数key，一次查询的时间分摊在计算并映射哈希、以及随后的访存之间，哪一项占主导取决于表有多少在cache 里。哈希本身的开销不一定低：identity 的 std::hash几乎不花成本，在 key 本身已经分布均匀时没问题，但如果 key的信息只集中在少数几个 bit 上——比如指针和对齐地址（低位总是0）或较小的连续 ID（高位总是 0）——在 identity hash下就会严重冲突，需要一个真正做混淆的哈希，比如absl::Hash（一次 128 位乘法加xor-shift）把它们打散到表里。因此该选哪个哈希取决于key（下文还会展开）。随着表增大，排名会经历三个阶段。当表能放进 L1/L2cache 时，访存很快——只有几纳秒——所以每次探测的指令数（哈希加 slot映射）和访存相当，正是它拉开了各表的差距；最精简的组合胜出，ska::flat_hash_map搭配 identity 的 std::hash 在小规模下最快（两台机器上 1,024个元素时每次命中约 1.3 ns），M1 上 fph::DynamicFphMap紧随其后，只落后约 0.1 ns。在中间区间，表位于 L2/L3 cache 里时，fph::DynamicFphMap 领先（Xeon 上 200,000 时约 3.4 ns，1.2M时 10.9 ns），因为它有上界的探测次数让碰到的 cache line很少。在最大的规模下，每次查询都 cache miss、访存占主导，ska::flat_hash_map 又重新最快（10^7 时 Xeon 上约 14.7ns，M1 上 9.3 ns），因为读取 cache line 最少的表——单个紧凑的 slot数组——无论用什么哈希都会胜出。

未命中则更能区分高下。要证明一个 key不存在，表必须排除它可能占据的每一个 slot，而每个 slot 存了一字节metadata 的表，无需碰完整的 key 就能做到。fph::MetaFphMap自成一档：它基本只用一次访存就能排除一个不存在的 key，从约 6,000个元素起就有最好的平均未命中时间，长尾也紧得多——在 1.2M 个元素时它的 P99未命中延迟约为 34 ns，而 r_h::unordered_flat_map /absl::flat_hash_map 约为 106-111 ns，需要走探测链的ska::flat_hash_map 和 tsl::robin_map 则为440-465 ns。这个优势一直保持到 metadata 数组本身离开 L3cache（这里大约在 10^7），之后它也要多一次 DRAM访问。在未命中上，常规表里 absl::flat_hash_map最好，因为它正是围绕同样的 metadata 思路构建的。50%命中的情况大致是两者的平均，而结果不断交替会带来分支预测失败的惩罚，使所有差距都缩小。

字符串 key

字符串 key改变了局面，因为哈希的成本高得多——要哈希和比较的是整个字符串，而不是单个64 位字——而且较长的字符串可能存放在堆上。有两个效应特别突出。

第一，面向字节的 xxHash_xxh3成为几乎每个表最优的哈希，而且字符串越长越是如此：哈希占主导，所以一个快的字节哈希比表本身更重要。第二，cache内查询的下限随长度急剧上升。在 Xeon 上，一次命中的 cache 内查询，整数key 约 1.3 ns，12 字节字符串约 6.5 ns，定长 24 字节字符串约 13 ns，64字节字符串约 16 ns。12 到 24字节之间的跳变主要来自小字符串优化（SSO）：长度不超过约 15字节的字符串会内联存放在 std::string对象内，更长的则分配在堆上，于是查询必须跟着一个指针到另一条 cache line上去比较字符。这一点在数据里直接体现出来——变长 24 字节的 key大多短到能内联，比定长 24 字节（全部分配在堆上）快约一倍（小规模下约 7ns 对 13 ns）。

除了下限更高，排名和整数情况一致：perfect hash table 在 cache内领先（对 64 字节 key，命中时 fph::DynamicFphMap 和fph::MetaFphMap 搭配 xxHash_xxh3 最快），robinhood 系的 tsl::robin_map 和 ska::flat_hash_map在变成访存受限后反超，而 fph::MetaFphMap又一次在未命中上占据主导（64 字节 key，1,024 时约 8 ns，1.2M 时 60ns，而紧随其后的表约为 63-68 ns）。

value 大小的影响

把 value 从 8 字节增大到 56 字节（64 字节的 pair）会让每个 slot大四倍，于是每一层 cache 能放下的条目更少，每个表都更早变成访存受限；在10^7 时，8 字节 value 下约 15 ns 的一次命中，到 56 字节 value 下要约 21ns。这把天平进一步推向碰 cache line 最少的表：fph::DynamicFphMap 凭借有上界的探测次数，在大 value下领先的区间比小 value 下更宽。如果 value较大，就应该给中等和大规模的结果比小规模更高的权重。

构造和修改表

对 perfect hash table，插入把查询的排名整个反转了过来。flat系的表——absl::flat_hash_map、ska::flat_hash_map、emhash::hash_map7、tsl::robin_map、ankerl::unordered_dense_map——填充最快（预留容量时，小规模下每次插入约 4-6 ns，10^7 时 25-35ns），而 std::unordered_map 慢得多（10^7 时接近 125ns），因为它为每个元素分配一个节点。perfect hash table则以很大差距垫底：在 Xeon 上，构建 perfect hash 让fph::DynamicFphMap 和 fph::MetaFphMap 在 10^7时每个元素大约要 1,450-1,900 ns，约为 std::unordered_map 的12-15 倍（M1 上为 11-12 倍）。去掉 reserve调用会让每个表的插入时间大致翻倍，因为扩容会触发反复的 rehash。

删除-插入测试交替执行一次删除和一次插入以保持表大小不变，它偏好 flat系的表（ska::flat_hash_map、tsl::robin_map、absl::flat_hash_map）；开放寻址的表会在删除的条目处留下墓碑（tombstone），而perfect hash table表现最差，在最大规模下会超时，因为它们无法低成本地应对频繁的增删。

key 的类型和 value 的大小在这里同样重要。对字符串key，每次插入和删除还要多算一次字符串哈希，对超过 SSO上限的字符串，还要为字符做一次堆分配和释放——所以 12 字节和 64 字节字符串workload之间差距很大，而整数插入则纯粹由表本身的机制主导。和查询一样，更大的value 会把访存受限的区间更早地推到前面。

遍历

遍历几乎完全由存储布局决定，与哈希函数无关，也几乎与 key的类型无关（迭代器访问的是固定大小的表slot；它不会重新哈希，对内联存储的条目也不会解引用 key）。ankerl::unordered_dense_map 和emhash::hash_map7 把条目存放在一个紧凑、连续的数组里，无论load factor 如何，每个元素的遍历时间都近似常数——Xeon 上约 0.22 ns，M1上约 2.0 ns，在整个规模范围内都很平。内联的开放寻址表必须扫描一个稀疏的slot 数组并跳过空 slot，所以代价随规模上升；基于节点的std::unordered_map 最慢，要追那些会 cache miss 的指针（Xeon上 10^7 时每个元素约 35 ns）。perfect hash table在这里没有特别的好处，因为它们遍历的也是稀疏布局。

内存占用和 load factor

在整数 key-value 上测得的内存占用，在 10^7个元素时把这些表分成三组。每个 slot 一字节 metadata 的SwissTable——absl::flat_hash_map 和ska::bytell_hash_map——最紧凑，约 272 MB；基于节点的std::unordered_map 和 absl::node_hash_map次之（约 308 MB 和 297 MB）；fph系的表为了那个加速查询的索引，占用约为最紧凑者的两倍（约 556-572MB）；而 ska::flat_hash_map 和 tsl::robin_map最大，约 768 MB，因为它们保持较低的最大 load factor，并在每个 slot里存放经过对齐填充的完整 value。

load factor 图能解释这一点。开放寻址的表按翻倍扩容，所以占用率在大约0.4 到 0.9 之间呈锯齿状起伏；ska::flat_hash_map 和tsl::robin_map 稳定在最低值（大规模下约0.30），用空槽换速度，而 std::unordered_map 接近1.0（每个元素一个节点，没有空槽）。提高 max_load_factor会把 flat 表排得更紧——ska::flat_hash_map 在 10^7 时从约0.30 升到0.60，空间利用率大致翻倍——代价是探测更长。由于内存占用决定了一个表何时跨过各级cache 的边界，这正是查询结果里那些 cache层级背后的结构性原因：更臃肿的表会在更小的元素数量上就掉出 cache。

哈希函数和表一样重要

对整数 key，std::hash 是 identity函数。自己会做混淆的表——最典型的是ska::flat_hash_map——可以安全地使用它，并享受它的零成本。但对不是均匀随机的key——那些信息只集中在少数几个 bit 上的 key，比如指针或较小的连续ID——假定哈希已经均匀的表（absl::flat_hash_map、emhash::hash_map7、tsl::robin_map）在identity hash下会发生灾难性的冲突，严重到某些组合会在构造时超时，所以它们需要一个好的混淆哈希，比如absl::Hash。即使是好的哈希也可能有弱点：robin_hood::hash对某些这类 key 模式打散得不好，使 tsl::robin_map搭配它时在中等规模出现一段不规则的塌陷。对字符串key，xxHash_xxh3 全面胜出。

平台差异：Rocket Lake 与 M1Max

两台机器的内存系统差别很大。Xeon E-2388G（Rocket Lake）有 48 KBL1、512 KB L2 和 16 MB L3，页大小 4 KB；M1 Max 有 128 KB L1、12 MB L2 和48 MB 系统级 cache，页大小 16 KB。M1 更大的 cache 和页把每一级 cache的边界都向右推，并减轻了 TLB 压力，所以虽然各表的排名在不同平台上大体一致，但一个表反超另一个的规模点并不相同。有一个怪现象：M1上 libc++ 的 std::unordered_map 用取模来索引 bucket，当bucket 数量是 2 的幂时，取模退化成一个 2的幂掩码，丢掉了哈希的高位，这使得这个组合在元素数量恰好是 2的幂时慢得反常。

如何选择哈希表

有两个实际问题基本决定了大部分选择：表被写的频率相对读有多高，以及它相对于实际能用到的cache 有多大。

关于第一个问题：如果表构造一次之后，被查询的次数远多于被修改，那么perfect hash 的 fph::DynamicFphMap（未命中常见时用fph::MetaFphMap）能给出最好的查询性能——代价是构造慢、无法应对频繁更新，以及大约是最紧凑表两倍的内存，所以它远比一个不断变化的表更适合做静态字典、以读为主的索引，或成员集合。如果插入、删除和查询混合，flat表是更均衡的全能选手，而 absl::flat_hash_map 搭配absl::Hash（字符串则用xxHash_xxh3）是一个快速、紧凑、对分布稳健的默认选择。

第二个问题需要把“cache 内很快”这句话拆开来看。一个表“在 cache里”，指的是它的整个内存占用——而不只是元素数量——能放进某一级 cache：在Xeon 上，L2 大约能放 16,000 个小（16 字节）条目，L3大约能放一百万个，而当 value 较大或 key是堆分配的字符串时，能放的数量会成比例地减少。因此，ska::flat_hash_map——在所有数据都驻留时最快的表——主要适合真正小的表，或者内存足够宽裕的场景。问题在于ska::flat_hash_map同时也是所有表里内存占用最大的（它之所以快，正是因为 loadfactor 低），所以在相同元素数量下，它比紧凑的表更早离开cache，也会更激烈地与程序其余部分争用 cache。在真实应用里，cache要和同时运行的一切共享，所以有效的阈值远低于裸 cache大小；如果内存紧张、cache 有争用，或者表很大，那么紧凑的absl::flat_hash_map 或 ska::bytell_hash_map通常会胜过它——尽管在独占整个 cache 的 benchmark 里ska::flat_hash_map略有优势。对以遍历为主的工作，无论规模大小，ankerl::unordered_dense_map 都是明确的选择。

场景	推荐
构造一次，之后大量查询（以读为主 / 静态）	`fph::DynamicFphMap`（命中为主）或`fph::MetaFphMap`（未命中为主）
通用，插入 / 删除 / 查询混合	`absl::flat_hash_map`（搭配`absl::Hash`，字符串用`xxHash_xxh3`）——快、紧凑、稳健
表很小，或有充足且无争用的 cache，想要最低查询时间	`ska::flat_hash_map`——但它是最大的表，所以一旦变大就改用紧凑的表
内存紧张、cache 共享或有争用，或表很大	`absl::flat_hash_map` 或`ska::bytell_hash_map`（最紧凑）
以遍历 / 频繁全表扫描为主	`ankerl::unordered_dense_map`
需要引用 / 指针稳定性	`absl::node_hash_map` 或`std::unordered_map`

最后的建议

std::unordered_map在几乎每一项吞吐测试里都是最慢的表，原因是它每个元素一个节点的布局，所以它主要值得在确实需要其迭代器和指针稳定性保证时保留。除此之外，上面这张表是一个起点，而不是定论：表、哈希、key分布、value 大小、表大小和平台所构成的完整空间极其庞大，真实 workload可能落在这里测过的各种情况之间。最可靠的答案永远是：在真实的数据和操作组合上，对两三个最有希望的候选做一次benchmark。

← 返回 Hash Table Benchmark目录

Hash Table Benchmark - 整数删除和插入

2026-06-13T13:55:00.000Z

这一篇测试整数 key 下反复删除和插入的性能。

点击图例中的标签，可以隐藏或显示图中对应哈希表和哈希函数的数据线。

这个测试先构造一个大小为 N 的哈希表，然后重复执行 M次下面的操作：

向哈希表中插入一个新元素
从哈希表中随机删除一个元素

这个测试结果同样和数据分布高度相关，尤其和“被删除的数据”和“新插入的数据”之间的关系有关。这里删除元素时是等概率随机选择的。真实场景里，元素未必会等概率地被删除；比如最可能被删除的元素也许正是最近插入的元素。

吞吐

这里记录的是整个过程的耗时，包括 insert 和 erase 两部分。

y 轴是平均单次操作耗时，计算方式是time/op = (time for insert + time for erase) / (2 * M)，也就是insert 和 erase 的平均耗时。这个数字反映的是对哈希表做修改的效率。

:

在 Intel Rocket Lake 上，ska::flat_hash_map 搭配std::hash 在几乎整个范围内都是最快或接近最快的一组，大约 5到 37 ns 每操作。中等规模下，emhash::hash_map7 搭配absl::Hash、以及 absl::flat_hash_map 搭配absl::Hash 也比较接近。tsl::robin_map在小规模和很大规模时都不慢，10^7 个元素时大约 39ns，但在中间规模会变慢，在 400,000 到 800,000 附近升到 60-90 ns。这和robin_hood::hash 在这些 key pattern 上分布较差有关。

在 Apple M1 Max 上，ska::flat_hash_map 和std::hash 的组合在几乎所有数据规模下都有相对优势，大约 6 到33 ns。

另外值得注意的是，M1 Max 上 absl::node_hash_map有一段明显的性能下降，在大约 45,000 到 100,000个元素之间出现一段很明显的凸起，最高接近 135ns。std::unordered_map也有类似退化，随着规模增长一路升高，在 100,000 到 300,000个元素附近达到峰值，最高约 600ns。这个现象的原因还不清楚，可能与系统的内存分配策略有关，因为这两种哈希表在每次插入和删除时都需要做内存分配和回收。这个现象在数据上更明显。

:

在 Intel Rocket Lake 上，排名和前面的 : 类似：ska::flat_hash_map 搭配 std::hash仍然有比较明显的领先优势，大约 8 到 59ns；absl::flat_hash_map 是最接近的一组。

在 M1 Max 上，当元素数量大约在 32,768 到 1,200,000之间时，absl::flat_hash_map 和emhash::hash_map7 的相对表现会好一些，其中emhash::hash_map7 搭配 absl::Hash在几个点上会略快于 ska::flat_hash_map。

延迟

这里把插入和删除的延迟分开记录。注意，这里的插入延迟和“插入和构造”测试中的插入延迟不一样：构造测试中的延迟统计的是从大小0 一直插入到大小 N 的整个过程，而本测试中哈希表的大小始终保持在 N 或 N +1 附近。

插入（删除之后）

: 插入延迟

先看 P50 latency。数据规模较小时，ska::flat_hash_map搭配 std::hash 和 tsl::robin_map 搭配absl::Hash 属于第一梯队，大约 7 到 9ns。元素数量变大后，absl::flat_hash_map 和absl::node_hash_map 搭配 absl::Hash更有优势：大约 300,000 个元素之后，ska/tsl 系列会跳到 50 ns 以上，而absl 系列仍然在 24 到 28 ns 左右。接近 10^7 个元素时，大多数open-addressed 哈希表的 median latency 又会重新接近，约 92 到 99ns。

P99 latency 上，小中规模时 emhash::hash_map7 搭配absl::Hash 的 tail latency 最小，小规模约 31 ns，并且直到约200,000 个元素之前都保持领先。再往后则是absl::flat_hash_map 更好。

说到 open-addressed 哈希表的修改，就绕不开 tombstone机制。有些哈希表执行 delete 时，会在被删除元素所在 slot放一个特殊标记，也就是 tombstone。tombstone 和 empty marker 不一样。如果tombstone 太多，lookup 性能会受影响。因此一些哈希表会在 tombstone数量达到一定比例时rehash。这会让与删除交替进行的插入操作出现很高的最大延迟。P100 latency可以显示这一点。

除了元素数量为 2的幂时第一次插入可能触发扩容外，有些哈希表在部分数据点上的 P100 latency会和元素数量成比例。在 absl 系列哈希表和robin_hood::unordered_flat_map上都能观察到这个现象。如果应用对修改操作的最大延迟有严格要求，就不应该选择这些哈希表。

:插入延迟

当 value_type 变成 64 bytes 时，小数据规模下ska::flat_hash_map 搭配 std::hash 相比tsl::robin_map 的优势会变大。P50 上最小规模时大约是 8 ns 对11 ns。

P99 latency 上，小规模时 tail latency 最小的是absl::flat_hash_map 搭配 absl::Hash，大约 33ns，领先于 ska::flat_hash_map 和emhash::hash_map7。

删除

: 删除延迟

P50 latency 上，ska::flat_hash_map 搭配std::hash 几乎总是最小，只有大约 300,000 到 800,000个元素之间例外。在这一段里，ska::flat_hash_map 会跳高到大约100 到 160 ns，因为它更激进的扩容和较低的 load_factor让底层存储落到了更慢的内存层级；而 absl::flat_hash_map 和robin_hood::unordered_flat_map 仍然较低，大约 45 到 120ns，相对表现更好。超过 1,200,000 个元素后，各表又会重新接近。

P99 latency 上，元素数量较小时 emhash::hash_map7 搭配absl::Hash 最快，约 19 ns，并且领先到大约 3,000个元素。中等规模下，absl::flat_hash_map 搭配absl::Hash 的 tail latency 更小，大约从 8,000 到 200,000个元素都是如此。元素数量再变大后，很多哈希表的表现会接近。

:删除延迟

当 value_type 是 64 bytes 时，整体情况和基本一致。

吞吐附录

:

延迟附录

插入（删除之后）

: 插入延迟

删除

: 删除延迟

← 返回 Hash Table Benchmark目录

Hash Table Benchmark - 整数遍历

2026-06-13T13:55:00.000Z

这一篇测试整数 key 下遍历哈希表的性能。

点击图例中的标签，可以隐藏或显示图中对应哈希表和哈希函数的数据线。

这个测试测量的是遍历整个哈希表的性能。

遍历和查询、插入不太一样，它的速度几乎完全取决于哈希表在内存中如何存储元素，而几乎与哈希函数无关。这里测试的哈希表大致可以分成三类：

Dense array storage.ankerl::unordered_dense_map 和emhash::hash_map7 会把所有 key-value pair紧密地存到一段连续数组里，hash slot 中只保存 index 或少量metadata。遍历时只需要线性扫描 densearray，所以单元素成本很低，而且重要的是，这个成本基本不受load_factor 影响。
Inline open addressing.ska::flat_hash_map、ska::bytell_hash_map、tsl::robin_map、absl::flat_hash_map、fph::*和 robin_hood::unordered_flat_map 会把元素直接存到稀疏的slot array 里。遍历时必须走完整个 slot array，并跳过空slot。因此表越空、slot array 越大，单元素遍历成本就越高；当 slot array超出 cache 后，这个问题会更明显。
Node-based storage. std::unordered_map和 absl::node_hash_map 会为每个元素单独分配node。遍历时要在可能分散在 heap 上的 node 之间追指针。node 还在 cache里时问题不大，一旦落到 DRAM，性能会明显下降。

吞吐

:

图中的结果和上面的分析一致。在两个平台上，ankerl::unordered_dense_map都明显最快，并且在整个数据规模范围内基本是一条平线：Xeon E-2388G 上约0.22 ns 每元素，M1 Max 上约 2.0ns。原因是它始终遍历一段紧密排列的数组，不需要关心哈希表本身有多少slot。emhash::hash_map7 排在第二，也有类似的平坦曲线，Xeon上约 0.6 ns，M1 上约 2.6 ns。

每一种 inline open-addressing table 的表现都会随元素数量变化：slotarray 超出 cache 后，单元素成本开始上升。比如ska::flat_hash_map 在小规模时约 1 ns，到 10^7个元素时，Xeon 上会升到大约 9-10ns，因为这时大部分时间都花在从内存里读取空 slot 上。node-based 的std::unordered_map 在大规模时最慢，10^7 个元素时 Xeon 上约35 ns 每元素，M1 上约 22 ns，因为遍历 node list 基本变成了一串 cachemiss 的 pointer dereference。

有几组组合的曲线在中等规模之后就中断了。absl::flat_hash_map和 absl::node_hash_map 假设 hash value分布得比较好，但整数上的 std::hash 是 identity function；在masked-bit key 上会产生大量冲突，所以构造在大规模时timeout，这些数据点被记为 0，也不会画出来。

下面的其他整数分布和 56-byte value类型给出的排名基本相同。dense-storage table 仍然平坦且最快；56-byte slot的主要影响是让 open-addressing table更早受到内存带宽限制，因为它们现在每个 slot 需要移动 64 bytes。

:

延迟

单次 iterator step 的 P99 latency从尾部延迟角度说明了同样的问题（latency 只在 x86-64平台上测试）。ankerl::unordered_dense_map不随规模变化，基本维持在约 1.6 ns，因为在 dense array 上推进 iterator不太会遇到远距离的 cache miss。inline table 和 node-based table在底层存储超过 cache 后，tail latency 会逐渐变长：10^7个元素时，open-addressing table 的 P99 step 会到几十 ns，node-based 的std::unordered_map 和 absl::node_hash_map会到几百 ns，分别约 374 ns 和 439 ns。这些尖峰对应的，通常就是下一次访问slot 或 node 时遇到的 cache miss。

:

← 返回 Hash Table Benchmark目录

Hash Table Benchmark - 内存占用和 load factor

2026-06-13T13:55:00.000Z

这篇讨论哈希表的内存占用和 load_factor。

点击图例中的标签，可以隐藏或显示图中对应哈希表和哈希函数的数据线。

在前面的测试中，我们记录了堆内存占用和load_factor。堆内存占用是通过自定义 Allocator统计的，也就是在 allocate()调用时记录分配的字节数。不过这个数字是否准确，取决于哈希表容器是否正确使用了Allocator；也就是说，所有内存分配都必须经过这个allocator。有些哈希表，比如emhash::HashMap7，并非所有堆内存分配都会经过Allocator，所以这里拿不到准确的内存数据。

C++ 里一个比较麻烦的设计是，使用不同 Allocator template参数的类属于不同类型（std::pmr container试图解决的就是这个问题）。例如，使用 std::allocator 的std::basic_string 和使用自定义 allocator 的std::basic_string 是两种类型，而 std::hash之类的哈希函数通常只兼容使用 std::allocator 的std::string。因此，这些哈希函数不能直接用于使用其他allocator的字符串；我们统计堆内存占用的方法也就统计不到字符串自己的堆内存。因此这里仅统计key 和 value 都是整数类型的情况。

还需要说明一点：如果关心的不是总堆内存占用，而是与查询速度相关的 warmmemorysize，那么这个测试里的数据不能准确反映哈希表查询时实际需要用到多少cache。有些哈希表会为了非查询操作（比如插入）保留额外空间，而这部分内存在查询时并不会访问。

这个测试使用的元素数量集合和其他测试项目不同。为了考察哈希表在不同load_factor 下的表现，元素数量选择为 2 的幂的 0.4 倍或 0.6倍，例如0.4 x 2^10, 0.6 x 2^10, 0.4 x 2^11, 0.6 x 2^11, ...。

与查询相关的 cache 占用分析

哈希表占用多少堆内存、运行在什么load_factor，会直接影响查询速度。原因是这两者共同决定了一次查询需要经过多少内存，也决定了working set 会在多大规模时超出每一级 cache。较低的load_factor 会浪费更多 slot，但 probe chain通常更短；单元素占用越小，同样大小的 cache里能放下的元素就越多。查询吞吐测试中看到的几个 cache分界点，本质上就是哈希表内存占用超过 L1、L2、L3容量的位置。所以下面两组图正好能解释那些性能拐点的成因。

这些图主要描述的是数据结构本身，而不是处理器，所以堆内存数字大体上不依赖CPU。不过 STL 实现和 allocator不同，具体数字仍然可能有差异。下面的内存图因此把 Intel 和 M1 Max的实测值分开展示；这些数字主要由数据结构决定，但也会受具体实现影响。

堆内存占用

使用默认 max_load_factor时的内存占用

:

从内存占用上看，几类哈希表分得比较清楚。SwissTable 风格的absl::flat_hash_map 和 ska::bytell_hash_map每个 slot 只多花一个 metadata byte，是最紧凑的一档，在 10^7 个整数 pair时大约占 272 MB。node-based 的 std::unordered_map 和absl::node_hash_map 次之（大约 308 MB 和 297MB），主要开销来自每个元素单独分配 node 以及指针。perfect hash tablefph::DynamicFphMap 和 fph::MetaFphMap大约是最紧凑表的两倍（约 556-572 MB），这是为了加速查询而额外使用 index和 metadata 的代价。占用最大的是 ska::flat_hash_map 和tsl::robin_map，大约 768 MB，因为它们使用较低的max_load_factor，并且每个 slot里存的都是完整的、经过对齐填充的 valuetype。emhash::hash_map7 显示为0，是因为它并没有把所有分配都交给自定义计数allocator，所以这里无法测出它的内存。

使用较大 max_load_factor时的内存占用

:

load factor

使用默认max_load_factor 时的 load_factor

:

load_factor 图解释了上面一部分内存差异。大多数open-addressing 哈希表按翻倍方式扩容，所以 load_factor会呈锯齿状变化：刚扩容后大约在 0.4 左右，下一次扩容前会到0.75-0.9。这个测试采样的是 2 的幂的 0.4 倍和 0.6倍，所以图上的值主要集中在 0.5-0.76。使用 robin_hood::hash的 ska::flat_hash_map 和 tsl::robin_map会落在最低的一档，大规模时约为 0.29-0.30，也就是用更多内存换更短的 probechain；这也是它们查询快的原因之一。另一端是std::unordered_map，它的 load_factor 接近1.0，因为每个元素本来就单独分配 node，不需要像 flat table 那样留出空slot；它的内存开销主要花在 node 和指针上，而不是空 slot 上。提高max_load_factor 会让 flat table 填得更满。比如 10^7个元素时，ska::flat_hash_map 的 load_factor会从大约 0.30 提高到大约 0.60，空 slot 差不多少了一半；代价则是 probesequence 变长、查询变慢，这个 tradeoff 会在查询测试中体现出来。

使用较大max_load_factor 时的 load_factor

:

← 返回 Hash Table Benchmark目录

Hash Table Benchmark - 整数查询吞吐

2026-06-13T13:55:00.000Z

这一篇测试整数 key 下的查询吞吐。

点击图例中的标签，可以隐藏或显示图中对应哈希表和哈希函数的数据线。

这一篇测试三种情况下哈希表的查询性能：

查询表中存在的 key（命中，successful find）。
查询表中不存在的 key（未命中，unsuccessful find）。
查询有 50% 概率在表中的 key。

查询性能与内存层级的关系

在深入查询速度的细节之前，需要先注意一点：哈希表的查询速度和 cache命中率高度相关。对于整数的key-value，哈希表的查询操作主要就是从内存里加载数据，这一部分占据了大部分时间。

现代计算机系统采用分层的内存设计。比如 Intel Rocket Lake 有寄存器、L1cache、L2 cache、L3 cache 和 DRAM，速度依次递减。M1 Max 则有 L1cache、L2 cache、SLC cache 和 DRAM。

当某一层 cache 的 miss率上升时，整体查询时间就会被下一层更慢的存储硬件速度所限制。除了 cachemiss，TLB miss 同样会带来时间惩罚。下面这张 Xeon E-2388G 上命中查询的P50（中位数）延迟图，可以帮助说明这一点。要看清其中的结构，最简单的办法是只保留一个开放寻址的表，比如ska::flat_hash_map 搭配std::hash（点击图例中的其他项把它们隐藏掉）。对这样的表，中位数的查询经过一次key 比较就能成功，所以 P50基本反映了一次访存加载的延迟，能比较紧密地跟随内存层级。

从上图可以看到，在 Intel Rocket Lake架构上，查询性能按元素数量分成四个层级：

元素能完全放进 L1 cache。在 value_type 大小为 16字节、L1 数据 cache 为 48 KB 时，大约能放下 3,072 个元素。由于ska::flat_hash_map 默认的 load factor 通常小于0.5，这一段在图中对应 32 到 1,024。
元素能完全放进 L2 cache。在 value_type 大小为 16字节、L2 cache 为 512 KB 时，大约能放下 32,768个元素。在本测试中，ska::flat_hash_map 对应的范围是 1,500到 8,192。
元素能完全放进 L3 cache。在 value_type 大小为 16字节、L3 cache 为 16 MB 时，大约能放下 1,048,576个元素。在本测试中，ska::flat_hash_map 对应的范围是 12,000到 400,000。
不得不从 RAM 读取的情况。这通常发生在 L3 cache放不下所有元素时，一般是元素数量超过 1,048,576 的时候。

除了 cache miss，TLB miss 对哈希表查询速度也有显著影响。Rocket Lake有 64 个 L1 DTLB 表项（4KB 模式下；2MB 模式下为 32 个）和 1536 个 STLB表项。因此，在 4KB 页下，元素数量超过 16,384 时就会出现相当多的 L1 TLBmiss，超过 393,216 时则会出现 L2 TLB miss。使用大页（hugepage）可以大幅减少 TLB miss。M1 Max 上的 macOS 默认使用 16 KB 页，因此TLB miss 带来的惩罚比 Rocket Lake 平台默认的 4 KB 页要小得多。在 P50曲线上，当工作集把页表撑到超出 L2 TLB 的覆盖范围时，这个 TLB miss惩罚会在前面提到的 cache 层级台阶之上再多出一级。

M1 Max 每个线程可以使用 128KB L1 数据 cache、12MB L2 cache 和 48MBSLC cache，因此 cache命中率更高，在哈希表测试的大多数数据规模下性能也更好。

查询表中存在的 key（命中）

使用默认 max_load_factor

:

大致来说，哈希表的查询时间可以拆成四部分：

哈希函数计算 hash value 的时间。
把 hash value 映射到具体内存地址的时间。
从给定内存地址加载数据的时间。
把加载到的数据和目标 key比较的时间；如果比较不相等，还要加上额外的惩罚时间。

当元素数量较少时，CPU cache往往能放下所有元素。此时第三步相对较快，另外三部分就变得重要。第一步和第二步之间存在权衡：一步多做，另一步就能少做。如果第一步的哈希函数没有把元素均匀地分布到hash 空间，第二步就需要额外的计算，把这些不均匀的 hash value分散到底层的 slot 数组里。如果第一步用的是高质量的哈希函数、能均匀分布hash value，那么第二步通常只需要一条快速的按位与指令做截断（在 slot数量为 2 的幂时）。

这一点可以从上面的图里看出来。libc++ 和 libstdc++ 对std::hash 的实现，对 uint64_t 都使用 identityhash，所以第一步极快。但如果第二步直接用一条按位与指令取 slot数组下标，就会产生很多冲突，导致第四步出现多余的比较。那些第二步处理很简单的哈希表，比如absl::flat_hash_map、absl::node_hash_map、emhash::hash_map7和 tsl::robin_map，都需要高质量的哈希函数，光靠std::hash 是不够的。robin_hood::unordered_flat_map在第二步多做了一点工作，但搭配 std::hash仍达不到最优性能。libc++ 的 std::unordered_map 在使用std::hash 且元素数量为 2的幂时，性能也很差。robin_hood::hash对大多数要求好哈希函数的哈希表来说质量不够，但对robin_hood::unordered_flat_map 已经足够，这一点在 100,000到 3,100,000 这段数据点上可以看到。

相反，那些在第二步多做工作的哈希表，即使第一步用最简单的 identityhash，也仍能取得不错的性能，比如ska::flat_hash_map、ska::bytell_hash_map、fph::DynamicFphMap、fph::MetaFphMap 以及libstdc++ 的 std::unordered_map。这里推荐了解一下ska::flat_hash_map 在第二步用到的巧妙技巧——FibonacciHashing: The Optimization that the World Forgot (or: a BetterAlternative to Integer Modulo)。这个方法用到一次 64位乘法和一条右移指令。由于哈希函数本身（identityhash）不涉及任何算术指令，这两条基本就是 CPU 的 ALU需要处理的全部算术指令。

另一方面，对于需要“好”哈希函数、第二步只用一条按位与指令的哈希表，据我所知，还没有哪个哈希函数能既把代价控制在这两条指令以内，又在大多数数据分布上保持足够好的哈希质量。

正因为如此，在 Intel Rocket Lake 上当所有数据都能放进 L2 cache（或 M1Max 上的 L1 cache）时，ska::flat_hash_map 搭配std::hash目前是最快的组合。其他几乎所有组合，在第一步和第二步加起来都需要更多指令。在这段数据范围内，RocketLake 上第二快的是 tsl::robin_map 搭配absl::hash，差距非常小。在 M1 Max上，fph::DynamicFphMap 搭配 std::hash也几乎一样快，每次操作只差不到 0.1 纳秒。

不过，当 L2 cache 放不下所有元素、但 L3 cache还放得下时，ska::flat_hash_map 就不再是第一了。在 IntelRocket Lake 上，fph::DynamicFphMap 搭配std::hash 在 8,192 到 3,100,000个元素的范围内是最快的（不过在 400,000 个元素处，absl::flat_hash_map 搭配 absl::hash略快一点）。在 M1 Max 上，这个组合在元素数量处于 8,192 到 1,200,000时也表现突出，fph::MetaFphMap 在这一范围内排第二。考虑到ska::flat_hash_map 和 tsl::robin_map都采用激进的扩容策略，导致 load factor 偏低、更早出现 cache miss，而fph::DynamicFphMap 使用 perfecthash（即没有冲突），这些结果就不难理解了。

当数据放不进 L3 cache 时，ska::flat_hash_map 搭配std::hash 又重新成为最快的组合。tsl::robin_map搭配 absl::hash 紧随其后——相比 cache miss的开销，一两条指令的差距几乎可以忽略。即使在元素数量极大时，这两者依然最快，部分原因是很多其他哈希表会用辅助数组来存放额外信息。例如absl::flat_hash_map 使用了一个 metadata数组，在处理大数据时，它的 cache miss 率可能很高、代价也很大。相比之下，ska::flat_hash_map 和 tsl::robin_map 只用一个slot 数组存放 key-value 数据，一次从内存到 cache line的加载就足够了。

综合上面这些现象可以看出，高性能的哈希表在查询的第四步里失败比较都很少（要么像ska::flat_hash_map 那样限制了失败次数，要么像fph::DynamicFphMap 这样的 perfect hash table根本不会失败）。

在这个前提下，当数据小到能完全装进 cache时，第三步从内存加载的代价就变得很小。这一阶段，第一步和第二步指令的数量少、足够简单，对速度至关重要。能做到这一点的哈希表与哈希函数组合（ska::flat_hash_map搭配 std::hash）就是最快的。

当数据量略微增加、冲突变得更频繁时，能避免冲突的哈希表就能占到优势，比如fph::DynamicFphMap。absl::flat_hash_map在一定程度上用 SIMD 来处理冲突，在某些数据规模下也能保持优势。

当数据量继续增加，到了任何一次访存都会 cache miss的程度时，访存次数最少的哈希表就变成最快的。这要求冲突更少，同时也凸显出：在这一阶段，任何metadata 都会增加访存次数。此时 ska::flat_hash_map 和tsl::robin_map 是最快的选择。

总而言之，高性能的哈希表与哈希函数组合取决于多个因素。当数据完全装进cache 时， ska::flat_hash_map 搭配 std::hash表现最好，因为前两步所需的指令最少。随着数据规模增大，能有效避免冲突、或用SIMD 解决冲突的哈希表会占优，比如 fph::DynamicFphMap 和absl::flat_hash_map。最后，当数据规模超过 cache容量时，访存次数最少的哈希表会胜出，比如 ska::flat_hash_map和 tsl::robin_map。

:

当 value_type 的大小扩大到 64 字节时，cache能容纳的元素更少。而且一条 cache line只能放下一个元素，哈希表的冲突代价也就更高。不过现代 CPU强大的预取能力，通常能让使用线性探测或二次探测的哈希表把这部分代价压得很低。

总体来看，各哈希表之间的性能关系和的情况大体一致。数据量较少或较多时，ska::flat_hash_map 搭配std::hash 最快；而在中等数据量时，fph::DynamicFphMap 搭配 std::hash更胜一筹。

使用较大 max_load_factor

:

前面的测试都使用默认 load factor。但不同哈希表常常使用不同的 loadfactor，因为内存占用需求不同，性能上也会有差异。

哈希表对提高最大 load factor 的反应各不相同。更大的 load factor能减少内存占用、降低潜在的 cache miss率，从而提升性能，但同时也会增加哈希表的冲突，拖慢查询速度。

因此，如果某个哈希表的性能对 load factor 和冲突概率比较敏感，更大的load factor 反而会让它变慢，比如 ska::flat_hash_map 和tsl::robin_map。而对那些受 load factor 影响较小的表，比如fph::DynamicFphMap 和absl::flat_hash_map，性能则保持稳定，甚至随着 load factor增大而提升。

把较大的 max_load_factor和默认值对比一下，可以印证这些观察。

元素较少时，ska::flat_hash_map 搭配std::hash仍是最快的组合。随着元素数量上升，ska::flat_hash_map 和tsl::robin_map 的性能下降，而fph::DynamicFphMap 和 fph::MetaFphMap的性能总体上升，其他哈希表则变化不大。因此在较大的数据规模下，fph::DynamicFphMap 搭配 std::hash查询最快，其次是 fph::MetaFphMap 搭配std::hash，以及 absl::flat_hash_map 搭配absl::hash。

:

当 value_type 大小为 64 字节时，提高max_load_factor 得到的结果和类似。元素较少时ska::flat_hash_map 搭配 std::hash最快，而元素较多时 fph::DynamicFphMap 搭配std::hash 领先。

查询表中不存在的 key（未命中）

使用默认 max_load_factor

:

在哈希表里查找不存在的元素，和查找已有元素不一样。要确认目标 key和存储的 key 相等，必须做完整比较；但要证明两个 key 不同，hash value不同就够了。因此，存储了 hash value 或部分 hash的哈希表可以加快这件事。特别是用部分 hash value（比如 1 字节）作为metadata 时，它占用的 cache 空间比完整的 key 更少。

虽然absl::flat_hash_map、r_h::unordered_flat_map和 fph::MetaFphMap 这类哈希表用部分 hash 作为metadata，但在小规模查询时它们并不总是最快，因为额外的指令开销可能盖过cache 节省带来的好处。不过一旦 L1 cache不够用，这种做法的优势就显现出来了。

在 Intel Rocket Lake 上，元素数量超过 6,000后，fph::MetaFphMap 搭配 std::hash最快，并且几乎一路领先；只有在最大的规模（约一千万）附近，absl::flat_hash_map搭配 absl::Hash 才稍稍反超。在 M1 Max 上，不到 3,000个元素时 ska::flat_hash_map最快，fph::DynamicFphMap 紧随其后；6,000 到 150,000个元素时 fph::DynamicFphMap 领先，而超过 200,000 个元素后fph::MetaFphMap 胜出。M1 Max 更大的 cache容量很可能影响了这种变化，使得基于 metadata的方法在更大的元素数量下才占到优势。

:

使用 64 字节的 value_type 时，整体情况和类似。在 M1 Max上，fph::MetaFphMap 从 45,000个元素开始占据主导。这一变化是因为 cache 能容纳的元素数量变少了。

使用较大 max_load_factor

:

设置更大的最大 load factor 后，整体排名和默认 load factor时一致。ska::flat_hash_map领先的范围有所缩小，因为它的性能对 load factor 比较敏感。在 Intel RocketLake 上，元素数量不超过 1024 时 ska::flat_hash_map 搭配std::hash 最快；元素更多时则是 fph::MetaFphMap搭配 std::hash 更快。在 M1 Max上，ska::flat_hash_map 领先的范围同样更小了。

:

和上面一样，整体的相对速度关系与使用默认 load factor 时类似。

查询有 50% 概率在表中的 key

使用默认 max_load_factor

:

当查询的 key 有 50%概率在表中时，由于分支预测失败的惩罚拉长了查询时间，吞吐会下降，各哈希表之间的查询时间差距也随之缩小。为了让图更清晰、更易读，默认只显示每个哈希表最快的那个哈希函数。

从上面的图可以看到，除了std::unordered_map，各哈希表的性能可以说非常接近。

元素数量相对较少时，ska::flat_hash_map 搭配std::hash 在大多数数据点上仍是最快的。

在 Intel Rocket Lake 上，元素数量在 25,000 到 2,200,000之间时，fph::MetaFphMap 和 fph::DynamicFphMap搭配 std::hash 最快，absl::flat_hash_map 和ska::flat_hash_map 在某些数据点上也很接近。元素数量在2,200,000 到 6,000,000 之间时，absl::flat_hash_map 搭配absl::hash 是最快的组合。元素数量不少于 6,000,000时，ska::flat_hash_map 搭配 std::hash又回到第一。差距非常小，领先的表也会随元素数量变化。

在 M1 Max 上，元素数量大于 32,768 时，fph::MetaFphMap 和absl::flat_hash_map是最快的哈希表。absl::flat_hash_map的性能随元素数量波动，而 fph::MetaFphMap相对稳定。元素数量极大时，ska::flat_hash_map又回到第一。

:

使用较大 max_load_factor

:

命中附录

使用默认 max_load_factor

:

使用较大 max_load_factor

:

未命中附录

使用默认 max_load_factor

:

使用较大 max_load_factor

:

50% 命中附录

使用默认 max_load_factor

:

使用较大 max_load_factor

:

← 返回 Hash Table Benchmark目录

Hash Table Benchmark - 整数查询延迟

2026-06-13T13:55:00.000Z

这一篇测试整数 key 下的查询延迟。

点击图例中的标签，可以隐藏或显示图中对应哈希表和哈希函数的数据线。

这一篇测试三种情况下哈希表的查询延迟：

查询表中存在的 key（命中，successful find）。
查询表中不存在的 key（未命中，unsuccessful find）。
查询有 50% 概率在表中的 key。

延迟反映的情况和吞吐并不一样。吞吐测试会让很多次相互独立的查询同时进行，CPU的乱序执行引擎可以把它们的访存重叠起来。而下面的 P99延迟是单次查询耗时的 99分位，它刻画的是那些无法被掩盖的最坏访问——一次查询可能错过好几条 cacheline、走过很长的探测序列，或者发生分支预测失败。延迟只在 x86-64平台（Xeon E-2388G）上测试。

每张图里都有两个区间。当表还能放进 cache时，长尾取决于最坏情况下一次查询要做多少次访存：能限制探测次数的哈希表（perfecthash 的 fph::*），或者能借助 metadata 快速排除一个 key的哈希表，长尾都比较短；而在冲突下可能走过很长探测链的哈希表，长尾就更重。一旦表的大小超过L3 cache，几乎每一次 99 分位查询都至少要访问一次DRAM，于是长尾会落到一个由访存延迟决定的下限附近，在这台 Rocket Lake平台上大约是 420-460ns，此时哈希表的选择对长尾的影响远小于它对吞吐的影响。每一组的第二张图都使用了较大的max_load_factor，它把表填得更满，探测链略微变长，但大体上的排名不变。

查询表中存在的 key（命中）

使用默认 max_load_factor

:

命中查询的排名会随规模变化。规模较小时，简单的开放寻址哈希表长尾最短——ska::flat_hash_map搭配 std::hash 在 1,024 个元素时 P99 约为 7.8 ns。进入L2/L3 区间后，perfect hash 表反超：在 32,768个元素时，fph::DynamicFphMap 和fph::MetaFphMap 搭配 std::hash 有最好的P99（约 22ns），因为它们即使在最坏情况下也能保证探测次数很小且有上界。超过约一百万个元素后，所有表都收敛到约420-460 ns 的 DRAM 下限；基于节点的 std::unordered_map是明显的例外，因为一次长尾查询要先后解引用两个指针，而这两次都可能 cachemiss，达到 655-765 ns。

:

使用较大 max_load_factor

:

查询表中不存在的 key（未命中）

使用默认 max_load_factor

:

未命中正是 metadata设计最能发挥作用的场景。fph::MetaFphMap 只需读取一条metadata cache line 就能确认某个 key不存在，完全不用走探测序列。只要这块 metadata 数组还能放进cache，它的长尾就远比其他任何表都短：在 1,200,000 个元素时，它的 P99未命中延迟约为 34 ns，而其他表大致从约 106ns（r_h::unordered_flat_map、absl::flat_hash_map）一直到440-460ns（ska::flat_hash_map、tsl::robin_map）——长尾上有十倍以上的差距。这个优势在L3 区间最明显，到 10,000,000 个元素时就消失了：此时 metadata数组本身也放不进 L3 cache，于是连一次 metadata 读取都会变成一次 DRAMmiss，fph::MetaFphMap 也回落到大家共同的约 450 ns下限。这正是 fph::MetaFphMap最擅长的场景，也是未命中查询常见时优先选它而不是fph::DynamicFphMap 的主要理由。

:

使用较大 max_load_factor

:

查询有 50% 概率在表中的 key

使用默认 max_load_factor

:

50%的情况把命中和未命中混在一起，结果不断交替，带来额外的分支预测失败开销，使各个表之间的差距变小。在cache 内的区间，perfect hash table仍有一点长尾上的优势（fph::DynamicFphMap 在 32,768个元素时约为 27 ns），但一旦工作集离开cache，访存延迟下限又重新主导，各个表就很难区分了，只有基于节点的表明显落后（在最大规模下，absl::node_hash_map约为 520-620 ns，std::unordered_map 约为 675-785 ns）。

:

使用较大 max_load_factor

:

← 返回 Hash Table Benchmark目录

Hash Table Benchmark - 字符串删除和插入

2026-06-13T13:55:00.000Z

这一篇测试字符串 key 下反复删除和插入的性能。

点击图例中的标签，可以隐藏或显示图中对应哈希表和哈希函数的数据线。

这个测试先构造一个大小为 N 的哈希表，然后重复执行 M次下面的过程：

向哈希表中插入一个新元素
从哈希表中随机删除一个元素

整个过程中，表的大小基本保持在 N 或N+1，因此这里测到的不是扩容长大过程的成本，而是哈希表已经达到目标大小后，持续修改时的成本。对字符串key 来说，每次 insert 和 erase 仍然要对整个 key 计算hash，遇到冲突时还要比较字符串；对于超过 SSO 阈值的 key（24-byte 和64-byte 两组），每次 insert 还需要在 heap 上为字符串内容分配内存，每次erase 也要释放这块内存，所以 64-byte 的结果很大程度上由malloc/free 主导。12-byte key 会通过 SSO 存在std::string内部，不需要额外分配，因此比长字符串快很多。

这里有两点会从结构上影响结果。第一，open-addressing table 会使用tombstone：erase 时不会直接把 slot 标成 empty，而是标成deleted，这样 probe chain 才不会断；但 tombstone积累到一定程度后，哈希表必须 rehash，于是会出现 latencyspike。第二，perfect hash table fph::DynamicFphMap 和fph::MetaFphMap 并不适合这个 workload。每次 insert都可能触发 perfect-hash rebuild，所以它们不仅慢，在较大规模下还会timeout（这些点显示为 0.00，不会画出来）。它们 lookup很快，但如果频繁修改，代价就很大。

吞吐

这里记录的是整个过程的耗时，包括 insert 和 erase 两部分。

y 轴是平均单次操作耗时，计算方式是time/op = (time for insert + time for erase) / (2 * M)，也就是insert 和 erase 的平均耗时。

:

对于 64-byte fixed key，在 Xeon 上 xxHash_xxh3是最好的哈希函数，几个 flat open-addressing table排在最前面且差距不大：ska::flat_hash_map、tsl::robin_map、absl::flat_hash_map和 robin_hood::unordered_flat_map 在 1024 个元素时大约是67-72 ns，到 10^7 个元素时收敛到大约 320-360 ns。这时 64-byte string 的malloc/free 和 cache-missing probe占了主要时间。std::unordered_map 大约慢 50%，小规模时 93ns，10^7 时 513ns，因为每次修改除了字符串自己的分配和释放，还要额外分配和释放node。

perfect hash table要慢得多。fph::DynamicFphMap/fph::MetaFphMap在 1024 个元素时就已经是 160-170 ns 左右，之后还会timeout：fph::DynamicFphMap 在 32768之后没有画出的点，fph::MetaFphMap 在 1.2M 处出现 6050 ns的尖峰，之后也没有后续数据。这是因为持续插入会不断触发 perfect-hashrebuild。还要注意，ankerl::unordered_dense_map在小中规模下表现不错，1024 时约 75 ns，但 10^7 的点缺失（0.00）；它的dense-array设计在删除任意位置的元素后，需要用数组尾部的元素回填空洞以保持紧凑，因此在这里会有额外开销。

M1 Max 上排名类似，ska::flat_hash_map 和tsl::robin_map 领先，10^7 时约 370-380 ns，fph表在大规模下同样 timeout。下面几组较短 key的排序基本保持不变，但整体快很多：12-byte SSO key 让最快的几个 flattable 在 Xeon 10^7 时降到约 87-91 ns，因为没有字符串分配。

:

延迟

插入（删除之后）

:

延迟只在 Xeon E-2388G 上测试。这一节第一组图是 64-byte fixedkey，但如果想看清哈希表算法本身，12-byte SSO key反而更合适，因为它去掉了字符串分配带来的噪声。对于 insert-after-erase 的P50（median）latency，大规模下 absl::flat_hash_map 和absl::node_hash_map 最好，10^7 时大约 104-110ns；ska::flat_hash_map 和 tsl::robin_map在小规模时领先，1024 时大约 14-16 ns，但在 200k-1.2M 这一段会因为 probechain 变长而落后，约 88-100 ns。fph 表即使看 median 也明显落后，1024时约 50-68 ns，之后会升到几百 ns，并且大规模下没有后续数据。

P99（tail）能看到 tombstone-rehash 的影响。常规 flat table 的 tail相对可控，10^7 时 absl::flat_hash_map 大约 492ns，std::unordered_map 大约 1000 ns；但 perfect hash table会出现很大的尖峰：fph::MetaFphMap 的 P99 在 1.2M 时达到约44000 ns，在 10^7 时达到约 231000 ns，因为触发完整 perfect-hash rebuild的 insert 会直接落在 tail里。如果场景要求修改操作的延迟有上界，就不应该选择这些表。

对于 64-byte key，字符串分配会抬高 latency的下限：即使在小规模下，各表的 P99 也有几百 ns，1024 时约 470 ns；同时fph 的尖峰仍然存在，比如 fph::MetaFphMap 在 1.2M 时约 48000ns。其他长度的字符串也有类似模式。

:

删除

:

Erase latency 在各表之间更接近，因为 open-addressing table 的 erase本身代价不高：找到 slot 后放一个 tombstone，在 inline-stored路径上没有分配。对于 64-byte key，常规哈希表在 10^7 时的 P99 erase大多集中在约 1030 到 1140 ns，absl::flat_hash_map 约 1030ns，std::unordered_map 约 1390ns。这里的下限仍然主要来自释放字符串 heap buffer 的free，以及访问 slot 时的 cache miss。和前面一样，fph表是例外：fph::DynamicFphMap 在 32768 之后就timeout，fph::MetaFphMap 的 P99 在 1.2M 时超过约 1200 ns后也没有后续数据，因为当某次 erase 使 tombstone数量超过阈值时，会触发一次 perfect-hash rebuild。P50 erase在小中规模下主要由ska::flat_hash_map、tsl::robin_map 和emhash::hash_map7领先；其余字符串长度的结果也是同样模式，只是随字符串长度整体缩放。

:

← 返回 Hash Table Benchmark目录

Hash Table Benchmark - 字符串插入和构造

2026-06-13T13:55:00.000Z

这一篇测试字符串 key 下的插入和构造性能。

点击图例中的标签，可以隐藏或显示图中对应哈希表和哈希函数的数据线。

这一篇测试构造哈希表所花的时间。构造通过insert( const value_type& value )操作完成。测试分两种情况：插入前调用 reserve，以及不调用reserve。reserve 本身花的时间不计入总时间。

测试中，哈希表会被多次构造，吞吐测试记录的是总插入时间。

字符串的长度与 std::string::length()一致，也就是说还需要额外一个字节来保存结尾的空字符。

插入字符串 key的代价比插入整数更高，因为每次插入都要多做三件整数不用做的事：对整个 key的字节序列做哈希、冲突时比较整个字符串，以及为超过小字符串优化（SSO）阈值的key 分配堆内存来存放字符。在这里使用的 libstdc++/libc++实现中，长度不超过 15 的 std::string会把字节内联存放在控制块里（不分配内存），所以 12 字节的 key 是纯SSO、完全不碰分配器；而 24 字节和 64 字节的 key会落到堆上，每次插入还要付一次malloc。下面不同字符串长度变体之间的差异，主要就来自 SSO与堆分配的区别。

这里也先说明一下 perfect hash table的预期表现。fph::DynamicFphMap 和fph::MetaFphMap查询极快，因为它们构建了一个（近似）perfecthash，查询时无需探测，但正是这个构造过程让它们的插入很慢：随着表的增长，它们会周期性地重建perfect hash。所以在这个插入/构造测试里，fph系的表始终是最慢的，这个前提对理解插入结果很重要。

吞吐

预留空间后插入

:

提前调用 reserve后，容量在插入前就固定下来，因此这里看到的基本就是单次插入本身的代价（哈希、探测、分配、存储），不涉及rehash。在 Xeon 上，定长 64 字节 key 的结果里，xxHash_xxh3——它本就是为处理原始字节流而设计的——几乎在每个表上都是最佳哈希函数，几个领先的表也挨得很近：absl::flat_hash_map、ankerl::unordered_dense_map和 robin_hood::unordered_flat_map 在 1024 个元素时都在24-26 ns 左右，到 10^7 时收敛到约 118-119 ns，此时单次插入的代价主要来自64 字节字符串的 malloc 和 cachemiss，而不是哈希表算法。std::unordered_map 比 flat 表慢约 2倍（小规模约 48 ns，10^7 时 250ns），因为它在字符串分配之外，还要为每个元素分配一个节点。

fph 系的表在这里慢得多：在 Xeon 上，fph::MetaFphMap 和fph::DynamicFphMap 在 10^7 时分别达到约 2390 ns 和 2471ns——大约比 std::unordered_map 慢 10 倍、比最快的几个 flat表慢 20 倍——因为 perfect hash 的构建代价随表增长。（注意它们在 N=1024处的数据点，约 198 和 178 ns，来自对一个很小的表反复构建 perfect hash的开销；它们在 32768处反而相对更好，之后构建代价又重新占主导。）在 M1 Max上排名相同，但差距更小：fph 系的表在 10^7 时落在约 950 ns，而最快的几个flat 表约为 100-120 ns。

下面的 24 字节和 12字节变体排名相同，只是随着字符串变短而整体更快：在 10^7 时，最快的几个flat 表从约 118 ns（64 字节）降到约 92-112 ns（24 字节），再到约 50-63ns（12 字节），最后这一档是因为 12 字节的 key 是纯SSO、完全跳过了分配器。“max length N”变体和对应的“fixed lengthN”差不多，或者略快一点，因为随机生成的 key平均长度短于上限，要哈希、比较和拷贝的内容更少；不过长度不一也会让每个key 的代价不那么均匀。

:

不预留空间直接插入

:

不调用 reserve 时，每个表在填充过程中还要处理扩容和rehash，这大致让单次插入的时间整体翻倍。在 Xeon 上，定长 64 字节 key的结果里，absl::flat_hash_map 搭配 xxHash_xxh3在大规模下最快（10^7 时约 191 ns），因为它扩容开销小，rehash 时重排的是metadata数组，而不是再次搬动整条记录；ankerl::unordered_dense_map紧随其后（约 178 ns），因为它只需要扩展一个紧凑的数组。重探测的表受rehash 影响更大：ska::flat_hash_map 在 10^7 时爬到约 465ns，是 absl的两倍多，因为每次扩容都要把每个元素重新沿探测序列插入一遍。

fph 系的表在这里慢得多。不调用 reserve 时，每次扩容都会触发一次全新的perfect hash 构建，所以在 Xeon 上fph::MetaFphMap/fph::DynamicFphMap 在 10^7时达到约 3800 和 4180 ns ——约为最快的几个 flat 表的 10倍，也明显比它们调用 reserve时的数值更差，因为后者至少只在最终大小上构建一次 perfect hash。这正说明fph 是拿构造速度换查询速度。

下面更小的 key 和“max length”变体保持同样的排名；12 字节的 SSO key再次最快（absl 在 10^7 时约 64ns），因为它们从不调用分配器，只剩下表本身的扩容和探测代价。

:

延迟

单次插入的 P99 延迟只在 Xeon E-2388G上测试。从长尾来看，结论也是一样的：常规的 flat 表能把长尾限制住，而perfect hash table 每次重建时都会出现尖峰。

预留空间后插入

:

提前 reserve 的情况下，定长 64 字节 key 下几个 flat 表的 P99都收得很紧：absl::node_hash_map、ankerl::unordered_dense_map和 absl::flat_hash_map 在 10^7 时都在 490-530 ns左右，std::unordered_map 约 880 ns。64字节字符串的内存分配为所有这些表都设了一个下限。fph系的表又一次格外突出：在 10^7 时 fph::DynamicFphMap 爬到约12660 ns，fph::MetaFphMap 约 12420ns，差了一个数量级以上，因为即便预留了容量，perfect hash的构造也会偶尔出现非常耗时的步骤，主导了 99 分位。对 12 字节的 SSOkey，下限降低了（flat 表在 10^7 时约 460-490 ns），因为没有分配，但 fph的长尾仍然很高（fph::DynamicFphMap 约 11780 ns）。

:

不预留空间直接插入

:

不提前 reserve 时，常规表的 P99 和 reserve的情况相差不大——相对于插入次数，一次大到能落进 99 分位的 rehash是很罕见的——所以对 12 字节的 key，absl::flat_hash_map 在10^7 时仍约为 442 ns，std::unordered_map 约 850ns。相比之下，fph 系的表急剧恶化：不 reserve 时它们每次扩容都重建perfect hash，所以 fph::DynamicFphMap 和fph::MetaFphMap 在 10^7 时大约达到 20400 和 20360ns，几乎是它们 reserve时长尾的两倍。如果在意插入延迟的稳定性，就应该提前reserve，并在构造阶段避开 perfect hashtable。其余字符串变体遵循同样的规律。

:

← 返回 Hash Table Benchmark目录

Hash Table Benchmark - 字符串遍历

2026-06-13T13:55:00.000Z

这一篇测试字符串 key 下遍历哈希表的性能。

点击图例中的标签，可以隐藏或显示图中对应哈希表和哈希函数的数据线。

这个测试测量的是遍历整个哈希表的性能。

遍历这种操作几乎不受 key 类型影响。遍历时既不会重新计算 key 的hash，也不会比较两个字符串；它只是推进 iterator，并读出每个已经存好的entry。因此，和查询或插入不同，字符串长度和哈希函数选择在这里几乎没有影响。真正起决定作用的是哈希表在内存中如何组织元素，这一点和整数 key 的遍历测试基本一样。这里也可以分成三类：

Dense array storage.ankerl::unordered_dense_map 和emhash::hash_map7 会把所有 key-value pair紧密地存到一段连续数组里，hash slot 中只保存 index 或少量metadata。遍历时就是线性扫描 densearray，所以单元素成本很低，并且基本不受 load_factor影响。
Inline open addressing.ska::flat_hash_map、ska::bytell_hash_map、tsl::robin_map、absl::flat_hash_map、fph::*和 robin_hood::unordered_flat_map 会把元素直接存到稀疏的slot array 里。遍历时要走完整个 slot array，并跳过空slot，所以表越空、slot array 超出 cache 越多，单元素成本就越高。
Node-based storage. std::unordered_map和 absl::node_hash_map 会为每个元素单独分配node，遍历时需要在这些 node 之间追指针。

字符串这里还有一点要注意：存储的 entry 是std::pair。不管字符串本身是12、24 还是 64 个字符，这个 entry 的固定部分大小都一样，都是一个 32-byte的 std::string control block 加上value。较长字符串实际的字符内容会放在别处的堆内存上，但遍历时并不会碰这些字符内容，因为这里只推进iterator，不读取字符串本身。这也是为什么六种字符串数据的遍历结果几乎一样。

吞吐

:

图中的结果符合前面的内存布局分析。在两个平台上，ankerl::unordered_dense_map都明显最快，并且在整个数据规模范围内基本是平的：Xeon E-2388G 上大约 0.22ns 每元素，M1 Max 上大约 2.0ns。原因是它始终扫描一段紧密排列的数组，不管哈希表本身有多少slot。emhash::hash_map7 排在第二，也有类似的平坦曲线，Xeon上约 0.63 ns，M1 上约 2.6 ns。

各种 inline open-addressing table 的单元素成本会随元素数量上升，因为slot array 逐渐超过 cache。比如 ska::flat_hash_map 在 1024个元素时不到 1 ns，到 10^7 个元素时，Xeon 上升到大约 12.4ns，这时大部分时间都花在从内存里读取空 slot 上。node-based 的std::unordered_map 在大规模时最慢，10^7 个元素时 Xeon 上约48 ns 每元素，M1 上约 25 ns，因为遍历 node list 基本变成了一串 cachemiss 的 pointer dereference。

perfect hash table 在 open-addressing table中处于中间位置，这里并不领先：10^7 个元素时，Xeon 上fph::MetaFphMap 大约 7.4ns，fph::DynamicFphMap 大约 10.8 ns。perfect hash能换来很快的 lookup，但遍历还是要走稀疏的 slot array，所以对fph 没有优势；而 fph::DynamicFphMap 的 slot array相对更稀疏，因此反而成了扫描最慢的几个 flat table 之一。

下面五种字符串数据给出的结果几乎一样，连小数点后的数值都几乎一致。遍历不关心key 的具体内容，所以 fixed/max length 以及 12/24/64-byte的区别在这里看不出明显影响。

:

延迟

单次 iterator step 的 P99 latency从尾部延迟角度说明了同样的问题（latency 只在 Xeon E-2388G上测试）。ankerl::unordered_dense_map不随规模变化，基本维持在约 0.94 ns，因为在 dense array 上推进 iterator不太会遇到远距离的 cache miss。inline table 和 node-based table在底层存储超过 cache 后，tail latency 会逐渐变长：10^7个元素时，ska::bytell_hash_map 的 P99 step 大约 84ns，ska::flat_hash_map 大约 110ns，tsl::robin_map 大约 103 ns；node-based 的std::unordered_map 和 absl::node_hash_map会到几百 ns，分别约 406 ns 和 444 ns。这些尖峰对应的，通常就是下一次访问slot 或 node 时遇到的 cache miss。第一个点（N=1024）里ankerl 的 3.13 ns 是一个小异常点，应该是 cold-startartifact，之后就稳定在约 0.94 ns。其他五种字符串数据也有同样模式。

:

← 返回 Hash Table Benchmark目录

Hash Table Benchmark - 整数插入和构造

2026-06-13T12:30:14.000Z

这一篇测试整数 key 下插入并构造哈希表的性能。

点击图例中的标签，可以隐藏或显示图中对应哈希表和哈希函数的数据线。

这个测试测量的是构造哈希表所花的时间。构造时使用emplace( const value_type& value )。测试分为插入前先reserve 和不提前 reserve两种情况，reserve 自己花的时间不计入总时间。

最早测试时用的是 insert( const value_type &value)来构造哈希表，但后来发现有些哈希表并不使用std::pair 作为自己的value_type（也就是 STL container使用的类型），因此没法对所有被测哈希表统一使用 insert。

测试中，每种哈希表都会被构造很多次，吞吐测试记录的是总插入时间。

吞吐

y 轴是平均单次操作耗时，计算方式是time/op = sum{construct time} / (number of construct * number of elements)。

:

预留空间后插入

分析 reserve之后的插入性能时，首先能看到有些哈希表并不适合搭配std::hash 使用，比如emhash::hash_map7、tsl::robin_map、absl::node_hash_map和absl::flat_hash_map。这些表需要质量更好的哈希函数。当然，也有一些哈希表在插入测试中还没有暴露这个问题，但后面的查询测试会看得更清楚。

如果把这些没有使用合适哈希函数的组合先隐藏掉（可以点击图例里的标签隐藏对应数据线），最慢的是perfect hash table fph::DynamicFphMap 和fph::MetaFphMap，而且差距很大。这正是它们为快速查询付出的代价：构造perfect hash 本身很慢，而且元素越多越慢。Xeon E-2388G 上，1024 个元素时fph 表已经需要 37 到 51 ns每次插入；作为对比，std::unordered_map 大约 20 ns，最快的flat table 只有 4 到 6 ns。元素数量继续增加后，差距会更大：10^7个元素时，Intel CPU 上 fph 的插入时间大约 1450 到 1900 ns，约为std::unordered_map（约 125 ns）的 12 到 15 倍；Apple M1 Max上也有约 11 到 12 倍，fph 接近 1550 ns，std::unordered_map约 134 ns。

另外，在 M1 Max 上，std::unordered_map 搭配std::hash在部分数据点上异常慢。进一步看会发现，这些数据点的元素数量刚好是 2的幂：1024 个元素时每次插入约 165 ns，2048 时约 311 ns，8192 时暴涨到约2500 ns；而附近非 2 的幂规模（例如 800、1500、3000、6000）基本在 20 到32 ns。这里推测原因出在 M1 上 clang 所用的 libc++unordered_map 实现：它用 hash value 对 bucket 数取模来得到slot index。当 bucket 数刚好是 2 的幂时，这个取模等价于只保留 hash的低位，丢掉高位。而对整数来说 std::hash 又是 identityfunction，所以一旦 key 的信息主要集中在高位，就会在这些 2的幂规模上产生大量冲突。

单看插入最快的哈希表，x86-64 和 arm64 的结果就有些不同。

在 Intel Rocket Lake 上，小规模时几个 flat table性能基本相当：emhash::hash_map7 搭配absl::Hash、ska::flat_hash_map 搭配std::hash、以及 ankerl::unordered_dense_map在元素数量不超过几千时每次插入都在 4 到 5 ns左右。中等规模下，absl::flat_hash_map 搭配absl::Hash 最稳定，从 6000 到约 800,000 个元素基本保持在 6到 12 ns，而其他 flat table会更早上升。最大规模时结果又发生变化，而且不是单调的。tsl::robin_map搭配 robin_hood::hash 在 10^7 个元素时反而最快，大约 25ns；ankerl::unordered_dense_map 和ska::flat_hash_map 也很接近，大约 27 到 28ns。但同一个组合在 200,000 到 1,200,000 这一段会掉下去，升到大约 30 到42 ns 后又恢复。这种非单调更可能是 robin_hood::hash 在这段masked-bit key 上分布质量较差导致的，而不是单纯的 cache层级变化。另一方面，robin_hood::unordered_flat_map没有受到这个 hash quality 问题的明显影响：不管搭配absl::Hash 还是 robin_hood::hash都有竞争力。这说明它虽然需要好的哈希函数，但不像absl::flat_hash_map 等表那样强依赖 hash quality。

Apple M1 Max 上情况略有不同。元素数量不超过约 6000时，ska::flat_hash_map 搭配 std::hash最快，每次插入能低于 4 ns。超过 6000后，absl::flat_hash_map 搭配 absl::Hash领先，并且直到约 1,200,000 个元素都保持在 4.5 到 10 ns 左右。接近 10^7个元素时，几个 flat map 的差距缩小，收敛到约 20 到 22ns。这是因为元素很多后，working set 已经放不进 cache。这个现象在 : 中更明显，因为那种情况下cache 压力更大。

不预留空间直接插入

不提前 reserve 时，哈希表之间的排名又会变化。

在 Intel Rocket Lake 上，absl::flat_hash_map 搭配absl::Hash 几乎在所有规模下都是最快的一组，大约 16 到 44ns；emhash::hash_map7 和ankerl::unordered_dense_map紧随其后。小规模时，tsl::robin_map 和ska::flat_hash_map也几乎同样快，但规模变大后会落后，因为它们更激进的增长策略会触发更多rehash。

在 Apple Silicon 上，最小规模时 ska::flat_hash_map 搭配std::hash 最快，1024 个元素时约 14ns。元素数量超过几千后，absl::flat_hash_map 搭配absl::Hash 又成为最快，并且在后面的范围里基本保持在 20 到32 ns。emhash::hash_map7 搭配 absl::Hash稍微落后一些。

:

预留空间后插入

key 的模式和 :一样。区别在于 pair 的大小变成原来的 4 倍：每个元素 64bytes，而不是原来的 16 bytes。因此 working set 会更早超出 cache。

在 Intel Rocket Lake 上，小规模时ankerl::unordered_dense_map、ska::flat_hash_map搭配 std::hash、以及 absl::flat_hash_map 搭配absl::Hash 都很接近，大约 5 到 8ns。中等规模下，absl::flat_hash_map 搭配absl::Hash 最快，直到约 200,000 个元素都保持在 10 到 15 ns左右。但最大规模时 absl::flat_hash_map 会落后：10^7 时约 65ns，而 ska::flat_hash_map（约 43 ns）和tsl::robin_map 搭配 absl::Hash（约 40ns）明显更快。原因是 absl::flat_hash_map 把 metadata 和slot 存在两个不同数组中，一旦 working set 放不进 cache，每次 probe就可能付出两次内存访问；元素为 64 字节时，这个代价会更明显。

Apple Silicon 上，元素数量较小（不超过约6000）时，ska::flat_hash_map 搭配 std::hash最快。中大规模下，absl::flat_hash_map 搭配absl::Hash 领先，并保持到约 1,200,000个元素。再往后，ska::flat_hash_map 又会和absl::flat_hash_map 接近，甚至反超。原因是这个规模下 M1 Max也已经放不下 working set，而 absl::flat_hash_map 比较依赖cache 才能获得好的性能。它的 metadata 和 slot 在两个数组里，而ska::flat_hash_map 只有一个 slot array。所以即使发生 cachemiss，ska::flat_hash_map 通常也只需要从 RAM取一次数据。

不预留空间直接插入

不提前 reserve 时，结果和数据比较相似。这可能是因为大部分时间都花在内存分配和释放上。

有一个区别是：absl::node_hash_map 的排名比在数据中更好。这说明当sizeof(value_type) 较大，或者 value_type构造本身比较耗时时，absl::node_hash_map有一定优势，因为它不需要在 slot 之间移动 value。

延迟

:

预留空间后插入延迟

不预留空间直接插入延迟

从结果看，即使插入前没有 reserve，insert 操作的 P99latency 也基本和提前 reserve后处在同一水平。不过从理论上说，如果不提前 reserve，insert的最坏时间复杂度是 O(n)，因为哈希表可能需要扩容。如果提前reserve，则插入过程中通常可以避免 rehash。

因此可以再看 P100 latency，也就是 max latency。下面两张图分别是提前reserve 和不提前 reserve 时的插入 P100latency。

可以看到，提前 reserve 后，只有 fph 系列哈希表和robin_hood::unordered_flat_map会出现很大的最大插入延迟。fph 表在 10^7 个元素时会达到几千万ns，原因是要重建 perfecthash；robin_hood::unordered_flat_map 也会超过一百万ns。从实验数据看，其他哈希表在提前 reserve 后，插入的 worst-case timecomplexity 看起来不像 O(n)。即使元素数量达到10^7，ska::flat_hash_map 和ska::bytell_hash_map 的 P100 插入延迟也只有大约 760 到 830ns，这是很好的结果。

不提前 reserve 时，insert 的 P100 latency更能反映哈希表插入操作的最坏时间复杂度：O(n)。最大插入延迟和元素数量成比例，flattable 在 10^7 个元素时会达到 10^8 ns量级。相对来说，absl::flat_hash_map、robin_hood::unordered_flat_map以及 ankerl::unordered_dense_map在扩容时的最大延迟更小。

如果希望插入时间稳定，就应该提前reserve，这样大多数哈希表都可以避免插入过程中的 rehash。

:

预留空间后插入延迟

不预留空间直接插入延迟

当 value_type 是 64 bytes 时，排名和很接近。

吞吐附录

:

预留空间后插入

不预留空间直接插入

:

预留空间后插入

不预留空间直接插入

:

预留空间后插入

不预留空间直接插入

延迟附录

:

预留空间后插入延迟

不预留空间直接插入延迟

:

预留空间后插入延迟

不预留空间直接插入延迟

:

预留空间后插入延迟

不预留空间直接插入延迟

← 返回 Hash Table Benchmark目录

如何加速矩阵乘法——优化GEMM (CPU单线程篇)

2021-06-30T15:11:08.000Z

矩阵乘法GEMM(General matrixmultiply)是一个被广泛使用的基础算法，各种领域都需要应用，例如神经网络的核心计算任务就是矩阵乘法，交易中的各种信号计算也可能用到矩阵乘法。因此矩阵乘法的效率是极其关键的。

关于如何优化矩阵乘法，我准备写一个较短的系列博文，包括CPU单线程篇、CPU多线程篇、GPU篇。原本计划还有一个稀疏矩阵乘法篇，由于这学期毕业前也没有时间把GPU篇做到满意，因此，稀疏矩阵篇就没了，GPU篇也很不完整。如果日后有时间且有那冲动可能会补上（大概率没有）。

这是矩阵乘法优化第一篇，CPU单线程篇。

矩阵乘法对于同样的抽象算法，不同的优化带来的性能差异极大，现代的部分CPU上最朴素的矩阵乘法实现和最优实现甚至可以有百倍以上的性能差距，这比一些有更低时间复杂度的矩阵乘法算法的优化效果都有效。而这都是针对现代CPU的体系结构作出的针对性优化带来的，SIMD向量指令更是增加了CPU的处理大批量数据时的效率。在本文中，我们将介绍如何针对CPU进行单线程GEMM实现的优化。

这个系列的代码可以在https://github.com/renzibei/optimize-gemm中找到，部分测试代码来自于《并行计算基础》课程。。

矩阵的内存格式

要说清矩阵乘法，那么首先要统一矩阵的表示。对于C系语言而言，矩阵可以简单地用二维数组表示，例如矩阵中第i行第j列可以表示为。但是在系统底层的内存中，只有连续的储存空间，编译器会将高级语言的二维数组的访存转换为对一维内存地址的访问。将二维坐标映射成一维坐标有很多方法，直接的有两种：行主序(row-majororder)和列主序(column-major order)¹。简单地说，对于前面提到的元素，如果要映射为一维数组，既可以用行主序的的方式，如果一行的内存元素有个，则对应为；如果使用列主序的方式，如果一列的内存元素有个，则对应为。之所以这里说内存元素有个而不说一行有个元素或者说一列有个元素，是有原因的，例如，对于行主列的储存方式而言，矩阵一行有个元素，但是矩阵一行占用的内存不一定是个，可能由于内存对齐的原因，一行占用了个内存，且。因此，表示矩阵储存时，需要知道矩阵的储存格式是行主序还是列主序，还需要指出的值。对于C系编程语言而言，一般二维数组使用行主序的储存方式。对于Fortran语言和与其渊源颇深的BLAS框架，一般都使用列主序的储存方式。

本文和相关代码中都使用列主序的方式表示矩阵元素，即矩阵A的第i行第j列元素对应为。另外在代码中为了方便，很多地方，因此也可能直接表示成

测试方法

下文的讨论将围绕计算这个目标展开，其中A为M行K列矩阵，B为K行N列矩阵，C为M行N列矩阵。测试中的矩阵元素类型为单精度Float。

本文测试中的CPU使用的是ARM架构的鲲鹏920，主频2.6GHz，具有128bitSIMD寄存器与向量指令集。每核有私有的512KB L2 Cache。

本文中我们进行的性能测试的数据都是在M=N=K的情况下，测试N从127到1281的多个数据规模的性能，评价的指标为每秒浮点运算次数Flops

我们使用OpenBLAS框架作为优化的目标，OpenBLAS针对不同的CPU架构写了针对性的优化代码，其GEMM算法的优化程度基本属于最高的一个级别中（Intel的芯片上Intel自家的科学计算库性能更高）。在我们的测试环境中，OpenBLAS的平均浮点性能在32Gflops左右。

优化过程

在下面的优化过程中，我们都使用-O2优化，来让编译器做一些简单的自动优化，同时不会明显改变我们的优化意图。

最朴素实现的平均浮点性能为1.098Gflops，我们最终优化后的平均浮点性能约为28.3Gflops，距离OpenBLAS的性能还有一些距离。

多种优化后的性能随数据规模变化关系如Figure1所示，可以看到最终性能在数据规模够大后几乎不受数据规模影响，比较稳定。

Figure 1: 多种优化后性能随数据规模变化

前半部分优化参考了https://github.com/flame/how-to-optimize-gemm/wiki的一些方法。

朴素实现

朴素矩阵乘法就是一个简单的算法，三层循环。对于这个矩阵乘法和加法，可以用下面的代码描述：

for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
for (int k = 0; k < K; ++k) {
C[i + j * ldc] += A[i + k * lda] * B[k + j * ldb];
}
}
}

这段代码非常直接，而且有一些可以直接优化的部分，例如对的累加过程可以使用一个寄存器中的变量暂存，编译器为了防止指针的Alias产生，不能自动进行这一优化。

这种naive的方法的平均性能为1.098Gflops，这是一个相当差的性能。那么性能瓶颈在哪呢？

理论上的矩阵乘法要进行量级的乘加计算，内存数据量只有规模，内存访问次数是量级。GEMM既是计算密集型也是访存密集型的任务。如果我们的访存速度和计算速度几乎相当的话，花在访存指令上的时间应该和花在浮点计算指令上的时间相当。但是，我们知道内存的访问带宽远远小于CPU的浮点计算吞吐量，访存延迟也远高于CPU的浮点指令延迟，而CPU的Cache虽快，大小十分有限，不能塞下所有的矩阵数据。因此，朴素实现的瓶颈会在于访存指令的延迟，每个浮点计算指令都要等访存指令执行完。

那么，我们要决定我们优化的方向。我们需要解决访存带宽的问题，这个问题可以通过将矩阵分块（Blocking）的方法解决，虽然整个矩阵装不进Cache里，但是一个足够小的子矩阵还是可以的。将矩阵分块后，计算的次数和访存次数不变，但是更多的访存指令能从Cache直接获取数据，大大减小了平均访存延迟。

另外，我们可以使用SIMD向量化指令，一个指令可以操控多个数据，可以提高访存和计算吞吐率。

数据并行化的准备

为了之后的SIMD向量化，我们需要对算法的实现步骤做一些调整。例如，对于矩阵C的每一个元素的计算，朴素实现中每次只是拿矩阵A的一行去点乘矩阵B的一列。而如果我们同时算C中的4个元素，那么我们就能同时取A中的连续4行与B中的连续4列。这样连续取整块的内存是有利于后面的向量化的。

具体而言，我们每次同时计算C的4x4的16个元素，这样的话我们同时用到了A的连续4行与B的连续4列。

如果我们只是调整一下形式，不做其他优化的话，性能几乎不会有变化。现在的浮点性能为1.087Gflops。

内层循环的核心代码如下，注意其中的对应的是4x4的小方块中的而不是整个大矩阵中的位置。

for (int k = 0; k < K; ++k) {
    C[0 + 0 * ldc] += A[0 + k * lda] * B[k + 0 * ldb];
    C[0 + 1 * ldc] += A[0 + k * lda] * B[k + 1 * ldb];
    C[0 + 2 * ldc] += A[0 + k * lda] * B[k + 2 * ldb];
    C[0 + 3 * ldc] += A[0 + k * lda] * B[k + 3 * ldb];

    C[1 + 0 * ldc] += A[1 + k * lda] * B[k + 0 * ldb];
    C[1 + 1 * ldc] += A[1 + k * lda] * B[k + 1 * ldb];
    C[1 + 2 * ldc] += A[1 + k * lda] * B[k + 2 * ldb];
    C[1 + 3 * ldc] += A[1 + k * lda] * B[k + 3 * ldb];

    C[2 + 0 * ldc] += A[2 + k * lda] * B[k + 0 * ldb];
    C[2 + 1 * ldc] += A[2 + k * lda] * B[k + 1 * ldb];
    C[2 + 2 * ldc] += A[2 + k * lda] * B[k + 2 * ldb];
    C[2 + 3 * ldc] += A[2 + k * lda] * B[k + 3 * ldb];

    C[3 + 0 * ldc] += A[3 + k * lda] * B[k + 0 * ldb];
    C[3 + 1 * ldc] += A[3 + k * lda] * B[k + 1 * ldb];
    C[3 + 2 * ldc] += A[3 + k * lda] * B[k + 2 * ldb];
    C[3 + 3 * ldc] += A[3 + k * lda] * B[k + 3 * ldb];
  }

这一部分我写的可能不是很详细，大家可以参考https://github.com/flame/how-to-optimize-gemm/wiki的做法。

利用寄存器减少访存次数

上面的代码有一些很明显的可以减少访存次数的优化方法，例如将16个C中的元素都先用寄存器暂存，然后累加时使用寄存器，最后再写入内存。

另外，内层循环的每一次迭代中，A中的访问内存的次数为16次，B也为16次，但其实A与B都只各自访问了4个元素，因此其实也可以各用4个寄存器先加载内存，然后使用寄存器计算。

减少访存后，平均浮点性能为5.385Gflops，这相对于之前是一个很大的提升。

内层循环的核心代码如下，

register float c00 = 0, c01 = 0, c02 = 0, c03 = 0, c10 = 0, c11 = 0, 
   c12 = 0, c13 = 0, c20 = 0, c21 = 0, c22 = 0, c23 = 0, c30 = 0, c31 = 0, c32 = 0, c33 = 0;
 register float a0i, a1i, a2i, a3i;
 register float bi0, bi1, bi2, bi3;

 float *bi0_p, *bi1_p, *bi2_p, *bi3_p;

 bi0_p = B; bi1_p = B + 1 * ldb; bi2_p = B + 2 * ldb; bi3_p = B + 3 * ldb;
 for (int i = 0; i < n; ++i) {

   a0i = A[i * lda]; a1i = A[1 + i * lda]; a2i = A[2 + i * lda]; a3i = A[3 + i * lda];
   bi0 = *bi0_p++; bi1 = *bi1_p++; bi2 = *bi2_p++; bi3 = *bi3_p++;

   c00 += a0i * bi0;
   c01 += a0i * bi1; 
   c02 += a0i * bi2;
   c03 += a0i * bi3;

   c10 += a1i * bi0;
   c11 += a1i * bi1;
   c12 += a1i * bi2;
   c13 += a1i * bi3;

   c20 += a2i * bi0;
   c21 += a2i * bi1;
   c22 += a2i * bi2;
   c23 += a2i * bi3;

   c30 += a3i * bi0;
   c31 += a3i * bi1;
   c32 += a3i * bi2;
   c33 += a3i * bi3;

 }
 C[0 + 0 * ldc] += c00;  C[0 + 1 * ldc] += c01;  C[0 + 2 * ldc] += c02;  C[0 + 3 * ldc] += c03;
 C[1 + 0 * ldc] += c10;  C[1 + 1 * ldc] += c11;  C[1 + 2 * ldc] += c12;  C[1 + 3 * ldc] += c13;
 C[2 + 0 * ldc] += c20;  C[2 + 1 * ldc] += c21;  C[2 + 2 * ldc] += c22;  C[2 + 3 * ldc] += c23;
 C[3 + 0 * ldc] += c30;  C[3 + 1 * ldc] += c31;  C[3 + 2 * ldc] += c32;  C[3 + 3 * ldc] += c33;

SIMD向量化

之前我们已经将计算的顺序进行了改变，每次计算C的4x4的方块，每个内层循环的迭代中用到了4个矩阵A的元素和4个矩阵B的元素。这是很容易进行向量化的形式。

具体到ARM架构的CPU上，我们使用Neon向量指令集，每个指令可以操控128bit即4个Float数据，正好对我们上面的代码进行并行。

向量化后平均性能为9.963 Gflops，又有了进一步的提升。

内存循环的核心代码如下，

float32x4_t c_c0, c_c1, c_c2, c_c3, a_ri, b_vi0, b_vi1, b_vi2, b_vi3;
 c_c0 = vmovq_n_f32(0.0), c_c1 = vmovq_n_f32(0.0), c_c2 = vmovq_n_f32(0.0), c_c3 = vmovq_n_f32(0.0);

 float *bi0_p, *bi1_p, *bi2_p, *bi3_p;

 bi0_p = B; bi1_p = B + 1 * ldb; bi2_p = B + 2 * ldb; bi3_p = B + 3 * ldb;
 for (int i = 0; i < n; ++i) {
   a_ri = vld1q_f32(A + i * lda);
   b_vi0 = vld1q_dup_f32(bi0_p++); b_vi1 = vld1q_dup_f32(bi1_p++); 
   b_vi2 = vld1q_dup_f32(bi2_p++); b_vi3 = vld1q_dup_f32(bi3_p++);

   c_c0 = vmlaq_f32(c_c0, a_ri, b_vi0);
   c_c1 = vmlaq_f32(c_c1, a_ri, b_vi1);
   c_c2 = vmlaq_f32(c_c2, a_ri, b_vi2);
   c_c3 = vmlaq_f32(c_c3, a_ri, b_vi3);
 }
 vst1q_f32(C + 0 * ldc, c_c0); vst1q_f32(C + 1 * ldc, c_c1);
 vst1q_f32(C + 2 * ldc, c_c2); vst1q_f32(C + 3 * ldc, c_c3);

矩阵分块 Blocking

之前的方法在数据规模变大后性能都会有较大的下降，问题在于L2Cache大小有限，如果不停地访存很快会把L2Cache刷满一遍。因此应该让高密度计算中的访存范围集中，使用Blocked分块的方法。采取的分块策略是A每次访问MCxKC的块，B每次访问KCx ldb的块。其中MC和KC的大小进行多次尝试决定。

我们这里的分块并不彻底，B没有完全分块，其实B也可以分成KC xNC的块，只是在这一步继续分块对Cache带来的帮助并不大，因此我们暂且只分成这样，后续会将B也完全分成小块。

分块后的平均性能为13.612Gflops，主要带来的收益是矩阵规模提升时性能不会下降。

外层的分块过程如下，do_block函数内部的过程和之前的完整外部循环类似。

for (int k = 0; k < n; k += KC) {
    int K = min(n - k, KC);
    for (int i = 0; i < n; i += MC) {
      int M = min(n - i, MC);
      int N = n;
      do_block(M, N, K, n, n, n, A + i + k * n, B + k, C + i);
    }
}

内存重排 Packing

每次对A进行4x1的访存时，是对4行同一列元素进行的访存，但是每次循环就会跳到下一列，由于是列主序的矩阵，循环间访存不是连续的，最好将所有循环会访问的元素排到一起，可以减少跨区域访存的次数，增加数据在一条CacheLine中的概率。因此对A进行了4行元素的内存重排。

每次对B是进行1x4的访存，每次对同一行四列的元素访问，由于列主序，一次循环内的访存是不连续的，可以将4列的元素重排到一起。

对矩阵A的元素进行Packing后，平均性能为15.212Gflops；对矩阵B的元素Packing后，平均性能为 17.139 Gflops。

进一步提高计算/访存比

之前代码的kernel部分，循环内一次计算取A的四个float，B的四个float，但是，B的每个float是用来标量乘A向量的，因此当时的做法是把B的每个float重复为1个32bitx4的向量再与A的向量相乘，核心代码如下

a_ri = vld1q_f32(A);
b_vi0 = vld1q_dup_f32(B); 
b_vi1 = vld1q_dup_f32(B + 1);
b_vi2 = vld1q_dup_f32(B + 2); 
b_vi3 = vld1q_dup_f32(B + 3);
c_c0 = vmlaq_f32(c_c0, a_ri, b_vi0);
c_c1 = vmlaq_f32(c_c1, a_ri, b_vi1);
c_c2 = vmlaq_f32(c_c2, a_ri, b_vi2);
c_c3 = vmlaq_f32(c_c3, a_ri, b_vi3);

这段代码有5次访存，4次fma（乘加指令）向量乘（mla指令和fma的效果是一样的）。

其对应汇编代码如下(删掉了一些重新排布的无关代码)，有一次单向量寄存器的load，两次双向量寄存器的load，也就是总共load了5个128bit寄存器，然后进行了4次fma计算。

4010e0:3dc00080 ldrq0, [x4]
4010e8:2d401cb0 ldps16, s7, [x5]
4010ec:2d4114a6 ldps6, s5, [x5, #8]
4010f4:4f901004 fmlav4.4s, v0.4s, v16.s[0]
4010fc:4f871003 fmlav3.4s, v0.4s, v7.s[0]
401100:4f861002 fmlav2.4s, v0.4s, v6.s[0]
401104:4f851001 fmlav1.4s, v0.4s, v5.s[0]

我们粗略地计算乘加指令和load指令的比例的话，（ldp这种一次load两个寄存器的指令用的周期应该略低于只load一个寄存器的指令，但是我们还是算其为2个load指令），为4/5= 0.8

这对于矩阵乘法而言，并不是很好的计算访存比，对于矩阵乘法，总共需要的从内存中转移到寄存器的访存次数为，乘加计算为，

计算访存比是，问题在于我们的寄存器数量有限，不可能一次load后一直使用，因此我们只能尽可能地多使用已有的寄存器。

对于我上面写的代码，一个很容易的优化是，我只需要B的4个float，理论上一个load指令就可以全部加载进来，只是后面的普通fma指令要变成fma_lane指令。

新的核心代码如下

a_ri = vld1q_f32(A + i * lda);
b_vi0 = vld1q_f32(B);
c_c0 = vfmaq_laneq_f32(c_c0, a_ri, b_vi0, 0);
c_c1 = vfmaq_laneq_f32(c_c1, a_ri, b_vi0, 1);
c_c2 = vfmaq_laneq_f32(c_c2, a_ri, b_vi0, 2);
c_c3 = vfmaq_laneq_f32(c_c3, a_ri, b_vi0, 3);

汇编指令如下，原来的1个ldr指令2个ldp指令变成了2个ldr指令，只load了2次SIMD寄存器，乘加指令与load指令的计算/访存比变为4/ 2 = 2.0

4010e0:3cc104a1 ldrq1, [x5], #16
4010e4:3dc00080 ldrq0, [x4]
4010f0:4f811005 fmlav5.4s, v0.4s, v1.s[0]
4010f4:4fa11004 fmlav4.4s, v0.4s, v1.s[1]
4010f8:4f811803 fmlav3.4s, v0.4s, v1.s[2]
4010fc:4fa11802 fmlav2.4s, v0.4s, v1.s[3]

优化后的平均性能为17.847 Gflops，性能有小部分提升。

循环展开，A、B一次加载4x4

之前我们的kernel一次只加载了A的4x1和B的1x4的元素，但是考虑到每次循环都有一次add和cmp指令，以及充分利用流水线的思想，我们可以把kernel的循环展开，一次加载4个A的4x1和4个B的1x4的元素，这样就变为一次加载4x4的A中元素和4x4的B中元素，代码如下

a_c0_i0 = vld1q_f32(A + i * 4);
a_c0_i1 = vld1q_f32(A + i * 4 + 4);
a_c0_i2 = vld1q_f32(A + i * 4 + 8);
a_c0_i3 = vld1q_f32(A + i * 4 + 12);
b_vi0_0 = vld1q_f32(B + 0);
b_vi1_0 = vld1q_f32(B + 4);
b_vi2_0 = vld1q_f32(B + 8);
b_vi3_0 = vld1q_f32(B + 12);

c_c0 = vaddq_f32(vaddq_f32(vmulq_laneq_f32(a_c0_i0, b_vi0_0, 0), vmulq_laneq_f32(a_c0_i1, b_vi1_0, 0)) ,  vaddq_f32(vmulq_laneq_f32(a_c0_i2, b_vi2_0, 0), vfmaq_laneq_f32(c_c0, a_c0_i3, b_vi3_0, 0)));
    
c_c1 = vaddq_f32(vaddq_f32(vmulq_laneq_f32(a_c0_i0, b_vi0_0, 1), vmulq_laneq_f32(a_c0_i1, b_vi1_0, 1)) ,  vaddq_f32(vmulq_laneq_f32(a_c0_i2, b_vi2_0, 1), vfmaq_laneq_f32(c_c1, a_c0_i3, b_vi3_0, 1)));
    
c_c2 = vaddq_f32(vaddq_f32(vmulq_laneq_f32(a_c0_i0, b_vi0_0, 2), vmulq_laneq_f32(a_c0_i1, b_vi1_0, 2)) ,  vaddq_f32(vmulq_laneq_f32(a_c0_i2, b_vi2_0, 2), vfmaq_laneq_f32(c_c2, a_c0_i3, b_vi3_0, 2)));
    
c_c3 = vaddq_f32(vaddq_f32(vmulq_laneq_f32(a_c0_i0, b_vi0_0, 3), vmulq_laneq_f32(a_c0_i1, b_vi1_0, 3)) ,  vaddq_f32(vmulq_laneq_f32(a_c0_i2, b_vi2_0, 3), vfmaq_laneq_f32(c_c3, a_c0_i3, b_vi3_0, 3)));

转换为汇编如下，16个乘加指令，4个fadd指令，1个ldp指令，6个ldur指令，总共load了8个SIMD寄存器，计算/访存比为2.5，但是20个乘/加指令中只有16个是必要的，因此这里的性能反而会下降。

4011d0:ad40c0a0 ldpq0, q16, [x5, #16]
4011d4:910100a5 addx5, x5, #0x40
4011d8:3cdf00a7 ldurq7, [x5, #-16]
4011dc:91010021 addx1, x1, #0x40
4011e0:3cdd0025 ldurq5, [x1, #-48]
4011e4:3cdf0026 ldurq6, [x1, #-16]
4011e8:4f8098b1 fmulv17.4s, v5.4s, v0.s[2]
4011ec:4f8090b3 fmulv19.4s, v5.4s, v0.s[0]
4011f0:4f8710c4 fmlav4.4s, v6.4s, v7.s[0]
4011f4:4fa710c3 fmlav3.4s, v6.4s, v7.s[1]
4011f8:4f8718c2 fmlav2.4s, v6.4s, v7.s[2]
4011fc:4fa718c1 fmlav1.4s, v6.4s, v7.s[3]
401200:3cde0027 ldurq7, [x1, #-32]
401204:4fa090b2 fmulv18.4s, v5.4s, v0.s[1]
401208:4fa098a0 fmulv0.4s, v5.4s, v0.s[3]
40120c:4f9010e4 fmlav4.4s, v7.4s, v16.s[0]
401210:4fb010e3 fmlav3.4s, v7.4s, v16.s[1]
401214:4f9018e2 fmlav2.4s, v7.4s, v16.s[2]
401218:4fb018e1 fmlav1.4s, v7.4s, v16.s[3]
40121c:4eb11e27 movv7.16b, v17.16b
401220:3cdc00a6 ldurq6, [x5, #-64]
401224:eb0200bf cmpx5, x2
401228:3cdc0025 ldurq5, [x1, #-64]
40122c:4f8610b3 fmlav19.4s, v5.4s, v6.s[0]
401230:4fa610b2 fmlav18.4s, v5.4s, v6.s[1]
401234:4f8618a7 fmlav7.4s, v5.4s, v6.s[2]
401238:4fa618a0 fmlav0.4s, v5.4s, v6.s[3]
40123c:4e33d484 faddv4.4s, v4.4s, v19.4s
401240:4e32d463 faddv3.4s, v3.4s, v18.4s
401244:4e27d442 faddv2.4s, v2.4s, v7.4s
401248:4e20d421 faddv1.4s, v1.4s, v0.4s

代码的平均性能只有15.969 Gflops

重新排布指令，结合乘加

上面的代码中的求和部分有一些是不必要的，只要写成部分和，循环结束后再规约求和，另外还有一些求和可以利用fma指令在计算乘法时顺便求出，因此我们重新排布了指令如下

a_c0_i0 = vld1q_f32(A + i * 4);
a_c0_i1 = vld1q_f32(A + i * 4 + 4);
a_c0_i2 = vld1q_f32(A + i * 4 + 8);
a_c0_i3 = vld1q_f32(A + i * 4 + 12);
b_vi0_0 = vld1q_f32(B + 0);
b_vi1_0 = vld1q_f32(B + 4);
b_vi2_0 = vld1q_f32(B + 8);
b_vi3_0 = vld1q_f32(B + 12);
temp_v0 = vfmaq_laneq_f32(c_c0, a_c0_i0, b_vi0_0, 0);
c_c0 = vfmaq_laneq_f32(temp_v0, a_c0_i1, b_vi1_0, 0);
temp_v3 = vfmaq_laneq_f32(c_c1, a_c0_i1, b_vi1_0, 1);
c_c1 = vfmaq_laneq_f32(temp_v3, a_c0_i0, b_vi0_0, 1);
temp_v0 = vfmaq_laneq_f32(c_c2, a_c0_i0, b_vi0_0, 2);
c_c2 = vfmaq_laneq_f32(temp_v0, a_c0_i1, b_vi1_0, 2);
temp_v3 = vfmaq_laneq_f32(c_c3, a_c0_i1, b_vi1_0, 3);
c_c3 = vfmaq_laneq_f32(temp_v3, a_c0_i0, b_vi0_0, 3);


temp_v0 = vfmaq_laneq_f32(part1_c0, a_c0_i2, b_vi2_0, 0);
part1_c0 = vfmaq_laneq_f32(temp_v0, a_c0_i3, b_vi3_0, 0);
temp_v3 = vfmaq_laneq_f32(part1_c1, a_c0_i3, b_vi3_0, 1);
part1_c1 = vfmaq_laneq_f32(temp_v3, a_c0_i2, b_vi2_0, 1);
temp_v0 = vfmaq_laneq_f32(part1_c2, a_c0_i2, b_vi2_0, 2);
part1_c2 = vfmaq_laneq_f32(temp_v0, a_c0_i3, b_vi3_0, 2);
temp_v3 = vfmaq_laneq_f32(part1_c3, a_c0_i3, b_vi3_0, 3);
part1_c3 = vfmaq_laneq_f32(temp_v3, a_c0_i2, b_vi2_0, 3);

生成的汇编如下，浮点相关的全为乘加指令，4个ldp指令load8个寄存器，16个fma指令，计算访存比为2.0

4011e0:ad405854 ldpq20, q22, [x2]
4011e4:ad405cb5 ldpq21, q23, [x5]
4011e8:ad414850 ldpq16, q18, [x2, #32]
4011ec:91010042 addx2, x2, #0x40
4011f0:ad414cb1 ldpq17, q19, [x5, #32]
4011f4:910100a5 addx5, x5, #0x40
4011f8:4f951287 fmlav7.4s, v20.4s, v21.s[0]
4011fc:eb0100bf cmpx5, x1
401200:4f951a83 fmlav3.4s, v20.4s, v21.s[2]
401204:4fb712c5 fmlav5.4s, v22.4s, v23.s[1]
401208:4fb71ac1 fmlav1.4s, v22.4s, v23.s[3]
40120c:4f911206 fmlav6.4s, v16.4s, v17.s[0]
401210:4f911a02 fmlav2.4s, v16.4s, v17.s[2]
401214:4fb31244 fmlav4.4s, v18.4s, v19.s[1]
401218:4fb31a40 fmlav0.4s, v18.4s, v19.s[3]
40121c:4f9712c7 fmlav7.4s, v22.4s, v23.s[0]
401220:4f971ac3 fmlav3.4s, v22.4s, v23.s[2]
401224:4fb51285 fmlav5.4s, v20.4s, v21.s[1]
401228:4fb51a81 fmlav1.4s, v20.4s, v21.s[3]
40122c:4f931246 fmlav6.4s, v18.4s, v19.s[0]
401230:4f931a42 fmlav2.4s, v18.4s, v19.s[2]
401234:4fb11204 fmlav4.4s, v16.4s, v17.s[1]
401238:4fb11a00 fmlav0.4s, v16.4s, v17.s[3]

平均性能为25.952Gflops，开了-O3优化后平均性能为26.124Gflops，峰值性能为27.8 Gflops

再增加循环展开层数

之前一次加载16个A中的元素，如果一次加载32个A中的float，进行8x4的一次load，则性能还能有微弱提升

平均性能为26.22 Gflops，峰值性能为28.3 Gflops

其实接下来还有更多优化方法，例如Prefetch技术，在本轮迭代的计算中就先fetch下一轮迭代会用到的数据，充分利用流水线隐藏延迟，能够进一步提高性能。但由于这些技术高度和具体CPU架构相关且测试较为复杂，因此我们就不在此讨论。

关于研究矩阵乘法优化的思考

我们在这里探求单线程的矩阵乘法有没有什么用呢？其实对于绝大部分的人都是用不到的，而且我们研究了许久也连行业最先进水平也没赶上。在实际应用时，绝大部分有矩阵计算需求的人应该都会调用其他的科学计算框架。那么，我们为什么还要在这里研究矩阵乘法的优化呢？

从功利的角度回答，研究矩阵乘法优化的过程中，我们对于如何利用计算机的体系结构特点来进行优化进行了深入的学习和实践，这种经验在其他需要优化的场景中可能是有用的。另外，如果有一天我们需要在一个比较新的计算硬件上用到矩阵乘法，而常用的科学计算库还没有对该硬件进行针对性优化的话，我们或许能够亲自动手优化它。

从非功利的角度回答，just for fun!

https://en.wikipedia.org/wiki/Row-_and_column-major_order↩︎

在程序中重定向标准输入和标准输出的多种方法及原理

2020-12-31T18:17:19.000Z

如何在程序中重定向标准输入和标准输出呢？本文将记录多种方法并介绍背后的原理。

前一阵子在看一段代码时，虽然猜到那段代码的作用大概是重定向了stdout，但是一时没看明白是怎么完成的重定向。后来一阵学习才发现对stdin和stdout的重定向还有种种方法，而且对这些方法的完全理解需要了解操作系统中的文件描述符的一些实现。

如果对linux上的重定向很熟悉的话，那么这篇文章的内容就不需要看了。

一段重定向标准输出的代码

当初看到的代码做的事情大致是先fork产生了一个子进程，然后在子进程中用open打开了一个管道，然后直接向标准输出输出就将字节流输出到了管道中，抽象出重定向相关的最核心的代码就是下面的样子。

#include 
#include 
#include 

int main() {
    const char *filename = "./output.txt";
    close(1);
    open(filename, O_WRONLY | O_CREAT, 0666);
    printf("Hello, World!\n");
}

当编译并执行这段代码后，会发现向stdout的输出都写在了文件中，如下面的过程。

$ g++ -o test test1.cpp
$ ./test
$ cat output.txt
Hello, World!
$

可以看到，标准输出被重定向到了文件中，那么，这一重定向过程是怎么完成的呢？要完整地解释，就需要了解Unix/Linux的文件实现。

Unix/Linux的文件模型

Figure 1展示了Unix系统的文件实现，每一个进程有一个File DescriptorTable，File Descriptor Table中都是该进程的fd(FileDescriptor)，fd从0开始，都是很小的整数；每一个FileDescriptor都是一个index，File Descritpor Table中的每一项会指向一个系统全局的File Table中的File TableEntry，这个File TableEntry记录了一些信息包括文件的打开模式、当前seek位置(cursor)、指向该entry的FileDescriptor数量，每个File table Entry还会指向一个Vnode Table(Inode Tablein Linux)中的Vnode(Inode in Linux), vnode则是真正的关于文件的抽象。

Figure 1: File table and inode table, Qwertyus, via Wikimedia Commons

上面描述了Unix系统中文件的三层结构File Descriptor Table <-> File Table <-> Vnode Table，需要注意的是，多个FileDescriptor（不管是不是在同一进程中）可以指向同一个File TableEntry，多个File Table Entry可以指向同一vnode，因此，多个FileDescriptor代表同一文件会有两种情况：

多个File Descriptor指向同一File Table Entry，该File TableEntry指向一个vnode，例如同一进程的fd3和fd4都指向File Table Entry 3，FileTable Entry3 指向/tmp/output的vnode
多个File Descriptor指向不同的File TableEntry，这些entries指向同一vnode，例如同一进程的fd3指向Entry 4，fd4指向Entry 4，Entry3和Entry4都指向/tmp/output的vnode

那么，这两种情况会有什么区别呢？区别就在于情形1共享相同的File TableEntry，意味着他们共享相同的cursor，可以一起相继地写入，但是情形2是不同的FileTable Entry，两个cursor互相不同步，例如写入可能互相覆盖。

什么情况下会出现情形1呢？例如，同一进程中，使用dup或dup2函数复制一个fd的FileTable Entry到另一个fd，也就是产生了两个fd指向同一File TableEntry。还有可能是，使用fork产生了一个子进程，子进程会复制父进程的FileDescriptor Table。

什么情况会出现情形2呢？同一进程可以用open打开两次同一文件，这会产生两个FileTableEntry，两个fd分别指向两个entry，而对两个fd的写入是互相不知道对方seek的cursor位置的。

下面的代码演示了使用dup的情形1

#include 
#include 
#include 
#include 
#include 
#include 

int main() {
    const char filename[] = "./text.txt";
    const char info1[] = "123\n456\n";
    const char info2[] = "789\nabcde\n";
    int fd3 = open(filename, O_WRONLY | O_CREAT, 0666);
    int fd4 = dup(fd3);
    printf("fd3 is %d, fd4 is %d\n", fd3, fd4);
    assert(write(fd4, info2, strlen(info2)) > 0);
    assert(write(fd3, info1, strlen(info1)) > 0);
    
}

下面是运行结果，可以看到在对fd4写入内容后，对fd3写入是接在fd4写入内容后面的，说明fd3和fd4指向了同一FileTable Entry，用的同一cursor。

$ g++ -o test testdup.cpp
$ ./test
fd3 is 3, fd4 is 4
$ cat text.txt
789
abcde
123
456
$

下面的代码演示了open两次同一文件的情形

#include 
#include 
#include 
#include 
#include 
#include 

int main() {
    const char filename[] = "./text2.txt";
    const char info1[] = "123\n456\n";
    const char info2[] = "789\nabcde\n";
    int fd3 = open(filename, O_WRONLY | O_CREAT, 0666);
    int fd4 = open(filename, O_WRONLY | O_CREAT, 0666);
    assert(write(fd4, info2, strlen(info2)) > 0);
    assert(write(fd3, info1, strlen(info1)) > 0);
}

下面是运行结果，可以看到我们先对fd4进行写入，再对fd3进行写入，fd3的写入覆盖了fd4写入的部分内容，两个fd指向的FileTable Entry中的cursor都是0，因此都是从文件头开始写入的。

$ g++ -o test test34.cpp
$ ./test
$ cat text2.txt
123
456
e
$

另外，Unix系统有一个十分重要的特性，就是FileDescriptor都是从0开始的非负整数，而当系统新分配一个FileDescriptor给进程时，内核会选取最小的未分配的非负整数作为新fd。

重定向标准输入和标准输出的原理

在Unix/Linux系统设计中，每一个有3个预分配的FileDescriptor，分别是0（标准输入），1（标准输出），2（标准错误输出），例如在shell中运行一个程序，这三个FileDescriptor默认都会最终指向终端的vnode。

Figure 2演示了3个shell运行的进程的文件模型，他们的0,1,2 FileDescriptor都指向相同的File TableEntry，并且这些entries都指向终端vnode

Figure 2: 三个进程与三层文件模型，三个进程的0,1,2fd指向相同的File TableEntry， source: CS110: Principles of Computer Systems

那么，什么是对标准输入输出进行重定向呢？我们可以先想一想，哪些程序会用到标准输入输出呢？在Unix系统函数的层面，perror()函数会将错误信息输出到标准错误输出，也就是值为2的fd，那么如果我们将fd2对应到一个新的文件，标准错误输出就被重定向了。

因此，在Unix系统层面对标准输入输出的重定向可以总结为转移fd0,1,2对应的文件。

那么怎么实现这一点呢，最简单的对标准输入的重定向如下，先close(0);断开标准输入fd0和File Table Entry的连接，然后建立fd0和新的指向文件vnode的Entry的连接，之后从标准输入的读入就是从文件读入了。那么重定向标准输出和标准错误输出也是类似的。下面的代码演示的是最简单直接的方法。

#include 
#include 
#include 

int main() {
    const char filename[] = "./text.txt";
    close(0);
    assert(open(filename, O_RDONLY) == 0);
    //...
}

在展示其他重定向的方法之前，我们还需要讲明白c library中的stream和filedescriptor的关系，https://www.gnu.org/software/libc/manual/html_node/Streams-and-File-Descriptors.html简单地介绍了GNU中的FileDescriptor和C中的Stream的区别，FileDescriptor就是我们上面提到的概念，而Stream就是FILE *这样的结构，这种结构是对FileDescriptor的封装，加入了缓存buffer，和一些格式化输入输出之类的功能。我们可以从FileDescriptor创建一个Stream，也可以获取一个已有的FILE*的fd。Clibrary中的stdin,stdout,stderr都是Stream

而fopen，fclose的操作和open,close是类似的，Stream的开关除了会对FILE*结构的buffer进行处理外，也会做FileDescriptor和File Table Entry、vnode相关的处理。

下面的代码则是演示了fclose,freopenstdin对fd 0的影响。

#include 
#include 
#include 
#include 

int main() {
    fclose(stdin);
    if (fcntl(0, F_GETFD) < 0) {
        fprintf(stderr, "%s\n", strerror(errno));
    }
    freopen("text.txt", "r", stdin);
    int flags = 0;
    if (( flags = fcntl(0, F_GETFD) ) < 0) {
        fprintf(stderr, "%s\n", strerror(errno));
    }
    else {
        fprintf(stderr, "fd 0 valid, flags: %d\n", flags);
    }
}

运行结果如下，可见在fclose(stdin)后，fd0对entry的指向也被取消了，0不再是一个valid的filedescriptor，而在使用freopen后，fd0又被再次分配。也就是说，对Stream的重定向，也就会导致对fd的重定向。

$ g++ -o test testfclose.cpp
$ ./test
Bad file descriptor
fd 0 valid, flags: 0
$

当我们说明了Stream和FileDescriptor的区别后，我们除了可以通过对Stream的操作影响fd，也可以通过对fd的操作影响Stream。我们之前提到了Stream是对fd的封装，那么，如果我们改变一个FileDescriptor的指向，FILE*中的fd值并没有改变，但是fd指向的entry和vnode却变了，因此Stream实际指向的文件就发生了变化。那么就是说，我们对fd的重定向，也会导致对Stream的重定向。

到这里可以总结，fd是Unix系统层面的API，Stream是Clibrary的API，但是对fd的重定向会导致Stream的重定向，对Stream的重定向也会通过对fd的重定向实现。

重定向标准输入标准输出的各种方法

我们在第一节就已经展示了最简单的重定向标准输出的方法，这里就简单地再作介绍，下面的介绍为了简便，都用重定向标准输出来代表。

1. 先 close(1) 再 open

#include 
#include 
#include 

int main() {
    const char *filename = "./output.txt";
    close(1);
    open(filename, O_WRONLY | O_CREAT, 0666);
    printf("Hello, World!\n");
}

原理已经说过，就是先取消fd 1和文件的连接，再重新改变fd1的指向，open会分配最小的可用fd，也就是1；而printf是向Streamstdout中输出，由于stdout中的fd就是1，因此实际上就会向open的文件中输出。完成了对标准输出的重定向。

2. 使用dup

#include 
#include 
#include 
#include 

int main() {
    const char filename[] = "./output.txt";
    int fd3 = open(filename, O_WRONLY | O_CREAT, 0666);
    close(1);
    assert(dup(fd3) == 1);
    printf("Hello, World!\n");
}

dup(fd1)会将新分配一个fd2，fd2指向fd1指向的File TableEntry；当close(1)后，dup就会新分配1，并将fd1指向fd3指向的entry，而该entry指向一个文件的vnode。

3. 使用dup2

#include 
#include 
#include 
#include 

int main() {
    const char filename[] = "./output.txt";
    int fd3 = open(filename, O_WRONLY | O_CREAT, 0666);
    close(1);
    assert(dup2(fd3, 1) == 1);
    printf("Hello, World!\n");
}

方法3和方法2很相似，dup2(fd1,fd2)会新分配fd2，并将fd2指向fd1指向的FileTable Entry，剩下的就和方法2一样了。

4. 使用freopen

#include 

int main() {
    if (freopen("output.txt", "w", stdout)) {
        printf("Hello, World!\n");
    }
}

该方法形式上最为简单，需要注意的是，freopen会自动close原来的fd，不需要先手动fclose

题外话，如何回到重定向前的标准输入输出

上面的方法基本都取消了原来的fd和File TableEntry的连接，那么如果我们想再将标准输出重定向回去该如何呢？如果需要保留原来的fd的话，可以用dup/dup2先复制一下原来fd指向的FileTableEntry，然后再重定向，这样即使想回到最开始的标准输出文件（例如终端），也可以完成。

下面的代码演示了这一过程，先将fd 4指向fd 1指向的File TableEntry，which指向了终端的vnode，想要恢复stdout到终端时，只要先flushstdout的buffer，将fd 1再指向fd 4保留的File Table Entry，然后Streamstdout实际上就是指向终端的Stream

#include 
#include 
#include 

int main() {
    dup2(1, 4);
    if (freopen("output.txt", "w", stdout)) {
        printf("Hello, World!\n");
        fflush(stdout);
        dup2(4, 1);
        printf("output to shell\n");
    }
}

总结

这是一个很常见的问题，可以用于子进程的重定向输入输出等场景，但是对它的理解需要深入到对Unix文件模型实现的了解。我之前在这方面只会用freopen或者shell调用时redirect，但是并不知其所以然，所以记录下来。

我们可否说清什么存在？

2020-11-20T13:44:14.000Z

世界上存在什么，不存在什么？

这似乎是个自然科学的问题，但是，同样是个哲学上的问题，这是本体论的根本问题。

这个问题的答案，是和一个人对世界的认识论相关的，如果一个人是怀疑论者，那么他可能认为我们不可能搞明白什么存在，什么不存在。如果一个人是自然主义者，那么他可能认为一切都交由自然科学去鉴定。

鉴于这个问题实在牵扯到了方方面面，而且仍是争论不休的问题，我也只不过是在这里从几个方面记录下自己的想法而已。

名称(Naming)与含义(Meaning)的关系

从我的认识来说，名称(naming)和这个名称对应的含义(meaning)是两个概念。当我们在自然语言中说出一个名称的时候，我们想要用名称代指这个名称的含义。例如，当我们说出名称“狗”的时候，我们是用这个名称来代指一个物种；我们说出名称“素数“ 的时候，我们是在用这个词指代一些数。

当名称存在时，对应的含义不一定存在，或者说，对应的事物不一定存在。例如，我们的词典中有“飞马”(Pegasus)这个词，但是在我们常见的本体论体系中，并不认为飞马是存在的。

当说到这里，就有了一个绕不过去的问题，有人会说，飞马虽然不存在于物理世界中，但是我们的思维中可以有飞马这样一个概念。这引出的问题是，我们说的“存在”一词，exist也好，being也好，包含在思维中的存在吗？我个人的看法是，这是个对“存在”该词语本身的定义问题，如果要进行讨论，就先保证讨论的是同一个“存在”的意思。

由此另一个问题是，我们对事物的命名(naming)，是如何对应到事物本身的呢？我们又如何确认两个人说的同一名称指的是同一含义呢？

例如，我们在说“存在“，但是如果我们要对存在先进行一个统一的定义，我们又不得不问，什么是定义？AnilGupta的一篇文章讨论了我们过去在自然语言与逻辑中对“定义”一些用法，他将这些定义的方法分为很多类，例如有字典式定义、描述性定义、规范性定义、解释性定义等等。我们对许多词的定义都是用许多其他的词对其进行描述，无论是字典式定义、描述性定义、解释性定义，我们都会用到别的词来对一个词的含义进行描述或解释、规范，例如词可以由词定义，词可以由定义，可以由定义，而甚至可以有就是词这样的循环定义情况（至少在自然语言内非常常见）。如果我们用图模型来描述词的含义关系，将一个词表示为一个点，词的定义依赖表示为边的话，那么整个词语的含义关系就是一个复杂的图，如果我们允许循环定义，这张图还会有环的出现。

不难发现，如果我们追问词的定义的源头：有没有原子性的、不由其他词定义的词，那么我们可能是得不到答案的，这取决于有没有那些不需要由其他词解释的词。但是，有这样的词吗？或许名字和代词可以是，我可以指着我对一个说不同语言的人说我的名字，他或许可以知道我说的词是我的名字，但是他也有可能认为我说的词是“我”这个代词而不是我的名字。因此，这里不使用其他词而定义可能会出现名称和含义可能不对应的问题，也是困难的。

我在和刘奋荣老师讨论是否有词的定义的源头的词时，我原以为她会用分析哲学体系下的理论来回答我，但是她却提到了庄子的“物”的思想，指出庄子认为词的源头是“物”。但是我不是很了解庄子的思想，也就无法评说。当然，她也提到了词的定义存在着相互定义、成体系的情况，这和我上面的想法是类似的。

回到名称与含义的同一性问题，世界上的两个说着相同语言的人，一个人说的“桌子“和另一个人说的”桌子“是同一种东西吗？我想，要想使“是同一种东西”的命题为真，首先得明确他们对桌子的定义是相同的，但是一个重要的问题就是如何定义桌子？（我们现在还不是在讨论本质问题，即存不存在桌子这一问题，我们只是在讨论如何定义语言中“桌子”这个词。）那么，首先需要保证的是他们对每一个单词用的都是同一种定义方法，如果原子性、不需解释的词存在，还需要保证他们对这些不需解释的词所指的含义是相同的。看到这可能会想，这几乎就是不可能事，或许，在自然语言中让两个人对同一个单词都指相同的意思就是不可能的吧。

但是应用嘛，能凑合用就行了。

事物有本质吗

事物是否有本质是一个一直被争论的问题。首先，本质本身的定义都是不容易的，有人说本质是使一个实体成为其所在的不可缺少的属性。但是我并不认为这是一个说的很清楚的定义，什么叫使一个实体成为其本身，什么是实体的身份？

从我个人的观点而言，一个定义都难以定义清楚的，或者说我弄不清它定义的词语，我当然是不认为其存在的。存在主义说存在先于本质，但是我以为就没有本质。

世界上有很多相像的东西，例如同一工厂生产的两块规格相同的铁锭，我以为两个铁锭不过是以相似的成分构成的两个有相似形状的实体，我们称这种材质、形状的东西为“铁锭”，这是我们语言中的词汇，不代表存在什么“本质”。

我们能说清什么存在吗

Quine在那篇著名的On What There is¹中，提出"to be is to be a value of avariable"，即用一阶谓词逻辑来描述"tobe"这样一个存在命题。他几乎舍弃了一切名词，而使用谓词来表示存在。例如，"Thereis a horse"这句话可以被翻译为"There is something that xxxx"其中xxxx是用来定义horse的谓词，具体使用什么样的谓词，取决于使用者的哲学体系和自然科学体系。这个谓词，将something的范围限制到了horse上面。而且，你可以说出各种各样的存在命题，但这些命题可以为真也可以为假，取决于人怎样认识这个世界。

从Quine等人的观点看，我们的ontologicalcommitment(本体论承诺，即某事物存在的命题)的真假需要满足：在ontologicalcommitment为真时当且仅当我们认同的理论也为真。

上面的话意味着，每个人由于自己秉持的哲学观念、知识认知不同，认为存在的范围也会不一样。例如一个神学家，如果他信仰一个基督教的体系，那么他就需要认为上帝是存在的，否则他的体系就为假。又例如Empedocles相信世界的物质是由水、火、土、气四种元素构成的，那么他至少认为水、火、土、气作为基本元素存在着。

我们每个人的哲学观念与知识体系对“何物存在”的问题提出了要求，而我们对“何物存在”的认知又决定了我们的哲学观念与知识体系的一部分，也就是说，一个人的ontologicalcommitment与他的哲学观念与知识体系是必须自洽的。如果一个人能够在他的体系、他秉持的公理系统中没有漏洞地认定某物存在，那么对于他来说是没有矛盾的。至于别人的意见是不是与他相左，不在一个体系中又谈论什么呢？

总结而言，一个人可以在自己的哲学观念与知识体系中说清自己认为什么存在（理论上可以，实际上说清楚的难度很大）。

那么，我个人的本体论承诺中，什么存在呢？我前面提到了我认为没有本质存在，我对其他的实在的存在认定是和自然科学一致的。

什么是人？

经常有人会问：”什么是人？”，然后给出一个自己的答案。

这样的自问自答屡见不鲜，然而在我看来，如果你能说清人和狗的区别，那么你就能够先说清猫和狗的区别。即我认为，问什么是人，其实就是在问一个物种的定义是什么。

那么物种的定义是什么呢？根据我们上面的讨论，怎么定义物种这个词有非常多种方法，而我只想找出我让我满意的定义方法。

一种描述性的定义方法是形态学物种定义(morphologicalspecies)，描述一个物种的形态特征，如果这些特征只有该物种有，那么符合这些特征的就是这个物种。这种定义方法存在的问题是，人有限的认知能力中，很难认识到所有的物种以及这些物种的全部特征。例如，如果在另一个星球上发现了一个所有特征都和猫一样的生物，这种生物是猫吗？

另一种常见的定义方法是按生殖隔离定义，即定义隔离种(insularspecies)或说生物种(biologicalspecies)，这种定义方法也是中国高中生物采用的定义方法。而我认为，生殖隔离，应该更多地被视为一种特征，而不是用来定义物种的标准（当然，我没有用本质这个词）。更何况，这种定义方法也存在很多问题，例如无性繁殖的生物不能被这种方法定义。

还有一种物种的定义，是遗传物种(evolutionary species/phylogeneticspecies)，通俗地说，是在一段时间和空间内保持自己identity(我认为这里不应该翻译为本质，但是也没想到很好的翻译)的物种。这种定义的关键在于指出了物种存在的时间属性，物种是动态的，在一定时间中分化出现，又在一段时间后进化、分化出其他物种。下面这张图很好地描绘了一个生命之树(TreeofLife)，可以看到在不同的时间中演化出了不同的物种。而一个物种的存在，是有其时间范围的。

Figure 1: Tree of Life diagram, Leonard Eisenberg, evogeneao.com,已获得作者授权

遗传物种的定义当然也是存在问题的，存在模糊甚至矛盾的地方。但是我却很喜欢这种定义，在这种定义中，一种物种的身份的确认和其历史有不可割裂的关系。例如一个生物体之所以是人，是因为这个人有祖先是猿类，猿类有祖先是灵长目动物，灵长目动物有祖先是早期哺乳动物，早期哺乳动物有祖先是四足动物，四足动物有祖先是脊椎动物，脊椎动物有祖先是地球上的一个细胞。如果一个生物没有祖先是猿类，如果这个生物最早的祖先不在地球上，那么这个生物都不被归类为人类。下面这张图更细节地描绘了人类的演化树。

Figure2: Haeckel's Paleontological Tree of Vertebrates (c. 1879).公有领域

尾

我们的本体论系统，正如我们的自然语言一样漏洞百出甚至有不少矛盾之处，就像充满bug的“屎山”代码，但是这并不妨碍我们拿它凑合着用下去，至少我们用着还可以进行一些工作，还能交流与活着。

Quine, W.V., 1948. On what there is. The review ofmetaphysics, pp.21-38.↩︎

将Time Machine备份转移到新磁盘

2020-11-19T15:29:12.000Z

由于之前用来作为TimeMachine备份的硬盘只有1t，能记录的快照日期有限，我又购置了一个2t的移动硬盘来作为新的备份磁盘。但是在迁移旧备份到新磁盘的过程却并不简单。

我先后尝试了官网推荐的拷贝粘贴法、rsync法、磁盘工具的恢复磁盘法、dd法。

官网推荐方法

我最先尝试的就是官网推荐的方法将时间机器备份从一个备份磁盘传输到另一个磁盘，设置一下新磁盘的权限后就开始拷贝粘贴。

就不论拷贝的8个小时以上的准备时间了，在数个小时(至少大于6)的拷贝后，就会遇到某个被拷贝的文件被权限保护的问题。试了两次不行，遂放弃该方法。

rsync方法

rsync一直是用来同步数据的常用方法，这次自然也想到了它。设置了一下保留hardlink等参数后，就开始同步。结果在count files list结束后，出现了chown的权限错误，试了两次，未果，放弃。

磁盘工具的恢复磁盘

在网上看到的有一个方法是在开机Command+R进入恢复模式后使用磁盘助理进行恢复，我在没有进入恢复模式时两个大小不一致的磁盘不能使用恢复。我也不可能让电脑在恢复模式处于几个小时，于是并没有在恢复模式使用。

dd方法

dd是克隆磁盘的常见方法，以前在制作启动盘和整盘备份的时候就用过它。可以说它的功能应该和磁盘工具的恢复磁盘是类似的。先用dd将旧备份整盘克隆到新磁盘，然后再扩容一下新磁盘的文件系统，理论上应该就可行了。

使用diskutil list查看磁盘的标识符后

首先使用dd克隆

1	sudo dd if=/dev/disk_index1 bs=4m \| pv \| sudo dd of=/dev/disk_index2

克隆完成后先在磁盘工具中对新磁盘的HFS+文件系统进行一次“急救”检查，之所以进行这次检查似乎是要解决一下dd时的一些边界块大小问题，我不运行这次检查的话下一步会失败。

检查完成后就使用磁盘工具的分区功能将未使用的分区删去，然后新文件系统就会使用全部大小了。

至此Time Machine成功迁移到新磁盘，暂时使用没有出现问题。

通过代理服务器ssh连接内网服务器

2020-09-05T00:37:49.000Z

经常遇到的场景是，公司或学校的服务器都不能直接在外网进行访问，但是存在一个代理服务器，这时候就可以利用代理服务器来访问内网服务器。

使用跳板机访问内网服务器的场景和姿势都很多，我这里只介绍我碰到的场景。

网络状态

场景为，有客户端pcA，代理服务器P，目标服务器T，我们的最终需求是直接ssh到T上。

1
2
3

+------+       +----------+      +----------+
| pc A | <---> | Server P | <--> | Server T |
+------+       +----------+      +----------+

目前我们可以做到的是，先在A上ssh连接到代理服务器P，然后继续ssh连接到T，可以简单描述为在A上执行下面的过程。

1 2	ssh userP@hostnameP -p portP ssh userT@hostnameT -p portT

这种最朴素的方法需要两步ssh，但是能不能一步ssh就可以连接到T呢？

首先要问，为什么要一步ssh到T？

第一，这样可以简化ssh到目标服务器的过程，不需要两步ssh。第二，有些基于ssh的服务无法两步ssh，例如使用FileZilla等通过ssh浏览文件的软件，还有vscodeRemote SSH 这样的插件，都需要一步ssh到目标服务器。

笔者面临的更复杂的场景

1
2
3

+------+       +------------+       +----------+       +----------+
| pc A | <---> | Firewall F | <---> | Server P | <---> | Server T |
+------+       +------------+       +----------+       +----------+

其中FirewallF是一台网关服务器，而当执行ssh userP@hostnameF -p portF时，会连接到P，这说明服务器P的ssh监听端口portP已经被转发到了网关F的portF上，但是笔者所在的网络中，这里的网关服务器不是用的简单的端口转发，而是使用了一个程序监听的portF，验证身份后再将该tcp的连接的内容转发到P的portP上。因此很多简单的方法都失效了。但是我在服务器P有一个端口portM，上可以建立从服务器P的端口portM到Firewall的连接，这是我最终能够实现目标的关键。

好了，下面介绍几种我尝试过的方法。前几种都是在描述的简单的场景下有用的方法，最后一种方法是对我的场景也有用的方法。

使用ssh的Proxy Jump功能

其实目前大部分系统自带的OpenSSH软件已经有了ProxyJump功能，它exactly实现了我们第一个场景的需求。

在使用命令行直接ssh时，可以使用-J参数来使用该功能。下面的命令描述了简单的使用方法，只要这样一行ssh命令就可以进行把服务器P当作ssh跳板的功能。

1	ssh -J userP@hostnameP:portP userT@hostnameT:portT

也可以在~/.ssh/config中定义host来快捷地进行ssh访问

# ssh config file
# Server P
Host serverP
HostName hostnameP
User userP
Port portP

# Server T
Host serverT
HostName hostnameT
User userT
Port portT
ProxyJump serverP

这样只要使用

1	ssh serverT

就可以ssh到serverT上了。另外这里只用了一步跳转，其实还可以进行更多步跳转，如下面的~/.ssh/config设置

# ssh config file
# Server P
Host serverP
HostName hostnameP
User userP
Port portP

# Server Q
Host serverQ
HostName hostnameQ
User userQ
Port portQ
ProxyJump serverP

# Server T
Host serverT
HostName hostnameT
User userT
Port portT
ProxyJump serverQ

这样执行ssh serverT后，会发生2步跳转，先经过服务器P，再经过服务器Q，最后到服务器T

使用ssh的ProxyCommand功能

老旧的OpenSSH程序是不支持ProxyJump功能的，这时候可以使用OpenSSH的ProxyCommand功能，也可以达到一样的效果。

1	ssh -o ProxyCommand="ssh -W %h:%p userP@hostnameP:portP" userT@hostnameT:portT

上面的一行命令也可以通过Server P进行跳转ssh

当然，这种方法也是可以通过~/.ssh/config配置简单设置的。

使用ssh的-tt参数

如果OpenSSH老到连ProxyCommand都不支持，那么还可以通过-tt参数实现。

1	ssh -tt userP@hostnameP:portP ssh -tt userT@hostnameT:portT

-tt可以在ssh建立后立刻执行下一命令

使用端口转发

如果不是像笔者一样属于第二个情景，即ServerP以外还有一个防火墙，那么前面描述的方法已经完全够用了。但是笔者的情景必须要使用另外的方法。

之前提到，在笔者的场景中，服务器P上有额外的端口portM，而我们可以将ServerT的portT端口转发到ServerP的portM上，这样我们访问hostnameP:portM就相当于访问hostnameT:portT

端口转发有多种实现方法，笔者在网关服务器F上没有操作权限，但是可以在ssh时使用LocalForward功能进行端口转发

例如，我们可以将Server P的端口portM转发到pcA的本地端口portA上，只需要在pc A上运行

1	ssh -L portA:localhost:portM userP@hostnameF:portF

这样一来，我在pcA上访问localhost:portA就相当于访问hostnameP:portM，下一步就是将hostnameT:portT转发到hostnameP:portM上。

不过要注意的是，LocalForward转发默认转发后只在本地监听端口，例如现在进行了一步转发后，pcA的sshd进程会监听localhost:portA，但是别的计算机是不能访问hostnameA:portA的。

但是由于我们需要转发hostnameP:portM，意味着portM是对其他ip也都可见的端口，那么就需要使用-g(GatewayPorts)选项，这代表着会监听所有监听来自所有ip的对portM的请求。

在Server P上运行

1	ssh -L portM:localhost:portT -g userT@hostnameT:portT

就可以在ServerP上将hostnameT:portT转发到hostnameP:portM上，且整个内网都可以访问hostnameP:portM

这样一来，链条就打通了，首先在ServerP上将hostnameT:portT转发到hostnameP:portM上，然后在pcA上将hostnameP:portM转发到localhost:portA上，之后只需要在pc A上运行

1	ssh userT@localhost:portA

就可以ssh到Server T上了

上面的命令都可以写入~/.ssh/config中简化配置，在pcA上，等效的config配置为

Host serverP
HostName hostnameF
Port portF
User userP
LocalForward portA localhost:portM

Host serverT
HostName localhost
Port portA
User userT
# You'd better use RSA key to verify, e.g., append the content of ~/.ssh/id_rsa.pub to ~/.ssh/authorized_keys in Server T
# IdentityFile ~/.ssh/id_rsa
# IdentitiesOnly yes

在Server P上，config配置为

Host serverT
HostName hostnameT
Port portT
User userT
LocalForward portM localhost:portT
GatewayPorts yes

配置完成后，在Server P上运行

1	ssh serverT

在pc A上运行下面的命令进行端口转发

1	ssh serverP

再在pc A上运行

1	ssh serverT

就可以直接ssh到Server T了，配置同样可以直接在vscode RemoteSSH中使用。相对于使用vim写代码，个人更习惯通过vscode在serverT上写代码。

如果你的情境中Server P和Server T是一体的，即只是存在FirewallF和Server T，那么只需要把原Server P上的config配置放在ServerT上，并在Server T上运行ssh serverT,在pcA的config设置也都改成server T的相关配置即可。

另外，笔者的环境下，使用vscode Remote SSH时必须在pcA上指定IdentifyFile文件进行ssh serverT

使用Disqus JS让Disqus评论在国内可用

2020-07-25T17:39:02.000Z

Disqus在国内近几年一直访问不了，那么许多平常访问的游客甚至不知道博客有评论功能，这无疑是让人遗憾的事情。

要想让Disqus的功能可用，可以使用Disqus API +反向代理的方法，前端模拟Disqus的评论界面，再使用一个服务器反向代理DisqusAPI的请求，那么就可以让评论可以在国内网显示出来。

笔者对DisqusJS项目早有所耳闻，但是一直没有精力去使用，今天正好将其调试好，然而碰到了一些我意想不到的问题，导致花了很长时间。

神奇的Disqus JS

DisqusJS是一个前端脚本和反向代理服务器结合的轻量化的显示Disqus评论的方案。其比起其他的Disqus反向代理方案的优点是可以使用serverless的纯反代功能的服务器（例如免费的CloudflareWorkers），这样的话就不用担心自己的云服务器可能会换的问题。当然，这也限制了其功能，让它在基础模式下不能够发表评论。

其实使用起来很简单，遵循Github项目上的介绍，很快就能够完成。主要就是在网页中引入javascript脚本和CSS样式表，并初始化一个js类即可，从CDN引入资源如下。

1 2	<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/disqusjs@1.3/dist/disqusjs.css"> <script src="https://cdn.jsdelivr.net/npm/disqusjs@1.3/dist/disqus.js">script>

初始化的类的过程如下

<script>
function createDisqusJS() {
            window.dsqjs = new DisqusJS({
            shortname: '<%= theme.disqusjs.shortname %>',
            siteName: '<%= theme.disqusjs.sitename %>',
            identifier: '<%= page.path %>',
            url: '<%= page.permalink %>',
            title: '',
            api: '<%= theme.disqusjs.api %>',
            apikey: '<%= theme.disqusjs.apikey %>',
            nocomment: '<%= theme.disqusjs.nocomment %>',
            admin: '',
            adminLabel: ''
        });
}
createDisqusJS();
script>

但是我却碰到了许许多多的坑。

DisqusJS与InstantClick的兼容

在之前的博文中介绍过InstantClick这个基于PJAX机制的轻量Javascript框架，能够将网页变为单页式应用，减小跳转延迟。但是InstantClick的修改HTMLDOM的行为会导致一些加载上的问题。

例如，我将引入js和css资源的过程与执行初始化的过程都放在内部，理论上按顺序执行初始化应该在加载好js脚本之后，但是InstantClick在跳转到文章页面就先执行了初始化，而此时js脚本还未加载好，就会出现DisqusJS is undefined的错误。

解决这个错误倒也不难，只要知道了原因，就可以使用onload事件去执行初始化。因此我现在引入资源的过程如下，让css与js都异步加载。

1
2

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/disqusjs@1.3/dist/disqusjs.css" media="none" onload="if(media!='all')media='all'">
<script defer src="https://cdn.jsdelivr.net/npm/disqusjs@1.3/dist/disqus.js" onload="createDisqusJS()" disqusjs>script>

在古早版本中的DisqusJS中还有其他与PJAX机制兼容的问题，但是现在的版本已经对其进行了修复。

Disqus的identifiers机制

我在解决上了上面一个PJAX兼容性问题后，接着又碰到了下一个问题。我的评论区提示“ 当前Thread尚未创建。是否切换至完整Disqus模式”。我便去Github项目的文档里找有没有解释，当时看到这条issue #38:Thread初始化失败中作者回复：

Since DisqusJS is only a pure front-end project which doesn't requireany server, so create thread at Disqus requires user manually switchesto Disqus Mode.

意即，每个网页的Disqus评论是需要在Disqus的服务器中创建一个Thread来储存评论的，如果之前没有创建过，那么作为一个轻后端的项目在基础评论模式下DisqusJS是不会调用API去创建Thread的。

这话是没有问题的，但是问题在于我的Thread尚未创建的原因不是因为“这个网页”没有创建Thread，而是网页的identifier没有对应上，导致无法获取该网页的Thread（即使它存在）。

什么是identifiers呢？Disqus在JavaScriptconfiguration variables和Whatis a Disqusidentifier?中对Disqus如何区别不同的网页，即建立评论Thread与网页的对应关系的方法进行了介绍。总结而言，一个Thread真正unique的id，是它的threadid，而identifiers和urls都是用来对应到threadid的。如果我们保证identifier或url的唯一性，我们就可以通过identifier或url找到对应的唯一的评论Thread。如果identifiers不唯一（多个网页对应了一个identifier），那么就无法保证通过一个identifier对应一个网页。

在使用Disqus原生的js框架时，Disqus推荐在window.disqus_config变量中写明page.url、page.identifier与page.title，这样可以帮助Disqus给网页创建唯一的identifier。如果没有配置disqus_config，那么Disqus会使用网页的Url作为page.url，并以此来索引Threadid。

我的Disqus使用的问题在于，原来主题中在使用Disqus时是使用下面的两行javascript脚本来注册window.disqus_config，而使用window.location的问题在于，在localhost上和在有域名的服务器上浏览网页时会产生不同的location，这就导致一个网页无法对应唯一的identifier和url。

1 2	this.page.url = window.location.toString() this.page.identifier = window.location.pathname

我发现这个问题的方法，是发现使用Disqus APIthreads/list.json请求对应的identifier的thread列表时，会返回一堆thread而不是一个唯一的thread（原因就是identifier不唯一对应网页时，DisqusAPI会返回该shortname下的所有Thread），而DisqusJS认为这种情况下属于没有创建Thread。

知道了这个问题后，我去Disqus网站上把之前注册的网站删除（意味着删除了所有的Thread），重新建立我网站的评论系统。

你以为这样就能正常工作了吗？ Too young.

Disqus API的中文编码

我在此时使用下面的代码来建立identifier，使用url_for是因为想给作为identifier的path前加个斜杠/。然而我万万没想到的是，这个行为让我花了很多的时间去寻找问题所在。

1	identifier: '<% url_for(page.path) %>'

url_for的功能远不止给page.path加个斜杠，他还会对url进行编码，相当于再调用javascript的encodeURI函数，但是我当时并不知道这个问题，还以为是DisqusJS或浏览器在发GET请求时自动把url给编码了。

我来分析一下对encodeURI(page.path)会产生什么问题。

在使用完整评论模式（第一次使用会自动创建Thread）时，创建的thread的identifier是encodeURI(page.path)，然后Disqus的数据库里的identifier值就是encodeURI(page.path)，即Disqus不会在创建Thread时对identifier解码。

但是在使用DisqusAPI查询Thread列表时，他会对GET的参数进行URL解码，即相当于调用decodeURI，于是在与数据库里的identifier匹配时，它拿decodeURI(encodeURI(page.path))(也就是page.path)和数据库进行匹配，而数据库里只存了encodeURI(page.path)，那么自然匹配是失败的，然后threads/list.jsonAPI就会返回所有的Thread。

经过我的测试，如果你的GET方法的参数为thread=$IDENT，DisqusAPI服务器会首先调用ident:$IDE = decodeURIComponent($IDENT)，然后会在数据库里查询$IDE，但是像我说的那种情况，在数据库里的键值为encodeURI($IDE)，自然是查不到的。

令我疑惑的是，Disqus在自己的网站上I'mreceiving the message "We were unable to loadDisqus."说自己不支持非ascii码作为url，但是我即使直接通过curl请求未编码的中文，也不存在问题。

所以我现在不会主动对path进行编码，而是靠浏览器帮我编码传输。

当然，这里有一点很关键，我们不会主动对page.path进行编码，而是靠浏览器帮我们进行了GET参数的自动编码。而不同操作系统的不同浏览器对GET参数自动编码时采取的方案是不同的，虽然说现在主流浏览器都是采取%符号+utf-8编码，但是也有IE浏览器是使用系统编码，详情可以参考关于URL编码，因此依赖浏览器还是不稳定的，理论上DisqusJS应该自己对GET的参数进行encodeURIComponent后再发送请求。

关于encode这点，我已经给Disqus JS提了PullRequest并合并进master了。

现在，理论上你即使用IE浏览器也可以看到评论框的基本模式（没有安全补丁的xp系统由于SSL证书问题可能打不开网页，IE8之前的浏览器也不太行）。

gulp-babel对展开语法(Spread syntax)的错误转换

当我fork了DisqusJS的源码修改GET行为的参数编码时，我在本地测试上遇到了问题。该项目使用gulp生成部署时代码，使用gulp-babel精简javascript代码。我使用gulp-babel对整个javascript脚本进行精简后得到部署环境中的js文件，然后在本地服务器运行并用浏览器测试时，我发现插件不能正常工作了。奇怪的是，当不用gulp-babel精简时的原脚本是可以正常运行的。

那么基本可以确定是gulp-babel让脚本转换时出了问题，经过排查，我发现问题出在将HTMLCollection转换为Array的过程中。原代码是[...aTag]，其中aTag为一个HTMLCollection，这里用了展开语法(Spreadsyntax)，可以将可迭代的对象展开为数组，是ES6标准后来提出的语法。观察生成后的js文件，gulp-babel将对应的代码转换为了[].concat(aTag)，如果要达到类似的效果，concat的参数只能是数组，而不会把可迭代对象展开，[].concat(aTag)的写法会把aTag作为一个Object追加为数组的元素。因此这两者不是等价的。

那么，我们应该使用什么来达到这一行为而且不会被gulp改变语义呢？我们目前的需求是将HTMLCollection转换为Array，而HTMLCollection为什么可以转换为数组？首先，它是一个array-like的对象，更详细地说，它有length属性，且可以用数字作索引，那么这样的对象就有转换为Array的条件。另外，HTMLCollection在ES6标准中也成为了一个可迭代对象，而可迭代对象也是可以通过一些方法转换为Array的。

下表是我总结的三种可以将其转换为数组的方法，其中Array.prototype.slice.call支持的参数是array-like的对象，且支持的浏览器最为广泛，我不知道有什么浏览器是不支持它的。Array.from支持array-like的对象和可迭代对象，功能最丰富，但是也是ES6标准开始才有的方法。Spreadsyntax也是ES6标准开始的语法，且由于会被gulp-babel错误转换直接否决。

由于我们这里的需求只是将HTMLCollection转换为Array，因此选择支持最广泛也没什么缺点(可能代码长了点)的Array.prototype.slice.call即可。

Parameter	Array.prototype.slice.call	Array.from	Spread Syntax
Array-like objects with a lengthproperty and indexed elements	Yes	Yes	No
Iterable objects	No	Yes	Yes

当然，gulp-babel有插件支持对Spread syntax的转换， @babel/plugin-transform-spread可以完成该功能。

One More Thing

前面我们提到了IE浏览器在进行GET查询时对参数的编码行为和其他浏览器不同，那么我们不妨再谈一谈对IE浏览器兼容做的工作。

众所周知，IE11是不兼容ES6标准的，因此如果js代码中有ES6标准的用法都是不能直接运行于IE浏览器的，故我们如果要考虑IE浏览器，用到的ES6标准中的语法和新接口都需要使用polyfill的方法来进行兼容。

Disqus JS用到了ES6标准中的fetchAPI和Promise，这两者都是无法在IE中运行的。在DisqusJS的readme也提到了需要用polyfill的实现来代替。那么，如何判断当前浏览器是IE然后动态地加载polyfill代码呢？

我一开始使用对Request Header进行判断的检测方法，但是随着我对Featuredetection的进一步了解，我知道了如果是想实现跨浏览器的支持，那么Featuredetection比针对浏览器版本的检测更加有效和全面。例如，我当初只检测了IE，但如果用户用的是另一个也不支持ES6标准的古老浏览器呢？如果用户切换了Header呢？

针对浏览器的版本判断，总是需要考虑更多的内容，需要想得更加全面，也需要精确地了解哪个版本的浏览器不支持什么标准的什么特性，而这是极其消耗精力的。如果使用Featuredetection，我们能够花更少的精力就做到跨浏览器一致性。

例如，我只需要使用下面的代码就能简单地判断浏览器是否支持fetch特性。同样的，不同的特性都可以进行判断而决定是否对某一功能使用polyfill。这样能够做更精细而全面的跨浏览器一致性行为。

if (window.fetch) {
// use fetch
}
else {
// use polyfill
}

时光飞逝，Windows XP于2001年发售，截止至今已经19年了，Windows7是2009年发售的。不算Vista，至少2009年后基本没有多少新增个人WindowsXP的用户了。理论上，一台PC用了11年还能不换零件坚持用简直是奇迹。（其实我家里还有两台WindowsXP的PC）

根据statcounter的统计数据，全球范围内截止至2020年7月，Windows在桌面操作系统的市场份额是77.68%，其中XP又占Windows阵营中的0.82%（在中国是2.87%）,也就是说WindowsXP占所有桌面操作系统的0.64%，不知道其中有没有包括众多的工业用机。

不过我想，从人群划分来看，应该几乎没有使用WindowsXP的用户会点击到这个页面吧。