8

int配列で特定の値を検索する2つのバージョンがあります。

最初のバージョンは単純なものです

int FindWithoutBlock(int * Arr, int ArrLen, int Val)
{
    for ( int i = 0; i < ArrLen; i++ )
        if ( Arr[i] == Val )
          return i;
 return ArrLen;
}

2番目のバージョンはより高速である必要があります。渡される配列は、前の場合より1要素大きい必要があります。5つの値を持つ配列の場合、6つのintを割り当ててから、次のようにします。

int FindWithBlock(int * Arr, int LastCellIndex, int Val)
{
    Arr[LastCellIndex]  = Val;

    int i;
    for ( i = 0 ; Arr[i] != Val; i++ );
    return i;
}

このバージョンの方が高速である必要があります。Arrを反復するたびに配列の境界を確認する必要はありません。

今「問題」。デバッグで100K要素の配列に対してこれらの関数を100K回実行すると、2番目のバージョンは約2倍高速になります。ただし、リリースでは、最初のバージョンは約6000倍高速です。そして問題はその理由です。

これを実証するプログラムは、http：//eubie.sweb.cz/main.cppにあります。

どんな洞察も大歓迎です。ダニエル

4

7 に答える 7

8

DevStudio 2005 を使用した結果は次のとおりです。

デバッグ：

  • ブロックなし: 25.109
  • ブロック付：19.703

リリース：

  • ブロックなし: 0
  • ブロック付：6.046

DevStudio 内からではなく、コマンド ラインからこれを実行することが非常に重要です。DevStudio は、アプリのパフォーマンスに影響を与える何らかの処理を行います。

実際に何が起こっているのかを知る唯一の方法は、アセンブラー コードを見ることです。リリースで生成されたアセンブラは次のとおりです。

FindWithoutBlock:
00401000  xor         eax,eax 
00401002  cmp         dword ptr [ecx+eax*4],0F4240h 
00401009  je          FindWithoutBlock+1Ah (40101Ah) 
0040100B  add         eax,1 
0040100E  cmp         eax,186A0h 
00401013  jl          FindWithoutBlock+2 (401002h) 
00401015  mov         eax,186A0h 
0040101A  ret

コンパイラが ArrLen パラメーターを削除し、定数に置き換えたことに注意してください。それも機能として残しています。

コンパイラが他の関数 (FindWithBlock) で行ったことは次のとおりです。

004010E0  mov         dword ptr [esp+38h],186A0h 
004010E8  mov         ebx,0F4240h 
004010ED  mov         dword ptr [esi+61A80h],ebx 
004010F3  xor         eax,eax 
004010F5  cmp         dword ptr [esi],ebx 
004010F7  je          main+0EFh (40110Fh) 
004010F9  lea         esp,[esp] 
00401100  add         eax,1 
00401103  cmp         dword ptr [esi+eax*4],ebx 
00401106  jne         main+0E0h (401100h) 
00401108  cmp         eax,186A0h 
0040110D  je          main+0F5h (401115h) 
0040110F  call        dword ptr [__imp__getchar (4020D0h)] 
00401115  sub         dword ptr [esp+38h],1 
0040111A  jne         main+0CDh (4010EDh)

ここでは、関数がインライン化されています。これlea esp,[esp]は、次の命令を整列するための 7 バイトの nop です。コードは、インデックス 0 を他のすべてのインデックスとは別にチェックしますが、メイン ループは FindWithoutBlock バージョンよりも間違いなくタイトです。

うーん。FindWithoutBlock を呼び出すコードは次のとおりです。

0040106F  mov         ecx,edi 
00401071  mov         ebx,eax 
00401073  call        FindWithoutBlock (401000h) 
00401078  mov         ebp,eax 
0040107A  mov         edi,186A0h 
0040107F  cmp         ebp,186A0h 
00401085  je          main+6Dh (40108Dh) 
00401087  call        dword ptr [__imp__getchar (4020D0h)] 
0040108D  sub         edi,1 
00401090  jne         main+5Fh (40107Fh)

あはは！FindWitoutBlock 関数が呼び出されるのは 1 回だけです。コンパイラは、関数が毎回同じ値を返すことを発見し、1 回の呼び出しに最適化しました。FindWithBlock では、検索の前に配列に書き込むため、コンパイラは同じ仮定を行うことができません。したがって、配列は呼び出しごとに (潜在的に) 異なります。

これをテストするには、次のvolatileようなキーワードを追加します:-

int FindWithoutBlock(volatile int * Arr, int ArrLen, int Val)
{
    for ( int i = 0; i < ArrLen; i++ )
        if ( Arr[i] == Val )
            return i;

    return ArrLen;
}

int FindWithBlock(volatile int * Arr, int LastCellIndex, int Val)
{
    Arr[LastCellIndex]  = Val;

    int i;
    for ( i = 0 ; Arr[i] != Val; i++ );

    return i;
}

これを行うと、両方のバージョンが同じ時間 (6.040) に実行されます。メモリ アクセスが主要なボトルネックであるため、FindWithoutBlock のより複雑なテストは全体の速度には影響しません。

于 2012-05-25T11:06:44.237 に答える
2

まず、ewwwwww 嫌な C ゴミ。std::findそしてイテレータ？

しかし第二に、コンパイラのオプティマイザは、2 番目ではなく 1 番目の形式を認識するように作成されています。たとえば、インライン、アンロール、またはベクトル化されている可能性がありますが、2 番目のものはそうではありません。

一般的なケースでは、キャッシュの問題を考慮してください。配列の末尾に触れてから先頭に移動しています。これはキャッシュ ミスの可能性があります。ただし、最初のブロックでは、配列をシーケンシャルにのみ元気よく進んでいます-キャッシュの一貫性が向上しています。

于 2012-05-25T10:48:16.357 に答える
2

これは、回答というよりも拡張されたコメントです。Skizz はすでに質問に「あはは! FindWithoutBlock 関数は 1 回しか呼び出されていない!」と答えています。

テスト ドライバー
私は通常、テスト ドライバーのコードとテスト記事を別々のファイルに入れる傾向があります。1 つには、テスト ドライバーを配布するつもりはありません。別の例として、あなたが行ったようにそれらを組み合わせると、オプティマイザーは、関数を 100,000 回ではなく 1 回呼び出すなど、実際にはやりたくないことを実行できます。それらを分離すると、ドライバーとテスト記事に異なる最適化レベルを使用できます。同じことを 10 万回実行するループが本当に 10 万回実行されるように、最適化されていないドライバーをコンパイルする傾向があります。一方、テスト記事は、リリースに期待される最適化でコンパイルされています。

getchar()
の使用 CPU 使用率をテストするときに、テスト ループ内で I/O を使用するのは通常、悪い考えです。検出する項目が配列にない場合、テスト コードは getchar を呼び出しています。[残りの不完全な分析は省かれています。]更新:getchar検出される項目が配列内にあるときに、テスト コードが呼び出されます。テスト コードでアイテムが見つからない (したがってgetchar呼び出されない) ことが保証されていても、その呼び出しを行うことはお勧めできません。代わりに、速くて無害なことをしてください。

C 対 C++
あなたのコードは、C++ というよりも C± に似ています。mallocではなくを使用してnewおり、C と C++ の I/O を混在させており、 などの C++ ライブラリを使用していませんstd::find。これは、C から C++ に移行する場合によくあることです。などを意識すると良いstd::findです。これにより、機能を完全に排除できますFindWithoutBlock。

時期尚早な最適化
そのFindWithBlock定式化を使用する唯一の理由は、この検索がボトルネックになるためです。では、これは本当にボトルネックなのでしょうか? 配列を変更する必要がなく、したがって配列引数を としてマークできるため、定式化 (およびさらに優れている) は間違いなくより良い方法FindWithoutBlockです。配列を変更しているため、配列をそのようにマークすることはできません。std::findconstFindWithBlock

于 2012-05-25T12:33:50.263 に答える
0

最初のfor..ループには、反復ごとに2つの条件が含まれ、2番目のforループには、ループごとに1つの反復が含まれます。反復回数が多い場合、2番目の条件とイテレーターの増分の間にRAW依存関係があるため、この違いが示されるはずです。しかし、私はまだスピードアップがそれほど速くあるべきだとは思いません。

于 2012-05-25T10:39:38.607 に答える
0

私が観察したのは、最初のケースでは、コンパイラが実行時にループのサイズを認識していることです (例: < ArrLen)。2 番目のケースでは、コンパイラは認識できません。

于 2012-05-25T10:29:08.787 に答える
0

あなたのコンパイラは賢いです。

LLVM Try Outページを使用すると、次の IR が生成されます。

define i32 @FindWithoutBlock(i32* nocapture %Arr, i32 %ArrLen, i32 %Val) nounwind uwtable readonly

define i32 @FindWithBlock(i32* nocapture %Arr, i32 %ArrLen, i32 %Val) nounwind uwtable

唯一の違いはreadonly、最初の関数に属性が存在することです。

言語リファレンスページから:

読み取り専用

この属性は、関数がポインター引数 (byval 引数を含む) を介して書き込みを行わないこと、または呼び出し元関数から見える状態 (メモリ、制御レジスタなど) を変更しないことを示します。ポインター引数を逆参照し、呼び出し元で設定される可能性のある状態を読み取る場合があります。readonly 関数は、同じ引数セットとグローバル状態で呼び出された場合、常に同じ値を返します (または例外を同じようにアンワインドします)。C++ 例外スロー メソッドを呼び出して例外をアンワインドすることはできません。

これは、オプティマイザーが、関数が常に同じ計算を (特定のループに対して) 返し、それをループの外に引き上げることに気付く可能性があることを意味します。

于 2012-05-25T13:07:59.857 に答える
0

最初の例では、反復ごとに 2 つの条件がチェックされます:i < ArrLenとArr[i] == Val。2 番目の例では、確認する条件は 1 つだけです。そのため、最初のループが 2 倍遅くなります。

GCC を使用して同じ動作を観察することはできません。最初のループはまだ遅いです。

と-O0:

Without block: 25.83
With block: 20.35

と-O3:

Without block: 6.33
With block: 4.75

コンパイラーは何らかの形で配列にないことを推測したSearchValため、それを検索する関数を呼び出す理由はないと思います。

于 2012-05-25T10:35:02.920 に答える