2つの配列間の等しいバイト数を高速にカウントする

Question

SSE命令を使用して2つの16バイトの数値を比較するために、関数int compare_16bytes(__m128i lhs, __m128i rhs)を書きました。この関数は、比較を行った後に等しいバイト数を返します。

ここでは、任意の長さの2バイト配列を比較するために上記の関数を使用したいと思います。長さは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; 
} 

コンパイルおよび上記テストハーネスを実行します。

を我々は16ビットをアンパックし、蓄積する _mm_madd_epi16を使用して上記SSEコード内の1つの可能性の非自明なトリックがあること

$ 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 

---

注0/-1の値を32ビットの部分和に変換します。 -1*-1 = 1（もちろん0*0 = 0）ということを利用しています。ここでは、実際には1つの命令でアンパックして合計しているわけではありません。

---

UPDATE：以下のコメントで述べたように、このソリューションが最適ではない - 私はかなり最適な16ビット・ソリューションを取り、それが8ビットのデータのために動作させるために、開梱16ビットに8ビットを追加しました。しかしながら、8ビットデータの場合、より効率的な方法が存在する。 psadbw/_mm_sad_epu8を使用してください。私はこの回答を残念ながら残しておきますが、このようなことを16ビットデータでやりたい人にとっては、実際には入力データを解凍する必要のない答えの1つが受け入れられた答えになるはずです。

Answer 2

SSEの整数比較では、すべて0または1のいずれかのバイトが生成されます。カウントしたい場合は、最初に比較結果を7だけ右シフト（算術ではない）し、結果ベクタに加算する必要があります。 最後に、要素の合計によって結果ベクトルを減らす必要があります。この減少は、スカラーコードで、または一連の加算/シフトで実行する必要があります。通常、この部分は面倒なことではありません。

Answer 3

16 x uint8要素の部分和を使用すると、さらに優れたパフォーマンスが得られます。
ループを内側ループと外側ループに分割しました。
内側のループはuint8要素を合計します（各uint8要素は最大255の1になります）。
小さなトリック：_mm_cmpeq_epi8は、等しい要素を0xFFに設定し、（char）0xFF = -1とすることで、合計から結果を減算することができます。大きな入力のための最速の方法は、ベクターの任意のバイト要素の前に水平に合計に飛び出し、内側のループはpcmpeqb/psubbあるロテムの答え、ある

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 4

：ここ

はfast_compareのための私の最適化バージョンでありますアキュムレータがオーバーフローします。全ビットゼロベクトルに対してpsadbwの符号なしバイトのhsumを実行します。

/ネストされたループをアンロールすることなく、あなたが、あなたのループで0x7fのベクトルの代わりに、すべてゼロに対して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(0x00, set1(0x7f)) =>sum += 0x7f
• psadbw(0xff, set1(0x7f)) =>

sum += 0x80ので、代わりに、あなただけのn * 0x7fを、減算する必要がある（コンパイラは、実際のdivせずに効率的に行うべきである）255で割るのnは要素数です。

また、NehalemとAtomでは遅いため、128ビット*が32ビット整数よりもオーバーフローするとは思わない場合は、paddd（_mm_add_epi32）を使用できます。

これは、Paul Rのpcmpeqb/2x punpck/2x pmaddwd/2x paddwと非常によく似ています。