c - 为什么 SSE4.2 cmpstr 比常规代码慢？
问题描述
我正在尝试验证一个必须只包含 ASCII 可见字符、空格和 \t 的字符串。
但似乎 ASCII 表查找比在大多数 CPU 上使用 _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);
});
}
用它编译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
我还检查了程序集输出，并且 search_sse4cmpstr 使用 vpcmpestri 而 search_table 是非矢量化的。
我用错了吗？或者为什么这个指令存在？
编辑：正如评论中所指出的，cmpistr（具有较少参数的隐式长度指令）比 cmpestr 稍快，有时比表查找快。
但是，SSE2 按位和整数运算似乎更快。
EDIT2 Peter Cordes 找到了正确的答案。我已在新答案中添加了修改后的程序，因此如果您对 cmpstr 感兴趣，请查看此程序。
不要使用上面的代码！
解决方案
i该代码对前一个向量有不必要的依赖，在pcmpestri大约 12 + 5 个周期的 + L1d 负载使用延迟上成为瓶颈。 （https://agner.org/optimize/和https://uops.info/）所以是的，很遗憾，你用错了。
如果您将其编写为类似于标量循环，i+=16并且只是将pcmpestri结果作为循环退出条件进行检查，那么您的 Sandybridge 系列 CPU 上每 4 个时钟 1 个向量的吞吐量就会成为瓶颈。（特别是 SnB 和 IvB）。
或者，如果您的输入可以使用pcmpistri，那么情况就不那么糟糕了，并且可以在 Sandybridge-family 上以每 3 个时钟 1 个频率运行。
起初我没有注意到这个问题，因为我没想到循环会这样写，而且 asm 循环中还有其他混乱。：/我花了很多时间进行分析，perf以确保它不是我 Skylake CPU 上的微编码（8 uop）指令的前端瓶颈。查看现在存档的评论。
吞吐量瓶颈将使您以大约 4 个字节/周期的速度运行，而另一种方式大约为 1 个（每个输入字节加载 2 次，而英特尔因为 SnB 可以每个时钟执行 2 次加载）。所以加速了 4 倍。或以 1/时钟负载吞吐量将 Nehalem 提高 8 倍。
巧合的是，延迟瓶颈大约是每个输入字节大约 1 个周期，与表查找大致相同。
另外，不要使用len - i < 16; gcc 实际上是在循环内部计算出额外的 uops 成本。i < len-15知道后使用len>=16。（无符号类型使这变得很棘手，因为它们在零处包装；您希望它编译为一个 cmp/jcc 以跳过循环，然后是一个do{}whileasm 循环结构。所以初始len>=16真的与正常的循环条件是分开的。）
其他有趣的事实pcmpestri：
- 对于 memcmp，SSE4.2 字符串指令比 SSE2 快多少？（速度较慢，尤其是 AVX2）
- SSE42 & STTNI - PcmpEstrM 比 PcmpIstrM 慢两倍，是真的吗？是的，显式长度版本比隐式长度版本慢。
0显然，与在现有输入中扫描一个字节相比，基于额外 2 个长度输入的屏蔽更慢，并且花费更多的微指令。 - 性能不取决于立即数的值。有一次我认为确实如此，但这
i取决于结果，因此更改立即数会导致缓存行拆分，从而使循环延迟更糟。i+=16用循环重新测试显示没有效果。 - 如果与 REX.W 前缀一起使用（在 RAX 和 RDX 中而不是 EAX 和 EDX 中获取输入），英特尔的速度要慢得多（根据https://uops.info/），但没有内在的，所以你不要'不必担心编译器会这样做。
或者为什么这个指令存在？
这些说明是在 Nehalem 中介绍的。如果英特尔“赶上”并被广泛使用，例如短字符串，英特尔可能已经计划让它们更快strcmp。但是如果没有故障抑制（对于可能跨入新页面的未对齐负载），如果不检查有关指针的内容，它们就很难使用。如果您无论如何都要进行检查，那么您不妨使用高效的pcmpeqb/pmovmskb更少的微指令。pminub并且可能使用/ pcmpeqb/ pmovmskb->找到任一字符串中的第一个零bsf。可能有一个 SSE4.2 的用例用于 a 的初始启动strcmp，但是一旦你开始就没有那么多了。
世界上大多数人关心的是 UTF-8，而不是 8 位字符集。并且由于 UTF-16 不再是固定宽度的（多亏了 32 位 Unicode），即使是宽字符的东西也很难用这些来加速。
使用范围功能基本上需要手动矢量化，这对于只处理 ASCII 的东西来说是很多工作。
正如您所发现的，对于简单的情况，您可以更快地使用pcmpgtb布尔逻辑。使用 AVX2，您可以一次处理 32 个字节而不是 16 个字节，但是没有 AVX2 版本vpcmpistri，只有 16 字节指令的 AVX1 VEX 编码。
推荐阅读
- ios - 在 iOS 13 中使用什么来代替 UIImagePickerControllerReferenceURL？
- database - 将图像保存在房间数据库中
- php - 在管理产品编辑中访问和编辑 WooCommerce 产品元数据
- artifactory - 删除 6 个月未下载的工件
- google-cloud-platform - Google Cloud Storage 中的 Concat Avro 文件
- linux - 如何使用 docker-compose 使用主机网络配置
- email - 向 exim4 添加自定义标头
- c++ - 为什么即使在使用 constexr if 时我也会得到“使用未声明的标识符”？
- tekton - 使用具有多个部署的多个存储库实施 Tekton 的最佳实践是什么
- c# - 无法使用 Office 互操作签出文件