这段时间在优化服务耗时问题，其中perf打出来的热点显示，有一部分热点集中在string find. 由于之前看到sonic-cpp在使用simd加速string的一些操作，所以当时我想使用AVX2实现一版strstr来加速这个过程。但是在实现过程中，碰到一些问题,例如: 需要对输入进行对齐，类似是32、64字节，而输入字符串长度通常是不满足的，这样的话我们针对不同长度的字符串使用不同的指令，做起来还是有些繁琐的。幸运的是，我们找到了一个string库,做了相同的事情，而且支持多个指令集。通过引入该库，明显降低了在string操作上的热点，提升了响应速度。
1. stringzilla简介
stringzilla使用了SIMD做字符串常规操作的加速，支持多个指令集和多种语言。作者称It is up to 10x faster than the default and even other SIMD-accelerated string libraries in C, C++, Python, and other languages。以C/C++为例，支持find、rfind、hash、sort、copy、move等操作。header only,使用起来也很方便。
2. 常用操作
我们以C库为例，了解下其支持哪些常用操作。api集中在stringzilla.h文件头,只需要包含该文件即可。
首先定义了一个类似C++中string_view的sz_string_view_t，该类型是很多接口的入参类型。start指向的是数据首地址,length是string长度。
typedef struct sz_string_view_t {sz_cptr_t start;sz_size_t length;
} sz_string_view_t;
2.1 find
同多数接口一样，支持对称的操作,例如 rfind
std::string input = "abcdef";std::string target = "cde";sz_string_view_t src = {input.c_str(), input.size()};sz_string_view_t tar = {target.c_str(), target.size()};auto pos = sz_find(src.start, src.length, tar.start, tar.length);if (pos == SZ_NULL) {std::cout << "not found" << std::endl;return 0;}std::cout << pos << std::endl;
2.2 equal
等价于memcmp
2.3 hash
std::string input = "abcdef";
auto res = sz_hash(input.c_str(), input.size());
有了hash、equal之后，我们可以自定义hashmap. 例如下面这种unordered_set可以将sz_string_view_t作为其成员，避免了字符串拷贝。
2.4 其他
- copy
- move
- fill
- 随机数
3. 源码分析
以下源码以avx2指令集为例。
3.1 预备知识
3.1.1 查看机器支持的CPU指令集
cat /proc/cpuinfo flags可以看到机器支持的指令集。
3.1.2 avx2 的几个指令解释
- _mm256_set1_epi8, 使用8位的有符号整型填充256位
char src = 'a';__m256i ret = _mm256_set1_epi8(src);char * p = (char *)&(ret);for(int idx = 0; idx < 32; ++idx){std::cout << p[idx] << std::endl;}
- _mm256_lddqu_si256, 从256位整数内存地址中加载256位
char src = 'a';__m256i ret = _mm256_set1_epi8(src);__m256i tmp = _mm256_lddqu_si256(&ret);
- _mm256_cmpeq_epi8, 比较两个256位的整型向量中每8位是否相等。相同的位置结果设1，否则设0，所以返回值是无符号整型。
__m256i src1 = _mm256_set_epi32('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h');__m256i src2 = _mm256_set_epi32('a', 'b', 'c', 'd', 'e', 'f', 'g', '+');__m256i result = _mm256_cmpeq_epi8(src1, src2);for (int idx = 0; idx < 32; ++idx) {printf("%u,", ((unsigned char *)&result)[idx]);}// 'h'=0x00000068 '+'=0x0000002b// result: 0,0xFF,... 只有最后8位不等,同时考虑到入寄存器的顺序。所以输出结果只有第一个8位为0，其他位均为1
- _mm256_movemask_epi8, 对256位整型向量，按照每8位提取一个最高有效位，返回一个32位int数。
int mask = _mm256_movemask_epi8(result);printf("\n%x", mask);// 0xfffffffe, 对 3) 中result执行提取最该有效位。
- __builtin_ctz, 计算一个无符号整型从最低位开始第一个非0位的位置
int m = __builtin_ctz(mask);printf("%u\n", m);// 0Xffff fffe, 输出的是1
3.2 sz_find_byte_avx2
在源串中查找某个字符出现的位置。
首先是填充目标字符为32字节，256位向量。
然后，如果源串的长度大于32字节，则每次比较256位，通过_mm256_cmpeq_spi8逐字节进行比较，然后_mm256_movemask_epi8来提取最高位，也即是每一字节的匹配结果，然后求掩码的非0位即获得与目标字符匹配的位置。
其次，如果源串不足32位，则sz_find_byte_serial来实现查找。
该函数同样是先尽可能同时判断8字节，不足8字节的部分逐个比较。
(sz_u64_t)n[0] * 0x0101010101010101ull, 这一步是将单个字符扩充为8字节，64位。_sz_u64_each_byte_equal 是对64位实现按字节比较，返回对应掩码。
首先使用异或和取补操作，比较两个64位数，则相同部分是1，不同部分为0。接着按字节比较是否相等。vec.u64 & 0x7F7F7F7F7F7F7F7Full 先去除每个字节的最高位，vec.u64 & 0x8080808080808080ull提取每个字节的最高位。((vec.u64 & 0x7F7F7F7F7F7F7F7Full) + 0x0101010101010101ull), 这里是比较了每个字节的低7位是否相等，如果相等，加操作之后高位进1，变成0x80。同时如果高位为1，则单字节的结果为 0x80，表示单字节相等。
举个例子：
left.u64 = 0x1111111111111111;right.u64 = 0x1122222222222222;sz_u64_vec_t result = _sz_u64_each_byte_equal(left, right);
result结果为: 0x00 00 00 00, 00 00 00 80
sz_u64_ctz(match_vec.u64) / 8 为 63/8=7；如果输入字符为0x11,则说明在源串的第7字节(最高字节)找到了该字符。
3.3 sz_find
搞清楚了sz_find_byte_avx2的实现方式，我们再来看看sz_find是怎么实现的。
首先是根据宏定义选择合适的指令集
SZ_USE_X86_AVX512: avx512指令集
SZ_USE_X86_AVX2: avx2指令集
SZ_USE_ARM_NEON: arm处理器的NEON指令集
以avx指令集为例。
使用的是avx2 256位的寄存器，所以要求长度是大于32字节。首先是取目标字符串的首尾和中间三个位置的字符填充为256位，然后一次加载源字符串首尾和中间位置的32字节内容，接着分别进行比较，并获取掩码结果。掩码为1的部分表示源串与目标串首尾、中间字符相同的部分（这其实不太好理解，可以认为是在找源串中的一个位置，该位置很大可能是在结果集中的），得到这个位置后比较一次源串和目标串是否相等，相同直接返回，否则获取下一个掩码为1的位置。当目标串与源串长度差不够32位时，要使用其他的比较策略sz_find_serial。
sz_find_serial更为复杂，根据目标串长度，使用不同的查找函数。sz_find_byte_serial前面已经分析过了,我们来看一下_sz_find_2byte_serial。
双字节首先进行扩展(n_vec.u64 *= 0x0001000100010001ull), h_odd_vec,h_even_vec 分别存的是奇数起始、偶数起始向量。然后再64位上执行双字节比较(_sz_u64_each_2byte_equal, 与_sz_u64_each_byte_equal 相似的思路)。
总结
SIMD技术被应用于提高数据处理速度，但实现细节多、指令集不易理解，往往是服务优化的后续选择。而stringzilla 封装了多个指令集，提升了字符串处理速度，能够以较小改造成本提升服务表现。
