c++ - 如何优化一个循环？

Question

我有以下瓶颈功能。

typedef unsigned char byte;
void CompareArrays(const byte * p1Start, const byte * p1End, const byte * p2, byte * p3)
{
     const byte b1 = 128-30;
     const byte b2 = 128+30;
     for (const byte * p1 = p1Start; p1 != p1End; ++p1, ++p2, ++p3) {
        *p3 = (*p1 < *p2 ) ? b1 : b2;
    }
}

我想C++用 SSE2 内部函数替换代码。我已经尝试过_mm_cmpgt_epi8，但它使用了签名比较。我需要无符号比较。

有什么技巧（SSE、SSE2、SSSE3）来解决我的问题吗？

注意： 在这种情况下，我不想使用多线程。

Answer 1

与其抵消您的有符号值以使它们无符号，不如执行以下操作更有效：

• 用于_mm_min_epu8获取 p1, p2 的无符号最小值
• 比较这个最小值与 p2 的相等性，使用_mm_cmpeq_epi8
• 对于 p1 < p2 的元素，生成的掩码现在将为 0x00，对于 p1 >= p2 的元素，掩码为 0xff
• 您现在可以将此掩码与_mm_or_si128和一起使用_mm_andc_si128来选择适当的 b1/b2 值

请注意，这总共是 4 条指令，而使用偏移量 + 有符号比较方法则为 5 条。

Answer 2

您可以从数字中减去 127，然后使用 _mm_cmpgt_epi8

Answer 3

是的，这可以在 SIMD 中完成，但是制作掩码需要几个步骤。

我认为，Ruslik 是对的。您想用 0x80 对每个组件进行异或运算，以翻转有符号和无符号比较的意义。_mm_xor_si128 ( PXOR) 让你知道——在将掩码加载到 SIMD 寄存器之前，你需要在某处将掩码创建为静态字符数组。然后 _mm_cmpgt_epi8 给你一个掩码，你可以使用按位与（例如_mm_and_si128）来执行掩码移动。

Answer 4

是的，SSE 在这里不起作用。您可以使用 OpenMP 在多核计算机上提高此代码性能：

void CompareArrays(const byte * p1Start, const byte * p1End, const byte * p2, byte * p3)
{
     常量字节 b1 = 128-30;
     常量字节 b2 = 128+30;

     int n = p1End - p1Start;
     #pragma omp 并行
     for (int i = 0; i < n; ++p1, ++i)
     {
        p3[i] = (p1[i] < p2[i]) ? 乙1：乙2；
     }
}

Answer 5

不幸的是，上面的许多答案都是不正确的。让我们假设一个 3 位字：

无符号：4 5 6 7 0 1 2 3 == 有符号：-4 -3 -2 -1 0 1 2 3（位：100 101 110 111 000 001 010 011）

Paul R 的方法不正确。假设我们想知道 3 > 2.min(3,2) == 2，这表明是，所以该方法在这里有效。现在假设我们想知道是否 7 > 2。值 7 在有符号表示中为 -1，因此 min(-1,2) == -1，这错误地表明 7 不大于 2 无符号。

安德烈的方法也不正确。假设我们想知道是否 7 > 2，或者 a = 7，并且 b = 2。值 7 在有符号表示中为 -1，因此第一项 (a > b) 失败，该方法表明 7 不大于大于 2。

但是，由 Alexey 纠正的 BJobnh 的方法是正确的。只需从值中减去 2^(n-1)，其中 n 是位数。在这种情况下，我们将减去 4 以获得新的对应值：

旧签名：-4 -3 -2 -1 0 1 2 3 => 新签名：0 1 2 3 -4 -3 -2 -1 == 新未签名 0 1 2 3 4 5 6 7。

换句话说，unsigned_greater_than(a,b) 等价于signed_greater_than(a - 2^(n-1), b - 2^(n-1))。

Answer 6

使用 pcmpeqb 并成为你的力量。