使用英特尔 AVX-512 的快速位集解码

在软件中，我们经常使用“位集”：您使用位数组来表示小整数集。它是一种简洁快速的数据结构。有时您想从位集（例如0b110011 ）转到整数（例如，在本例中为 0、1、4、5）。我们考虑“平均”密度（例如，每个 64 位字设置多个位）。

您可以检查每个位的值，但更好的选择是使用处理器具有快速指令的事实来计算“尾随零”的数量。给定 0b10001100100，这条指令会给你 2。这会给你第一个索引。然后，您需要使用诸如word & (word - 1)之类的代码取消设置此最低有效位。

而（字！ = 0 ） {   
    结果[ i ] = trailingzeroes (字) ;   
    单词=单词& (单词- 1 ) ;   
    我+ + ;   
  }   

这段代码的问题在于迭代次数可能难以预测，因此您可能经常导致处理器错误地预测分支数。在现代处理器上，错误预测代价高昂。通过进一步展开此循环，您可以做得更好。我在较早的博客文章中描述了如何。

英特尔最新处理器具有非常强大的新指令集 (AVX-512)。在这种情况下，它允许在没有任何分支和很少指令的情况下进行解码。关键是vpcompressd指令及其对应的 C/C++ Intel函数 ( _mm512_mask_compressstoreu_epi32 )。它的作用是给定最多 16 个整数，它只选择与位集中的位集相对应的那些。因此，给定数组 0,1,2,3….16 并给定位集 0b111010，您将生成输出 1,3,4,6。该函数不会告诉您写入了多少相关值，但您可以只计算一个的数量，并且方便地，我们有一个快速指令，可通过_popcnt64函数获得。因此，以下代码序列将处理 16 位掩码并将它们写入指针 ( base_ptr )。

 __m512i base_index = _mm512_setr_epi32 ( 0 , 1 , 2 , 3 , 4 , 5 ,   
    6、7、8、9、10、11、12、13、14、15 ) ； _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _   
   
  _mm512_mask_compressstoreu_epi32 ( base_ptr ,    
    掩码， base_index ） ；   
   
  base_ptr + = _popcnt64 （掩码） ；   

处理 64 位掩码的完整函数稍长一些，但它本质上只是简单序列的 4 个副本。

无效avx512_decoder ( uint32_t * base_ptr , uint32_t & base ,   
    uint32_t idx ， uint64_t 位） {   
  __m512i start_index = _mm512_set1_epi32 ( idx ) ;   
  __m512i base_index = _mm512_setr_epi32 ( 0 , 1 , 2 , 3 , 4 , 5 ,   
    6、7、8、9、10、11、12、13、14、15 ) ； _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _   
  base_index = _mm512_add_epi32 ( base_index , start_index ) ;   
  uint16_t 掩码；   
  掩码=位& 0xFFFF ;   
  _mm512_mask_compressstoreu_epi32 ( base_ptr + base ,    
    掩码， base_index ） ；   
  基础+ = _popcnt64 (掩码) ;   
  常量__m512i 常量 16 = _mm512_set1_epi32 ( 16 ) ;   
  base_index = _mm512_add_epi32 ( base_index , constant16 ) ;   
  掩码= (位>> 16 ) & 0xFFFF ;   
  _mm512_mask_compressstoreu_epi32 ( base_ptr + base ,    
     掩码， base_index ） ；   
  基础+ = _popcnt64 (掩码) ;   
  base_index = _mm512_add_epi32 ( base_index , constant16 ) ;   
  掩码= (位>> 32 ) & 0xFFFF ;   
  _mm512_mask_compressstoreu_epi32 ( base_ptr + base ,    
    掩码， base_index ） ；   
  基础+ = _popcnt64 (掩码) ;   
  base_index = _mm512_add_epi32 ( base_index , constant16 ) ;   
  掩码=位>> 48 ;   
  _mm512_mask_compressstoreu_epi32 ( base_ptr + base ,    
    掩码， base_index ） ；   
  基础+ = _popcnt64 (掩码) ;   
}   

使用 AVX-512 有一个缺点：在短时间内，当使用宽寄存器（512 位）时，处理器可能会降低其频率。您仍然可以在较短的寄存器上使用相同的指令（例如，使用_mm256_mask_compressstoreu_epi32而不是_mm512_mask_compressstoreu_epi32 ），但在这种情况下，指令数量会增加一倍。

在带有 GCC 的 skylake-x 处理器上，我的基准测试显示新的 AVX-512 甚至在频率限制方面也表现出色。与上述基本方法相比，AVX-512 方法使用的周期减少了 45%，时间减少了 33%。我们报告位集中每个值集的指令数、周期数和纳秒数。 AVX-512 不会产生分支错误预测。

我的代码可用。

AVX-512 例程具有创纪录的速度。也有可能改进例程。

原文： https://lemire.me/blog/2022/05/06/fast-bitset-decoding-using-intel-avx-512/