使用 simd 查找字符的第一个实例

Question

我正在尝试使用 simd（AVX2 或更早版本）查找字符的第一个实例，在本例中为 '"'。我想使用 _mm256_cmpeq_epi8，但随后我需要一种快速方法来查找是否有任何结果字节__m256i 中的值已设置为 0xFF。当时的计划是使用 _mm256_movemask_epi8 将结果从字节转换为位，然后使用 ffs 获取匹配索引。使用 _mm_movemask_epi8 一次移出一部分是否更好？还有其他建议吗？

Answer 1

您的想法是正确的

_mm256_cmpeq_epi8

->

_mm256_movemask_epi8

。 AFAIK，至少对于 Intel CPU 来说这是实现这一点的最佳方法。

VPMOVMSKB r32, ymm

与 XMM 16 字节版本的速度相同，因此解压 256b 向量的两个通道并分别 movemask 它们然后重新组合整数结果将是巨大的损失。 （来源：Agner Fog 的指令表。请参阅 x86 标签 wiki 中的其他性能链接。）

通过将

ffs

保留到确定

_mm256_movemask_epi8

的非零结果之后，使循环内的代码尽可能高效。

TEST/JCC 可以宏融合为单个 uop，但 BSF/JCC 不能，因此需要额外的指令。 （无论如何，你都很难让 C 编译器发出 BSF/JCC。更有可能的是，对

ffs

的结果进行分支会给你某种输入非零的测试，然后是 BSF，然后加 1，然后比较并分支。与仅测试 movemask 结果相比，这显然很糟糕。）

（更新，在 C++20 中，使用

std::countr_zero

。 它可以编译为单个

tzcnt

，而不是

ffs

的差一。因为您已经检查了掩码是否为非零，如果不确定运行该代码的所有 CPU 都支持

rep

，希望可以优化为单个 (

bsf

)

tzcnt

指令。如果您可以在目标 CPU 中假设 BMI1，通常可以这样做对于 AVX2 代码，然后启用它，这样您就可以可靠地获得高效的

tzcnt

。）

另请注意，对于类似的问题，比较 movemask（例如，检查它是否为 0xFFFFFFFF）与非零分支一样有效。

---

正如 Paul R 所建议的，查看一些 strlen、strchr 和 memchr 实现可能会提供很多信息。在开源libc实现等地方有多种手写的asm实现。 （例如 glibc 和 Agner Fog 的 asmlib。）

许多 glibc 的版本都会扫描到对齐边界，然后使用一次读取 64B 的展开循环（在 4 个 SSE 向量中，因为我认为 glibc 没有 AVX2 版本）。

要优化长字符串，请通过将比较结果进行“或”运算并进行检查来减少测试比较结果的开销。如果您发现命中，请返回并重新测试您的向量以查看哪个向量命中。

对由多个 movemask 结果（使用 shift 和

ffs

）构建的一个 64 位整数执行

|

可能会更有效。我不确定在测试零之前是否在循环内执行此操作；我不记得 glibc 的 strlen 策略之一是否做到了这一点。

---

我在这里建议的所有内容都可以在 asm 中的 strlen、memchr 和相关函数的各种 glibc 策略中看到。这是 sysdeps/x86_64/strlen.S，但我可能在某个地方有另一个源文件使用了超过基线的 SSE2。 （或者不是，我可能正在考虑一个不同的函数，也许除了 SSE2 之外没有什么可以得到的，直到 AVX（3 操作数 insns）和 AVX2（256b 整数向量）。

另请参阅：

• glibc 的

  strchr-avx2.S

  （Woboq.org 有一个很好的源浏览器，可以对文件名/符号进行有用的搜索）。
• glibc 的

  memchr-avx2.S

---

glibc 的 memchr 使用 PMAXUB 而不是 POR。我不确定这对于某些神秘的微架构原因是否有用，但它在大多数 CPU 上运行在较少的端口上。也许这是所希望的，以避免与其他东西发生资源冲突？ IDK，看起来很奇怪，因为它与 PCMPEQB 竞争。

也许作者正在考虑最小/最大操作，因为

pminub

is 在 glibc 的

strlen

算法中很有用，其中

pminub

before 比较给出零字节，当且仅当任一输入为零时。