那些遇到过的问题

为什么 SSE4.2 cmpstr 比常规代码慢？

ner*_*wim 5 c performance x86 assembly sse

我正在尝试验证一个只能包含 ASCII 可见字符、空格和 \t 的字符串。

但在大多数 CPU 上，ASCII 表查找似乎比带有 _SIDD_CMP_RANGES 的 _mm_cmpestri 指令更快。我已经在 i5-2410M、i7-3720QM、i7-5600U 和未知类型的 KVM 虚拟化 Xeon 上进行了测试，只有最后一个矢量化版本速度更快。

我的测试代码在这里：

#include <stdio.h>
#include <string.h>
#include <inttypes.h>
#include <sys/time.h>
#include <sys/mman.h>
#include <immintrin.h>
#include <stdalign.h>
#include <stdlib.h>

#define MIN(a,b) (((a)<(b))?(a):(b))

#define ALIGNED16 alignas(16)

#define MEASURE(msg,stmt) { \
    struct timeval tv; \
    gettimeofday(&tv, NULL); \
    uint64_t us1 = tv.tv_sec * (uint64_t)1000000 + tv.tv_usec; \
    stmt; \
    gettimeofday(&tv, NULL); \
    uint64_t us2 = tv.tv_sec * (uint64_t)1000000 + tv.tv_usec; \
    printf("%-20s - %.4fms\n", msg, ((double)us2 - us1) / 1000); \
}

// Character table
#define VWSCHAR(c)  (vis_ws_chars[(unsigned char)(c)])   // Visible characters and white space
#define YES     1,
#define NO      0,
#define YES16   YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES
#define NO16    NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO
#define NO128   NO16 NO16 NO16 NO16 NO16 NO16 NO16 NO16

// Visible ASCII characters with space and tab
ALIGNED16 static const int vis_ws_chars[256] = {
// NUL SOH STX ETX EOT ENQ ACK BEL BS  HT  LF  VT  FF  CR  SO  SI
   NO  NO  NO  NO  NO  NO  NO  NO  NO  YES NO  NO  NO  NO  NO  NO
// DLE DC1 DC2 DC3 DC4 NAK SYN ETB CAN EM  SUB ESC FS  GS  RS  US
   NO16
// SP  !   "   #   $   %   &   '   (   )   *   +   ,   -   .   /
// 0   1   2   3   4   5   6   7   8   9   :   ;   <   =   >   ?
// @   A   B   C   D   E   F   G   H   I   J   K   L   M   N   O
// P   Q   R   S   T   U   V   W   X   Y   Z   [   \   ]   ^   _
// `   a   b   c   d   e   f   g   h   i   j   k   l   m   n   o
   YES16 YES16 YES16 YES16 YES16
// p   q   r   s   t   u   v   w   x   y   z   {   |   }   ~   DEL
   YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO
// Non-ASCII characters
   NO128
};

size_t search_logic(const char* data, size_t len) {
    __m128i ht = _mm_set1_epi8('\t');
    //__m128i del = _mm_set1_epi8(0x7f);
    __m128i td = _mm_set1_epi8('~');
    __m128i sp_m1 = _mm_set1_epi8(' ' - 1);
    size_t i = 0;
    while (len - i >= 16) {
        __m128i c = _mm_loadu_si128((const __m128i *) (data + i));
        // (!((c < del) && (c >= sp)) && (c != ht)) == 0
        //if(!_mm_testc_si128(_mm_and_si128(_mm_cmpgt_epi8(c, sp_m1), _mm_cmplt_epi8(c, del)), _mm_xor_si128(c, ht)))
            //break;
        // !(c == del) && ((c == ht) || (c >= sp)) == 1
        //if(!_mm_test_all_ones(_mm_andnot_si128(_mm_cmpeq_epi8(c, del), _mm_or_si128(_mm_cmpeq_epi8(c, ht), _mm_cmpgt_epi8(c, sp_m1)))))
            //break;
        // (((c != ht) && (c >= sp)) && (c > td)) == 0
        if(!_mm_test_all_zeros(_mm_and_si128(_mm_xor_si128(c, ht), _mm_cmpgt_epi8(c, sp_m1)), _mm_cmpgt_epi8(c, td)))
            break;
        i += 16;
    }
    // Check last 15 bytes
    for (; i < len; ++i) {
        if (!VWSCHAR(data[i])) {
            break;
        }
    }
    return i;
}

size_t search_table(const char* data, size_t len)
{
    // Search non-matching character via table lookups
    size_t i = 0;
    while (len - i >= 16) {
        if (!VWSCHAR(data[i + 0])) break;
        if (!VWSCHAR(data[i + 1])) break;
        if (!VWSCHAR(data[i + 2])) break;
        if (!VWSCHAR(data[i + 3])) break;
        if (!VWSCHAR(data[i + 4])) break;
        if (!VWSCHAR(data[i + 5])) break;
        if (!VWSCHAR(data[i + 6])) break;
        if (!VWSCHAR(data[i + 7])) break;
        if (!VWSCHAR(data[i + 8])) break;
        if (!VWSCHAR(data[i + 9])) break;
        if (!VWSCHAR(data[i + 10])) break;
        if (!VWSCHAR(data[i + 11])) break;
        if (!VWSCHAR(data[i + 12])) break;
        if (!VWSCHAR(data[i + 13])) break;
        if (!VWSCHAR(data[i + 14])) break;
        if (!VWSCHAR(data[i + 15])) break;
        i += 16;
    }
    // Check last 15 bytes
    for (; i < len; ++i) {
        if (!VWSCHAR(data[i])) {
            break;
        }
    }
    return i;
}

size_t search_sse4cmpstr(const char* data, size_t len)
{
    static const char legal_ranges[16] = {
        '\t', '\t',
        ' ',  '~',
    };
    __m128i v1 = _mm_loadu_si128((const __m128i*)legal_ranges);
    size_t i = 0;
    while (len - i >= 16) {
        __m128i v2 = _mm_loadu_si128((const __m128i*)(data + i));
        unsigned consumed = _mm_cmpestri(v1, 4, v2, 16, _SIDD_LEAST_SIGNIFICANT|_SIDD_CMP_RANGES|_SIDD_UBYTE_OPS|_SIDD_NEGATIVE_POLARITY);
        i += consumed;
        if (consumed < 16) {
            return i;
        }
    }
    // Check last 15 bytes
    for (; i < len; ++i) {
        if (!VWSCHAR(data[i])) {
            break;
        }
    }
    return i;
}

size_t search_sse4cmpstr_implicit(const char* data, size_t len)
{
    static const char legal_ranges[16] = {
        '\t', '\t',
        ' ',  '~',
    };
    __m128i v1 = _mm_loadu_si128((const __m128i*)legal_ranges);
    size_t i = 0;
    while (len - i >= 16) {
        __m128i v2 = _mm_loadu_si128((const __m128i*)(data + i));
        unsigned consumed = _mm_cmpistri(v1, v2, _SIDD_LEAST_SIGNIFICANT|_SIDD_CMP_RANGES|_SIDD_UBYTE_OPS|_SIDD_NEGATIVE_POLARITY);
        i += consumed;
        if (consumed < 16) {
            return i;
        }
    }
    // Check last 15 bytes
    for (; i < len; ++i) {
        if (!VWSCHAR(data[i])) {
            break;
        }
    }
    return i;
}

int main()
{
    printf("Setting up 1GB of data...\n");
    size_t len = 1024 * 1024 * 1024 + 3;
    char* data = (char*)mmap(NULL, len, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_POPULATE, -1, 0); // Aligned
    srand(0);
    for (size_t i = 0; i < len; ++i) {
        const char v = rand() % 96;
        data[i] = v == 95 ? '\t' : ' ' + v;
    }
    size_t end = len - 2;
    data[end] = '\n'; // Illegal character to be found

    MEASURE("table lookup", {
        size_t i = search_table(data, len);
        if (i != end) printf("INCORRECT RESULT: %zu instead of %zu", i, end);
    });
    MEASURE("cmpestr ranges", {
        size_t i = search_sse4cmpstr(data, len);
        if (i != end) printf("INCORRECT RESULT: %zu instead of %zu", i, end);
    });
    MEASURE("cmpistr ranges", {
        size_t i = search_sse4cmpstr_implicit(data, len);
        if (i != end) printf("INCORRECT RESULT: %zu instead of %zu", i, end);
    });
    MEASURE("logic ranges", {
        size_t i = search_logic(data, len);
        if (i != end) printf("INCORRECT RESULT: %zu instead of %zu", i, end);
    });
}
Run Code Online (Sandbox Code Playgroud)

编译gcc -O3 -march=native -pedantic -Wall -Wextra main2.cpp它给了我这些结果：

Setting up 1GB of data...
table lookup         - 476.4820ms
cmpestr ranges       - 519.3350ms
cmpistr ranges       - 497.5770ms
logic ranges         - 153.2650ms
Run Code Online (Sandbox Code Playgroud)

我还检查了程序集输出，search_sse4cmpstr 使用 vpcmpestri，而 search_table 是非矢量化的。

难道是我用错了？或者为什么这条指令存在？

编辑：正如评论中所指出的，cmpistr（带有较少参数的隐式长度指令）比 cmpestr 稍快，有时比表查找更快。

然而，SSE2 按位和整数运算似乎更快。

EDIT2 Peter Cordes 找到了正确的答案。我已在新答案中添加了修改后的程序，因此如果您对 cmpstr 感兴趣，请查看此答案。

不要使用上面的代码！

Pet*_*des 4

i该代码对前一个向量有不必要的依赖，pcmpestri造成约 12 + 5 个周期的 + L1d 加载使用延迟的瓶颈。 （https://agner.org/optimize/和https://uops.info/）所以，是的，不幸的是，你用错了它。

如果您将其编写为类似于标量循环，执行i+=16并仅检查pcmpestri结果作为循环退出条件，则您的 Sandybridge 系列 CPU 上每 4 个时钟 1 个向量的吞吐量将成为瓶颈。（特别是 SnB 和 IvB）。

或者，如果您的输入可以使用pcmpistri，那么情况会好一些，并且可以在 Sandybridge 系列上达到每 3 个时钟 1 次。

我一开始没有注意到这个问题，因为我没想到循环会这样写，而且 asm 循环中还有其他混乱。：/我花了很多时间进行分析，perf以确保它不是我的 Skylake CPU 上的微编码（8 uop）指令的前端瓶颈。请参阅现已存档的评论。

吞吐量瓶颈会让您以大约 4 字节/周期的速度运行，而另一种方式则为大约 1 字节/周期（每个输入字节 2 个负载，Intel 因为 SnB 每个时钟可以执行 2 个负载）。所以加速了 4 倍。或者 Nehalem 上的 8 倍，负载吞吐量为 1/时钟。

巧合的是，延迟瓶颈约为每个输入字节 1 个周期，与表查找大致相同。

另外，不要使用len - i < 16; gcc 实际上在循环内计算了这一点，消耗了额外的 uops。i < len-15一旦知道就使用len>=16。（无符号类型使这个问题变得棘手，因为它们在零处换行；您希望它编译为 cmp/jcc 以跳过循环，然后是 asmdo{}while循环结构。因此初始len>=16确实与正常循环条件分开。）

其他有趣的事实pcmpestri：

  • 对于 memcmp，SSE4.2 字符串指令比 SSE2 快多少？（速度较慢，尤其是使用 AVX2）
  • SSE42 和 STTNI - PcmpEstrM 比 PcmpIstrM 慢两倍，这是真的吗？是的，显式长度版本比隐式长度版本慢。显然，基于额外 2 个长度输入的掩码比扫描0现有输入中的字节更慢并且花费更多的微指令。
  • 绩效并不取决于即时的价值。我一度认为是这样，但这取决于i结果，因此更改立即数会导致缓存行分裂，从而使循环延迟变得更糟。用循环重新测试i+=16没有效果。
  • 如果与 REX.W 前缀一起使用（在 RAX 和 RDX 中获取输入，而不是 EAX 和 EDX），对于 Intel 来说会慢得多（根据https://uops.info/），但没有内在的，所以你不需要不必担心编译器会这样做。

或者为什么这条指令存在？

这些指令是在 Nehalem 中引入的。如果它们“流行起来”并被广泛使用（例如短字符串），英特尔可能会计划让它们变得更快strcmp。但是如果没有错误抑制（对于可能跨入新页面的未对齐加载），如果不检查有关指针的内容，它们就很难使用。如果你无论如何都要进行检查，你不妨使用一个有效的pcmpeqb/pmovmskb更少的微指令。也许可以使用pminub// ->找到任一字符串pcmpeqb中的第一个零。也许 SSE4.2 在 的初始启动中有一个用例，但一旦开始使用就不那么频繁了。pmovmskbbsfstrcmp

世界上大多数人关心的是 UTF-8，而不是 8 位字符集。由于 UTF-16 不再是固定宽度的（多亏了 32 位 Unicode），即使是宽字符的东西也很难用它们来加速。

使用范围功能基本上需要手动矢量化，这对于仅处理 ASCII 的东西来说是大量工作。

正如您所发现的，对于简单的情况，您可以使用pcmpgtb布尔逻辑更快地进行。使用 AVX2，您可以一次处理 32 个字节而不是 16 个字节，但是没有 AVX2 版本vpcmpistri，只有 16 字节指令的 AVX1 VEX 编码。

归档时间：

查看次数：

1003 次

最近记录：

6 年，3 月 前
SSE42和STTNI - PcmpEstrM比PcmpIstrM慢两倍,是真的吗？ 7
对于memcmp,SSE4.2字符串指令比SSE2快多少？ 2
更多相关链接
相关归档
对于数组中的每个元素，我们如何计算右侧大于该元素的元素数？ 20
函数调用在Haskell中有多少开销？ 17
为什么在一个简单的应用程序中有这么多GC_FOR_ALLOC？ 15
如何通过访问时间而不是创建时间来优先等待 CompletableFutures？ 8
x86架构中的"EU"是什么？(计算有效地址？) 7
php处理包含文件 7
ArrayList的性能 7
SSE和AVX的频道/通道改组？ 6
在(Visual)C++中调用动态创建函数的约定 5
用于英特尔处理器的TLB ASID标签中有多少位？以及如何处理“ ASID溢出”？ 4
难疑归档
在JavaScript中深度克隆对象的最有效方法是什么？ 5181
什么是JSONP,为什么创建它？ 2040
如何为C#Auto-Property提供默认值？ 1773
为什么在数组迭代中使用"for ... in"是一个坏主意？ 1761
安全地将JSON字符串转换为对象 1298
我是否提交了由npm 5创建的package-lock.json文件？ 1164
如何使用Windows开发机器为iPhone开发？ 1161
按列名从pandas DataFrame中删除列 1136
将先前的提交分解为多个提交 1113
在Ruby on Rails中对nil v.空v.空白的简要解释 1098