时间戳

首页 > 解决方案 > _mm_cmpistri 的模式 12

x86 - _mm_cmpistri 的模式 12

问题描述

2016 年论文中用于子字符串搜索的 Simd 算法：

bool like(const uint8_t* string, __m128i pat, [...]) {
    size_t i = 0;
    while (i + 16 < str_len) {
        __m128i str = _mm_loadu_si128(&string[i]);
        size_t j = _mm_cmpistri(pat, str, 12);  // mode 12
        if (j >= 16) i += 16;
        else {
            if (j + pat_len <= 16) return true;
            i += j;
        }
    }
    // Process remainder
    if (i + pat_len <= str_len) {
        __m128i str = _mm_loadu_si128(&string[i]);
        size_t j = _mm_cmpestri(pat, pat_len,
                                str, str_len - i, 12);
        if (j < 16 && j + pat_len <= 16) return true;
    }
    return false;
}

什么是模式 12 _mm_cmpistri？

这很慢吗？

谢谢。

标签： x86ssesimd

解决方案

pcmpistri在 Ryzen 上每 2 个时钟吞吐量一个，在 Skylake 上每 3 个时钟一个。它是更快的 SSE4.2 字符串指令之一，比显式长度指令更快。（https://agner.org/optimize/）。这对于子字符串搜索非常好，但对于更简单的strchr/memchr搜索则不适用：对于 memcmp，SSE4.2 字符串指令比 SSE2 快多少？和 SSE42 & STTNI - PcmpEstrM 比 PcmpIstrM 慢两倍，是真的吗？

请注意，您的标题提到_mm_cmpestri了显式长度字符串的慢速版本。但是您的代码使用_mm_cmpistri隐式长度字符串的快速版本。

（该搜索循环中的其余代码应该非常有效地编译。如果编译器使用分支而不是vs.cmov条件，分支预测 + 推测执行将隐藏依赖关系，因此多个迭代可以同时进行，在在输入向量末尾找到部分匹配的大多数情况下，分支未命中的成本。至少我认为这是条件。使用会在输入向量之间创建数据依赖关系，并且指令的延迟约为 2 或其吞吐量的 3 倍。）i+=16i+=jcmov

我不知道它与strstr使用 AVX2 的调优避免 SSE4.2 字符串指令相比有多好。 我猜这可能取决于您正在搜索的子字符串的长度，或者可能取决于数据的其他属性，例如您找到的字符串的开头或结尾有多少误报候选者。

您已经在https://github.com/WojciechMula/sse4-strstr上找到的微基准测试应该不错。Wojciech 编写了很好的代码，并且对各种 x86 uarches 的调优有足够的了解，以便真正优化。我没有查看他的字符串基准，但我查看了他的 popcnt 代码，该代码探索了将 Harley-Seal 与 AVX512F 一起使用vpernternlogd以实现大幅加速。

英特尔的 ISA 参考手册（第 2 卷）有一整节关于字符串指令的模式（第 4.1 节，“PCMPESTRI / PCMPESTRM / PCMPISTRI / PCMPISTRM 的 Imm8 控制字节操作”），与https://www.felixcloutier上的条目分开.com/x86/pcmpistri。

通常你会用十六进制或二进制写模式，而不是十进制，因为它有多个位域。 12 = 0b00001100.

英特尔的内在函数指南也包含有关操作的全部细节的伪代码，但如果您不了解高级目的，它会非常繁重。一旦你这样做，它会很有帮助。 https://software.intel.com/sites/landingpage/IntrinsicsGuide/#expand=2403,6062,4147,948&techs=SSE4_2,AVX,AVX2&text=pcmpi

另请参阅https://www.strchr.com/strcmp_and_strlen_using_sse_4.2以获得更易读的各种模式指南。在这里引用部分内容：

聚合操作

字符串处理指令的核心是聚合操作（立即位 [3:2]）。

  • ...

  • 等序（imm[3:2] = 11）。子字符串搜索 (strstr)。第一个操作数包含要搜索的字符串，第二个操作数是要搜索的字符串。如果在相应位置找到子字符串，则位掩码包括 1：

     operand2 = "WhenWeWillBeWed!", operand1 = "We"
 IntRes1  =  000010000000100

计算聚合函数后，可以对 IntRes1 进行补码，扩展为字节掩码（_mm_cmpistrm）或收缩为索引（_mm_cmpistri）。结果写入 xmm0 或 ECX 寄存器。英特尔手册很好地解释了这些细节，因此无需在此重复。

字节 ( ) 的低 2 位00表示字符格式：在本例中为00 unsigned BYTE.

（有符号与无符号可能与比较相等而不是基于范围的模式无关。）

我认为位 5:4 是“极性”，用于处理字符串的结尾。

位 6 是返回索引而不是掩码的指令的“索引”版本的位扫描方向。（如bsr与bsf）。 0在这种情况下，查找第一个匹配的开始而不是最后一个匹配的结束。

第 7 位（8 位立即数的高位）未使用/保留。

另请参阅https://www.officedaytime.com/simd512e/simdimg/str.php?f=pcmpistri以获取导致结果的步骤的表格/图表，以及立即修改/选择在各种步骤。

推荐阅读