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

Question

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

这是 ARMv7+NEON 问题的姐妹问题： What is the most efficient way to do SIMD unsigned 64 bit comparison (CMHS) on ARMv7 with NEON?

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

Answer 1

给你。

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

Here’s a test app.

如果 SSE3 可用，movshdup 也是替代 pshufd (_mm_shuffle_epi32) 的好选择，可以将 srai 结果复制到每个元素中的低位双字。（或者如果下一次使用是 movmskpd 或其他仅取决于每个 qword 的高位部分的东西，则将其优化掉）。

例如，在Conroe/Merom上（第一代Core 2、SSSE3和大多数SIMD执行单元是128位宽，但shuffle单元有限制），pshufd是2微指令，3周期延迟（flt->int 域）。 movshdup 只有 1 uop，1 个周期的延迟，因为它的硬连线洗牌只有 within 每个 64 位寄存器的一半。 movshdup 在“SIMD-int”域中运行，因此它不会在整数移位和您接下来执行的任何整数操作之间造成任何额外的旁路延迟，这与 pshufd 不同。 (https://agner.org/optimize/)

如果您在进行 JITing，那么您只会在没有 SSE4.2 的 CPU 上使用它，这意味着 Intel 在 Nehalem 之前，AMD 在 Bulldozer 之前。请注意，psubq (_mm_sub_epi64) 在某些 CPU 上比更窄的 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 );
}

Answer 2

翻译自 Hacker's Delight:

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

概念：If mixed "signs" (unsigned MSBs) then return a else return 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的符号。

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

What is the most efficient way to do unsigned 64 bit comparison on SSE2?

assembly

sse

simd

sse2