假设我们要从由可变长度字段组成的输入流中提取字段。我们所知道的是每个字段的最大宽度,并且每个字段以值为 1
的字节结尾。我们希望将打包字段提取为固定格式,其中每个字段都有其最大宽度(如果输入字段小于最大值,则用零填充)。
每个字段的最小宽度为一个字节。
例如,我们期望接收两个字段的值。第一个的最大宽度为 3 个字节,第二个的最大宽度为 2 个字节。
假设我们有一个输入向量 {X, 1, 1},因此我们知道第一个字段的值为 {X, 1},第二个字段的值为 {1}。因此,在这种情况下,结果向量应等于 {0, X, 1, 0, 1}。
或者,我们有一个输入向量 {1, 1},因此结果向量应等于 {0, 0, 1, 0, 1}。
我想我知道一种使用查找表来做到这一点的方法。问题是,如果我们决定一次处理超过 64 位,我们最终会得到太大的查找表。
最佳答案
一种合理的方法是使用矢量化 cmp
查找所有 1,然后 movmskb
将这些结果作为位图存入通用寄存器,然后使用该值用于查找 pshufb
掩码,该掩码根据位图将字节扩展到字段中。
此技术还可以无成本地处理“最大字段”限制,因为该行为内置于查找表中的随机掩码中。
现在您将无法使用完整的 32 字节 ymm
寄存器来创建 32 位位图并直接查找,因为它需要 128 GB 之类的东西查找表1,这是不可行的(或者至少会非常慢)。在实践中,您将处理一些固定数量的输出字节,以使表大小保持合理,例如 8 到 16 字节之间。最佳值可能取决于您在紧密循环中执行此操作的次数以及周围代码的缓存压力成本。
假设您仍然想要更快的速度。您可以查看字段长度的实际分布,如果一些“典型”排列占主导地位,您可以使用乐观算法来获取位图,将其散列到较小的位数,然后然后在第一级随机控制表中查找该值,该表仅包含“预期”字段长度的条目。同时,您进行另一次查找以验证实际的完整位图是否与与第一级表关联的预期完整位图匹配。
当您在第一级表中命中时,您将按照上面的方式进行,并进行较大的(16 或 32 字节)随机播放,否则您将退回到如上所述的几个较小的查找。哈希值需要类似于预期值的“完美哈希值”,这样就不会发生冲突。
您可以在运行时计算查找表,或者将其作为常量嵌入到二进制文件本身中。
1 ...即使您确实创建了这样一个巨大的查找表,您也会遇到 pshufb
在两个 16 字节 channel 中工作的限制,而不是跨越整个 32 字节寄存器。
关于x86 - 使用字节分隔符快速 SIMD 提取可变大小字段,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45242612/