x86 - 如何使用 SIMD 检查偶数/奇数 channel 是否在给定范围内？

Question

给定一个存储 16 个字符的 __m128i，偶数索引 channel 指的是 偶数 channel (即位于 0、2 的 channel ) , 4, ..., 14)，奇数索引 channel 指奇数 channel (即位于 1、3、5、... 15 的 channel )。

在我的应用程序中，偶数/奇数车道必须在给定范围内。例如，假设 even_min 为 1，even_max 为 7，odd_min 为 5，odd_max 为 10:

# valid
vec1: [1, 5, 6, 10, 2, 6, 4, 6, 2, 7, 4, 9, 2, 7, 4, 8] 

# invalid because 0-th (even) is greater than even_max
vec2: [8, 5, 6, 10, 2, 6, 4, 6, 2, 7, 4, 9, 2, 7, 4, 8]

如何更高效地检查是否有效？

我现在的解决方案很简单，分别查看两个比较结果:

  __m128i even_min = _mm_set1_epi8(xxx);
  __m128i even_max = _mm_set1_epi8(xxx);
  __m128i even_mask =
      _mm_set_epi8(0, -1, 0, -1, 0, -1, 0, -1, 0, -1, 0, -1, 0, -1, 0, -1);

  __m128i evenRange = _mm_and_si128(_mm_cmpge_epi8(vec, even_min),
                                    _mm_cmple_epi8(vec, even_max));
  bool isEvenOk = _mm_testc_si128(evenRange, even_mask);

// the code for checking odd bytes is similar

请注意，要使用包含条件比较无符号字符，两个宏定义如下:

#define _mm_cmpge_epi8(a, b) _mm_cmpeq_epi8(_mm_max_epu8(a, b), a)

#define _mm_cmple_epi8(a, b) _mm_cmpge_epi8(b, a)

Answer 1

为每车道创建一个向量 min值，以及每 channel 的另一个 max es.例如，_mm_set1_epi16((odd_min<<8) | (uint8_t)even_min) 。 (注意强制转换以避免符号扩展)。

那么你只需要一次范围检查。您应该更有效地做到这一点，而不是通过模拟 cmpge 和 cmple 各有 2 条指令。正如安德烈在评论中建议的，一个简单的方法是 v == min(max(v, a), b) ，这与您的 v == min(v, a) 的想法相同.

由于您在许多输入中使​​用相同的分钟/最大值，因此一些额外的设置工作是值得的，以使每个范围检查更便宜。 normal range-check trick的c - min < max-min使用无符号比较，但我们可以通过翻转两侧的 MSB(即添加或减去 0x80)来使用 SSE 有符号比较来实现。这就像将无符号范围转换为有符号范围。这可以是同一减法的一部分， c - min - 0x80 < max - min - 0x80 (签名比较)。 (谢谢@amonakov提醒这是可能的。)

// unsigned compare-trick, range-shifted for use with  pcmpgtb

// loop-invariant constants, set these up once
  __m128i mins = _mm_set1_epi16( ((odd_min<<8) | (uint8_t)even_min) ^ 0x8080);
  // if (odd_max == 0x7F && even_max == 0x7F){ ... }  // TODO: just check vec > mins
  __m128i maxes = _mm_set1_epi16( ((odd_max<<8) | (uint8_t)even_max) );
  __m128i rangelen = _mm_sub_epi8(maxes, mins);   // includes the 0x80 top bit from mins
   // compilers will constant-propagate through this, except maybe MSVC.  If that's a problem, write it a different way.

// Work inside the loop
  __m128i vsub = _mm_sub_epi8(vec, mins);
  __m128i vout_of_range = _mm_cmpgt_epi8(vsub, rangelen);
  // TODO: check for off-by-one errors in case I got this wrong, or inclusive vs. exclusive.
   // consider mins = 0^0x80, maxes = 1, rangelen=1^0x80 = -127.  
   // vec = 2: vsub = 2^0x80 = -126.  -126 > -127 so it's out-of-range (by 2; this range is exclusive at the top).

  bool isOk = !_mm_movemask_epi8(vout_of_range);  // ok if no bits set

@chtz 建议一个 paddb + paddusb + pmovmskb如果范围的大小小于 128，则可能是这样。因此，范围内的值不会在每个字节中设置 MSB，但超出范围的值最终将大于 128。(并且无法环绕因为饱和。)pmovmskb获取每个字节的 MSB，因此无需比较结果即可工作。 psubb/pcmpgtb在大多数 CPU 上应该同样好。 (检查 != 0 与检查位图结果 == 0 一样便宜。)

---

其他方式:比 sub/cmpgt 差，比 min 好/max/cmpeq

其他可能性包括 (v < mins) | (v > maxes) 并检查是否没有元素为真。 _mm_movemask_epi8(or_result) == 0 。这比 min/max/cmpeq 具有更好的关键路径延迟，因为我们有两个独立的比较，而不是 3 个操作的链。两种方式都需要原始向量的副本(除非您使用 AVX 进行编译以允许单独的目标)。

或者(v > min-1) & (v < max+1) ，这对于编译时间常数最小/最大是可行的。如果 min 已经是 INT8_MIN，则它始终为 true，因此它会优化为只需要其他条件。但当 Even_min 为 -128 而 odd_min 为其他值时，这是一个问题:没有值可以使 pcmpgtb对于偶数 channel 中的所有输入始终为 true，同时仍检查奇数 channel 。我一直在想 AND 可以作为 ptest 的一部分来完成。 ( _mm_test_* )，但实际上没有 _mm_test_all_ones 。如果 128 位 AND 结果中有任何非零位，则 ZF 被清除。 (CF 也是如此，基于 ANDN 结果。)

或者使用cmpgt两次并反转其中一个结果作为组合它们的一部分，例如与 _mm_andnot_si128 (pandn)

---

ptest比较结果的效率不是很高，因为它在大多数 CPU 上解码为 2 uop； pmovmskb + 标量 cmp或test也是 2 uop ( https://uops.info )，并且 cmp 或 test 可以与分支进行宏融合(如果您在分支上进行分支)。 ptest确实避免了需要临时寄存器并可能保存 movdqa如果您正在测试稍后也想使用的向量(不是比较结果)，则使用寄存器复制，但通常只有当您实际上使用其仅检查某些元素的功能(例如奇数/偶数掩码)时才有效.

就您而言，即使采用两次单独比较的策略，更好的策略可能是 2x _mm_movemask_epi8和(evens & (odds>>1) & 0x5555 == 0x5555 。 (0x5555 是 0b0101...0101，只是测试偶数元素)。

或者_mm_srli_epi16(odds, 8)/_mm_and_si128(evens, shifted_odds)得到一个向量，其中偶数元素具有您关心的结果。 (奇数元素为零，因为逻辑移位在那里产生了零，因此 _mm_movemask_epi8(and_result) == 0x5555 不需要屏蔽掉我们不关心的元素。)