在C语言中,是否有一种无分支技术可以计算两个无符号整数之间的绝对差值?例如:给定变量a和b,当a=3,b=5或b=3,a=5时,我希望得到值2。最好还能使用SSE寄存器向量化计算。
从tommesani.com得知,解决这个问题的一种方法是使用饱和无符号减法两次。
由于饱和减法永远不会低于0,因此可以计算: r1 = (a-b).saturating r2 = (b-a).saturating
如果a大于b,则r1将包含答案,r2将为0;反之亦然。 将两个部分结果进行OR运算即可得到所需结果。
根据VTUNE用户手册,PSUBUSB/PSUBUSW适用于128位寄存器,因此您应该能够通过这种方式获得大量并行性。
max(i,j) - min(i,j)
(i>j)*(i-j) + (j>i)*(j-i)
您可以使用SSE寄存器,但编译器可能会自动为您完成此操作。
SSE2:
看起来与Phernost的第二个函数速度差不多。有时候GCC会安排它比Phernost的函数快一个周期,有时候会慢一点。
__m128i big = _mm_set_epi32( INT_MIN, INT_MIN, INT_MIN, INT_MIN );
a = _mm_add_epi32( a, big ); // re-center the variables: send 0 to INT_MIN,
b = _mm_add_epi32( b, big ); // INT_MAX to -1, etc.
__m128i diff = _mm_sub_epi32( a, b ); // get signed difference
__m128i mask = _mm_cmpgt_epi32( b, a ); // mask: need to negate difference?
mask = _mm_andnot_si128( big, mask ); // mask = 0x7ffff... if negating
diff = _mm_xor_si128( diff, mask ); // 1's complement except MSB
diff = _mm_sub_epi32( diff, mask ); // add 1 and restore MSB
SSSE3:
比之前的版本稍微快一点。取决于循环外部声明的内容有很多变化。(例如,将a
和b
声明为volatile
可以使速度更快!这似乎是调度的随机效应。)但这始终比其他方式快一个周期左右。
__m128i big = _mm_set_epi32( INT_MIN, INT_MIN, INT_MIN, INT_MIN );
a = _mm_add_epi32( a, big ); // re-center the variables: send 0 to INT_MIN,
b = _mm_add_epi32( b, big ); // INT_MAX to -1, etc.
__m128i diff = _mm_sub_epi32( b, a ); // get reverse signed difference
__m128i mask = _mm_cmpgt_epi32( b, a ); // mask: need to negate difference?
mask = _mm_xor_si128( mask, big ); // mask cannot be 0 for PSIGND insn
diff = _mm_sign_epi32( diff, mask ); // negate diff if needed
SSE4(感谢rwong):
无法进行测试。
__m128i diff = _mm_sub_epi32( _mm_max_epu32( a, b ), _mm_min_epu32( a, b ) );
计算差异并返回绝对值
__m128i diff = _mm_sub_epi32(a, b);
__m128i mask = _mm_xor_si128(diff, a);
mask = _mm_xor_si128(mask, b);
mask = _mm_srai_epi32(mask, 31);
diff = _mm_xor_si128(diff, mask);
mask = _mm_srli_epi32(mask, 31);
diff = _mm_add_epi32(diff, mask);
这比使用有符号比较操作少了一个操作,并且产生更少的寄存器压力。
与之前相同的寄存器压力,多了2个操作,更好的分支和依赖链合并,指令对uops解码进行配对,以及单独的单元利用率。虽然这需要一个加载,但可能超出缓存。在此之后,我已经没有更多想法了。
__m128i mask, diff;
diff = _mm_set1_epi32(-1<<31); // dependency branch after
a = _mm_add_epi32(a, diff); // arithmetic sign flip
b = _mm_xor_si128(b, diff); // bitwise sign flip parallel with 'add' unit
diff = _mm_xor_si128(a, b); // reduce uops, instruction already decoded
mask = _mm_cmpgt_epi32(b, a); // parallel with xor
mask = _mm_and_si128(mask, diff); // dependency merge, branch after
a = _mm_xor_si128(a, mask); // if 2 'bit' units in CPU, parallel with next
b = _mm_xor_si128(b, mask); // reduce uops, instruction already decoded
diff = _mm_sub_epi32(a, b); // result
在Core2Duo上进行200万次迭代后,每个版本的时间差都无法测量。因此,请选择您更容易理解的版本。
以下一个或多个条件可能会导致无分支代码,具体取决于计算机和编译器,因为条件表达式都非常简单。
我还没有阅读所有sse答案,但可能有些向量代码中包含以下内容;确实所有以下内容都可向量化(如果您首先进行无符号比较,或者通过首先切换msb进行伪造)。我认为提供一些实用的标量解答对这个问题会很有帮助。
unsigned udiff( unsigned a, unsigned b )
{
unsigned result = a-b; // ok if a<b;
if(a <b ) result = -result;
return result;
}
unsigned udiff( unsigned a, unsigned b )
{
unsigned n =(a<b)? (unsigned)-1 : 0u;
unsigned result = a-b;
return (result^n)-n; // 'result' if n = 0; '-result' if n = 0xFFFFFFFF
}
unsigned udiff( unsigned a, unsigned b )
{
unsigned axb = a^b;
if( a < b ) axb = 0;
return (axb^b) - (axb^a); // a-b, or b-a
}
unsigned udiff( unsigned a, unsigned b )
{
unsigned n= (unsigned)(
(long long)((unsigned long long)a - (unsigned long long)b)>>32
); // same n as 2nd example
unsigned result = a-b;
return (result^n)-n; // 'result' if n = 0; '-result' if n = 0xFFFFFFFF
}
int d = a-b;
int ad = ((d >> 30) | 1) * d;
嗯...这很容易...
int diff = abs( a - b );
易于向量化(使用SSE3):
__m128i sseDiff = _mm_abs_epi32( _mm_sub_epi32( a, b ) );
a和b都是无符号整数。考虑a=0和b=0xffffffff的情况。正确的绝对差应该是0xffffffff,但你的解决方案会给出1。
4-255
,正确的绝对差是251。但将其视为有符号数-5并取绝对值会得到5,这与255-250得到的答案相同。 - Peter Cordes
POR
可以在更多的端口上运行而不是PSUB
。 - Peter Cordes