8

私の仕事はチェック（>兆チェック）です。2つのintには、事前定義されたニブルのペア（最初のペアは0x2 0x7、2番目のペアは0xd 0x8）が含まれていますか。例えば：

bit offset:   12345678
first int:  0x3d542783     first pair of  0x2    second:   0xd   
second int: 0x486378d9      nibbles:      0x7      pair:   0x8
               ^  ^

したがって、この例では、必要なペアで2つのオフセットをマークします（オフセットは2と5ですが、7ではありません）。実際のオフセットと見つかったペアの数は、私のタスクでは必要ありません。

したがって、与えられた2つのintについて、問題は次のとおりです。同じオフセットにこれらのニブルのペアのいずれかが含まれていますか。

私は自分のプログラムをチェックしました。この部分は最もホットな場所です（gprof証明済み）。そしてそれは非常に何度も呼ばれます（gcov証明されています）。実際には、ネストされたループの3番目または4番目のループ（最もネストされたループ）です。

私の現在のコードは遅いです（私はそれを関数として書き直しますが、それは内部ループからのコードです）：

static inline int nibble_check (uint32_t A, uint32_t B)
 __attribute__((always_inline))
{
  int i;
  for(i=0;i<8;i++)

    if(  ( ( (A&0xf) ==0xD) && ( (B&0xf) ==0x8) )     // first pair
      || ( ( (A&0xf) ==0x2) && ( (B&0xf) ==0x7) )  )  // second pair
        return 1; // nibbles found
    else {
        A>>=4;
        B>>=4;
    }

  return 0; // nibbles not found
}

もう1つのタスクは、オフセット0、4、8ビットなどだけでなく、オフセット0、2、4、8、10、...ビットでもこのペアを見つけることです。

#define douburu_nibble_check(A,B) (nibble_check(A,B) || nibble_check(A>>2, B>>2) )

この関数とマクロを並行して書き直すことは可能ですか？

私のコンパイラはgcc452で、CPUは32ビットモード（x86）のIntelCore2Soloです。

4

6 に答える 6

7

単語のゼロバイトをテストするためのトリックがあります（たとえば、 http： //graphics.stanford.edu/~seander/bithacks.html#ZeroInWordを参照）。高速な方法は、次の式を使用することです。

(x - 0x01010101) & ~x & 0x80808080

これは、32ビットワード内の4バイトのいずれかが0の場合はゼロ以外の値に評価され、それ以外の場合は0に評価されます。

この方法は、ここで機能するように適合させることができます。

static inline int nibble_check(uint32_t A, uint32_t B)
{
  uint32_t tmp1, tmp2;

  tmp1 = (A ^ 0x22222222) | (B ^ 0x77777777);
  tmp2 = (A ^ 0xdddddddd) | (B ^ 0x88888888);

  return !!(((tmp1 - 0x11111111) & ~tmp1 & 0x88888888) |
            ((tmp2 - 0x11111111) & ~tmp2 & 0x88888888));
}
于 2011-03-04T00:17:56.683 に答える
2

最速の解決策は、おそらくある種のルックアップテーブルを使用することです。

あなたはどのくらい記憶に制約がありますか？16ビットテーブルは64Kであり、一度に4つのニブルをテストできます。したがって、そのうちの4つ（ニブルごとに1つ）は256Kになります。

私があなたの問題を理解すれば、これはうまくいくと思います。これは8ビットの例です。16ビットに拡張できます。：

 /* Look for 0x2 in either nibble - hits on 0x02, 0x20, 0x22 */
 char table_0x2[] = {
     0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 0x02 */
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 0x20, 0x22 */
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
 };

 char table_0x7[] = { fill this in };
 char table_0xd[] = { fill this in };
 char table_0x8[] = { fill this in };

 int nibble_check (uint32_t A, uint32_t B)
 {

       int i;

       for (i = 0; i < 4; i++) {
           if ((table_0x2[A & 0xff] && table_0x7[B & 0xff]) ||
               (table_0xd[A & 0xff] && table_0x8[B & 0xff])) {
                  /*
                   * check to see if the A&B hits are in corresponding
                   * nibbles - return 1 or break
                   */
           }

           A = A >> 8;
           B = B >> 8;

       }
       return 0;
   }

より良い実装は次のとおりです。

 /* 16 bit tables - upper 8 bits are A, lower 8 bits are B */
 /* for 0x02, 0x07 */
 char *table_2_7;
 /* for 0x0d, 0x08 */
 char *table_d_8;

 void init(void)
 {
     int i;
     int j;

     /* error checking eliminated for brevity */
     table_2_7 = malloc(64 * 1024);
     table_d_8 = malloc(64 * 1024);

     memset(table_2_7, 0, 64 * 1024);
     memset(table_d_8, 0, 64 * 1024);

     for (i = 0 ; i < 16; i++) {
         for (j = 0 ; j < 16; j++) {
             table_2_7[(i << 12)   | (0x2 << 8)  | (j << 4)   | (0x7 << 0)] = 1;
             table_2_7[(0x2 << 12) | (i << 8)    | (0x7 << 4) | (j << 0)] = 1;

             table_d_8[(i << 12)   | (0xd << 8)  | (j << 4)    | (0x8 << 0)] = 1;
             table_d_8[(0xd << 12) | (i << 8)    | (0x8 << 4) | (j << 0)] = 1;
    }
}


 }

 int nibble_check(uint32_t A, uint32_t B)
 {
     int i;

     for (i = 0; i < 4; i++) {
         if (table_2_7[ ((A & 0xff) << 8) | (B & 0xff) ] ||
             table_d_8[ ((A & 0xff) << 8) | (B & 0xff) ]) {
             return 1;
         }

         A = A >> 8;
         B = B >> 8;

     }
     return 0;
 }
于 2011-03-03T23:31:47.513 に答える
1

ループを展開してみましたか？

if( ( ((A & 0x0000000F) == 0x0000000D) && ((B & 0x0000000F) == 0x00000008) )
 || ( ((A & 0x000000F0) == 0x000000D0) && ((B & 0x000000F0) == 0x00000080) )
 || ( ((A & 0x00000F00) == 0x00000D00) && ((B & 0x00000F00) == 0x00000800) )
 || ( ((A & 0x0000F000) == 0x0000D000) && ((B & 0x0000F000) == 0x00008000) )
// etc
// Then repeat with 2 & 7

ループを展開すると、ビット単位と演算の数が同じになり、比較の数も同じになると思いますが、すべての右シフトを実行して結果を保存する手間を省くことができます。

編集:(展開結果に応じて、条件付きおよび無条件のジャンプが発生します）

これにより、追加の作業を行うことを犠牲にして、ジャンプがなくなります。この種の最適化が必要なものに取り組んでからしばらく経ちましたが、これによってジャンプが発生することはありません。（そうでない場合は、&&を＆に置き換えてみてください。&&はコンパイラーをトリガーして短絡ロジックを生成する可能性がありますが、＆はジャンプなしで常に後半を評価する可能性があります。）

bool result = false;
result |= ( ((A & 0x0000000F) == 0x0000000D) && ((B & 0x0000000F) == 0x00000008) )
result |= ( ((A & 0x000000F0) == 0x000000D0) && ((B & 0x000000F0) == 0x00000080) )
result |= ( ((A & 0x00000F00) == 0x00000D00) && ((B & 0x00000F00) == 0x00000800) )
result |= ( ((A & 0x0000F000) == 0x0000D000) && ((B & 0x0000F000) == 0x00008000) )
// etc
return result;
于 2011-03-03T23:36:06.097 に答える
1

一致しない候補を以前に破棄する可能性があります。

int nibble_check (uint32_t A, uint32_t B) 
{
    if ( !(A & B & 0x22222222) && !(A & B & 0x88888888))
       return 0;
    //rest of checking here...
}
于 2011-03-04T00:02:50.910 に答える
1 
static inline int nibble_check (uint32_t A, uint32_t B)
 __attribute__((always_inline))
{
    // shift x by n nibbles
    #define s(x, n) ((x) << 4 * (n))
    // mask the nth nibble of x
    #define m(x, n) ((x) & s(0xf, n))
    // D^8 and 2^7 both == 5, so check for that first, for speed
    // this is equivalent to
    // (A_nibble == 0XD && B_nibble == 0x8) || (A_nibble == 0x2 && B_nibble == 0x7)
    #define t(n) (m(AB,n) == s(5,n) && (m(B,n) == s(7,n) || m(B,n) == s(8,n))

    uint32_t AB x = A ^ B;

    return t(0) || t(1) || t(2) || t(3) || t(4) || t(5) || t(6) || t(7);
    #undef t
    #undef m
    #undef s
}
于 2011-03-04T00:03:23.030 に答える
0

テーブルベースのアプローチは次のようになります。

static inline int has_zeros (uint32_t X)
{
    int H = (X >> 16);
    int L = X & 0xFFFF;
    return (ztmap[H>>3]&(1<<(H&7))) ||
           (ztmap[L>>3]&(1<<(L&7)));
}

static inline int nibble_check (uint32_t A, uint32_t B)
 __attribute__((always_inline))
{
  return has_zeros((A ^ 0xDDDDDDDDU)|(B ^ 0x88888888U)) ||
         has_zeros((A ^ 0x22222222U)|(B ^ 0x77777777U));
}

1つのアイデアは、16ビットの数値にニブルが含まれているかどうかをチェックする65536値のマップを事前に計算することです0000。私の例ではビットテーブルを使用しましたが、バイトテーブルの方が大きくてキャッシュフレンドリーではない場合でも高速になる可能性があります。

テーブルチェックがある場合は、最初の32ビット整数を最初のニブルを繰り返してxorし、2番目の整数を2番目のニブルを繰り返してxorすることができます。最初のニブルが最初の整数に存在する場合、ゼロが取得され、2番目のニブルの2番目の整数でも同じことが起こります。または、2つの結果をゼロにすることができるのは、検索対象のペアが存在する場合のみです。

次に、他のニブル値のペアに対して検索を繰り返すことにより、検索が完了します。

ただし、通常のチェスゲーム（つまり、2人の王しかいない）でのキングキング攻撃の場合、座標を使用してチェックを行うと、これよりもはるかに高速になる可能性があることに注意してください。

于 2011-03-04T00:05:32.093 に答える