Unicode标识符

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

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

性能比较

以下表格显示了五种Unicode标识符实现之间的比较。

• unicode-ident 是此crate；
• unicode-xid 是由 "unicode-rs" org 运行的广泛使用的crate；
• ucd-trie 和 fst 是由 ucd-generate 工具支持的两种数据结构；
• roaring 是Roaring位图的Rust实现。

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

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

基准测试的源代码位于本仓库的 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输入相比，该库最终比最快的库慢约10倍。

一个潜在的改进是更紧凑地打包表条目。Rust的 char 类型是一个21位的整数，填充到32位，这意味着每个表条目都持有22位未使用的空间，总共3.9 K。它们可以将每个表条目压缩到6字节，省略一些填充，从而在空间使用上提高25%。通过一些巧妙的方法，可能可以将它们压缩到5字节甚至4字节，通过存储低字符和一个范围，而不是低字符和高字符。我不期望性能会有很大改善，但这可能是所有库中最节省空间的，只需要大约7 K来存储。

ucd-trie

它们的数据结构是一个针对Unicode代码点特别定制的压缩 trie 集合。该设计归功于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来表示代码点集，以实现前缀压缩。trie的最终状态嵌入在叶子或“块”中，其中每个块是一个64位整数。整数的每个位位置对应于特定的代码点是否在集合中。这些块不仅是trie最终状态的紧凑表示，也是一种后缀压缩形式。特别是，如果多个连续的64个代码点的范围具有相同的Unicode属性，则它们都映射到trie最终级别的同一块。

鉴于针对Unicode代码点进行了定制，此trie被划分为三个不相交的集合：tree1、tree2、tree3。第一个集合对应于代码点 [0, 0x800)，第二个 [0x800, 0x10000)，第三个 [0x10000, 0x110000)。这些分区方便地对应于1或2字节UTF-8编码的代码点空间、3字节UTF-8编码的代码点空间和4字节UTF-8编码的代码点空间。

在此数据结构中的查找比二分搜索效率高得多。根据访问的trie分区，查找可能触及1、2或3个缓存行。

可能的一种性能改进方法是使这个包能够通过UTF-8编码的字符串进行查询，返回字符串中第一个字符对应的Unicode属性。如果没有这样的API，调用者需要将UTF-8编码的输入数据分词成char，然后将char传递给ucd-trie，而ucd-trie将撤销这项工作，将其转换回 trie 遍历的变长表示。

fst

使用有限状态转换器。这种表示在ucd-generate中内置，但我不知道它与ucd-trie表示相比有什么优势。特别是，ucd-trie针对存储Unicode属性进行了优化，而fst则没有。

据我所知，与ucd-trie相比，fst在处理大型数据集时的主要问题是它没有针对只有21位中的32位是有意义的这一事实进行优化。在结构中存在一些密集的数组，它们可能永远不会被使用。

roaring

这个包是Roaring Bitmap的纯Rust实现，这是一种专门用于存储32位无符号整数集合的数据结构。

Roaring位图是压缩位图，通常比WAH、EWAH或Concise等传统压缩位图性能更好。在某些情况下，它们可以快数百倍，并且通常提供显著的压缩。

在这个用例中，性能相当有竞争力，但仍然比Unicode优化的包慢得多。同时，压缩效果显著更差，数据结构需要6倍的空间来存储。

我还测试了croaring包，这是一个围绕C语言参考实现Roaring Bitmap的FFI包装器。这个包比纯Rust的roaring慢了大约15%，这可能是FFI开销造成的。我没有进一步调查。

unicode-ident

这个包与ucd-trie库最相似，因为它基于存储在trie表示叶子中的位图，实现了前缀压缩和后缀压缩。

主要区别是

• 使用单级2级trie，而不是3个深度不同的不相交分区。
• 使用更大的块：512位而不是64位。
• 同时压缩XID_Start和XID_Continue属性，而不是在两个中重复相同的trie叶子块。

以下图显示了未压缩的XID_Start和XID_Continue Unicode布尔属性，以行为主序排列

XID_Start	XID_Continue

未压缩，这些属性需要140 K存储空间，这超出了合理的范围。然而，正如您所看到的，这两个位图以及行之间存在很大的相似性，这有利于压缩。

这个包在trie的叶子级别存储上述位图的512位“行”，并在叶子之外的单级中索引。结果，在两个位图中共有124个独特的512位块，因此7位足以索引它们。

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

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

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

is_xid_start:
	mov eax, edi
	shr eax, 9
	lea rcx, [rip + unicode_ident::tables::TRIE_START]
	add rcx, rax
	xor eax, eax
	cmp edi, 201728
	cmovb rax, rcx
	test rax, rax
	lea rcx, [rip + .L__unnamed_1]
	cmovne rcx, rax
	movzx eax, byte ptr [rcx]
	shl rax, 5
	mov ecx, edi
	shr ecx, 3
	and ecx, 63
	add rcx, rax
	lea rax, [rip + unicode_ident::tables::LEAF]
	mov al, byte ptr [rax + rcx]
	and dil, 7
	mov ecx, edi
	shr al, cl
	and al, 1
	ret

许可证

Unicode字符数据库的使用，如本crate所示，受 Unicode许可证协议 - 数据文件和软件（2016） 管理。

本crate中所有未使用Unicode字符数据库作为输入生成的知识产权，根据您的选择，受 Apache许可证，版本2.0 或 MIT许可证 管理。

生成的文件包含从Unicode字符数据库中导出的表格数据，以及crate原始源代码内容的知识产权。在涉及这些生成的文件时，必须遵守Unicode许可证协议以及Apache许可证或MIT许可证的条款。

除非您明确声明，否则根据Apache-2.0许可证定义的，您有意提交以包含在本crate中的任何贡献，都应按上述方式许可，无需任何附加条款或条件。