获取16或32字节固定大小缓冲区的C字符串长度？（XMM或YMM寄存器宽度）

Question

有没有办法通过将存储在16或32字节缓冲区中的ASCII字符串加载到XMM或YMM寄存器中来获取其长度？本质上，我在寻找第一个零字节的索引（以位或字节为单位）。

我的目标是避免循环和分支。我希望在AVX或SSE中，沿着BSF（位向前扫描）的线路存在一些东西，但操作的是字节，而不是位。

也许像下面这样？

_my_constant_time_strlen:
 vpxor ymm0, ymm0
 VPCMPEQB ymm0, ymm0, [rdi]
 vpmovmskb eax, ymm0
 bsf eax, eax
 ; string length is in eax?

   ; and rax, 31              ; editor's note: useless AND
 ret

Answer 1

这正是使用AVX2实现strlen或memchr的方法。

vpmovmskb（内在：int-mm256\u movemask\u epi8（\uu m256i））将比较向量转换为字节比较结果的位图，您可以使用bsf（或更好的是tzcnt）进行搜索。

您的代码已经完全符合您的要求。（对于固定大小的缓冲区，您知道缓冲区中的某个地方会有匹配；您的和eax，31对这一点没有帮助）

如果避免破坏循环，可以将vpxor从循环中调零。此外，使用vpxor XMM（非YMM）将寄存器归零：在AMD Zen1和Alder Lake E-Core上保存uop。

移位/或从较窄的pmovmskb/ps/pd结果组装32位或64位掩码可能很有用，允许您在不进行分支的情况下对多达64个元素进行位扫描。

真正的工作是在Intel CPU（Haswell/Skylake）上总共只有3个uop:vpcmpeqb是1个微融合uop，因为您避免了索引寻址模式<代码>vpmovmskb是1 uop，具有2到3个周期的延迟<代码>tzcnt是Intel或AMD CPU上的1 uop。（bsf在Intel上也是1 uop）。在英特尔tzcnt或bsf上有3个周期的延迟。

因此，在主流Intel上，从准备好的向量加载数据到RAX中的长度的总延迟为1（vpcmpeqb）2或3（movmsk）3（tzcnt）=6或7个周期。这是无分支的，只是一个数据依赖项，所以这是相当合理的。这不包括加载使用延迟或存储转发延迟，无论地址或数据是否在关键路径上。并且吞吐量非常出色，在Intel上每时钟为1 strlen（在端口0和/或端口1上遇到瓶颈）。

在AMD Zen1上，vpcmpeqb ymm是2 uops，延迟为2c。vpmovmskb ymm是2 uops（对于端口FP2），延迟为3c。tzcnt是2 uops，延迟为2c。所以总延迟=7个周期，并且吞吐量是每2个周期1个，在movemask吞吐量上遇到瓶颈。（Ryzenlzcnt是1 uop/1c延迟；大概tzcnt是位反向lzcnt或类似的东西。）

AMD Zen2和更高版本将SIMD执行单元扩展到256位宽，使用单uop vpcmpeqb ymm，但仍然是2-uop tzcnt

来自的数字https://agner.org/optimize/和https://uops.info/

SSE4.2 pcmpistri可以扫描向量以查找是否包含零字节，但相对较慢，一次只能处理16个字节，没有AVX2版本。它或pcmpistrm是多个UOP，在Intel上具有3个周期的吞吐量，在AMD Zen上具有2个周期的吞吐量。这是一条有趣且功能强大的指令，但对于您可以使用vpcmpeqb解决的问题而言，它的速度过快。https://www.strchr.com/strcmp_and_strlen_using_sse_4.2演示了如果您想了解strlen的速度有多慢（尤其是在比Nehalem更新的cpu上），如何将其用于strlen。更有用的是，该页面解释了它可以执行的不同类型的搜索（如any==any搜索集合，或使用一个向量对作为范围，或子字符串搜索，如strstrstr），立即数操作数是如何编码的。

pcmpistri如果您只有16个字节要查看，它可能是一条有用的指令；它负责位置=bitsearch（掩码）部分。但是如果您有（可能）更多数据要查看，它就不太好了。在Intel上，它的所有3个uops都在同一个端口上运行，因此如果它在循环中没有太多乱序执行可以重叠的周围代码，则对吞吐量不利。

除此之外，对于没有movmsk先整数的水平矢量搜索/扫描，唯一想到的是phminposuw，这不是你想要的。（它可以找到一个16位的零元素。

或者可能vpandavpcmpeqb得到向量为1,2,4,8,16，…幂为2的结果，然后vpsadbw进行字节的水平相加。结果中的最低设置位表示该8字节块中前0的位置。但这只适用于8个元素-

或者，您可以执行log2（vector_length）步骤，对下一个元素进行洗牌和掩蔽，以得到一个向量，其中输入中只有前0个具有0xff元素。然后将向量为0,1,2,3,4，…和vpsadbw的VPAND与hsum连接，唯一的非零元素将是字节位置。但是，如果出于某种原因确实需要XMM寄存器中的结果，那么这比返回XMM寄存器的vpcmpeqb要昂贵得多。（hsum实际上需要vpsadbw-Vextract128-vpaddb-vpshufd-vpshufd-

对于较长的字符串，您可以test eax， eax/jz.keep_looping而不是实际上对每个movemask结果进行位扫描。bsf和tzcnt确实根据输入为零（分别为ZF=1或CF=1）设置FLAGS，但测试jcc可以宏融合到单个测试和分支uop中。如果您不小心，前端带宽（可能还有后端执行端口）对于小而不小的strlen（L1d缓存中的数据很热）的吞吐量已经是一个问题。

长字符串的memchr或strlen的主循环可能来自一两个缓存线的多个比较结果，以摊销movemask/branch，然后从循环外找出它的来源。

或者对于strlen具体来说，vpminub在vpcmpeqb之前的两个原始输入数据向量，如果输入中有零字节，则获取零字节。（离开循环后，该策略需要重新检查输入数据，而不仅仅是比较向量。）glibc strlen执行此操作；另请参阅在x86和x64上读取同一页面内的缓冲区末尾是否安全？有关链接和另一个要注意的问题，如果在可能接近页面末尾的可变长度数据上使用它。

如果eax为零，则您的bsf eax，eax将保持eax不变（由AMD记录，由两者以这种方式实现。但Intel将其记录为“未定义”的整数结果）。否则，它将使用0到31之间的值写入EAX，因此无论哪种方式，AND都是完全冗余的。

我认为所有AVX2 CPU也支持BMI1 tzcnt，它将为0的输入提供32个字节（未找到任何字节）。它的性能也更好：在AMD上，bsf的速度较慢。

具有AVX2的CPU：

• AMD自挖掘机（自Piledriver以来已经有tzcnt）
• Haswell以来的英特尔（带有tzcnt的BMI1也是新的）
• 通过/ZHAOXIN自具有BMI1/tzcnt的开县ZX-C。

在不支持BMI1的CPU上，它将作为bsf执行，这对于非零输入（相同的整数结果）很好。因此，这是代码性能升级的下降，已经排除了全零掩码，或者不关心在这种情况下会发生什么。

bsf如果输入为零则设置ZF=1，这与tzcnt不同，它像普通指令一样根据输出设置ZF，但为全零输入设置CF=1。然后您使用哪种指令（以及CPU以哪种形式运行它）很重要。

如果您只查看一个固定大小的块，bsf或tzcnt的FLAGS结果可能有助于检测零输入，如果您想cmov上面的其他内容。位扫描之前的test/jcc为1 uop（并且意味着您在（罕见的？）未找到的情况下跳过它），与之后的独立jcc相同。最近的CPU宏保险丝测试/jz。但是jcc之后保存了一些机器代码大小。并且cmov不会融合，因此如果您使用FLAGS结果，则在tzcnt之前进行测试将花费额外费用。