string - 使用 SSE4.2 或更早版本优化 find_first_not_of
问题描述
我正在为协议编写文本数据包分析器,并在优化它时发现find_first_not_of
调用是一个很大的瓶颈。
从本质上讲,如果一个数据包只包含有效字符,我需要查找它是否有效,这比默认的 C++ 函数要快。
例如,如果所有允许的字符都是f
, h
, o
,t
和w
, 在 C++ 中我只会调用s.find_first_not_of("fhotw")
, 但在 SSEx 中我不知道在将字符串加载到一组__m128i
变量中之后。
显然,_mm_cmpXstrY
函数文档在这方面并没有真正帮助我。(例如_mm_cmpistri
)。起初我可以减去_mm_sub_epi8
,但我认为这不是一个好主意。
此外,我坚持使用 SSE(任何版本)。
解决方案
Wojciech Muła 的这篇文章描述了一种 SSSE3 算法来接受/拒绝任何给定的字节值。(与文章相反,应该使用饱和算法进行范围检查,但我们没有范围。)
SSE4.2 字符串函数通常比手工编写的函数慢。例如,pcmpistri
SSE4.2 字符串指令中最快的 Skylake 上的 3 uops、3 周期吞吐量。与每 16 个字节的输入 1 个 shuffle 和 1 个 pcmpeqb 相比,使用 SIMD AND 和 movemask 组合结果。加上一些加载和寄存器复制指令,但仍然很可能比每 3 个周期 1 个向量快。不过,处理短的以 0 结尾的字符串并不那么容易;如果您还需要担心这一点,SSE4.2 值得考虑,而不是已知大小的块是矢量宽度的倍数。
对于“fhotw”,请尝试:
#include <tmmintrin.h> // pshufb
bool is_valid_64bytes (uint8_t* src) {
const __m128i tab = _mm_set_epi8('o','_','_','_','_','_','_','h',
'w','f','_','t','_','_','_','_');
__m128i src0 = _mm_loadu_si128((__m128i*)&src[0]);
__m128i src1 = _mm_loadu_si128((__m128i*)&src[16]);
__m128i src2 = _mm_loadu_si128((__m128i*)&src[32]);
__m128i src3 = _mm_loadu_si128((__m128i*)&src[48]);
__m128i acc;
acc = _mm_cmpeq_epi8(_mm_shuffle_epi8(tab, src0), src0);
acc = _mm_and_si128(acc, _mm_cmpeq_epi8(_mm_shuffle_epi8(tab, src1), src1));
acc = _mm_and_si128(acc, _mm_cmpeq_epi8(_mm_shuffle_epi8(tab, src2), src2));
acc = _mm_and_si128(acc, _mm_cmpeq_epi8(_mm_shuffle_epi8(tab, src3), src3));
return !!(((unsigned)_mm_movemask_epi8(acc)) == 0xFFFF);
}
使用数据的低 4 位,我们可以从我们的集合中选择一个具有该低半字节值的字节。例如'o'
(0x6f) 进入表的高字节,因此表单的输入字节0x?f
尝试与之匹配。即它是 的第一个元素_mm_set_epi8
,从高到低。
有关其他特殊/更一般情况的此技术的变体,请参阅完整文章。
推荐阅读
- algorithm - 来自未排序点数组的近似线段
- javascript - 将JS合并为一个文件后,slick不起作用
- ios - Xcode 12 - AppName 的架构 (arm64) 不包括 iPhone 11 Pro 可以执行的架构(英特尔 64 位)
- javascript - mapbox-gl 中的集群属性
- javascript - 简单的 React 文件上传,不附加表单数据
- javascript - 从本地主机上的不同端口获取错误
- java - 使用 JavaServer Pages (jsp) 创建下拉导航栏
- python - 使用 python OS 模块配置 databricks-connect
- android - Gradle 构建失败并出现内存不足:Java 堆空间错误
- windows-10 - Nuget 包管理器未在 Visual Studio 2019 中恢复包