用于 Zig 编程语言的高吞吐量 Parser
Validark/Accelerated-Zig-Parser
A high-throughput tokenizer and parser (soon™️) for the Zig programming language.
主线的 Zig tokenizer 使用确定性有限状态机。这些对于某些应用来说非常好，但词法分析通常可以采用其他技术来提高速度。
提供了两个 tokenizer 实现：
- 一个版本，每 64 字节的块产生几个位串，并使用这些位串跳过连续字符匹配。我曾就此主题做过两次 演讲。 (目前这段代码已经消失了，但我将在 3 个月内重新构建它，以便在 7 月的 Utah-Zig 演讲中比较 Zig Tokenizer 的主题)
- 一个版本，为我们在 64 字节块中所做的 所有 事情生成位串，并利用向量压缩来同时找到所有 token 的范围。参见此动画。我还做了一个关于我的宏伟计划的演讲（实际上更像是一个咆哮）这里。不幸的是，它并没有像我希望的那样实现，因为我生病了，没有时间给予它应有的关爱。但我的下一次演讲一定会让你大吃一惊，保证！
目前在我电脑上的测试台在运行时会打印出以下内容：
Read in files in 26.479ms (1775.63 MB/s) and used 47.018545MB memory with 3504899722 lines across 3253 files
Legacy Tokenizing took 91.419ms (0.51 GB/s, 38.34B loc/s) and used 40.07934MB memory
Tokenizing with compression took 33.301ms (1.41 GB/s, 105.25B loc/s) and used 16.209284MB memory
That's 2.75x faster and 2.47x less memory than the mainline implementation!
我还有更多的优化计划 >:D !!! 敬请期待！
请参阅我关于新 tokenizer 的文章：https://validark.dev/posts/deus-lex-machina/
Tokenizer 1:
以下内容是关于 Tokenizer 1 的。这些信息有点过时，但优化策略仍然适用。
Results
当前 utf8 验证器已关闭！过去几天我进行了一些性能优化，但尚未完成移植我的更改。
测试台完全读取 src/files_to_parse 文件夹中所有 Zig 文件。在我的测试中，我在 src/files_to_parse 文件夹中安装了 Zig 编译器、ZLS 和其他一些 Zig 项目。测试台迭代每个 Zig 文件的源字节（添加了 sentinels），并在每个文件上调用 tokenization 函数**，且 utf8 验证器已关闭**。
为了 tokenizing 3,218 个 Zig 文件和 1,298,380 个换行符，原始 tokenizer 和我的新 tokenizer 具有以下特征：
memory (megabytes)
raw source files | 59.162811MB
original (tokens) | 46.089775MB
this (tokens) | 18.50827MB
内存减少了 2.49 倍！
请记住，与传统 tokenizer 的速度进行比较并不一定很简单。我很容易看到通过在我的代码中进行微不足道的更改，传统 tokenizer 的性能更改约 15%。它很大程度上取决于特定的编译。也就是说，以下是我在机器上看到的一些数字（我的实现中 utf8 验证器已关闭）：
x86_64 Zen 3
当前 utf8 验证器已关闭！过去几天我进行了一些性能优化，但尚未完成移植我的更改。
run-time (milliseconds) | throughput (megabytes per second) | throughput (million lines of code per second)
---|---|---
read files (baseline) | 37.03ms | 1597.85 MB/s | 35.06M loc/s
original | 218.512ms | 270.78 MB/s | 5.94M loc/s
this | 72.107ms | 820.57 MB/s | 18.01M loc/s
速度快了约 3.03 倍！ 当前 utf8 验证器已关闭！过去几天我进行了一些性能优化，但尚未完成移植我的更改。
RISC-V SiFive U74
当前 utf8 验证器已关闭！过去几天我进行了一些性能优化，但尚未完成移植我的更改。
run-time (milliseconds) | throughput (megabytes per second) | throughput (million lines of code per second)
---|---|---
read files (baseline) | 318.989ms | 185.47 MB/s | 4.07M loc/s
original | 2.206s | 26.81 MB/s | 0.59M loc/s
this | 894.963ms | 66.11 MB/s | 1.45M loc/s
速度快了约 2.47 倍！ 当前 utf8 验证器已关闭！过去几天我进行了一些性能优化，但尚未完成移植我的更改。
To-do
- 修复 utf8 验证器并获得良好的 SWAR 实现。
- 使其能够返回保存非换行符位图的内存。
- 实际实现 AST parser。
Maintenance note
奇怪的是，我认为其中一些代码也更易于维护，因为向 tokenizer 添加运算符或关键字实际上只是将另一个字符串添加到相关数组中。我在编译时断言（grep for comptime assert）中显式检查我使用的所有假设和技巧，因此违反任何这些不变量都会导致编译错误，告诉您为什么不能更改某些内容。
但是，我确实有很多奇怪的 SWAR 技巧，编译器希望有一天会自动执行。
Designing for high performance
在性能优化的微妙平衡中，您通常需要：
- 一次处理多个事物能力
- 更少无法预测的分支
- 线性遍历更少量的连续内存
我尝试通过以下方式实现每一个目标：
- SIMD，即单指令、多数据。您不必一次操作单个元素，而是可以同时操作 16、32 或 64 个元素。我们不按字符逐个遍历，而是使用 SIMD 来检查标识符/关键字的长度、引号的长度、空格的长度以及注释或单行引号的长度。这使我们能够比一次一个字节更快地移动。我们还使用 SIMD 技术来验证正确的 utf8 一致性，该技术从 simdjson 由 travisstaloch 移植过来，用于 simdjzon。请注意，该特定代码已获得 Apache 许可，包含在
main.zig文件的底部。- 我实际上没有使用 SIMD 来查找
'a'形式的“字符字面量”，因为这些字面量通常非常短，并且在测试中实际上并没有带来太多好处。 - 我们不能也不想将 SIMD 用于所有内容，因为：
- 注释可以位于引号内，引号可以位于注释内
- 选择下一个要匹配的位串（可能？）效率不高。您必须将每个向量相乘，然后将所有向量进行 OR 运算，获取下一个位置，然后重复。我可以尝试这种方法，但我怀疑它是否实用。我还注意到，当我查看 arm64 输出时，它比 x86_64 需要 更多 向量指令，并且在 SIMD 中执行所有操作会在 arm64 上生成数百条指令。但这仍然可能值得，尤其是在 x86_64 上，但我对此表示怀疑。
- 运算符无处不在，并且在 SIMD 中执行所有操作将需要大量工作，而标量代码执行起来并不那么糟糕。
- 注释可以位于引号内，引号可以位于注释内
- 我实际上没有使用 SIMD 来查找
- SWAR，即寄存器内的 SIMD。我们在这里将多个字节读入 4 或 8 字节寄存器，并使用传统的算术和逻辑指令来同时操作多个字节。
- 为缺少正确 SIMD 指令的机器提供了 SWAR 回退。
- 我们可以通过广播字符并执行异或运算来检查与字符的相等性：
- 为缺少正确 SIMD 指令的机器提供了 SWAR 回退。
0xaabbccddeeffgghh
^ 0xcccccccccccccccc
--------------------
0x~~~~00~~~~~~~~~~
* 前面的步骤将在字节数组中我们在其中找到目标字节（在本例中为 `cc`）的位置产生 0。然后，我们可以添加广播的 `0x7F`。
0x~~~~00~~~~~~~~~~
+ 0x7F7F7F7F7F7F7F7F
----------------
0x8~8~7F8~8~8~8~8~
* 这将在每个字节的最高有效位中产生一个 1 位，该字节在前一步之后最初不是 0。到目前为止，我提出的该技术的唯一问题是可能跨字节溢出。为了解决这个问题，我们在开始此算法之前屏蔽掉每个字节的最高位。这样，当我们添加 7F 时，我们知道它不会溢出到每个字节的最高有效位之外，然后我们知道我们可以查看每个字节的最高有效位来告诉我们目标字节是否 *不* 在那里。
* 然后，我们可以屏蔽掉每个字节的最高有效位，并模拟一个 movmask 操作，即通过乘法将这些位集中在一起：
Example with 32 bit integers:
We want to concentrate the upper bits of each byte into a single nibble.
Doing the gradeschool multiplication algorithm, we can see that each 1 bit
in the bottom multiplicand shifts the upper multiplicand, and then we add all these
shifted bitstrings together. (Note `.` represents a 0)
a.......b.......c.......d.......
* ..........1......1......1......1
-------------------------------------------------------------------------
a.......b.......c.......d.......
.b.......c.......d..............
..c.......d.....................
+ ...d............................
-------------------------------------------------------------------------
abcd....bcd.....cd......d.......
Then we simply shift to the right by `32 - 4` (bitstring size minus the number of relevant
bits) to isolate the desired `abcd` bits in the least significant byte!
* 即使在具有向量和强大指令的机器上，SWAR 技术仍可用于运算符匹配。
3. 通过以下方式减少不可预测的分支：
* 使用 SIMD/SWAR。使用传统的 while 循环来捕获上述类别中完全无法预测数量的字符几乎可以保证每次退出循环时都会出现分支预测错误，如果分支预测器状态不佳，则可能在整个循环中出现多次分支预测错误。使用 SIMD/SWAR，我们可以改为生成一个位串，其中标记了与目标字符对应的位置中的 0，例如匹配的 "，根据光标的位置移动该位串，并计算尾随的 1（位与您可能期望的相反的原因是，当我们移动位串时，它将被 0 填充）。在大多数情况下，我们只需要一个“计算尾随的 1”操作即可找到我们应该转到的下一个位置。无需完全无法预测的 while 循环，该循环按字符逐个遍历！
* 使用完美的哈希函数。具体来说，像 var 和 const 这样的关键字通过完美的哈希函数映射到 7 位地址空间中。可以通过将完美的哈希函数应用于每个标识符并执行表查找以查找它可能匹配的关键字，然后执行单个 16 字节与 16 字节的比较以查看标识符是否与该关键字匹配，从而检查标识符是否与关键字列表匹配。关键字在内存中被填充为 16 个字节，并在最后一个字节中存储一个 len，以便我们可以检查传入的标识符是否具有与预期关键字相同的长度。我们还使用 Phil Bagwell 的数组映射 trie 压缩技术，这意味着我们有一个 128 位位图，并使用该位图查找要检查的位置，从而使我们能够拥有一个不需要有 128 个插槽的打包缓冲区。我们对运算符执行类似的技巧。
* 由于 Zig 的编译时执行功能，我可以做的一件很酷的事情是告诉 Zig，当我们没有哈希到最大 7 位值（即 127）的运算符或关键字时，我们需要一个虚拟运算符/关键字（因为我将这些哈希到 7 位的地址空间）。如果添加或删除了哈希到 127 的运算符或关键字，编译时逻辑将自动删除或添加虚拟运算符/关键字。非常棒！目前，一种完美的哈希方案需要一个虚拟元素，而另一种则不需要。很高兴知道，如果我们进行更改，例如更改哈希函数或添加/删除运算符或关键字，它将自动找出要做的正确的事情。这些技巧在传统的编程语言中并不好。我们要么在启动时完成这项工作，要么更糟糕的是，有人将所有假设都烘焙到代码中，然后更改它就变成了 Jenga 游戏，只是更难，因为这些碎片并不都在一个地方。在 Zig 中，我们编写一次，编译时执行会处理其余的事情。
* 我使用了一个技巧，我只是为每个文件的 token 分配了上限量的内存，并使用分配器的 resize 工具来回收我没有填充的空间。这个技巧的好处是我可以始终假设有足够的空间，这消除了检查这种事情是否安全的需要。
* 我将 sentinels 放在文件的末尾（并在前面放置一个换行符）以使其余的代码更简单。这使我们可以在任何时候安全地返回一个字符，如果完美的哈希函数希望我们从只有一个字符的标识符中获取最后两个字符，并且还可以让我们安全地通过源文件的末尾。通过在缓冲区的末尾放置 " 和 ' 字符，我们可以消除在搜索这些字符的代码中的边界检查，并且只需在热循环完成后检查我们是否击中了 sentinel 节点即可。我们目前没有为换行符跳出这些循环，我们可能应该这样做。对这些的所有其他验证都应该在实际尝试分配它们应该表示的字符串或字符时进行。
* 我们无条件地做一些事情，这些事情可以隐藏在分支后面，但成本很低，因此没有意义。当成本高昂且通常可预测时，我们将其他事情隐藏在分支后面。例如，utf8 验证通常只是确保所有字节都小于 128，即 0x80。一旦我们看到一些非 ascii 序列，那么我们就必须做更多计算密集的工作，以确保字节序列有效。
* 表查找。我将 SIMD/SWAR 代码合并为一个代码，以便我们沿着完全相同的代码路径来查找要跳过的 non_newline/identifier/non_unescaped_quote/space 字符的数量。这可能比拥有 4 个单独的相同热循环副本效率更高。
* 内联 SIMD/SWAR 循环，即使在需要展开 8 次的机器上也是如此。事实证明，在我的测试中这很值得，可能是因为它是一个非常热的循环！
4. 我们通过不显式存储起始索引来减少内存消耗，这通常需要与源长度的地址空间匹配。在 Zig 的情况下，源文件被限制为最多 ~4GiB，任何给定文件只需要 32 位地址空间。因此，目标是将 32 位起始索引减少到更小的值。单调递增整数序列的准简洁方案立即浮现在脑海中，例如 Elias-Fano encoding。但是，我们可以通过简单地存储每个 token 的长度而不是起始索引来实现良好的空间压缩。因为 token 几乎总是具有可以容纳在一个字节中的长度，所以我们尝试将所有长度存储在一个字节中。如果长度太大而无法存储在一个字节中，我们改为存储一个 0，并将接下来的 4 个字节作为真实长度。这是因为 token 不能具有长度 0，否则它们将不存在，因此我们可以使用长度 0 来触发特殊行为。我们还知道，这个想法不会影响我们需要分配的 Token 元素数量的上限，因为要使 token 占据的空间是典型 token 的 3 倍，它需要具有至少 256 的长度，细心的读者可能会注意到，这明显大于 3。
5. 尽可能少地使用变量。虽然现在的机器拥有的寄存器比过去多得多，但您仍然只能访问 16 或 32 个通用寄存器！如果您有比这更多的变量，则必须溢出到堆栈（实际上比这更糟，因为表达式中的中间值也暂时需要自己的寄存器）。虽然机器确实有可以在幕后使用的额外寄存器，但您没有！因此，我们可以通过以下方式获得更好的性能
* 使用指针而不是指针 + 索引
* 巧妙地编写我们的 non_newlines 位串。我没有将我从 SIMD/SWAR 代码中获得的所有位串存储在堆栈上的 [4]u64（在 64 位机器上）中，然后单独写入 non_newlines 指针，而是将 所有 位串写入为 non_newlines 位串分配的内存中。每次，我都会将我们在分配中写入的位置增加单个位串的宽度，即 64 位机器上的 8 个字节。由于我始终将 non_newlines 写入分配中的当前位置，并且其他位串在它之后写入，因此最后我们将只留下 non_newlines 位串。唯一的缺点是我们需要比其他方式多分配 3 个 u64，但这几乎没有任何麻烦。以下是此策略在内存中的外观图：
|0|1|2|3|4|5|6|7|8|9| <- slots
|a|b|c|d| <- We write our bitstrings to 4 slots. (`a` is `non_newlines`)
|a|b|c|d| <- Each time, we move one slot forward
|a|b|c|d|
|a|b|c|d|
|a|b|c|d|
|a|b|c|d|
|a|b|c|d|
|a|a|a|a|a|a|a|b|c|d| <- In the end, we are left with this
Still to-do
除了 main.zig 文件中列出的待办事项之外，此计划还重写 Zig parser，该 parser 也生成抽象语法树。我对如何显着提高那里的效率也有很多想法。敬请关注！
我的最终目标是将此存储库与 Zig 编译器集成。
How to use
git clone https://github.com/Validark/Accelerated-Zig-Parser.git
接下来，在 src/files_to_parse 文件夹下安装一个或多个 Zig 项目。
cd Zig-Parser-Experiment/src/files_to_parse
git clone https://github.com/ziglang/zig.git
git clone https://github.com/zigtools/zls.git
然后运行它！
cd ../..
zig build -Doptimize=ReleaseFast run
Latest work
在过去的几天里，我：
- 在启用 SWAR 的机器上，禁用了引号解析循环的循环展开。在我的 Sifive U74 上只有 1% 的提升，但考虑到目前大约是 9 毫秒，我就接受了。
- 更新了非向量架构的关键字查找算法，以在可能的情况下使用对齐加载。仍然有改进的空间，但今天我看到了 ~5% 的性能提升。
- 更新到 稍微更好地优化的版本 的转义检测算法。
- 创建了切换，以便可以非常轻松地在 SIMD/SWAR 部分和原始标量版本之间移动
"和'。似乎对于必须使用 SWAR 的机器，执行原始标量版本更快（在我的 RISC-V SiFive U74 上几乎 ~8% 的提升）。另一方面，在我的桌面上，在 SIMD 中进行引号分类仍然更有效，但对于其他不太强大的设备，可能不值得。- 在大端硬件上也可以进行权衡。SIMD
'/"转义检测算法目前必须以小端执行，因此如果我们不想使用原始标量版本，则必须在某个地方进行反转（或对向量进行字节反转）。- 使用 SIMD，我们需要进行向量反转，除非我们有快速的机器字位反转指令。目前，除了 arm/aarch64 之外，我不知道 Zig 编译器支持的任何具有快速位反转指令的 ISA。
- 我们利用 arm 的位反转指令 (
rbit)，以便我们可以直接在我们的位串查询中使用clz，而不是rbit+clz。在小端机器上，我们在转义检测算法之后进行翻转。在大端机器上，我们可以在之前进行翻转，但那样我们只能在转义检测算法之前和之后反转反斜杠。如今，arm 通常是小端，但谁知道呢，也许未来的 ISA 可以利用这种灵活性。
- 我们利用 arm 的位反转指令 (
- mips64 和 powerpc64 具有内置的
clz指令，并通过@bitSizeOf(usize) - clz(~x & (x -% 1))模拟ctz。因此，如果我们想在 SIMD 中做引号 并 使用clz，我们将不得不翻转我们的位串两次！哎哟！希望我和其他人都弄清楚如何制作转义字符位串生成算法的大端等效物。 - 一些 sparc64 机器具有
popc（例如 niagara 2 及更高版本），可以通过popc(~x & (x -% 1))模拟ctz。要执行clz，我们必须执行x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; x |= x >> 32;将最高有效位一直向右扩展，然后我们可以反转位串以获得前导零的掩码，并计算该掩码的 popcount。因此，在大端 sparc64 机器上，我们 希望 进行位反转。此外，LLVM 的矢量化目前不适用于 sparc64（或 powerpc）机器，因此我们可能暂时必须使用 SWAR 算法。 - 没有
clz内置的机器可能可以比clz更快地模拟ctz。 - 使用 SWAR，我们可以对被视为向量的寄存器执行
@byteSwap，或者我们可以使用位反转 movmask 算法反转位。后一个问题是，我们必须在乘法之前对位串执行额外的右移，因为最高有效字节的最高有效位必须移动到其字节的最低位位置。我们 可以 通过改为使用高位乘法运算并将这些位集中在双机器字的上半部分，并保持 3 条指令 movmask 来避免这种额外的移位。但是，这个想法的问题是高位乘法可能是一个函数调用或具有糟糕的吞吐量/端口约束，而乘法通常具有每个周期 1 的吞吐量。但实际上吞吐量是一个问题吗？不确定。我们 确实 在乘法之间有很多其他工作要做。- 要为一个块生成 3 个位串，我们需要 3 个额外的指令来完成位反转 movmask（假设我们不在 SWAR 中完成
'/"）。因此，如果我们可以在不到 3 次移位和/或不到 3 条指令中更快地完成机器字字节反转，那么执行字节反转会更明智。或者，如果我们以某种方式具有快速的高位乘法，我们可以使用它来消除额外的 3 次移位（每个本机子块）。
- 要为一个块生成 3 个位串，我们需要 3 个额外的指令来完成位反转 movmask（假设我们不在 SWAR 中完成
- 现在，我认为在没有快速位反转（因此仅为 arm atm）的大端硬件上最好禁用位串转义序列算法。
- 由于 sparc64 和 powerpc 必须使用 SWAR，直到 LLVM 改进，因此它们应该在标量代码中执行引号/转义逻辑，而不是在向量代码中执行。sparc64 机器缺少位反转和字节反转，因此我们可以在 sparc64 上使用 movmask-reversed 函数。
- powerpc 可以留在高端并使用
clz。 - mips64 具有向 ISA 添加向量指令的扩展，但我不知道它是否已进入真正的硬件，或者这些向量对于我们在此处执行的 SIMD 类型是否真的有用。
- 因此，mips64 可以留在高端并使用
clz。
- 因此，mips64 可以留在高端并使用
- 使用 SIMD，我们需要进行向量反转，除非我们有快速的机器字位反转指令。目前，除了 arm/aarch64 之外，我不知道 Zig 编译器支持的任何具有快速位反转指令的 ISA。
- 在大端硬件上也可以进行权衡。SIMD
- 部分添加了一些控制字符禁令，但仍有更多工作要做。但截至目前，还不完整。
- 将 SWAR movmask 算法替换为在典型硬件上显着更好的算法。以前，我们使用的是 来自 Wojciech Muła 的算法，对于 64 位操作数
x，它基本上会执行：(@as(u128, x) * constant) >> 64。现在，我们可以通过将目标位集中在最高有效字节中来保持在较低的 64 位内，因此不需要加宽。对于我能找到信息的关于mulhi与mul之间的差异的几乎每台机器来说，这都是非常好的消息。通常，mulhi指令具有更高的延迟和显着更差的吞吐量，有些机器甚至根本没有mulhi指令。我的算法修改了 Wojciech Muła 的算法，使其仅使用乘法产品的较低 64 位：
Example with 32 bit integers:
We want to concentrate the upper bits of each byte into a single nibble.
Doing the gradeschool multiplication algorithm, we can see that each 1 bit
in the bottom multiplicand shifts the upper multiplicand, and then we add all these
shifted bitstrings together. (Note `.` represents a 0)
a.......b.......c.......d.......
* ..........1......1......1......1
-------------------------------------------------------------------------
a.......b.......c.......d.......
.b.......c.......d..............
..c.......d.....................
+ ...d............................
-------------------------------------------------------------------------
abcd....bcd.....cd......d.......
Then we simply shift to the right by `32 - 4` (bitstring size minus the number of relevant
bits) to isolate the desired `abcd` bits in the least significant byte!
- 为导出 non_newline 位图奠定了基础，这样我们就可以在以后在编译器中使用它来确定我们所在的行 无需以后在管道中逐字节遍历。
- 使用一个巧妙的技巧，我们将 SIMD/SWAR movmasked 位串写入已分配的区域，但是我们每次都将写入的位置移动一个位串的宽度。这样，最后我们用我们在每个步骤中写入的第一个位串填充了我们的缓冲区，开销基本上是每个块（64 位机器上的 64 个字节）一条指令（指针增量）。
|0|1|2|3|4|5|6|7|8|9| <- slots
|a|b|c|d| <- We write our bitstrings to 4 slots. (`a` is `non_newlines`)
|a|b|c|d| <- Each time, we move one slot forward
|a|b|c|d|
|a|b|c|d|
|a|b|c|d|
|a|b|c|d|
|a|b|c|d|
|a|a|a|a|a|a|a|b|c|d| <- In the end, we are left with this
- 修复了随机性能问题，例如编译器没有意识到我们的 SIMD/SWAR 块始终是对齐加载。（在不太主流的机器上，这非常重要！）
- 使 SIMD/SWAR 代码逐块锁定执行，而不是让每个单独的组件分别加载其 64 个（在 64 位机器上）字节。我假设 LLVM 能够在某些情况下重用加载的向量，但在实践中，我在过去一周看到了巨大的加速。当然，在 utf8 验证器正在重做时，它暂时关闭。但是，在我的 Zen 3 机器上，我通常看到运行 utf8 验证器与不运行之间基本上没有性能差异。原因是我们可以几乎总是提前退出（当整个块都是 ascii 时）。由于对齐/缓存/偶然性，我通常看到我的 tokenization 时间随着 utf8 验证器的 打开 而 减少，所以我认为我没有不公平地利用我最近的测量结果。
- 关闭了 utf8 验证器。我需要修复它的类型，以便可以重新启用它。我们还需要移植 SWAR 版本。simdjson 或 Golang 可能有一些我们可以使用的技巧。
- 添加了一个选项来启用或禁用将注释折叠到相邻节点中 (
FOLD_COMMENTS_INTO_ADJACENT_NODES)。这应该使我更容易更改我对 AST 实现的细节。 - 添加了更多测试和编译时断言。我们正在到达那里！
About
A high-throughput parser for the Zig programming language.