sse4.2 的字符串操作指令
前段时间实现了基于 Succinct Data Structure 的自动机，这种自动机（内存）存储方式将状态转移的 label 单独存储起来，从而，查找 label 就是一个在 byte 数组中查找 byte 的操作，并且，绝大多数情况下，需要查找的这个 byte 数组都非常短（状态的平均转移(label)数一般情况下大约是 2 ）。
于是，我发现了 _mm_cmpestri intrinsic 函数(会被编译器翻译成 pcmpestr 指令)：
|
1 2 3 4 5 6 7 |
int _mm_cmpestri ( __m128i a, int la, __m128i b, int lb, const int mode ); |
intel 官方资料说这个函数的 latency 是 7~11 个 CPU clock，是相当快的了，虽然还是比一般的简单指令慢，但是比除法指令要快5~10倍！
有趣的是，在使用这条指令时，触发了 gcc-4.7 的一个bug (当时把它发在了新浪微博上)：
gcc -O0 为 _mm_cmpestri 产生了错误的代码
天狼星_Sirius 发布于2014年6月26日 18:23
sse4.2 指令 pcmpestri 的操作数可以是内存或 xmm 寄存器，一个操作数是内存时，不要求内存对齐。但 load xmm 寄存器需要内存对齐，gcc -O0 不优化，于是产生了一条 load xmm 和一条 pcmpestr xmm1 xmm2 指令，结果在 load xmm 时 SegFault 了！
换 -O2，省掉了 load xmm 指令， 生成 pcmpestr memptr xmm 指令，一切 OK。
intel icc 编译器则无此问题
实际的 byte 查找函数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#if defined(__SSE4_2__) #include <nmmintrin.h> inline int // _mm_cmpestri length param is int32 sse4_2_search_byte(const byte_t* data, int len, byte_t key) { __m128i key128 = { key }; // sizeof(__m128i)==16 assert(len <= 16); int idx = _mm_cmpestri(key128, 1, *(const __m128i*)data, len, // don't require memory align _SIDD_UBYTE_OPS|_SIDD_CMP_EQUAL_ORDERED|_SIDD_LEAST_SIGNIFICANT); if (idx < 16) // _mm_cmpestri returns 16 when not found return idx; else return len; } inline size_t fast_search_byte(const byte_t* data, size_t len, byte_t key) { if (len <= 16) return sse4_2_search_byte(data, len, key); else return binary_search_byte(data, len, key); } #else #define fast_search_byte binary_search_byte #endif |
当然，在实际中，如果转移数大于等于32，就直接用位图 + popcnt 来查找了。
