登录如何在程序中嵌入有大量字符串的 HashMap
作者：Rstack 团队 - quininer
当需要在应用程序中静态的嵌入大量可查询的数据时，你会怎么做？
常见的做法是直接嵌入 JSON 数据，然后在初始访问时做解析：
static MAP: LazyLock<HashMap<&str, usize>> =
LazyLock::new(|| serde_json::from_str(include_str!("data.json")).unwrap());
缺点显而易见：
- 需要在初次访问时阻塞调用
- 需要分配永不释放的常驻内存
- 还需要引入复杂的 json parser
我们在这里介绍一些技术，构造完全静态、高效的 Map：
- 即不需要初始化、不需要解析、不需要内存分配
- 同时尽可能保持快速的编译性能和极小的体积占用
高效的静态可查询 Map
MPHF：全称 Minimal Perfect Hash Function，是构造高效静态 Map 的常用技术
通常我们认为 hashmap 的时间复杂度 O(1)，额外空间开销为 0，但这仅限于所有 keys 的 hash 不发生冲突的情况。
当发生冲突时，通常冲突的 key 将会被分配到同一个 bucket 中，
这导致时间复杂度可能回落到 O(N)，并且 bucket 总是引入额外的空间占用，不能保证空间紧凑。
而 mphf 技术可以使得 hashmap 时间、空间总处在完美状态。
最坏时间复杂度 O(1)，不存在空槽，空间布局紧凑。
最简单的 MPHF
mphf 定义上是一种完全单射的 hash function，可以将指定的 key 集合一对一映射到同等大小的值域。
此结构最简单的 mphf 构造方法是：
f(x) = h(seed, x) mod n- 不停轮换 hash function 所使用的的 seed
- 直到有合适的
seed可以使得所有 x 产生的 hash mod n 无冲突
但对于大量 keys 的情况，期待有单个 seed 能够使得 hash 无冲突的映射所有 x 是不现实的
- 即使高质量的 hash function 存在这个可能性，也很难在合理时间内搜索到合适的 seed
更实用的 MPHF 构造
对于大量 keys 的情况，常见的处理和传统 hashmap 颇为类似
- 对 keys 分 bucket 处理，按 bucket 去冲突
- 每个 bucket 记录一个值，称为 displace
- 当 bucket 发生冲突时，修改 displace 值
- 调整该 bucket 内 keys 具体映射到的 index
- 重复直到所有 bucket 无冲突
我们在这里简单描述几种 MPHF 构造：FCH、CDH、PtHash，三者大同小异，主要区别是使用 displace 的方式不同
| hash | 特点 | |
|---|---|---|
| FCH | f(x) = (h(x) + d[i]) mod n |
按数字调整偏移。这导致调整范围过小，很难找到合适的 displace 值。 |
| CDH | f(x) = φσ[g(x)](x) mod n |
使用独立的 hash 值调整偏移。效果很好，但比起其他方案要多进行一次 hash （或更长的 hash 输出）。 |
| PtHash | f(x) = (h(x) ⊕ h'(k[i])) mod n |
使用数字k做 xor。兼具以上两者的好处，调整范围足够大，也不需要进行较重的 hash。 |
更先进的 MHPF 构造：PtrHash
Ptr-hash 在 PtHash 基础上有许多改进，其中最有趣的是 bucket 调整使用了 cuckoo hash 策略。
Cuckoo hash 是一种经典的 hashmap 去冲突方案
- 当 key 发生冲突时，不像典型的 hashmap 使用 bucket 同时容纳多个 key
- 而是新 key 会将旧 key 踢出，旧 key 使用新的 hash 函数重新分配 index
- 如果旧 key 重新分配 index 时发生冲突，重复以上步骤
- 其过程神似杜鹃鸠占雀巢，故称为 Cuckoo hash
高效的去冲突策略使得 ptr-hash 可以使用质量更低的 hash 算法，以及为每个 displace 仅使用 1byte，相比传统方案时间、空间开销更小。
Cuckoo hash 策略的好处
踢出旧 key 重新安排听起来非常低效，为什么这是个好的构造策略？
其基本思路是：
- 在合适的负载下，很大可能存在可以容纳所有 keys 的排布方式
- 但传统 hashmap 中，旧 bucket 的位置一旦产生就不会变更
- 这很可能不是最佳的排布方式，尤其是早期插入的 bucket 的 displace 基本是 0
- 而 Cuckoo hash 的踢出策略，可以给予旧 bucket 重新调整排布的机会
面临体积膨胀问题…
MPHF 解决了静态数据的查询问题，但… 如果我们写出以下类似以下的代码
static NAMES: &[&str] = &[
"alice", "bob", // ...
];
当我们朴素的使用 MPHF 来索引 &[&str] 等数据，会发现它编译过慢、产物体积过大，
问题出在哪里呢？
&[&str] 膨胀
&str 开销
如果对 Rust 的内存布局有一定了解，很容易注意到 &str 其本质是 (*const u8, usize)。
这意味着 &[&str] 中，每个字符串要有 16byte 的额外体积占用。
对于短字符串而言，其索引的二进制体积开销甚至要大于其字符串本身。
但这还不是全部。
relocation 开销
我们构造一个使用大量 &[&str] 的程序，打印 section headers 会发现
9 .rela.dyn 00499248 0000000000000fd8 DATA
11 .rodata 00419c10 000000000049a240 DATA
24 .data.rel.ro 00496b80 00000000009042a8 DATA
它最大的 section 并不是用于存放不变数据的 .rodata，而是 .rela.dyn 和 .data.rel.ro！
回想一下我们定义的全局变量 NAMES，这是一个 &str 的列表，里面存放的是指向字符串的指针。
但我们的 so 在被加载前，它的基地址尚未确定，编译器怎么能产生一个还不确定的指针列表呢？
答案是 dynamic linker 需要在 so 被加载时对数据进行调整，该过程被称为 relocation。
- 编译时，产生
.data.rel.ro段和.rela.dyn段- 其中
.data.rel.ro存放的是仅在 relocation 过程中可变的 readonly data - 而
.rela.dyn存放的是需要 relocation 的数据的 metadata
- 其中
- so 被加载时，dynamic linker 遍历整个
.rela.dyn段对.data.rel.ro段（及其他）进行调整
typedef struct {
Elf64_Addr r_offset; // Address
Elf64_Xword r_info; // 32-bit relocation type; 32-bit symbol index
Elf64_Sxword r_addend; // Addend
} Elf64_Rela;
这意味着 &[&str] 中每个字符串还额外有 24byte 的体积开销，并且会影响整个程序的启动性能！
ELF 新的 relocation 方案 RELR 能够极大改善该问题，可以做到每个字符串仅 2bit 的体积开销 see maskray.me/blog/2021-1…
Mac 和 Windows 上的 relocation 占用要比 ELF 的 RELA 方案稍好，但不如新方案 RELR
打包字符串和手动索引
Position index
既然编译器产生的字符串索引有那么多开销，那么我们可以打包字符串并且手动建立索引。
一个简单方案是拼接所有字符串，然后使用 string end position 作为索引
const STRINGS: &str = include_str!("string.bin");
const INDEX: &[u32] = [
4, 10, 15, // ...
];
fn get(index: usize) -> Option<&'static str> {
let end = INDEX.get(index)? as usize;
let start = index.checked_sub(1)
.map(|i| INDEX[i])
.unwrap_or_default() as usize;
Some(&STRINGS[start..end])
}
这使得每个字符串索引开销仅有 4byte，并且完全消除了 relocation 开销。
- 所有内容均处于
.rodata中，可以直接通过相对地址访问。
访问过程仅涉及简单的运算，性能没有太大牺牲。
String pool
Position index 很紧凑，我们还可以使用 Elias-Fano 技术使得它更紧凑。 但简单的拼接字符串会使得编译器无法合并重复的字符串，导致它在特定场景下反而有所劣化。
例如以下代码，可以观察到 S[0]、S[1] 的两个字符串地址完全相同，证明编译器对它们进行了合并。
static S: &[&str] = &[
"alice", "alice"
];
assert_eq!(S[0].as_ptr(), S[1].as_ptr());
我们可以使用 string pool 自行对字符串进行合并，来避免这一缺点。
#[derive(Default)]
struct StrPool<'s> {
pool: String,
map: HashMap<&'s str, u32>,
}
impl<'s> StrPool<'s> {
pub fn insert(&mut self, s: &'s str) -> u32 {
*self.map.entry(s).or_insert_with(|| {
let offset = self.pool.len();
self.pool.push_str(&s);
let len: u8 = (self.pool.len() - offset).try_into().unwrap();
let offset: u32 = offset.try_into().unwrap();
if offset > (1 << 24) {
panic!("string too large");
}
offset | (u32::from(len) << 24)
})
}
}
作为节省空间的技巧，我们可以将 offset 和 length 通过 bitpack 打包到单个 u32 中。 使得它和 position index 一样，每个字符串的索引开销仅为 4byte，但代价是单个字符串的最大长度被限制为 255。
编译速度
作为打包字符串的另一个好处，这也极大的改善了编译时间和内存使用。
朴素的&[&str]方案中 rustc 耗时极大的三个阶段会在字符串打包后减少至可忽略。
before:
time: 1.414; rss: 258MB -> 761MB ( +503MB) type_check_crate
time: 2.325; rss: 712MB -> 651MB ( -61MB) LLVM_passes
time: 2.217; rss: 476MB -> 597MB ( +121MB) finish_ongoing_codegen
after:
time: 0.022; rss: 107MB -> 142MB ( +35MB) type_check_crate
time: 0.100; rss: 194MB -> 183MB ( -11MB) LLVM_passes
time: 0.098; rss: 159MB -> 177MB ( +18MB) finish_ongoing_codegen
主要是避免让编译器产生大量对象、以及避免对其进行不必要的优化。
总结
嵌入静态 HashMap 看起來很简单，但 naive 的方案总有各种代价需要牺牲。 我们介绍了 MPHF 技术和字符串打包技术，可以在不牺牲任何方面的情况下实现该功能。
| 启动耗时 | 查询性能 | 内存占用 | 体积占用 | 编译速度 | |
|---|---|---|---|---|---|
| lazy + json parse | O(N) | Θ(1) | O(N) | 紧凑 | 快 |
mphf + &[&str]
|
_ | O(1) | _ | 膨胀 | 慢 |
| mphf + string pack | _ | O(1) | _ | 紧凑 | 快 |
