如何优化循环？

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;
    }
}

我希望使用SSE2内置函数替换C++代码。我尝试过_mm_cmpgt_epi8，但它使用了有符号比较。我需要无符号比较。

有没有什么技巧（SSE、SSE2、SSSE3）可以解决我的问题？

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

- Alexey Malistov

---

你知道你正在针对哪种处理器架构吗？一次处理一个64位字块（通过位操作在寄存器中进行比较）可以在一定程度上减少内存总线争用。编译器的汇编代码应该有助于提供思路......SSE不是用于浮点运算而不是整数运算吗？ - Pontus Gagge

SSE有一些整数指令。 - Crashworks

为什么不将它们标记为已签名？在比较之前，对每个元素进行简单的XOR 0x80操作即可完成工作。 - ruslik

Answer 1

不要将有符号值偏移以使它们变为无符号值，一个稍微更有效的方法是执行以下操作：

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

请注意，总共需要4条指令，而使用偏移+带符号比较方法需要5条指令。

- Paul R

Answer 2

你可以从你的数字中减去127，然后使用_mm_cmpgt_epi8函数。

- BЈовић

---

看起来是正确的答案。但我认为你的127必须替换为128。或者使用128进行异或运算。 - Alexey Malistov

问题在于我认为只有 MMX 中的打包加法，这是完全不同的寄存器集。 - Crashworks

Answer 3

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

Ruslik说得对，我认为你想要将每个组件与0x80异或以翻转有符号和无符号比较的意义。_mm_xor_si128（PXOR）可以实现这一点--您需要在加载到SIMD寄存器之前将掩码作为静态字符数组创建在某个地方。然后_mm_cmpgt_epi8可以为您获取掩码，您可以使用按位AND（例如_mm_and_si128）执行掩码移动。

- Crashworks

Answer 4

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

void CompareArrays(const byte * p1Start, const byte * p1End, const byte * p2, byte * p3)
{
     const byte b1 = 128-30;
     const byte b2 = 128+30;
int n = p1End - p1Start;
     #pragma omp parallel for
     for (int i = 0; i < n; ++p1, ++i) 
     {
        p3[i] = (p1[i] < p2[i]) ? b1 : b2;
     }
}

- Alex F

---

@ VJo - 当然可以。在单核计算机上，这段代码的表现与问题中的原始代码完全相同。 - Alex F

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 大。

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

然而，BJobnh的方法，经过Alexey的修正后是正确的。只需从值中减去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))。

- T Wu

---

如果您仔细查看我的答案，您会发现我正在使用无符号的最小操作。 - Paul R

Answer 6

使用pcmpeqb，让力量与你同在。

- Alexander Solonsky

---

pcmpeqb 是一个检查相等的指令。我需要比较更少。 - Alexey Malistov

啊，是的。然后是pcmpgtb。仍然使用Power，但要明智地使用。 - Alexander Solonsky

OP需要无符号比较。 - Michael Foukarakis