x86 - 使用 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 来说这是实现这一点的最佳方法。 PMOVMSKB r32, ymm与 XMM 16 字节版本的速度相同，因此解压 256b 向量的两个 channel 并分别 movemask 它们然后重新组合整数结果将是巨大的损失。 (来源: Agner Fog's instruction table 。请参阅 x86 标签 wiki 中的其他性能链接。)

通过保留ffs，使循环内的代码尽可能高效。直到您从 _mm256_movemask_epi8 中识别出非零结果之后.

TEST/JCC 可以宏融合到单个微指令中，但 BSF/JCC 不能，因此需要额外的指令。 (无论如何，你都很难让 C 编译器发出 BSF/JCC。更有可能的是，对 ffs 的结果进行分支会给你某种输入非零的测试，然后是 BSF，然后加 1，然后比较并分支。与仅测试 movemask 结果相比，这显然很糟糕。)

(更新，在 C++20 中，使用 std::countr_zero 。它可以编译为单个 tzcnt ，而不是 ffs 的差一。因为您'已经检查过掩码是否非零，如果不确定运行该代码的所有 CPU 都支持 rep ，希望可以优化为单个 ( bsf ) tzcnt 指令。如果您可以假设 BMI1 在您的 objective-c PU(通常可用于 AVX2 代码)，然后启用它，这样您就可以可靠地获得高效的 tzcnt 。)

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

<小时/>

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

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

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

执行 ffs 可能会更有效基于您根据多个 movemask 结果构建的一个 64 位整数(使用 shift 和 | )。我不确定在测试零之前是否在循环内执行此操作；我不记得 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's memchr使用 PMAXUB 代替 POR。我不确定这对于某些神秘的微架构原因是否有用，但它在大多数 CPU 上运行在较少的端口上。也许这是所希望的，以避免与其他东西发生资源冲突？ IDK，看起来很奇怪，因为它与 PCMPEQB 竞争。