使用 simd 查找字符的第一个实例
Find the first instance of a character using simd
我正在尝试使用 simd（AVX2 或更早版本）查找字符的第一个实例，在本例中为“””。我想使用 _mm256_cmpeq_epi8，但我需要一个快速的方法查找 __m256i 中的任何结果字节是否已设置为 0xFF。然后计划使用 _mm256_movemask_epi8 将结果从字节转换为位，然后使用 ffs 获得匹配索引。使用 _mm_movemask_epi8 一次移出一部分是否更好？还有其他建议吗？
_mm256_cmpeq_epi8 -> _mm256_movemask_epi8 你的想法是正确的。 AFAIK，至少这是为 Intel CPU 实现此功能的最佳方式。 PMOVMSKB r32, ymm 与 XMM 16 字节版本的速度相同，因此将 256b 向量的两个通道解包并分别移动掩码然后重新组合整数结果将是一个巨大的损失。 （来源：Agner Fog's instruction table. See other perf links in the x86 标签维基。）
通过保留 ffs 直到您从 _mm256_movemask_epi8.
中识别出非零结果，使循环内的代码尽可能高效
TEST/JCC 可以宏融合成一个 uop，但 BSF/JCC 不能，所以它需要额外的指令。 （无论如何，你都很难让 C 编译器发出 BSF/JCC。更可能的是，对 ffs 结果的分支会给你某种输入非零的测试，然后 BSF，然后加 1，然后比较和分支。与仅测试 movemask 结果相比，这显然是可怕的。）
另请注意，对于类似的问题，比较移动掩码（例如检查它是否为 0xFFFFFFFF）与非零分支一样有效。
正如 Paul R 所建议的，查看一些 strlen、strchr 和 memchr 实现可能会提供信息。在开源 libc 实现和其他地方有多个手写的 asm 实现。 （例如 glibc 和 Agner Fog's asmlib。）
许多 glibc 版本扫描到对齐边界，然后使用一次读取 64B 的展开循环（在 4 个 SSE 向量中，因为我认为 glibc 没有 AVX2 版本）。
要针对长字符串进行优化，通过将比较结果进行 OR 运算来减少测试比较结果的开销，并进行检查。如果找到命中，请返回并重新测试您的向量以查看命中的向量。
对您从多个移动掩码结果（使用 shift 和 |）构建的一个 64 位整数执行 ffs 可能会更有效一些。我不确定在测试零之前是否在循环内执行此操作；我不记得 glibc 的 strlen 策略之一是否做到了这一点。
我在这里建议的所有内容都可以在 asm 中的各种 glibc 策略中看到，用于 strlen、memchr 和相关函数。这是 sysdeps/x86_64/strlen.S，但我可能在某处使用了超过基线 SSE2 的其他源文件。 （或者不是，我可能正在考虑一个不同的功能，也许除了 SSE2 之外没有什么可以得到的，直到 AVX（3-operand insns）和 AVX2（256b 整数向量）。
另请参阅：
- glibc 的
strchr-avx2.S（Woboq.org 有一个很好的源代码浏览器，可以搜索文件名/符号）。
- glibc 的
memchr-avx2.S
glibc's memchr 使用 PMAXUB 而不是 POR。我不确定这是否出于某些神秘的微体系结构原因有用，但它在大多数 CPU 上运行在较少的端口上。也许这是需要的，以避免与其他东西发生资源冲突？ IDK，看起来很奇怪，因为它与 PCMPEQB 竞争。
我正在尝试使用 simd（AVX2 或更早版本）查找字符的第一个实例，在本例中为“””。我想使用 _mm256_cmpeq_epi8，但我需要一个快速的方法查找 __m256i 中的任何结果字节是否已设置为 0xFF。然后计划使用 _mm256_movemask_epi8 将结果从字节转换为位，然后使用 ffs 获得匹配索引。使用 _mm_movemask_epi8 一次移出一部分是否更好？还有其他建议吗？
_mm256_cmpeq_epi8 -> _mm256_movemask_epi8 你的想法是正确的。 AFAIK，至少这是为 Intel CPU 实现此功能的最佳方式。 PMOVMSKB r32, ymm 与 XMM 16 字节版本的速度相同，因此将 256b 向量的两个通道解包并分别移动掩码然后重新组合整数结果将是一个巨大的损失。 （来源：Agner Fog's instruction table. See other perf links in the x86 标签维基。）
通过保留 ffs 直到您从 _mm256_movemask_epi8.
TEST/JCC 可以宏融合成一个 uop，但 BSF/JCC 不能，所以它需要额外的指令。 （无论如何，你都很难让 C 编译器发出 BSF/JCC。更可能的是，对 ffs 结果的分支会给你某种输入非零的测试，然后 BSF，然后加 1，然后比较和分支。与仅测试 movemask 结果相比，这显然是可怕的。）
另请注意，对于类似的问题，比较移动掩码（例如检查它是否为 0xFFFFFFFF）与非零分支一样有效。
正如 Paul R 所建议的，查看一些 strlen、strchr 和 memchr 实现可能会提供信息。在开源 libc 实现和其他地方有多个手写的 asm 实现。 （例如 glibc 和 Agner Fog's asmlib。）
许多 glibc 版本扫描到对齐边界，然后使用一次读取 64B 的展开循环（在 4 个 SSE 向量中，因为我认为 glibc 没有 AVX2 版本）。
要针对长字符串进行优化，通过将比较结果进行 OR 运算来减少测试比较结果的开销，并进行检查。如果找到命中，请返回并重新测试您的向量以查看命中的向量。
对您从多个移动掩码结果（使用 shift 和 |）构建的一个 64 位整数执行 ffs 可能会更有效一些。我不确定在测试零之前是否在循环内执行此操作；我不记得 glibc 的 strlen 策略之一是否做到了这一点。
我在这里建议的所有内容都可以在 asm 中的各种 glibc 策略中看到，用于 strlen、memchr 和相关函数。这是 sysdeps/x86_64/strlen.S，但我可能在某处使用了超过基线 SSE2 的其他源文件。 （或者不是，我可能正在考虑一个不同的功能，也许除了 SSE2 之外没有什么可以得到的，直到 AVX（3-operand insns）和 AVX2（256b 整数向量）。
另请参阅：
- glibc 的
strchr-avx2.S（Woboq.org 有一个很好的源代码浏览器，可以搜索文件名/符号）。 - glibc 的
memchr-avx2.S
glibc's memchr 使用 PMAXUB 而不是 POR。我不确定这是否出于某些神秘的微体系结构原因有用，但它在大多数 CPU 上运行在较少的端口上。也许这是需要的，以避免与其他东西发生资源冲突？ IDK，看起来很奇怪，因为它与 PCMPEQB 竞争。