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

Question

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

- Jimbo

---

我应该补充一下，simd并不是必需的，总体而言我只是在寻找最快的方法。也许可以用一些位运算技巧？ - Jimbo

你的基本想法是正确的 - 我有一种感觉，在 StackOverflow 上你之前描述过类似于你现在实现的 SIMD 实现，但快速搜索并没有找到。请注意，你正在实现的实际上是 strchr（或者如果你知道长度则为 memchr），并且可能已经存在 SIMD 优化的实现可用。另外，请注意对于尚未缓存的字符串，你的函数很可能会受到内存带宽的限制。 - Paul R

这是一个SSE实现，它可以扫描字符串寻找'\0'（实际上是strlen），你也许可以进行修改。 - Paul R

相关帖子：https://stackoverflow.com/questions/47245773/why-is-strchr-twice-as-fast-as-my-simd-code - Jimbo

Answer 1

您的想法是正确的，使用_mm256_cmpeq_epi8 -> _mm256_movemask_epi8。据我所知，这至少是在Intel CPU上实现此操作的最佳方法。PMOVMSKB r32, ymm与XMM 16字节版本的速度相同，因此拆分256b向量的两个通道并单独移动掩码，然后重新组合整数结果将导致巨大的性能损失。(来源: Agner Fog's instruction table. 请参阅x86标记wiki中的其他性能链接。)

通过在确定_mm256_movemask_epi8的非零结果之后再执行ffs，使循环内的代码尽可能高效。

TEST/JCC可以将宏融合成单个uop，但BSF/JCC不能，因此需要额外的指令。(而且你很难让C编译器发出BSF/JCC。更有可能的是，在ffs的结果上进行分支，给你一些测试输入是否为非零的测试，然后BSF，然后加1，然后比较和分支。与仅测试movemask结果相比，这显然是可怕的。)

(更新，在C++20中，请使用std::countr_zero。它可以编译为单个tzcnt，而不是ffs的偏移1。由于您已经检查了掩码是否为非零，希望可以优化为单个（rep）bsf指令，如果不确定所有运行代码的CPU都支持tzcnt。如果您可以假设目标CPU支持BMI1，通常可以对AVX2代码进行启用，以便您可以可靠地获得高效的tzcnt。)

此外，请注意，对于类似的问题，比较movemask（例如检查它是否为0xFFFFFFFF）与在其非零时进行分支操作一样有效。

---

如Paul R所建议的那样，查看一些strlen、strchr和memchr的实现可能会很有启发性。在开源libc实现和其他地方有多个手写的asm实现。(例如glibc和Agner Fog的asmlib)。

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

为了优化长字符串，通过将比较结果OR在一起减少测试比较结果的开销，并检查它。如果找到匹配项，请返回并重新测试您的向量以查看哪个向量有匹配项。

在一个由多个movemask结果(带有移位和|)组成的64位整数上执行ffs可能会更有效率。我不确定在测试为零之前是否要在循环内部执行此操作;我不记得glibc的strlen策略是否这样做过。

---

我在这里提出的所有建议都可以在各种glibc策略中看到，例如strlen、memchr和相关函数。这里是sysdeps/x86_64/strlen.S，但可能还有另一个源文件在使用超过基线SSE2的内容。(或者没有，我可能想到了另一个函数，也许除了AVX(3操作数指令)和AVX2(256b整数向量)之外，没有什么可以获得的了。

另请参阅:

• glibc的 strchr-avx2.S (Woboq.org具有用于文件名/符号的有用搜索的漂亮源代码浏览器)。
• glibc的 memchr-avx2.S

---

glibc的memchr使用PMAXUB而不是POR。我不确定这是否出于某些神秘微架构原因而有用，但它在大多数CPU上运行时使用的端口更少。也许这是期望的，以避免与其他资源发生冲突？我不知道，似乎很奇怪，因为它与PCMPEQB竞争。

- Peter Cordes

---

_mm_movemask_epi8 的设计初衷是在新型处理器上比 _mm256_movemask_epi8 更快，即使需要调用两次也是如此。如果不需要调用两次，则避免额外的调用可以节省时间。当然，这似乎取决于处理器，在Haswell处理器上，延迟相等，使用更大的调用（即_mm256_movemask_epi8）似乎是更好的方法。 - Jimbo

@Jimbo：哦，嗯，我没有注意到Agner Fog的Skylake表中PMOVMSKB r，v被列为2-3c延迟。在Haswell上， VMOVMSKPS/D r32, ymm为2c延迟，但xmm版本为3c延迟！这很令人惊讶。你在哪里看到256b版本更慢？你确定ymm版本在Skylake上不是更快吗？ - Peter Cordes

@Jimbo：无论如何，差异最多只有一个周期的延迟，没有额外的uops或吞吐量。 _mm256_movemask_epi8仍然是你能做的最好的选择。 你用两个单独的半部分所能做的任何事情都不可能像只使用一个VPMOVMSKB r32, ymm那样好。在上半车道上使用128b movmsk需要先将其提取到寄存器的低128b中，使用3个周期的延迟车道交叉洗牌，例如VEXTRACTF128。 - Peter Cordes

无论如何，请记住测试循环条件的掩码只对检测错误预测和在最后一次迭代后将掩码提供给BSF或TZCNT（ffs）敏感。分支预测的推测执行意味着每个条件分支指令都是单独的依赖链。即，控制依赖关系不是数据依赖关系。JCC上标志输入的较短延迟不会影响吞吐量，只有在检测到分支错误预测之前的延迟才能被检测到。 - Peter Cordes