检查是否缺少字符串，简单的 AVX-512 版本

假设您想要检查某个字符串是否存在于大型文档中。在 C 中，您可以使用标准函数strstr执行以下操作：

 bool is_present = strstr ( mydocument , needle ) ;  
   

它很简单，而且可能非常快。

你能做得更好吗？

最近的 Intel 和 AMD 处理器具有在 512 位寄存器上运行的指令。所以我们可以使用一条指令比较 64 个字节。搜索字符串的最简单算法可能如下所示……

1. 从我们的输入文档中加载 64 个字节，将它们与目标字符串第一个字符的 64 个副本进行比较。
2. 如果找到匹配项，则加载目标字符串的第二个字符，在一个寄存器内将其复制 64 次。从我们的输入文档中加载 64 个字节，偏移量为一个字节。
3. 根据需要对第二个、第三个等等字符重复……
4. 然后在输入中前进 64 个字节并重复。

使用 Intel 内部函数，算法如下所示：

    
   
  对于( size_t i = 0 ; . . . ; i + = 64 ) {  
   
    __m512i 比较器= _mm512_set1_epi8 （针[ 0 ] ） ；  
   
    __m512i 输入= _mm512_loadu_si512 ( in + i ) ;  
   
    __mmask64 匹配= _mm512_cmpeq_epi8_mask （比较器，输入） ；  
   
    for ( size_t char_index = 1 ;匹配 && char_index < needle_len ;   
   
         字符索引+ + ) {  
   
      比较器= _mm512_set1_epi8 （针[ char_index ] ） ；  
   
      input = _mm512_loadu_si512 ( in + i + char_index ) ;  
   
      比赛=  
   
          _kand_mask64 （匹配， _mm512_cmpeq_epi8_mask （比较器，输入） ） ；  
   
    }  
   
    如果（匹配） {返回真； }  
   
  }  
   
  返回假；  
   

这是我能想到的最简单的算法。

我们现在要根据strstr对其进行基准测试。为了让它变得有趣，我将选择一个字符串，它设计为在输入文档中重复“几乎”，除了它的最后一个字符。这是最坏的情况。

我在 Intel Icelake 处理器上使用 GCC 11。我的基准测试的源代码是可用的。

不出所料，我天真的 AVX-512 方法在此基准测试中的字符串长度扩展性很差。然而，这有点悲观，我希望通过更现实的用例获得更好的结果。

应该可以通过更复杂的方式做得更好。然而，对于短字符串，我们的速度已经是strstr的两倍，这令人鼓舞。

原文： https://lemire.me/blog/2022/12/15/checking-for-the-absence-of-a-string-naive-avx-512-edition/