In C is there a branch-less technique to compute the absolute difference between two unsigned ints? For example given the variables a and b, I would like the value 2 for cases when a=3, b=5 or b=3, a=5. Ideally I would also like to be able to vectorize the computation using the SSE registers.
From tommesani.com, one solution for this problem is to use saturating unsigned subtraction twice.
As the saturating subtraction never goes below 0, you compute: r1 = (a-b).saturating r2 = (b-a).saturating
If a is greater than b, r1 will contain the answer, and r2 will be 0, and vice-versa for b>a. ORing the two partial results together will yield the desired result.
According to the VTUNE users manual, PSUBUSB/PSUBUSW is available for 128-bit registers, so you should be able to get a ton of parallelization this way.
compute the difference and return the absolute value
__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);
This requires one less operation that using the signed compare op, and produces less register pressure.
Same amount of register pressure as before, 2 more ops, better branch and merging of dependency chains, instruction pairing for uops decoding, and separate unit utilization. Although this requires a load, which may be out of cache. I'm out of ideas after this one.
__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
After timing each version with 2 million iterations on a Core2Duo, differences are immeasurable. So pick whatever is easier to understand.