正如@Mysticial在上面的评论说,做比较和纵向总结,然后只在主循环的末尾水平总结:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <emmintrin.h>
// reference implementation
int fast_compare_ref(const char *s, const char *t, int length)
{
int result = 0;
int i;
for (i = 0; i < length; ++i)
{
if (s[i] == t[i])
result++;
}
return result;
}
// optimised implementation
int fast_compare(const char *s, const char *t, int length)
{
int result = 0;
int i;
__m128i vsum = _mm_set1_epi32(0);
for (i = 0; i < length - 15; i += 16)
{
__m128i vs, vt, v, vh, vl, vtemp;
vs = _mm_loadu_si128((__m128i *)&s[i]); // load 16 chars from input
vt = _mm_loadu_si128((__m128i *)&t[i]);
v = _mm_cmpeq_epi8(vs, vt); // compare
vh = _mm_unpackhi_epi8(v, v); // unpack compare result into 2 x 8 x 16 bit vectors
vl = _mm_unpacklo_epi8(v, v);
vtemp = _mm_madd_epi16(vh, vh); // accumulate 16 bit vectors into 4 x 32 bit partial sums
vsum = _mm_add_epi32(vsum, vtemp);
vtemp = _mm_madd_epi16(vl, vl);
vsum = _mm_add_epi32(vsum, vtemp);
}
// get sum of 4 x 32 bit partial sums
vsum = _mm_add_epi32(vsum, _mm_srli_si128(vsum, 8));
vsum = _mm_add_epi32(vsum, _mm_srli_si128(vsum, 4));
result = _mm_cvtsi128_si32(vsum);
// handle any residual bytes (< 16)
if (i < length)
{
result += fast_compare_ref(&s[i], &t[i], length - i);
}
return result;
}
// test harness
int main(void)
{
const int n = 1000000;
char *s = malloc(n);
char *t = malloc(n);
int i, result_ref, result;
srand(time(NULL));
for (i = 0; i < n; ++i)
{
s[i] = rand();
t[i] = rand();
}
result_ref = fast_compare_ref(s, t, n);
result = fast_compare(s, t, n);
printf("result_ref = %d, result = %d\n", result_ref, result);;
return 0;
}
编译并运行上述测试工具:
$ gcc -Wall -O3 -msse3 fast_compare.c -o fast_compare
$ ./fast_compare
result_ref = 3955, result = 3955
$ ./fast_compare
result_ref = 3947, result = 3947
$ ./fast_compare
result_ref = 3945, result = 3945
请注意,有在我们使用_mm_madd_epi16
解包和积累16位以上SSE代码一个可能的非显而易见的伎俩0
/-1
值到32位部分和。我们利用了这个事实-1*-1 = 1
(当然还有0*0 = 0
) - 我们在这里并没有真正进行乘法运算,只是在一条指令中进行解包和求和。
UPDATE:在下面的评论中指出,该方案不是最优的 - 我只花了相当最佳的16位解决方案,并加入8位到16位的拆包,使之成为8位的数据。然而,对于8位数据,存在更有效的方法,例如,使用psadbw
/_mm_sad_epu8
。我将这里的答案留给子孙后代,对于任何想要用16位数据做这种事情的人来说,但其他答案中的其中一个不需要拆开输入数据的答案应该是公认的答案。
如果剩余字节数小于16,则使用for循环(长度/ 16次),并将零填充到lhs和one。填充应该是不同的,以便它不会错误地将填充计数为相等。 – 2013-03-09 17:42:10
'while(length> = 16){/ *使用你的函数*/length - = 16; } if(length)/ *使用比较长度(最多15个字节)的版本* /;' – pmg 2013-03-09 17:42:55
FYI这通常称为[*汉明距离*](http://en.wikipedia.org/wiki/Hamming_distance ) - 这可能是一个有用的搜索词。 – 2013-03-09 18:02:50