动机
昨天在参加 RubyKaigi 的时候顺便瞄到了 st.c 的实现，然后让我回想起来，现在的 Ruby 的 Hash 实现主要来自于 Vladimir Makarov 在 2016 年实现的精心调优的 open-addressing 实现的版本。我突然想起 Google absl 实现里有个 Swiss Tables 实现吊打了 C++ 标准库的实现，而 Rust 的标准库实现基于的 hashbrown 也是基于相同的原理。我就在思考时隔十年我们能不能把 SwissTables 相关的算法移植到 Ruby 上进一步提升 Ruby 处理 Hash 类型的性能，要知道 Hash 类型是 Ruby 中调用极其频繁的类型，它替代了很多其它语言中 struct 的功能，因此性能提升能带来很直观的收益。
尝试
直接的移植后发现性能不升反降了，这和 Ruby 中 Hash 的用法很有关系。Ruby 中非常多的 Hash 对象非常小，而 Makarov 2016 年的实现对此做了非常细腻的优化。
于是我的做法转变成了，保留 Ruby 中原先对不同大小 Hash 的分层存储，从 Swiss Tables 对 control bit 更好的对超标量 / 向量化的支持和 H2 短哈希更好的缓存命中这两个角度进一步进行优化，只针对大的 Hash 对象（容量 >= 64）的情况进行处理。
设计
1. 三数组布局
| array | width | role |
|---|---|---|
entries[] |
16B (以前为 24B) | 以插入顺序记录 (key, record) 的日志 |
hashes[] |
每 slot 4B | 与之并行的截断 32 位哈希数组（也编码删除标记） |
bins[] |
自适应 1 / 2 / 4 / 8B | 基于哈希的索引数组，存放指向 entries[] 的索引 |
ctrl[] |
每 slot 1B |
H2（哈希的高 7 位）或 EMPTY (0xff) / DELETED (0xfe)
|
entries[] 和 hashes[] 长度相同并由相同索引寻址，因此迭代和 slot 重用保持简单。ctrl[] 是快速拒绝过滤器，和 bins[] 并列；只有当某个 ctrl 字节与 H2 匹配时，我们才会加载（现在更小的）entry 和并行哈希以确认匹配。对 ctrl[] 在 uint64_t 读取上完成，这本质上是一种 SWAR 优化。
2. 紧凑的 st_table_entry
修改前：
struct st_table_entry {
st_hash_t hash; /* 8 B */
st_data_t key; /* 8 B */
st_data_t record; /* 8 B */
}; /* 24 B */
修改后：
struct st_table_entry {
st_data_t key; /* 8 B */
st_data_t record; /* 8 B */
}; /* 16 B */
哈希移入 tab->hashes[i]，由于大多数情况可以依赖 H2 进行匹配。因此这样我们可以进一步提升 cacheline 的命中效率，从而提高 CPU L1 的命中率。
3. 新的哈希函数
仅存储低 32 位哈希意味着我们不能再从原始 unsigned long 哈希的高位 7 位读取 H2，而这是 SwissTables 原先设计所采用的做法。naive 的实现是在每次重建/重哈希/st_shift/st_general_foreach 中重新计算完整 64 位哈希以保证正确性，但会严重损害插入和重建性能 —— 尤其是对于类似 string 这样的变长类型的性能损害很大。
解决方法是从截断的 32 位哈希的一个不同位段推导 H2，该位段与用于选取 bin 的位段不重叠：
/* bin index: low `bin_power` bits, masked by `bins_mask(tab)` */
hash_bin(uint32_t h, st_table *tab) { return h & bins_mask(tab); }
/* H2: bits 25..31 of the same 32-bit hash, never overlaps with */
/* the bin index because bin_power is capped well under 25 in */
/* practice. */
static inline unsigned char
st_swiss_h2(st_hash_t hash) {
return (unsigned char)((hash >> 25) & 0x7f);
}
这使得存储的 uint32_t 是自包含的：每次探测都能从同一字中读取 bin 索引和 H2 字节，无需调用 do_hash()，重建/重哈希/移位/foreach 全部使用 ST_HASH_AT_IDX(tab, i) 而不是重新计算。
截断带来的另外两个细节：
-
normalize_hash_value()已更新，以确保0xFFFFFFFF（32 位哈希 slot 的墓碑标记）永远不会与真实哈希值冲突——如果截断结果落在该保留值上我们会进行跳变（bump）。在未启用ST_USE_SWISS_BINS编译的平台上保留 64 位的保留值。 -
MARK_ENTRY_DELETED/DELETED_ENTRY_P宏新增了 table 参数，以便读取/写入并行的哈希 slot。
4. 在 H2 匹配时进行 prefetch
当 SWAR 在控制组中找到候选的 H2 匹配时，下一步是加载匹配的 st_table_entry 的哈希。我们在 find_table_entry_ind / find_table_bin_ind / find_table_bin_ptr_and_reserve 中在检测到匹配后立即对两者发出 __builtin_prefetch。在以查找为主的工作负载上，这能掩盖 SWAR 快速过滤器本会暴露的 CPU L2 缓存延迟。
与 master 的结果比较
两个二进制均来自相同代码树（master = 42b3cdc51a，swiss = 3c0446847f），相同编译器，相同编译选项。每个脚本运行 5 次，使用 --disable-gems，报告最佳结果。内存为 macOS arm64（M4 Max）上 /usr/bin/time -l 的最大常驻集大小（maximum resident set size）。
吞吐量（时间越低越好）
| benchmark | master (s) | swiss (s) | speedup |
|---|---|---|---|
| aref_int_large | 0.8352 | 0.6862 | +17.8 % |
| aref_str_large | 0.9915 | 0.8406 | +15.2 % |
| aref_miss_large | 1.0803 | 0.7896 | +26.9 % |
| aref_mix_50 | 1.0337 | 0.8201 | +20.7 % |
| insert_grow | 0.1138 | 0.1105 | +2.9 % |
| churn (mixed RW) | 0.0321 | 0.0304 | +5.5 % |
| iterate | 0.0566 | 0.0565 | ±0.1 % |
查找是主要的收益点——成功查找（+15 % … +20 %）和未命中（+27 %）均有提升，后者的原因是缺失的 key 现在能在第一个 SWAR 组立即短路，无需加载 entry/bin。插入和混合负载略有提速，因为重建不再调用 do_hash。迭代不受影响（它不需要访问 bins 或 ctrl）。
内存
| benchmark | master (MB) | swiss (MB) | delta |
|---|---|---|---|
| insert_grow | 66.62 | 60.44 | −9.3 % |
| aref_str_large | 15.27 | 15.23 | −0.3 % |
| aref_mix_50 | 16.64 | 16.61 | −0.2 % |
| churn | 13.19 | 13.03 | −1.2 % |
每表内存（通过 ObjectSpace.memsize_of，在多个哈希上求和）：
| workload | master | swiss | delta |
|---|---|---|---|
| 2 000 hashes × 200 entries | 14.66 MB | 12.11 MB | −17.4 % |
| 1 hash × 100 000 entries | 4.19 MB | 3.28 MB | −21.9 % |
2000 hashes × 200 entries 模拟了常见的 Rails 负载，这可以节省 ~17.4% 的 Hash 内存占用。
这两种内存视图一致：任何保留大量存活条目的工作负载（无论是一个大哈希还是许多小哈希）都会因条目从 24B → 16B 的变化以及每槽 1B 的 ctrl[] / 4B 的 hashes[] 配对而显著减少内存，因为它们合计（每槽 5B）仍小于在 entries[] 中每槽节省的 8 B。表的每表开销在小于约 64 条目时大致保持不变；Swiss 路径仅在 entry_power ≥ 6（表容量 ≥ 64）时启用。