向量化检查哪些字节在一个集合中

这是一篇关于 SIMD 字节查找的文章,主要内容如下:

  • 引言:定义了问题是从字节流中获取指示哪些字节在预定义集合中的字节掩码或位掩码,SIMD 指令可使此任务比标量代码更快,文中展示了几种 SIMD 方法,包括通用算法、特殊情况算法和基本 SIMD 方法。
  • SIMD 算法:主要成分是 pshufb 指令,可在 16 字节寄存器中进行并行字节查找。
  • 通用算法:用 16x16 位的位图表示集合,通过低 4 位选择行,高 4 位选择列来测试字节是否在集合中。
  • 示例:以一个具体的集合为例,展示了如何使用通用算法检查字节是否在集合中。
  • 实现:通过一系列 SSE 指令实现通用算法,包括加载输入字节、提取低高 nibble、选择位图行、计算位掩码、选择行的一半以及最终检查字节是否在集合中。
  • 替代实现:可通过 pshufb 指令避免使用较慢的 blend 指令,需要不同的索引来获取不同的行。
  • 特殊情况 1 - 小集合:处理最多 8 个不同元素的集合,分别考虑低高 nibble 的子集,用位集编码子集,通过查找表进行转换和测试。
  • 特殊情况 2 - 常量 nibble:当集合值的高或低 nibble 是常量时,只需一次 pshufb 调用即可分类最多 16 个元素的集合。
  • 特殊情况 3 - 唯一低高 nibble:当低和高 nibble 都不重复时,只需两次 pshufb 调用即可分类最多 16 个元素的集合。
  • 基本 SIMD 方法:枚举了一些简单的 SIMD 方法,如比较集合元素与输入向量、比较输入向量与范围边界等。
  • 致谢:感谢 Geoff Langdale 和 Michael Howard 的评论和修复。
  • 源代码:可在 github 上获取源代码。
阅读 8
0 条评论