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

Unicode ID_start

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

变更日志

1.2.0

• 修补 ・ U+30FB KATAKANA MIDDLE DOT 和 ･ U+FF65 HALFWIDTH KATAKANA MIDDLE DOT

Unicode 4.1至Unicode 15意外地将这两个字符从ID_Continue中省略。然而，这个错误在Unicode 15.1中得到纠正。任何支持ES6+但使用Unicode版本早于15.1的JS VM都将认为这是语法错误，因此我们故意省略这些字符，使其在ES5和ES6+中都是有效的标识符。更多信息请见 https://www.unicode.org/L2/L2023/23160-utc176-properties-recs.pdf 中的2.2节

1.1.2

• Unicode 15.1.0

1.1.1

• Unicode 15.0.0

1.0.4

• Unicode 14.0.0

性能比较

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

• unicode-id-start 是这个crate，它是 unicode-ident 的一个分支；
• unicode-xid 是由“unicode-rs”组织维护的广泛使用的crate，unicode-id 是 unicode-xid 的一个分支；
• ucd-trie 和 fst 是由 ucd-generate 工具支持的两个数据结构。
• roaring 是 Roaring bitmap 的 Rust 实现。

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

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

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

数据结构比较

unicode-id

它们使用字符范围的有序数组，并执行二分搜索以查找给定字符是否落在这些范围之一内。

static ID_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 个字节，通过存储低 char 和范围而不是低 char 和高 char。我不期望性能会有很大提高，但这可能是在所有库中最有效的空间利用率，只需要大约 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 个缓存行。

一种可能的性能改进是为此 crate 提供一种基于 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 个 char 中的 32 位是有意义的这一事实进行优化。在结构中存在一些密集的数组，这些数组中有大范围的值永远不可能被使用。

roaring

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

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

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

我还对 croaring crate 进行了基准测试，这是一个围绕 C 引用实现 Roaring Bitmap 的 FFI 包装器。这个 crate 比纯 Rust 的 roaring 慢约 15%，这可能是 FFI 开销。我没有进一步调查。

unicode-ident

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

主要区别在于

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

以下图显示了未压缩的ID_Start和ID_Continue Unicode布尔属性，按行主序排列

ID_Start	ID_Continue

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

该crate在trie的叶子级别存储上述位图的512位“行”，并增加一个单独的级别来索引叶子。结果发现，在两个位图之间有124个独特的512位块，因此7位足够索引它们。

选择512位块大小作为使数据结构总大小最小化的尺寸。较小的块，如256或128位，会实现更好的去重，但需要更大的索引。较大的块会增加叶子位图中的冗余。512位块是索引总大小和叶子位图的最佳选择。

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

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

is_id_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许可证的条款。

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