_mm_cmpistri 模式 12

Question

Simd子串搜索算法2016paper:

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;
}

_mm_cmpistri 的模式 12 是什么？

这很慢吗？

谢谢。

Answer 1

pcmpistri 在 Ryzen 上每 2 个时钟吞吐量一个，在 Skylake 上每 3 个时钟吞吐量一个。它是更快的 SSE4.2 字符串指令之一，比 explicit-length 指令还快。 (https://agner.org/optimize/). It's pretty good for substring searches, but not for simpler strchr / memchr searches: How much faster are SSE4.2 string instructions than SSE2 for memcmp? and SSE42 & STTNI - PcmpEstrM is twice slower than PcmpIstrM, is it true?

请注意，您的标题提到了 _mm_cmpestri，explicit-length 字符串的慢速版本。但是您的代码使用 _mm_cmpistri，implicit-length 字符串的快速版本。

（该搜索循环中的其余代码应该非常有效地编译。如果编译器使用分支而不是 cmov 作为 i+=16 与 i+=j 条件，分支prediction + speculative execution 将隐藏依赖关系，因此可以同时进行多次迭代，对于大多数在输入向量末尾找到部分匹配的情况，代价是分支未命中。至少我认为这就是条件for. 使用 cmov 会在输入向量之间产生数据依赖性，并且指令的延迟是其吞吐量的 ~2 或 3 倍。）

我不知道它与使用避免 SSE4.2 字符串指令的 well-tuned strstr 的 well-tuned strstr 相比效果如何。 我会我猜这可能取决于您要搜索的子字符串的长度，或者可能是数据的其他属性，例如您找到的字符串开头或结尾有多少 false-positive 个候选对象。

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

Intel's ISA ref manual (vol.2) has a whole section about modes for string instructions (Section 4.1, “Imm8 Control Byte Operation for PCMPESTRI / PCMPESTRM / PCMPISTRI / PCMPISTRM”), separate from the entry on https://www.felixcloutier.com/x86/pcmpistri.

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

Intel 的内在函数指南也有关于操作的完整细节的伪代码，但如果您不知道 high-level 的目的，它会非常繁重。一旦你这样做了，它会很有帮助。 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 以获得更易读的各种模式指南。此处引用部分内容：

Aggregation operations

The heart of a string-processing instruction is the aggregation operation (immediate bits [3:2]).
...
Equal ordered (imm[3:2] = 11). Substring search (strstr). The first operand contains a string to search for, the second is a string to search in. The bit mask includes 1 if the substring is found at the corresponding position:
 operand2 = "WhenWeWillBeWed!", operand1 = "We"
 IntRes1  =  000010000000100
After computing the aggregation function, IntRes1 can be complemented, expanded into byte mask (_mm_cmpistrm) or shrinked into index (_mm_cmpistri). The result is written into xmm0 or ECX registers. Intel manual explains these details well, so there is no need to repeat them here.

字节的低2位（00）表示字符格式：本例为00 unsigned BYTE.

（有符号与无符号可能与比较相等性的模式无关，而不是 range-based。）

位5:4是"polarity"，用于处理字符串的结尾，我想。

第 6 位是 bit-scan 指令的 "index" 版本的方向，return 是索引而不是掩码。（比如 bsr 与 bsf）。 0 在这种情况下找到第一场比赛的开始而不是最后一场比赛的结束。

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

另请参阅 https://www.officedaytime.com/simd512e/simdimg/str.php?f=pcmpistri 以获取导致结果的步骤的表格/图表，以及即时修改中的不同字段/select 在各个步骤执行的操作.

_mm_cmpistri 模式 12

Mode 12 of _mm_cmpistri

x86

sse

simd