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

Question

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

我的目标是避免循环和分支。我希望 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

这正是您实现的方式 strlen或 memchr与 AVX2。 (对于固定大小的缓冲区，您知道缓冲区中的某处会有匹配项。)

(除了现在你有一个多余的 and )。
vpmovmskb将您的比较向量转换为字节比较结果的位图，您可以使用 BSF 进行搜索。您的代码已经完全符合您的要求。

您可以吊起vpxor - 如果避免破坏循环，则将其归零。

真正的工作是在 Intel CPU (Haswell/Skylake) 上总共只有 3 个 uops :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 锐龙上，vpcmpeqb ymm是 2 uop，具有 2c 延迟。 vpmovmskb ymm是 2 uops(对于 Port2)，延迟为 3c。 tzcnt是 2 uop，具有 2c 延迟。因此，总延迟 = 7 个周期，吞吐量是 movmsk 吞吐量的瓶颈，每 2 个周期有 1 个。 (Ryzen lzcnt 是 1 uop/1c 延迟；大概 tzcnt 是位反转 + lzcnt 或类似的东西。)

来自 https://agner.org/optimize/ 的号码.

没有扫描 XMM 或 YMM 寄存器的第一个非零字节的指令，唯一有效的方法是 pcmpeqb/pmovmskb .您可以 vmovd xmm0, eax最后，如果您想要向量 reg 中的字节位置而不是整数。

但通常您希望将结果保存在整数寄存器中。

对于没有 movmsk 到整数的水平向量搜索/扫描，唯一想到的是 phminposuw ，这不是您想要的。

或者 vpand向量为 1,2,4,8,16, ... 2 的幂，然后 vpsadbw进行字节的水平添加。结果中的最低设置位告诉该 8 字节块中第一个 0 的位置。

或者你可以做 log2(vector_length) 混洗和屏蔽下一个元素的步骤，这样你最终会得到一个向量，其中输入中只有第一个 0 有 0xff元素。然后VPAND向量为 0,1,2,3,4,...和 vpsadbw到 hsum，唯一的非零元素将是字节位置。但这比vpcmpeqb贵得多/vpmovmskb/bsf/vmovd回到 XMM 寄存器，如果你出于某种原因真的想要 XMM 寄存器中的结果。

如果您不确定是否有任何零字节，请使用 tzcnt而不是 bsf ，因为它产生 32 (操作数大小)用于全零输入。 bsf在 AMD 上也较慢，所以实际上你应该总是使用 tzcnt这里 .
bsf如果输入为零，则不修改目的地。 (由 AMD 记录；英特尔说“未定义”但无论如何都实现了。)

和/或在位扫描后检查 ZF 以检测全零输入情况。 ( tzcnt 为全零输入设置CF，并根据输出是否为零设置ZF。)

另外，使用 vpxor XMM 将寄存器清零，不是 YMM .在 AMD 上节省 uop。