3

サイズが約 1MB のファイルを解析し、最初の 300KB を読み取り、多数の特定の署名を検索しています。私の戦略は、バイトごとに、そのバイトがマップ/ベクトル/署名の先頭にある可能性があることがわかっているバイトの中にあるかどうかを確認し、そうであれば完全な署名を探すことです-この例では、バイトは x37、x50、および x52 です。合計 90 個のファイル (実際には 9 個のファイルを 10 回) を処理すると、次のコードは 2.122 秒で実行されます。

        byte * bp = &buffer[1];
        const byte * endp = buffer + bytesRead - 30; // a little buffer for optimization - no signature is that long
        //multimap<byte, vector<FileSignature> >::iterator lb, ub;
        map<byte, vector<FileSignature> >::iterator findItr;
        vector<FileSignature>::iterator intItr;
        while (++bp != endp)
        {
            if (*bp == 0x50 || *bp == 0x52 || *bp == 0x37)  // Comparison line
            {
                findItr = mapSigs.find(*bp);
                for (intItr = findItr->second.begin(); intItr != findItr->second.begin(); intItr++)
                {
                    bool bMatch = true;
                    for (UINT i = 1; i < intItr->mSignature.size(); ++i)
                    {
                        if (intItr->mSignature[i] != bp[i])
                        {
                            bMatch = false;
                            break;
                        }
                    }

                    if (bMatch)
                    {
                        CloseHandle(fileHandle);
                        return true; 
                    }
                }
            }
        }

ただし、私の最初の実装は 84 秒という遅い時間で終了します。唯一の違いは、上記の「// 比較行」というラベルの付いた行に関連しています。

findItr = mapSigs.find(*bp);
if (findItr != mapSigs.end())
...

3 つの値を含むベクトルを使用した非常によく似た実装でも、処理が非常に遅くなります (190 秒)。

if (find(vecFirstChars.begin(), vecFirstChars.end(), *bp) != vecFirstChars.end())
{
    findItr = mapSigs.find(*bp);
    ...

しかし、ベクトルの要素に直接アクセスする実装は、かなりうまく機能します (8.1 秒)。静的な比較ほどではありませんが、他のオプションよりもはるかに優れています。

if (vecFirstChars[0] == *bp || vecFirstChars[1] == *bp || vecFirstChars[2] == *bp)
{
    findItr = mapSigs.find(*bp);
    ...

これまでで最速の実装 (以下のコンポーネント 10 に着想を得たもの) は次のとおりで、約 2.0 秒を記録しています。

bool validSigs[256] = {0};
validSigs[0x37] = true;
validSigs[0x50] = true;
validSigs[0x52] = true;

while (++bp != endp)
{
    if (validSigs[*bp])
    {
    ...

これを拡張して、2 番目の文字が有効かどうかを確認するために 2 つの validSig を使用すると、合計実行時間が 0.4 秒に短縮されます。

他の実装の方がパフォーマンスが良いと思います。特にマップは、より多くの署名プレフィックスが追加されるにつれてスケーリングする必要があり、検索は O(log(n)) 対 O(n) です。私は何が欠けていますか？私の唯一の暗い推測は、静的な比較と（あまり存在しないが）ベクトルのインデックス付けにより、比較に使用される値をレジスタまたはその他の場所にキャッシュして、読み取りよりも大幅に高速化することです。記憶から。これが正しい場合、特定の値が頻繁に使用されることをコンパイラに明示的に伝えることができますか? 以下のコードで利用できる明らかではない他の最適化はありますか?

Visual Studio 2008 でコンパイルしています。

4

2 に答える 2

1

これは、実行された命令の数に帰着するのに十分簡単です。ベクター、マップ、またはルックアップ テーブルはすべて CPU レベル 1 データ キャッシュに常駐するため、メモリ アクセスに時間がかかりません。ルックアップ テーブルに関しては、ほとんどのバイトがシグネチャ プレフィックスと一致しない限り、ブランチ プレディクタはフロー制御に時間がかかるのを停止します。(ただし、他の構造ではフロー制御のオーバーヘッドが発生します。)

つまり、ベクトル内の各値を順番に比較するには、3 つの比較が必要です。マップは O(log N) ですが、リンクされたデータ構造をナビゲートするため、係数 (big-O 表記では無視されます) が大きくなります。構造体へのアクセスは 1 つの機械語命令で完了できるため、ルックアップ テーブルは小さな係数の O(1) であり、残りは 0 との 1 つの比較だけです。

パフォーマンスを分析する最良の方法は、valgrind/kcachegrind などのプロファイラー ツールを使用することです。

于 2012-11-08T00:42:15.980 に答える
0

「定数に対する比較」は、3 つのメモリアドレスを 3 つの定数と比較します。このケースは、コンパイラがそのように感じた場合、アンロールやビット最適化などを行うのが非常に簡単になります。記述された ASM がここに持つ唯一のブランチは、非常に予測可能です。

リテラル 3 要素のベクトル ルックアップの場合、ベクトル値のアドレスを逆参照する追加コストが発生します。

ベクトル ループの場合、コンパイラはこの時点でベクトルの大きさを認識していません。したがって、一般的なループを作成する必要があります。このループには分岐があり、一方の方向に 2 回、次に他方の方向に進む分岐です。コンピュータがヒューリスティックな「前回と同じように分岐する」を使用すると、多くの分岐予測が失敗します。

その理論を検証するには、分岐をより予測可能にしてみてください。一度に最大 100 の異なる入力バイトの各要素を検索してから、次の要素を検索します。これにより、コード内の 33% ではなく、約 98% の確率で単純な分岐予測が機能します。つまり、署名がなくなるまで、署名 0 の 100 (または任意の) 文字をスキャンし、次に署名 1 の 100 (または任意の) 文字をスキャンします。次に、次の 100 文字のブロックに進み、署名をスキャンします。100 を選択したのは、分岐予測の失敗を回避しようとしているからです。数パーセントの分岐予測の失敗はそれほど悪くないと考えています。:)

解決策としてはmap、well maps には一定の高いオーバーヘッドがあるため、遅いことはかなり予測可能です。a の主な用途は、map大規模な n ルックアップを処理することと、それらに対するコーディングが非常に簡単であるという事実です。

于 2012-11-08T03:09:58.933 に答える