Unicode 标识符

Unicode 标准附件 #31 的实现，用于确定哪些 char 值在编程语言标识符中是有效的。

此 crate 是旧版 unicode-xid crate 的优化实现。它使用更少的静态存储，并且能够以更高的性能对 ASCII 和非 ASCII 码点进行分类，比 unicode-xid 快 6 倍。

性能对比

下表展示了五种 Unicode 标识符实现之间的对比。

• unicode-ident 即本 crate；
• unicode-xid 是由 "unicode-rs" 组织维护的广泛使用的 crate；
• ucd-trie 和 fst 是 ucd-generate 工具支持的两种数据结构；
• roaring 是 Roaring 位图的 Rust 实现。

“静态存储”列显示了 crate 烘焙到二进制文件中的 static 表的总大小，以千字节为单位。

其余列显示评估单个 char 是否具有 XID_Start 或 XID_Continue Unicode 属性的每次调用成本，比较输入数据中 ASCII 与非 ASCII 码点的不同比例。

	静态存储	0% 非 ASCII	1%	10%	100% 非 ASCII
unicode-ident	10.3 K	0.41 ns	0.44 ns	0.44 ns	0.93 ns
unicode-xid	12.0 K	2.43 ns	2.50 ns	2.85 ns	8.65 ns
ucd-trie	10.4 K	1.28 ns	1.25 ns	1.20 ns	1.97 ns
fst	144 K	50.9 ns	51.0 ns	48.5 ns	26.7 ns
roaring	66.1 K	4.28 ns	4.22 ns	4.25 ns	4.61 ns

基准测试的源代码位于此仓库的 bench 目录中，可以通过运行 cargo criterion 重复测试。

数据结构对比

unicode-xid

他们使用字符范围的排序数组，并通过二分查找来确定给定字符是否落在这些范围之一内。

static XID_Continue_table: [(char, char); 763] = [
    ('\u{30}', '\u{39}'),  // 0-9
    ('\u{41}', '\u{5a}'),  // A-Z
    …
    ('\u{e0100}', '\u{e01ef}'),
];

此数据结构使用的静态存储会随着 Unicode 中标识符码点连续范围的数量而扩展。每个表项占用 8 字节，因为它由一对 32 位 char 值组成。

在 Unicode 码点空间的某些范围内，这种表示方式相当稀疏——有些范围内，数万个相邻的码点都是有效的标识符字符。而在其他地方，这种表示方式则效率低下。像 µ（U+00B5）这样被非标识符码点包围的字符，在表中会占用 64 位，而在密集位图中只需 1 位。

在具有 64 字节缓存行的系统上，对表进行二分查找平均会触及 7 个缓存行。每个缓存行只能容纳 8 个表项。此外，二分查找过程中执行的分支对于分支预测器来说可能大多是不可预测的。

总体而言，对于非 ASCII 输入，该 crate 的速度大约是最快 crate 的 1/6。

一个潜在的改进方向是更紧凑地打包表项。Rust 的 char 类型是一个填充至 32 位的 21 位整数，这意味着每个表项有 22 位的空间被浪费，总计达 3.9 K。相反，它们可以将每个表项压缩到 6 字节，省去部分填充，从而节省 25% 的空间。通过一些巧妙的设计，或许可以通过存储起始字符和长度（而非起始字符和结束字符）将其压缩到 5 字节甚至 4 字节。我预计性能不会有太大提升，但这可能是所有库中空间效率最高的，只需约 7 K 的存储空间。

ucd-trie

其数据结构是一种专门为 Unicode 码点定制的压缩字典树集合。该设计归功于 Raph Levien，相关内容见于 rust-lang/rust#33098。

pub struct TrieSet {
    tree1_level1: &'static [u64; 32],
    tree2_level1: &'static [u8; 992],
    tree2_level2: &'static [u64],
    tree3_level1: &'static [u8; 256],
    tree3_level2: &'static [u8],
    tree3_level3: &'static [u64],
}

它使用字典树（trie）来表示码点集合，以实现前缀压缩。字典树的终态嵌入在叶子节点或“块”中，每个块是一个 64 位整数。整数的每个位位置对应于特定码点是否在集合中。这些块不仅是字典树终态的紧凑表示，也是一种后缀压缩形式。特别是，如果多个包含 64 个连续码点的范围具有相同的 Unicode 属性，那么它们在字典树的最终层都映射到同一个块。

由于是为 Unicode 码点量身定制，此字典树分为三个不相交的集合：tree1、tree2、tree3。第一个集合对应码点范围 [0, 0x800)，第二个对应 [0x800, 0x10000)，第三个对应 [0x10000, 0x110000)。这些分区分别对应于 1 字节或 2 字节 UTF-8 编码的码点、3 字节 UTF-8 编码的码点以及 4 字节 UTF-8 编码的码点空间。

在此数据结构中进行查找比二分查找高效得多。根据访问的字典树分区不同，一次查找只需访问 1、2 或 3 个缓存行。

该 crate 的一个可能性能改进是提供一种基于 UTF-8 编码字符串进行查询的方式，返回字符串中第一个字符对应的 Unicode 属性。如果没有这样的 API，调用者就需要将其 UTF-8 编码的输入数据标记化为 char，将 char 传递给 ucd-trie，而 ucd-trie 为了进行字典树遍历，又需要将其转换回变长表示，这相当于做了无用功。

fst

使用 有限状态转换器（finite state transducer）。这种表示方式内置于 ucd-generate 中，但据我所知，它相比 ucd-trie 表示方式没有任何优势。特别是 ucd-trie 针对存储 Unicode 属性进行了优化，而 fst 并非如此。

据我观察，在这个使用场景下，fst 相对于 ucd-trie 具有更大的体积和更慢的查找速度，主要原因是它没有专门针对 char 中只有 21 位是有意义的这一事实进行优化。其结构中存在一些密集数组，包含了许多永远不可能被使用的大范围。

roaring

该 crate 是 Roaring Bitmap 的纯 Rust 实现，Roaring Bitmap 是一种旨在存储 32 位无符号整数集合的数据结构。

Roaring 位图是一种压缩位图，其性能通常优于传统的压缩位图（如 WAH、EWAH 或 Concise）。在某些情况下，它们的速度可能快数百倍，并且通常提供更好的压缩率。

在这个使用场景中，其性能具有一定的竞争力，但仍明显慢于针对 Unicode 优化的 crate。同时，其压缩率也显著更差，数据结构所需的存储空间是前者的 6 倍。

我还对 croaring crate 进行了基准测试，它是 Roaring Bitmap C 参考实现的 FFI 包装器。这个 crate 始终比纯 Rust 的 roaring 慢约 15%，这可能仅仅是 FFI 开销导致的。我没有进行进一步调查。

unicode-ident

该 crate 与 ucd-trie 库最为相似，它基于存储在字典树叶子节点的位图，实现了前缀压缩和后缀压缩。

主要区别如下：

• 使用单个 2 层字典树，而非 3 个不同深度的不相交分区。
• 使用更大的块：512 位，而非 64 位。
• 同时对 XID_Start 和 XID_Continue 属性进行压缩，而不是在两者之间复制相同的字典树叶子块。

下图以行优先顺序展示了未压缩形式的 XID_Start 和 XID_Continue Unicode 布尔属性：

XID_Start	XID_Continue

未压缩时，这些属性需要 140 KB 的存储空间，这超出了合理范围。然而，如您所见，这两个位图之间以及各行之间存在高度的相似性，这非常有利于压缩。

该 crate 将上述位图的一个 512 位“行”存储在字典树的叶子层，并使用一个额外的层级来索引叶子节点。事实证明，两个位图共有 124 个唯一的 512 位块，因此 7 位就足以对它们进行索引。

选择 512 位的块大小是为了最小化数据结构的总大小。更小的块（如 256 位或 128 位）可以实现更好的去重，但需要更大的索引。更大的块会增加叶子位图的冗余。512 位块在索引和叶子位图的总大小方面是最优的。

实际上，由于只有 124 个唯一块，我们可以使用一个 8 位索引，并利用一个空闲位在半块级别进行索引。通过消除任何块的后半部分与任何其他块的前半部分之间的冗余，这额外实现了 8.5% 的压缩率。请注意，这与使用一半大小的块不同，因为它不需要增加字典树第一层的大小。

与二分查找或 ucd-trie crate 相比，在此数据结构中执行查找是直线代码，无需分支。

is_xid_start:
	mov eax, edi
	mov ecx, offset unicode_ident::ZERO
	shr eax, 9
	cmp edi, 210432
	lea rax, [rax + unicode_ident::tables::TRIE_START]
	cmovb rcx, rax
	movzx eax, byte ptr [rcx]
	mov ecx, 1539
	bextr ecx, edi, ecx
	and edi, 7
	shl eax, 5
	movzx eax, byte ptr [rax + rcx + unicode_ident::tables::LEAF]
	bt eax, edi
	setb al
	ret

许可协议

本 crate 对 Unicode 字符数据库的使用受 Unicode 许可协议 的约束。

本 crate 内所有未使用 Unicode 字符数据库作为输入生成的知识产权，均根据您的选择，采用 Apache 许可协议 2.0 版 或 MIT 许可协议 进行许可。

生成的文件包含源自 Unicode 字符数据库的表格数据，以及来自 crate 原始源代码内容的知识产权。当涉及这些生成文件时，您必须同时遵守 Unicode 许可协议以及 Apache 许可协议或 MIT 许可协议中的任意一项条款。

除非您明确另有说明，否则您依据 Apache-2.0 许可协议定义的、有意提交并纳入本 crate 的任何贡献，均应按上述方式许可，不附加任何额外条款或条件。