2

4バイトの値を検索して、一連のバイトを反復処理する必要があります（4バイトはすべて同じです）。データの長さは可変であり、これらのバイトはデータ内のどこにあってもかまいません。私は最初のインスタンスを探しています。このロジックはコードの重要な部分で実行されるため、可能な限り最速の実装を見つけようとしています。

これは、Windowsのx86およびx64でのみ実行されます。

typedef unsigned char Byte;
typedef Byte* BytePtr;
typedef unsigned int UInt32;
typedef UInt32* UInt32Ptr;

const Byte MARKER_BYTE = 0xAA;
const UInt32 MARKER = 0xAAAAAAAA;

UInt32 nDataLength = ...;
BytePtr pData = ...;
BytePtr pEnd = pData + nDataLength - sizeof ( UInt32 );

// Option 1 -------------------------------------------
while ( pData < pEnd )
{
    if ( *( (UInt32Ptr) pData ) == MARKER )
    {
        ... // Do something here
        break;
    }

    pData++;
}

// Option 2 -------------------------------------------
while ( pData < pEnd )
{
    if ( ( *pData == MARKER_BYTE ) && ( *( (UInt32Ptr) pData ) == MARKER ) )
    {
        ... // Do something here
        break;
    }

    pData++;
}

私Option 2は速いと思いますが、私の推論が正しいかどうかはわかりません。

Option 1最初にメモリから4バイトを読み取り、それを4バイトの定数と照合し、見つからない場合は次のバイトにステップして最初からやり直します。メモリからの次の4バイトの準備完了は、すでに読み取られた3バイトとオーバーラップするため、同じバイトを再度フェッチする必要があります。私の4バイトマーカーの前のほとんどのバイトは2回読み取られます。

Option 2一度に1バイトのみを読み取り、その1バイトが一致する場合は、そのアドレスから4バイトの値全体を読み取ります。このようにして、すべてのバイトが1回だけ読み取られ、一致する4バイトだけが2回読み取られます。

私の推論は正しいですか、それとも私は何かを見落としていますか？

そして、誰かがそれを持ち出す前に、はい、私は本当にこの種の最適化を実行する必要があります。:)

編集：このコードはIntel/AMDベースのコンピューターでのみ実行されることに注意してください。通常のx86/x64コンピューター（デスクトップ/サーバー）が問題やパフォーマンスの低下なしにこれを実行する限り、他のアーキテクチャーがこれを実行できないかどうかは気にしません。

編集2：コンパイラはVC ++ 2008です（それが役立つ場合）。

4

4 に答える 4

6

Boyer-Moore アプローチを試すこともできます。

pData = start + 3;
int i;

while(pData < pEnd) {
    for(i = 0; i < 4; ++i) {
        if (*(pData-i) != MARKER_BYTE) {
            pData += 4-i;
            break;
        }
    }
    if (i == 4) {
        /* do something here with (pData-3) */
        break;
    }
}

運が良ければ、一致が見つかるまで 4 バイトごとにしかテストされません。

それがすべてのバイトをテストするよりも速いか遅いかは、このような短いパターンの推測です。

于 2012-05-15T20:06:03.943 に答える
3

オプション 1 では、アラインされていないメモリ アクセスが大量に実行されます。これがハードウェアで可能かどうかはわかりません。少なくとも一部のハードウェアでは、Windows は結果として生じる例外をインターセプトし、非常にゆっくりとメモリ アクセスをエミュレートします。パフォーマンスの完全な災害。

とにかく、あなたはすでにコードを持っています。それを測定して、100% 確信してみませんか?

于 2012-05-15T19:40:25.000 に答える
1

このアプローチは完全ではありませんが、0xAA パターンを一度に 8 バイト検索することが基本的な考え方です。見つかった場合は、MARKER パターンの二次検索を実行できます。

フェーズ 1: 配列が 8 バイトでアラインされるまで、バイトごとのテストを実行します。

フェーズ 2: #define HAS_NUL_BYTE(x) ((x) - 0x0101010101010101ull) & ~x & 0x8080808080808080ull)

uint64_t  value;
for (...) {
    value = *(uint64_t *) array[i] ^ 0xAAAAAAAAAAAAAAAAull;
    if (HAS_NUL_BYTE (value) != 0) {
        perform secondary search for the MARKER pattern
    }
    i += 8;
}

このアプローチには、(うまくいけば) 次の利点があります。

  1. 0xAA がウィンドウにない場合、8 バイトではなく 8 バイトごとに 1 回の比較。
  2. ミスアラインされたメモリ アクセスが少なくなります。

欠点は次のとおりです...

  1. もっと複雑です
  2. 配列に多数の 0xAA バイト (ただし MARKER は含まない) が含まれている場合、一次検索での誤検出がパフォーマンスに影響します。

もう1つ-これはWindowsの下のx86-64でのみ実行されると述べたので、アセンブリでこれを書くことを検討しましたか? そうであれば、PCMPEQB 命令が役に立つかもしれません。

お役に立てれば。

于 2012-05-16T01:28:27.017 に答える
1

オプション 2. 最初の 256 回のうち 255 回が必要なバイトではない場合、4 バイトをフェッチする理由はありません。

ピートのために、ループを展開します。

編集：展開。長さはnDataLengthです。次のように言えます。

pEnd1 = pData + (nDataLength & -8);
while (pData < pEnd1){
  if (pData[0] == theByteIWant){ ... }
  if (pData[1] == theByteIWant){ ... }
  ...
  if (pData[7] == theByteIWant){ ... }
  pData += 8;
}
while(pData < pEnd){
  if (pData[0] == theByteIWant){ ... }
  pData++;
}

それが何をするか見てください。(pData < pEnd)答えがほぼ常に同じである質問をするのに半分の時間を費やすことはありません。

于 2012-05-15T20:59:51.063 に答える