使用 AVX-512 更快地从字符串中删除字符

在软件中，想要从字符串中删除特定字符是一个常见问题。为了使问题更准确，让我们考虑删除所有 ASCII 控制字符和空格。实际上，这意味着删除所有小于或等于 32 的字节值。

我之前讨论过一个相关的问题，即从字符串中删除所有空格。当时，我得出的结论是，最快的方法可能是使用 SIMD 指令和大型查找表。 SIMD 指令可以在任何给定时间对多个字进行操作：大多数商品处理器的指令一次可以对 16 个字节进行操作。因此，例如，使用一条指令，您可以比较 16 个连续字节并识别所有空格的位置。完成后，您必须以某种方式移动不需要的字符。大多数指令集没有用于此目的的指令，但是 x64 处理器有一条指令可以移动字节，只要您有预先计算的 shuffle 掩码 ( pshufb )。 ARM NEON 也有类似的指令。因此，您按以下方式进行：

1. 识别块中所有不需要的字符（例如，16 个字节）。
2. 在大表中查找洗牌掩码。
3. 使用 shuffle 掩码移动不需要的字节。

这种方法速度很快，但可能需要大表。事实上，如果你加载 16 个字节，你需要一个包含 65536 个随机掩码的表。存储这么大的表不是很实用。

最近的英特尔处理器有方便的新指令，可以完全满足我们的要求：它们会删除不需要的字节（ vpcompressb ）。它需要具有AVX-512 VBMI2的最新处理器，例如 Ice Lake、Rocket Lake、Alder Lake 或 Tiger Lake 处理器。英特尔很难确定哪个处理器上具有哪些功能，因此您需要进行一些研究，以确定您最喜欢的英特尔处理器是否支持所需的指令。 AMD 处理器不支持 VBMI2。

除了新指令之外，AVX-512 还允许您以更大的块（64 字节）处理数据。使用 Intel 指令，代码几乎是可读的。我创建了一个只包含空间字节的寄存器，然后迭代我的数据，每次加载 64 个字节的数据。我将其与空间进行比较：我只想保留比空间大的值（以字节为单位）。然后我调用 compress 指令取出不需要的字节。我定期读取（每 64 个字节），但我写入可变数量的字节，因此我将写入指针推进了我的掩码中设置的位数：我使用快速指令（ popcnt ）计算那些。

 __m512i 空格= _mm512_set1_epi8 ( ' ' ) ;   
  尺寸_t i = 0 ;   
  对于( ; i + 63 <多少; i + = 64 ) {   
    __m512i x = _mm512_loadu_si512 (字节+ i ) ;   
    __mmask64 notwhite = _mm512_cmpgt_epi8_mask （ x ，空格） ；   
    _mm512_mask_compressstoreu_epi16 （字节+ pos ， notwhite ， x ） ；   
    pos + = _popcnt64 (非白色) ;   
  }   

我已经更新了despacer 库及其基准。使用 Tiger Lake 处理器 (3.3 GHz) 和 GCC 9 (Linux)，我得到以下结果：

你的结果会有所不同。尽管如此，我们发现 AVX-512 对这项任务非常有用，并且相关功能超过了所有其他此类功能。这不仅仅是原始速度，还有我们不需要查找表并且代码不依赖于分支预测的事实：没有难以预测的分支可能会在实践中损害您的速度。

结果应该不会让我们感到惊讶，因为我们几乎第一次拥有对该操作的直接硬件支持（“修剪不需要的字节”）。缺点是很少有处理器支持所需的指令集。目前尚不清楚 AMD 是否会支持这些花哨的指令。

我应该以 Linus Torvalds 对 AVX-512 的看法结束：

我希望 AVX-512 痛苦地死去，英特尔开始解决真正的问题，而不是试图创建神奇的指令，然后创建它们看起来不错的基准

我无法预测英特尔或 AVX-512 会发生什么，但如果过去有任何迹象，那么专业和强大的指令将拥有光明的未来。

原文： https://lemire.me/blog/2022/04/28/removing-characters-from-strings-faster-with-avx-512/