ARM处理器上匹配字符的最快方法？

# 在ARM处理器上匹配字符的最快方法？ 来源: https://lemire.me/blog/2026/04/19/the-fastest-way-to-match-characters-on-arm-processors/ 考虑以下问题。给定一个字符串，您必须匹配所有ASCII空白字符（`\t`、`\n`、`\r`和空格）以及JSON中一些重要的字符（`:`,`,`,`[`,`]`,`{`,`}`）。JSON是一种基于文本的数据格式，用于Web服务。一个简单的JSON文档如下所示。 `` { "name": "Alice", "age": 30, "email": "[email protected]", "tags": ["developer", "python", "open-source"], "active": true } `` 我们想使用SIMD（单指令多数据）指令来解决这个问题。使用这些指令，您可以在一条指令中将16字节的块与另一个16字节的块进行比较。 这是快速的simdjson JSON库中的一个子问题，当我们索引JSON文档时。我们称这个任务为*向量化分类*。我们在解析DNS记录时也使用相同的技术，等等。在实际的simdjson库中，我们还必须处理字符串和引号，这会更复杂。 我需要定义我所说的‘匹配’字符是什么意思。在我的例子中，对于每个64字节的块，得到两个64位掩码就足够了：一个用于空格，一个用于重要字符。为了说明，让我考虑一个16字节的变体： `` {"name": "Ali" } 1000000100000001 // 重要字符 0000000010000010 // 空格 `` 因此，我希望得到二进制格式的数字`0b1000000100000001`和`0b0000000010000010`（分别是十进制中的33025和130）。 我推荐您参考Langdale和Lemire（2019）的文章，了解如何使用ARM处理器上可用的传统SIMD指令（NEON）来实现。他们的关键想法是使用表驱动的无分支分类器：对于每个字节，分成高半字节和低半字节，使用SIMD表查找将每个半字节映射到位掩码，然后将两个掩码（通过按位与）结合起来，以确定该字节是否属于目标集合（空格或JSON结构字符）。这避免了每个字符进行多次单独相等比较。 现在，在最新的ARM处理器上有一种更好的方法。 128位版本的NEON于2011年随ARMv8-A架构（AArch64）引入。苹果发挥了重要作用，并且首次在iPhone 5S的Apple A7芯片中使用。您可以依赖所有64位ARM处理器支持NEON，这很方便。（存在32位ARM处理器，但它们主要用于嵌入式系统，而非主流计算。） ARM NEON很好，但正在变老。它无法与x64（AMD和Intel）处理器上可用的AVX-512指令集相提并论。AVX-512指令不仅支持更宽的寄存器（64字节，而ARM NEON为16字节），而且还拥有更强大的指令。 但ARM还有其他的东西：可伸缩向量扩展（SVE）及其后继者SVE2。尽管SVE最初于2016年引入，但直到2022年我们才真正能使用它。亚马逊Graviton 3使用的Neoverse V1架构是我第一个能访问到的。不久之后，我们得到了带有Neoverse V2和N2架构的SVE2。如今它已广泛可用：AWS上的Graviton4、Azure上的Microsoft Cobalt 100、Google Cloud上的Google Axion（以及较新的Google Cloud ARM CPU）、NVIDIA Grace CPU，以及Qualcomm、MediaTek和Samsung的几款芯片。注意我排除了谁？苹果。由于不明确的原因，苹果尚未采用SVE2。 我对SVE/SVE2感受复杂。像RISC-V一样，它打破了ARM NEON和x64 SIMD使用固定长度寄存器（16字节、32字节、64字节）的方法。这意味着您在编码时不应该知道寄存器的宽度。 这对芯片制造商来说很方便，因为他们可以选择调整寄存器大小以更好地适应市场。然而，它似乎已经失败了。虽然Amazon的Graviton 3处理器有256位寄存器……但之后所有商用芯片的寄存器都是128位的。 从好的方面来看，SVE/SVE2有类似于AVX-512的掩码，因此您可以在寄存器的子集中加载和处理数据。它解决了早期SIMD指令集的一个长期问题：输入不是寄存器大小的整数倍。SVE/SVE2和AVX-512都可能使尾部处理更优雅。能够仅对寄存器的一部分进行操作可以实现巧妙的优化。遗憾的是，SVE/SVE2不允许像AVX-512那样高效地将掩码移动到通用寄存器或从通用寄存器移出。这是它们使用可变长度寄存器设计的直接后果。因此，即使您的寄存器可能始终是128位并包含16字节，指令集也不允许假设掩码适合16位字。 我对SVE/SVE2感到悲观，直到我了解到它是为了与ARM NEON互操作而设计的。因此，您可以在ARM NEON代码中使用SVE/SVE2指令。如果您知道SVE/SVE2寄存器与ARM NEON寄存器（16字节）匹配，这一点尤其有效。 对于我所做的工作，有两个重要的SVE2指令：`match`和`nmatch`。在它们的8位版本中，它们的作用如下：给定两个向量`a`和`b`，每个最多包含16个字节，`match`对每个位置`i`设置一个谓词位为`true`，如果`a[i]`等于`b`中的*任何*字节。换句话说，`b`充当一个小型查找集，`match`同时测试`a`中每个字节的集合成员资格。`nmatch`指令是逻辑补：它设置一个谓词位为`true`，其中`a[i]`*不*匹配`b`中的任何字节。因此，一条指令就替换了原本需要的一系列相等比较和OR归约。在下面的代码中，`op_chars`保存8个JSON结构字符，`ws_chars`保存4个空格字符；在16字节块`d0`上调用一次`svmatch_u8`会产生一个谓词，其中输入字节是结构字符的位置恰好有一个`true`位。该代码使用SVE2内建函数：编译器提供的C/C++函数，几乎一对一地映射到CPU SIMD指令，因此您无需编写汇编即可获得接近汇编的控制。 `` // : , [ ] { } uint8_t op_chars_data[16] = { 0x3a, 0x2c, 0x5b, 0x5d, 0x7b, 0x7d, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; // \t \n \r ' ' uint8_t ws_chars_data[16] = { 0x09, 0x0a, 0x0d, 0x20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; // 将字符加载到SIMD寄存器中 svuint8_t op_chars = svld1_u8(svptrue_b8(), op_chars_data); svuint8_t ws_chars = svld1_u8(svptrue_b8(), ws_chars_data); // 加载数据 // const char * input = ... svbool_t pg = svptrue_pat_b8(SV_VL16); svuint8_t d = svld1_u8(pg, input); // 进行匹配 svbool_t op = svmatch_u8(pg, d, op_chars); svbool_t ws = svmatch_u8(pg, d, ws_chars); `` 在此代码片段中，`svuint8_t`是包含无符号8位通道（字节）的SVE向量类型。`svbool_t`是SVE谓词（掩码）类型。`svptrue_b8()`构建一个谓词，其中所有8位通道都处于活动状态，`svld1_u8(pg, ptr)`使用谓词`pg`决定实际读取哪些通道，从内存将字节加载到SVE向量中。 如果您到目前为止一直注意，您可能注意到我的代码有点错误，因为我在字符集中包含了0。但只要我假设输入中不存在零字节，就可以。实际上，我可以重复其中一个字符，或者使用一个我预计不会在输入中出现的虚构字符（例如字节值`0xFF`，它在有效的UTF-8字符串中不会出现）。 在标准SVE/SVE2中，`op`和`ws`是谓词，而不是整数掩码。一个实用的技巧是将每个谓词物化为字节（`0xFF`表示真，`0x00`表示假），例如使用`svdup_n_u8_z`。 `` svuint8_t opm = svdup_n_u8_z(op, 0xFF); svuint8_t wsm = svdup_n_u8_z(ws, 0xFF); `` 当SVE向量为128位时，此字节向量通过`svget_neonq_u8`自然映射到NEON的`uint8x16_t`，然后我们可以使用NEON操作（掩码加成对加法）高效地构建标量位掩码。在四个16字节块上重复此操作，给出64字节块所需的两个64位掩码。 它与纯NEON代码相比如何？我使用不同的编译器编译处理64字节块的过程。 | 方法 | GCC 16 | LLVM clang 20 | |------|--------|---------------| | simdjson (NEON) | 69 | 66 | | SVE/SVE2 (new!) | 42 | 52 | 有趣的是，GCC 16甚至在纯NEON代码中采用了SVE指令，这表明在针对SVE/SVE2时重新编译旧的NEON代码可能是有益的。 我希望在基准测试中测试两个编译器，但我想在AWS Graviton 4上快速运行基准测试。我也不想从源代码编译GCC 16。所以我只使用了LLVM clang 20，它在AWS提供的镜像中很容易获得（我选择了RedHat 10）。 AWS Graviton 4处理器是Neoverse V2处理器。Google在其云中有自己的Neoverse V2处理器。在我的测试中，它以2.8 GHz运行。 我的基准测试生成1 MiB的随机字符串，并计算指示字符位置的位图。它可以在GitHub上找到。我的结果如下。 | 方法 | GB/s | instructions/byte | instructions/cycle | |------|------|-------------------|--------------------| | simdjson (NEON) | 11.4 | 0.94 | 3.5 | | SVE/SVE2 (new!) | 14.4 | 0.67 | 3.8 | 因此，SVE/SVE2方法比等效的NEON方法快约25%，指令数减少30%，而且没有任何花哨的优化。重要的是，由于`match`指令的存在，代码相对简单。 可能SVE2函数`match`是在ARM处理器上匹配字符的最快方法。 *致谢*：本文的灵感来源于GitHub用户`liuyang-664`的一个草图。 ## 参考文献 Langdale, G., & Lemire, D. (2019). Parsing gigabytes of JSON per second (https://doi.org/10.1002/spe.3396). The VLDB Journal, 28(6), 941-960. Koekkoek, J., & Lemire, D. (2025). Parsing millions of DNS records per second (https://doi.org/10.1002/spe.3396). Software: Practice and Experience, 55(4), 778-788. Lemire, D. (2025). Scanning HTML at Tens of Gigabytes Per Second on ARM Processors (https://doi.org/10.1002/spe.3420). Software: Practice and Experience, 55(7), 1256-1265.