使用simd查找一个角色的第一个实例

我想查找一个角色的第一个实例，在这种情况下使用simd（AVX2或更早版本）'''。我想使用_mm256_cmpeq_epi8，但是我需要一个快速的方法来查找__m256i中的任何结果字节是否已被设置为0xFF，然后计划使用_mm256_movemask_epi8将结果从字节转换为位，并使用ffs来获得匹配的索引。使用_mm_movemask_epi8一次搬出的一部分的任何其他建议使用simd查找一个角色的第一个实例

来源

2016-12-01 Jimbo

我应该补充说，simd是没有必要的，一般我只是寻找最快的方法。也许有点魔力？ – Jimbo

你的基本想法是合理的 - 我有一种感觉，可能已经有一个SIMD实现，就像你在StackOverflow上的一个问题中描述的一样，但是一个快速搜索并没有解决它。注意你正在实现的是'strchr'（或者'memchr'，如果你知道这个长度的话），而且可能已经有了SIMD优化的可用实现。还要注意的是，对于尚未处于缓存中的字符串，您的函数可能会受到内存带宽的限制。 –

[这是一个SSE实现，它扫描一个''\ 0'']（http://stackoverflow.com/a/14524319/253056）（有效地'strlen'）字符串，你可能会适应它。 –

你有正确的想法与_mm256_cmpeq_epi8 - ？。。>_mm256_movemask_epi8据我所知，这是实现此为英特尔CPU的最佳方式至少PMOVMSKB r32, ymm是相同的速度作为XMM的16字节版本，所以解开这两个l将会是一个巨大的损失一个256b矢量的anes和movemask他们分开，然后重新组合整数结果。（来源：Agner Fog's instruction table看到x86标签维基其他PERF链接。）

由离开ffs，直到你从_mm256_movemask_epi8确定了非零的结果后，充分利用循环内的代码尽可能高效。

TEST/JCC可以将宏融入单个uop，但BSF/JCC不会，因此需要额外的指令。（你很难得到一个C编译器发出BSF/JCC无论如何，更可能的分支结果ffs会给你一些测试输入非零，然后BSF，然后加1 ，然后进行比较和分支。与仅测试movemask结果相比，这显然非常糟糕。）

还要注意，对于类似的问题，比较movemask（例如检查是否为0xFFFFFFFF）与分支效果一样高效不为零。

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

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

为了优化长字符串，通过将比较结果“OR”在一起来减少测试比较结果的开销，并检查它。如果您发现一个命中，请返回并重新测试您的向量以查看哪个向量具有命中。

将ffs作为您在多个移动遮罩结果之外建立的一个64位整数（使用shift和|）可能会更有效一些。在测试零之前，我不确定在循环内部执行此操作;我不记得glibc的strlen策略是否做到了。

一切我在这里提出的东西可以在ASM可以看到在不同的glibc策略的strlen，了memchr，以及相关的功能。这里是sysdeps/x86_64/strlen.S，但是我可能会在其他地方使用比基准SSE2更多的源文件。（还是不行，我可能会考虑不同的功能，也许没有什么可以得到的超越SSE2，直到AVX（3操作数的insn）和AVX2（256B整数向量）

参见：

glibc's strchr-avx2.S（Woboq.org有一个很好的源代码浏览器，可以搜索文件名/符号）。
的glibc的memchr-avx2.S

glibc's memchr使用PMAXUB代替POR。我不确定这对于一些神秘的微架构理由是否有用，但是它在大多数CPU上运行的端口更少。也许这是需要的，以避免资源冲突与其他事情？ IDK似乎很奇怪，因为它与PCMPEQB竞争。

来源

2016-12-01 16:43:14

_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版本较慢？您确定Skylake的ymm版本不会更快吗？ –

@Jimbo：无论如何，差异最多只有一个周期的等待时间，没有额外的uops或吞吐量。 **'_mm256_movemask_epi8'仍然是你可以做的最好的**。单独使用两个半部分无法做到的事情可能与仅使用一个VPMOVMSKB r32，ymm一样好。在上通道上使用128b movmsk需要先将其提取到寄存器的低128b，然后像VEXTRACTF128一样进行3周期延迟的通道交叉混洗。 –

使用simd查找一个角色的第一个实例

回答

相关问题