快速计数两个阵列之间相等的字节数[重复](Fast counting the number of e

2019-07-21 06:25发布

这个问题已经在这里有一个答案:

  • 可以在两个字符串之间计数字节匹配使用SIMD进行优化? 3个回答

我写的函数int compare_16bytes(__m128i lhs, __m128i rhs) ,以比较使用SSE指令两个16字节的数字:该函数返回多少字节进行比较后相等。

现在我想用上面的功能,以比较任意长度的两个字节数组:长度可能不是16个字节的倍数,所以我需要处理这个问题。 我怎么能完成以下功能的实现? 我怎么能改善以下功能?

int fast_compare(const char* s, const char* t, int length)
{
    int result = 0;

    const char* sPtr = s;
    const char* tPtr = t;

    while(...)
    {
        const __m128i* lhs = (const __m128i*)sPtr;
        const __m128i* rhs = (const __m128i*)tPtr;

        // compare the next 16 bytes of s and t
        result += compare_16bytes(*lhs,*rhs);

        sPtr += 16;
        tPtr += 16;
    }

    return result;
}

Answer 1:

作为@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

请注意,在上述SSE代码的一个可能的非显而易见的特技在这里我们使用_mm_madd_epi16解包和累积16位0 / -1值以32位部分和。 我们利用这样一个事实-1*-1 = 1 (和0*0 = 0 ,当然) -我们并不是真的做乘法这里,刚刚开箱和在一个指令总结。


更新:由于在下面的评论中指出,该方案不是最优的 - 我只花了相当最佳的16位解决方案,并加入8位到16位的拆包,使之成为8位的数据。 然而,对于8个数据有更有效的方法,例如使用psadbw / _mm_sad_epu8 。 我将在这里离开这个答案留给后人,和任何人谁可能想要做这种事情与16位数据,但不要求拆包输入数据应该是公认的答案其他的答案真的之一。



Answer 2:

在16×UINT8元素使用部分和可给予更为出色的表现。
我已分割循环到内环和外环。
内回路总和UINT8元件(每个元件UINT8可以总结到255的“1”)。
小窍门:_mm_cmpeq_epi8设置为等于元件为0xFF,和(炭)为0xFF = -1,所以可以减去总和的结果(减去-1用于添加1)。

这里是我的fast_compare优化的版本:

int fast_compare2(const char *s, const char *t, int length)
{
    int result = 0;
    int inner_length = length;
    int i;
    int j = 0;

    //Points beginning of 4080 elements block.
    const char *s0 = s;
    const char *t0 = t;


    __m128i vsum = _mm_setzero_si128();

    //Outer loop sum result of 4080 sums.
    for (i = 0; i < length; i += 4080)
    {
        __m128i vsum_uint8 = _mm_setzero_si128(); //16 uint8 sum elements (each uint8 element can sum up to 255).
        __m128i vh, vl, vhl, vhl_lo, vhl_hi;

        //Points beginning of 4080 elements block.
        s0 = s + i;
        t0 = t + i;

        if (i + 4080 <= length)
        {
            inner_length = 4080;
        }
        else
        {
            inner_length = length - i;
        }

        //Inner loop - sum up to 4080 (compared) results.
        //Each uint8 element can sum up to 255. 16 uint8 elements can sum up to 255*16 = 4080 (compared) results.
        //////////////////////////////////////////////////////////////////////////
        for (j = 0; j < inner_length-15; j += 16)
        {
              __m128i vs, vt, v;

              vs = _mm_loadu_si128((__m128i *)&s0[j]); // load 16 chars from input
              vt = _mm_loadu_si128((__m128i *)&t0[j]);
              v = _mm_cmpeq_epi8(vs, vt);             // compare - set to 0xFF where equal, and 0 otherwise.

              //Consider this: (char)0xFF = (-1)
              vsum_uint8 = _mm_sub_epi8(vsum_uint8, v); //Subtract the comparison result - subtract (-1) where equal.
        }
        //////////////////////////////////////////////////////////////////////////

        vh = _mm_unpackhi_epi8(vsum_uint8, _mm_setzero_si128());        // unpack result into 2 x 8 x 16 bit vectors
        vl = _mm_unpacklo_epi8(vsum_uint8, _mm_setzero_si128());
        vhl = _mm_add_epi16(vh, vl);    //Sum high and low as uint16 elements.

        vhl_hi = _mm_unpackhi_epi16(vhl, _mm_setzero_si128());   //unpack sum of vh an vl into 2 x 4 x 32 bit vectors
        vhl_lo = _mm_unpacklo_epi16(vhl, _mm_setzero_si128());   //unpack sum of vh an vl into 2 x 4 x 32 bit vectors

        vsum = _mm_add_epi32(vsum, vhl_hi);
        vsum = _mm_add_epi32(vsum, vhl_lo);
    }

    // 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 (j < inner_length)
    {
        result += fast_compare_ref(&s0[j], &t0[j], inner_length - j);
    }

    return result;
}


Answer 3:

对于大的输入的最快方式是Rotem公司的回答,其中所述内环是pcmpeqb / psubb ,向量累加器溢出的任何字节元素之前打破以水平总和。 做无符号字节HSUM与psadbw针对全零向量。

另请参阅如何计算使用SIMD角色出现 ,在那里你可以使用C ++与内在的AVX2计数匹配使用来自另一个数组,而不是这个问题的加载的矢量_mm_set1_epi8(char_to_count) 有效地增加了比较的结果是一样的,采用psadbw的水平总和。


如果没有展开/嵌套循环,最好的选择可能是

pcmpeqb   -> vector of  0  or  0xFF  elements
psadbw    -> two 64bit sums of  (0*no_matches + 0xFF*matches)
paddq     -> accumulate the psadbw result in a vector accumulator

#outside the loop:
horizontal sum
divide the result by 255

如果你没有在循环了很多寄存器的压力, psadbw针对向量0x7f ,而不是全零。

  • psadbw(0x00, set1(0x7f)) => sum += 0x7f
  • psadbw(0xff, set1(0x7f)) => sum += 0x80

因此,而不是由255分(编译器应该高效地完成没有实际的div ),你只需要减去n * 0x7f ,其中n是元素的数量。

还要注意的是paddq是前期的Nehalem和Atom慢,所以你可以使用paddd_mm_add_epi32 ),如果你不希望128 *计数永远溢出32位整数。

与此相比非常好,保罗的r pcmpeqb / 2X punpck / 2X pmaddwd / 2X paddw


但随着小UNROLL,你可以积累4或8个比较结果psubb psadbw / paddq之前。



Answer 4:

在SSE的整数比较产生字节,要么全零或全1。 如果你想算,你首先需要右移(不是算术)的比较结果7,然后添加到结果向量。 最后,你还需要通过总结它的元素,以减少结果向量。 这种降低在标量的代码来完成,或者用加/移位的序列。 通常,这部分是不值得担忧。



文章来源: Fast counting the number of equal bytes between two arrays [duplicate]
标签: c++ c sse simd sse2