字节数组置换 SSE 优化

Question

字节数组置换 SSE 优化

12

我想使用SSE内嵌函数翻译这段代码。我找到了pshufb SSSE3指令和类似的__builtin_ia32_pshufb128(v128i, v128i) GCC内部函数，可能可以与此代码一起使用。该代码通过以特定方式交换数组中的字节，按索引k排列字节向量s。

void permutation(int k, std::vector<char> & s) 
{
  for(size_t j = 1; j < s.size(); ++j) 
  {
      std::swap(s[k % (j + 1)], s[j]); 
      k = k / (j + 1);
  }
}

我花了一个小时的时间思考如何将代码翻译成pshufb。是否可以通过单个pshufb置换16字节，还是需要多个指令？好的解决方案应该每次只置换16个字节。

编辑：问题的更多背景：我正在迭代所有可能的s排列。提前计算同一个s的多个结果是可以的。但是我需要稍后再产生第k个排列，最好作为O（1）操作。

- JATothrim

2

这是一个相当奇特的排列。对于所有 j，使得 j! > k，这将只交换s[j]和s[0]，这将插入原始的s[j]向上移动一个位置，最后一个留在s[0]中。 - Martin Bonner supports Monica

2

即使您使用64位整数（不太可能），对于所有j> 20，这仍然是正确的。对于32位整数，它将对所有j> 12成立。如果您要排列大于该大小的向量，则可能希望在k == 0时中断，并对其余幻灯片使用memmove。如果您要排列小于该大小的向量，则很难相信这是您的性能瓶颈。 - Martin Bonner supports Monica

你是否尝试迭代所有大小为 |s| 的可能排列？我建议使用 std::next_permutation，它不使用除法，这是一种非常慢的操作。 - stgatilov

关于矢量化：是否允许一次处理几个连续的“k”值（例如 k = 24、25、26，...，29）？您是否对不同的“k”使用相同的字符串“s”？预计算和存储某些查找数据是否可以？ - stgatilov

您可以一次处理16个字符串，并将s[j]的所有16个值（对于单个j值）存储在单个__m128i寄存器中。在这种转置布局中，您可以像通常交换字节一样交换寄存器（如果交换索引相同）。然后，您可能会获得更好的性能。但是，您必须在此转置布局中执行所有检查，因为将数据转置回“每个寄存器一个字符串”的布局非常昂贵。 - stgatilov

显示剩余5条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- stgatilov · Accepted Answer

单次调用

请注意，您可以使用混合基数的位置表示法将数字k写下，以便该表示法中的每个数字都定义了对于几个连续的j值交换元素的索引。

例如，对于长度为12的字符串，您可以将任何k写成以下三位数字的基数：

720 = 1*2*3*4*5*6  (0-th digit, lowest value)
504 = 7*8*9        (1-th digit)
1320 = 10*11*12    (2-th digit, highest value)

现在，您可以为每个位置和该位置的每个数字值预先计算所有元素的累积排列，并将其保存在查找表中。然后，您将能够通过单个指令执行多个交换操作。

以下是一个示例（预计算将是最难的部分）：

//to be precomputed:
__m128i mask0[ 720];
__m128i mask1[ 504];
__m128i mask2[1320];

__m128i permutation(int k, __m128i s) {
    s = _mm_shuffle_epi8(s, mask0[k %  720]); k /=  720;  //j = [1..5]
    s = _mm_shuffle_epi8(s, mask1[k %  504]); k /=  504;  //j = [6..8]
    s = _mm_shuffle_epi8(s, mask2[k       ]);             //j = [9..11]
    return s;
}

您可以根据需要平衡步数和查找表大小来变化基数的分解。

注意：除法运算非常缓慢。仅使用编译时常量进行除法，然后优化器会将它们转换为乘法。检查生成的汇编代码以确保没有除法指令。

许多调用

不幸的是，使用建议的解决方案仍然会消耗大部分时间进行索引计算，请参见 generated assembly。如果您一次处理几个连续值的 k，则可以显着减少此开销。

优化解决方案的最简单方法是：单独迭代 k 的数字，而不是在 k 上执行单个循环。然后索引计算变得不必要。此外，您可以重复使用部分计算结果。

__m128i s;// = ???
for (int k0 = 0; k0 <  720; k0++) {
    __m128i s0 = _mm_shuffle_epi8(s, mask0[k0]);
    for (int k1 = 0; k1 <  504; k1++) {
        __m128i s1 = _mm_shuffle_epi8(s0, mask1[k1]);
        for (int k2 = 0; k2 < 1320; k2+=4) {
            //for k = (((k2+0) * BASE1) + k1) * BASE0 + k0:
            __m128i sx0 = _mm_shuffle_epi8(s1, mask2[k2+0]);
            //for k = (((k2+1) * BASE1) + k1) * BASE0 + k0:
            __m128i sx1 = _mm_shuffle_epi8(s1, mask2[k2+1]);
            //for k = (((k2+2) * BASE1) + k1) * BASE0 + k0:
            __m128i sx2 = _mm_shuffle_epi8(s1, mask2[k2+2]);
            //for k = (((k2+3) * BASE1) + k1) * BASE0 + k0:
            __m128i sx3 = _mm_shuffle_epi8(s1, mask2[k2+3]);

            // ... check four strings: sx0, sx1, sx2, sx3
        }
    }
}

这样平均每个排列需要进行一次洗牌（参见assembly），看起来非常完美。

代码和结果

这里是所有解决方案的完整工作代码。

请注意，查找表的生成不容易完全解释，相应的代码相当大（并且充满了讨厌的细节）。

在Intel Core 2 Duo E4700 Allendale (2600MHz)上运行的基准测试结果为：

2.605 s: original code         (k < 12739451)
0.125 s: single-call fast code (k < 12739451)
4.822 s: single-call fast code (k < 479001600)
0.749 s: many-call fast code   (k < 479001600)

因此，单次调用版本比原始代码快大约20倍，多次调用版本比单次调用版本快大约6.5倍。