如何在程序中嵌入有大量字符串的 HashMap

[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 https://maskray.me/blog/2021-10-31-relative-relocations-and-relr

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)	_	紧凑	快

[g-plane]

一般来说，[&'static str; N] 中大概有多少个元素时，需要考虑优化？

[quininer]

体积和编译时间的开销其实都很线性。体积开销可以直接算出来的，N=1024 就会额外占 40K。至于编译时间，测试了一下一万个以内还不算明显，超过一万个就会明显感觉编译变慢。

经验上的话，感觉 N>1024 就可以考虑优化一下。