饱和减法 - AVX或SSE4.2

Question

我正在提升一个程序（C语言）的性能，但是即使优化最“昂贵”的循环，也无法获得更好的执行时间。

如果数组元素大于零，则必须从一个无符号长整型数组中减去1。

循环代码如下：

unsigned long int * WorkerDataTime;
...
for (WorkerID=0;WorkerID<WorkersON;++WorkerID){
    if(WorkerDataTime[WorkerID] > 0) WorkerDataTime[WorkerID]-=1;
}

我尝试了这个:

for (WorkerID=0;WorkerID<WorkersON;++WorkerID){
    int rest = WorkerDataTime[WorkerID] > 0;
    WorkerDataTime[WorkerID] = WorkerDataTime[WorkerID] - rest;
}

但执行时间相似。

问题: 是否有任何内在指令（SSE4.2、AVX等）可以直接完成此操作？（我正在使用gcc 4.8.2）

我知道可以使用char或short元素来实现（_mm_subs_epi8和_mm_subs_epi16），但我不能使用AVX2。

谢谢。

- Cristian Morales

---

抱歉，我正在使用GCC 4.8.2。 - Cristian Morales

你的CPU是什么？AMD还是Intel？ - Z boson

https://dev59.com/ymAf5IYBdhLWcg3w52E_#24171383 - Z boson

尝试使用“-mxop”编译。 - Z boson

@Zboson 理解你的观点。我之所以发表评论，是为了让提问者意识到如果他们真的需要更快的速度，优化可能并不是最佳选择。不必要的优化实际上可能会减慢事情的进展，尤其是在整数运算方面。 - Mgetz

Answer 1

使用SSE4，只需三个指令即可完成。以下是一个处理整个数组的代码示例，将所有非零无符号整数递减：

void clampedDecrement_SSE (__m128i * data, size_t count)
{
  // processes 2 elements each, no checks for alignment done.
  // count must be multiple of 2.

  size_t i;
  count /= 2;

  __m128i zero = _mm_set1_epi32(0);
  __m128i ones = _mm_set1_epi32(~0);

  for (i=0; i<count; i++)
  {
    __m128i values, mask;

    // load 2 64 bit integers:
    values = _mm_load_si128 (data);

    // compare against zero. Gives either 0 or ~0 (on match)
    mask   = _mm_cmpeq_epi64 (values, zero);

    // negate above mask. Yields -1 for all non zero elements, 0 otherwise:
    mask   = _mm_xor_si128(mask, ones);

    // now just add the mask for saturated unsigned decrement operation:
    values = _mm_add_epi64(values, mask);

    // and store the result back to memory:
   _mm_store_si128(data,values);
   data++;
  }
}

使用AVX2技术，我们可以每次处理4个元素来提高效率：

void clampedDecrement (__m256i * data, size_t count)
{
  // processes 4 elements each, no checks for alignment done.
  // count must be multiple of 4.

  size_t i;
  count /= 4;

  // we need some constants:
  __m256i zero = _mm256_set1_epi32(0);
  __m256i ones = _mm256_set1_epi32(~0);

  for (i=0; i<count; i++)
  {
    __m256i values, mask;

    // load 4 64 bit integers:
    values = _mm256_load_si256 (data);

    // compare against zero. Gives either 0 or ~0 (on match)
    mask   = _mm256_cmpeq_epi64 (values, zero);

    // negate above mask. Yields -1 for all non zero elements, 0 otherwise:
    mask   = _mm256_xor_si256(mask, ones);

    // now just add the mask for saturated unsigned decrement operation:
    values = _mm256_add_epi64(values, mask);

    // and store the result back to memory:
   _mm256_store_si256(data,values);
   data++;
  }
}

编辑：增加了SSE代码版本。

- Nils Pipenbrinck

---

SSE 有这些指令吗？如果有的话，我会更新我的帖子。 - Nils Pipenbrinck

是的，+1，因为我认为你的答案比我的更聪明。它需要比使用XOP多一条指令，但仍然非常好。我根据你的答案更新了我的答案。 - Z boson

@Zboson 我更新了我的答案，并添加了SSE版本。 - Nils Pipenbrinck

我听说你可以通过 ones = _mm_cmpeq_epi8(ones, ones) 快速将寄存器设置为全1。 - phuclv

@CristianMorales，Nils比我更应该得到采纳的答案。他在我之前（XOP比SSE4.1更不常见）提出了一个更通用的解决方案（针对SSE4.1）。我应该意识到对于无符号数，x>0与x!=0是相同的。 - Z boson

Answer 2

除非您的CPU支持XOP，否则没有有效的方法可以比较无符号64位整数。

以下内容摘自Agner Fog的向量类库。这显示了如何比较无符号64位整数。

static inline Vec2qb operator > (Vec2uq const & a, Vec2uq const & b) {
#ifdef __XOP__  // AMD XOP instruction set
    return Vec2q(_mm_comgt_epu64(a,b));
#else  // SSE2 instruction set
    __m128i sign32  = _mm_set1_epi32(0x80000000);          // sign bit of each dword
    __m128i aflip   = _mm_xor_si128(a,sign32);             // a with sign bits flipped
    __m128i bflip   = _mm_xor_si128(b,sign32);             // b with sign bits flipped
    __m128i equal   = _mm_cmpeq_epi32(a,b);                // a == b, dwords
    __m128i bigger  = _mm_cmpgt_epi32(aflip,bflip);        // a > b, dwords
    __m128i biggerl = _mm_shuffle_epi32(bigger,0xA0);      // a > b, low dwords copied to high dwords
    __m128i eqbig   = _mm_and_si128(equal,biggerl);        // high part equal and low part bigger
    __m128i hibig   = _mm_or_si128(bigger,eqbig);          // high part bigger or high part equal and low part bigger
    __m128i big     = _mm_shuffle_epi32(hibig,0xF5);       // result copied to low part
    return  Vec2qb(Vec2q(big));
#endif
}

如果你的CPU支持XOP，那么你应该尝试使用-mxop编译，并查看循环是否向量化。

编辑：如果GCC不能按照你的要求向量化，而你的CPU有XOP，则可以执行以下操作

for (WorkerID=0; WorkerID<WorkersON-1; workerID+=2){
    __m128i v = _mm_loadu_si128((__m128i*)&WorkerDataTime[workerID]);
    __m128i cmp = _mm_comgt_epu64(v, _mm_setzero_si128());
    v = _mm_add_epi64(v,cmp);
    _mm_storeu_si128((__m128i*)&WorkerDataTime[workerID], v);
}
for (;WorkerID<WorkersON;++WorkerID){
    if(WorkerDataTime[WorkerID] > 0) WorkerDataTime[WorkerID]-=1;
}

使用-mxop编译，并包含#include <x86intrin.h>。

编辑：如Nils Pipenbrinck所指出，如果您没有XOP，可以使用一个额外的指令_mm_xor_si128来完成此操作:

for (WorkerID=0; WorkerID<WorkersON-1; WorkerID+=2){
    __m128i v = _mm_loadu_si128((__m128i*)&WorkerDataTime[workerID]);
    __m128i mask = _mm_cmpeq_epi64(v,_mm_setzero_si128());
    mask = _mm_xor_si128(mask, _mm_set1_epi32(~0));
    v= _mm_add_epi64(v,mask);
    _mm_storeu_si128((__m128i*)&WorkerDataTime[workerID], v);
}
for (;WorkerID<WorkersON;++WorkerID){
    if(WorkerDataTime[WorkerID] > 0) WorkerDataTime[WorkerID]-=1;
}

编辑： 根据Stephen Canon的评论，我了解到使用SSE4.2中的pcmpgtq指令可以更有效地比较一般的64位无符号整数：

__m128i a,b;
__m128i sign64 = _mm_set1_epi64x(0x8000000000000000L);
__m128i aflip = _mm_xor_si128(a, sign64);
__m128i bflip = _mm_xor_si128(b, sign64);
__m128i cmp = _mm_cmpgt_epi64(aflip,bflip);

- Z boson

---

在这种情况下，OP正在将一个数字与0进行比较，这比比较2个无符号数字要容易得多。 - phuclv

是的，我在发布原始答案后意识到了这一点。你读完我的回答了吗？ - Z boson

是的，我知道，我只是为那些不知道原因的人解释了一下。 - phuclv

幸运的是，AVX-512解决了这个问题（比较指令的非正交性）。我们漫长的国家噩梦结束了。我还应该注意到，SSE4.2允许更有效的无符号64位通用比较序列（翻转符号位，使用pcmpgtq）。 - Stephen Canon

@StephenCanon，你又一次是正确的。我以为你指的是SSE4.1，因为我认为SSE4.2只增加了字符串相关的内容，但现在我看到它也添加了pcmpgtq，所以Agner的函数应该有一个SSE4.2分支。 - Z boson