我可以使用 SIMD 来加速字符串操作吗？

Question

SIMD 指令是否仅用于矢量数值计算？或者它是否适合一类字符串操作任务，例如将数据行写入文本文件，其中行的顺序无关紧要？如果是这样，我应该从哪些 API 或库开始？

Answer 1

是的！这实际上是在高性能解析库中完成的。一个例子：simdjson - 一种每秒可以解析千兆字节 JSON 的解析器。自述文件中有一个关于 simdjson 的部分，其中有一个指向讨论一些实现细节的演讲的链接。

SIMD 指令对数值进行操作，但是一旦您处于该级别，“文本”就只是数值，例如 UTF-8 代码点只是无符号 8 位整数，具有大量 SIMD 支持。处理位图充满了对多个 8 位无符号整数的并行操作，而且很方便地发生这种情况，以至于 SIMD 指令集涵盖了这些操作，因此它们中的很多也可用于文本处理。

I/O 比 CPU 慢很多数量级

并不真地。它速度较慢，但​​是当 CPU 必须执行会影响流式传输性能的任务时，例如分支预测错误、缓存未命中或在死胡同上浪费大量推测执行资源时，CPU 很容易跟不上 I/O . 用于快速存储访问或多机通信的现代网卡会使 CPU 的内存端口饱和。他们都。并保持这种状态。但这是最先进的，目前相当昂贵（绑定 50 GBit 链接等）。顺序的，一次字节的解析器代码比这慢得多。

Answer 2

是的，尤其是对于 ASCII，例如Convert a String In C++ To Upper Case。或者检查有效的 UTF-8 ( https://lemire.me/blog/2020/10/20/ridiculously-fast-unicode-utf-8-validation/ )，或检查字符串是否恰好是UTF-8。（如果是这样，你知道你有固定宽度的字符，这对其他事情非常有用。）

正如 Daniel Lemire 报道的那样，UTF-8 验证的早期尝试给出了“每个字符几个 CPU 周期”。但是使用 SIMD，他和合作者能够实现每字节约 1 条指令，网络速度为约 12GB/s。（相比之下，Haswell 台式机的 DRAM 带宽约为 25GB/s，或 Skylake 的 DDR4-2133 为 34GB/s）。

当然，大多数 C 库已经有像strlen, strcpy, strcasecmp,strstr等函数的手写 asm 实现，如果它是一个胜利就使用 SIMD（比如在 x86-64 上pmovmskb允许相对有效的比较/分支对任何/所有 SIMD 比较结果是对或错。）我回答的第一部分为什么 glibc 的 strlen 需要如此复杂才能快速运行？有一些指向 glibc 在主流平台上实际使用的手动优化的 asm 的链接，而不是问题所询问的可移植的纯 C 后备。

https://github.com/WojciechMula/sse4-strstr有多种strstr实现方式。子串搜索是一个更难的问题，有非平凡的算法选择以及蛮力。SSE4.2“字符串”指令可能对此有所帮助，但如果没有，那么 SIMD 向量比较肯定可以用于更好的蛮力构建块。

（SSE4.2“字符串”指令pcmpistri对于memcmp/ 来说肯定更糟，strcmp而strlen普通 SSE2（或 AVX2）更好。请参阅SSE4.2 字符串指令比 memcmp 的 SSE2 快多少？和 https://www.strchr.com /strcmp_and_strlen_using_sse_4.2 )

您甚至可以通过查找基于向量比较位图的 shuffle 控制向量来做一些很酷的技巧，例如从字符串中获取 IPv4 地址的最快方法或如何使用 SIMD 实现 atoi？. 尽管我不确定 SIMD atoi 是否能胜过标量，尤其是对于短数字。

我天真地说 SIMD 无济于事，因为对于长字符串内存带宽将是瓶颈。为什么不是这样？

与现代 CPU 速度相比，DRAM带宽确实相当不错，尤其是当数据以字节块而非 8 字节double块的形式出现时。并且数据在复制后（例如来自read系统调用）在 L3 缓存中通常很热。

即使数据必须来自 DRAM，现代台式机/笔记本电脑 CPU 也可以在每个核心时钟周期加载大约 8 个字节，无论如何都在 2 倍之内，特别是如果这个核心不与其他核心上的其他带宽密集型代码竞争. 祝你好运跟上一个字节一次的标量循环。

此外，如果您只是执行了一个read()系统调用来让内核将一些数据从网络缓冲区或页面缓存中 memcpy 到您的进程内存中，那么这些数据在 L3 缓存中可能仍然很热，甚至在 L2 中。Xeon CPU 甚至可以 DMA 进入 L3 缓存，或者类似的东西。以内存带宽为目标是一个相当低/没有野心的目标，并且是一个不充分优化函数的糟糕借口，如果它实际上得到了很多使用。

处理相同数据的指令更少，让乱序执行程序“看到”更远的地方，并在硬件预取不会（例如跨页面边界）的情况下更早地开始对后面的页面/缓存行进行按需加载。并且还可以更好地将字符串处理与早期/后期的独立工作重叠。

它还可以对超线程更加友好，如果在其上运行任何东西，HT 兄弟核心将具有更好的吞吐量。（如果没有很多线程处于活动状态，则可能什么都没有）。此外，如果 SIMD 足够高效，它可以节省能源：通过流水线跟踪指令是成本的很大一部分，而不是整数执行单元本身。跑步时更高的功率，但更快完成，是好的：比赛睡觉。CPU 在完全空闲时比仅运行“廉价”指令时节省的电量要多得多。

Answer 3

SIMD 指令的使用级别非常低。将数据写入文本文件是一个更高的级别，涉及缓冲 I/O 等。

例如，您可以使用 SIMD 将字符串从小写转换为大写。将 SIMD 封装到库中是没有意义的。您自己编写说明。这也意味着它们是特定于处理器的（例如 x86/AMD64 上的 SSE 变体）。

为了并行处理多行文本，您可以使用微并行化，例如 OpenMP 或 TBB 提供的微并行化。

但是，如果您坚持使用写入文本文件的示例，我们就会进入性能优化的另一个领域（I/O 而不是计算）。