在 SSE2 上进行无符号 64 位比较的最有效方法是什么？

Question

PCMPGTQ 在 SSE2 上不存在，并且本身不适用于无符号整数。我们的目标是为无符号 64 位比较提供向后兼容的解决方案，以便我们可以将它们纳入 WebAssembly SIMD 标准中。

这是 ARMv7+NEON 问题的姊妹问题： 在 ARMv7 上使用 NEON 进行 SIMD 无符号 64 位比较 (CMHS) 的最有效方法是什么？

并且与已回答的 SSE2 和 Neon 的签名比较变体问题相关：

如何在sse2上模拟pcmpgtq？

支持 CMGT 在 ARMv7a 和 Neon 上进行 64 位签名比较的最有效方法是什么？

Answer 1

减法的进位是无符号比较谓词。

我们可以使用与以下情况相同的技巧来捕获执行： 计算两个数字的平均值。只是在这里我们将其基于半减法器而不是半加法器。

__m128i sse2_cmpgt_epu64(__m128i a, __m128i b) {
    b = _mm_xor_si128(b, a); // diff
    a = _mm_and_si128(a, b); // borrow `a & ~b`
    b = _mm_sub_epi64(_mm_srli_epi64(b, 1), a); 
    return _mm_shuffle_epi32(_mm_srai_epi32(b, 31), _MM_SHUFFLE(3,3,1,1));
}

---

翻译自黑客之乐：

static
__m128i sse2_cmpgt_epu64(__m128i a, __m128i b) {
    __m128i r = _mm_andnot_si128(_mm_xor_si128(b, a), _mm_sub_epi64(b, a));
    r = _mm_or_si128(r, _mm_andnot_si128(b, a));
    return _mm_shuffle_epi32(_mm_srai_epi32(r, 31), _MM_SHUFFLE(3,3,1,1));
}

概念：如果混合“符号”（无符号 MSB）则返回

a

，否则返回

b - a

(MSB(a) ^ MSB(b)) ? a : b - a; // result in MSB

这是有道理的：

• 如果

  a

  的 MSB 已设置而

  b

  未设置，则

  a

  上面无符号（因此 MSB(a) 是我们的结果）
• 如果

  b

  的 MSB 已设置而

  a

  未设置，则

  a

  下面无符号（因此 MSB(a) 是我们的结果）
• 如果它们的 MSB 相同，则它们的值位于无符号范围的同一半中，因此

  b-a

  实际上是 63 位减法。 MSB 将取消，并且

  b-a

  的 MSB 将等于“借用”输出，该输出告诉您

  a

  是否严格高于

  b

  。 （就像标量

  sub

  的 CF 标志一样。

  jb

  是

  jc

  ）。所以 MSB(b-a) 就是我们的结果。

请注意，SIMD andnot/and/or 是位混合，但我们只关心 MSB。我们用 srai -> shuffle_epi32 广播它，丢弃低位中的垃圾。 （或者使用 SSE3，

movshdup

，如 @Soont 的答案中所述。）

---

它与有符号比较不同：

(MSB(a) ^ MSB(b)) ? ~a : b - a; // result in MSB

如果符号混合，那么

~a

的符号当然也是

b

的符号。

Answer 2

给你。

__m128i cmpgt_epu64_sse2( __m128i a, __m128i b )
{
    // Compare uint32_t lanes for a > b and a < b
    const __m128i signBits = _mm_set1_epi32( 0x80000000 );
    a = _mm_xor_si128( a, signBits );
    b = _mm_xor_si128( b, signBits );
    __m128i gt = _mm_cmpgt_epi32( a, b );
    __m128i lt = _mm_cmpgt_epi32( b, a );

    // It's too long to explain why, but the result we're after is equal to ( gt > lt ) for uint64_t lanes of these vectors.
    // Unlike the source numbers, lt and gt vectors contain a single bit of information per 32-bit lane.
    // This way it's much easier to compare them with SSE2.

    // Clear the highest bit to avoid overflows of _mm_sub_epi64.
    // _mm_srli_epi32 by any number of bits in [ 1 .. 31 ] would work too, only slightly slower.
    gt = _mm_andnot_si128( signBits, gt );
    lt = _mm_andnot_si128( signBits, lt );

    // Subtract 64-bit integers; we're after the sign bit of the result.
    // ( gt > lt ) is equal to extractSignBit( lt - gt )
    // The above is only true when ( lt - gt ) does not overflow, that's why we can't use it on the source numbers.
    __m128i res = _mm_sub_epi64( lt, gt );

    // Arithmetic shift to broadcast the sign bit into higher halves of uint64_t lanes
    res = _mm_srai_epi32( res, 31 );
    // Broadcast higher 32-bit lanes into the final result.
    return _mm_shuffle_epi32( res, _MM_SHUFFLE( 3, 3, 1, 1 ) );
}

这是一个测试应用程序。

如果 SSE3 可用，

movshdup

也是一个不错的选择，而不是

pshufd

(_mm_shuffle_epi32) 将 srai 结果复制到每个元素中的低位 dword。 （或者如果下一次使用是

movmskpd

或其他仅取决于每个 qword 的高部分的东西，则优化它）。

例如，在 Conroe/Merom 上（第一代 Core 2、SSSE3 和大多数 SIMD 执行单元均为 128 位宽，但混洗单元有限制），

pshufd

为 2 uops、3 个周期延迟（flt->int 域） 。

movshdup

只有 1 uop、1 个周期延迟，因为它的硬连线洗牌仅在寄存器的每个 64 位半个寄存器中。 movshdup 在“SIMD-int”域中运行，因此它不会在整数移位和接下来执行的任何整数操作之间造成任何额外的旁路延迟，与

pshufd

不同。 （

https://agner.org/optimize/

） 如果您进行 JITing，您只能在没有 SSE4.2 的 CPU 上使用它，这意味着 Intel 在 Nehalem 之前，AMD 在 Bulldozer 之前。请注意，在某些 CPU 上，

psubq

(

_mm_sub_epi64

) 比较窄的

psub

慢一些，但它仍然是最佳选择。为了完整起见，这里是 SSSE3 版本（与 SSE3 不太一样），以恒定负载为代价节省了一些指令。确定它是更快还是更慢的唯一方法是在旧计算机上进行测试。

__m128i cmpgt_epu64_ssse3( __m128i a, __m128i b )
{
    // Compare uint32_t lanes for a > b and a < b
    const __m128i signBits = _mm_set1_epi32( 0x80000000 );
    a = _mm_xor_si128( a, signBits );
    b = _mm_xor_si128( b, signBits );
    __m128i gt = _mm_cmpgt_epi32( a, b );
    __m128i lt = _mm_cmpgt_epi32( b, a );

    // Shuffle bytes making two pairs of equal uint32_t values to compare.
    // Each uint32_t combines two bytes from lower and higher parts of the vectors.
    const __m128i shuffleIndices = _mm_setr_epi8(
        0, 4, -1, -1,
        0, 4, -1, -1,
        8, 12, -1, -1,
        8, 12, -1, -1 );
    gt = _mm_shuffle_epi8( gt, shuffleIndices );
    lt = _mm_shuffle_epi8( lt, shuffleIndices );
    // Make the result
    return _mm_cmpgt_epi32( gt, lt );
}