12

最適化と分岐予測についての議論の要点を示すために、Cコードを書きました。それから、私は予想よりもさらに多様な結果に気づきました。私の目標は、C ++とCの間で共通のサブセットであり、両方の言語の標準に準拠し、かなり移植性のある言語でそれを書くことでした。さまざまなWindowsPCでテストされました。

#include <stdio.h>
#include <time.h>

/// @return - time difference between start and stop in milliseconds
int ms_elapsed( clock_t start, clock_t stop )
{
    return (int)( 1000.0 * ( stop - start ) / CLOCKS_PER_SEC );
}

int const Billion = 1000000000;
/// & with numbers up to Billion gives 0, 0, 2, 2 repeating pattern 
int const Pattern_0_0_2_2 = 0x40000002; 

/// @return - half of Billion  
int unpredictableIfs()
{
    int sum = 0;
    for ( int i = 0; i < Billion; ++i )
    {
        // true, true, false, false ...
        if ( ( i & Pattern_0_0_2_2 ) == 0 )
        {
            ++sum;
        }
    }
    return sum;
}

/// @return - half of Billion  
int noIfs()
{
    int sum = 0;
    for ( int i = 0; i < Billion; ++i )
    {
        // 1, 1, 0, 0 ...
        sum += ( i & Pattern_0_0_2_2 ) == 0;
    }
    return sum;
}

int main()
{
    clock_t volatile start;
    clock_t volatile stop;
    int volatile sum;
    printf( "Puzzling measurements:\n" );

    start = clock();
    sum = unpredictableIfs();
    stop = clock();
    printf( "Unpredictable ifs took %d msec; answer was %d\n"
          , ms_elapsed(start, stop), sum );

    start = clock();
    sum = unpredictableIfs();
    stop = clock();
    printf( "Unpredictable ifs took %d msec; answer was %d\n"
          , ms_elapsed(start, stop), sum );

    start = clock();
    sum = noIfs();
    stop = clock();
    printf( "Same without ifs took %d msec; answer was %d\n"
          , ms_elapsed(start, stop), sum );

    start = clock();
    sum = unpredictableIfs();
    stop = clock();
    printf( "Unpredictable ifs took %d msec; answer was %d\n"
          , ms_elapsed(start, stop), sum );
}

VS2010でコンパイル。/O2の最適化IntelCore2、WinXPの結果:

Puzzling measurements:
Unpredictable ifs took 1344 msec; answer was 500000000
Unpredictable ifs took 1016 msec; answer was 500000000
Same without ifs took 1031 msec; answer was 500000000
Unpredictable ifs took 4797 msec; answer was 500000000

編集:コンパイラの完全なスイッチ:

/ Zi / nologo / W3 / WX- / O2 / Oi / Oy- / GL / D "WIN32" / D "NDEBUG" / D "_CONSOLE" / D "_UNICODE" / D "UNICODE" / Gm- / EHsc / GS / Gy / fp:precise / Zc:wchar_t / Zc:forScope / Fp "Release \ Trying.pch" / Fa "Release \" / Fo "Release \" / Fd "Release \ vc100.pdb" / Gd / analysis- / errorReport:queue

他の人がそのような投稿をしました...MinGW、g ++ 4.71、-O1最適化Intel Core 2、WinXPの結果でコンパイル:

Puzzling measurements:
Unpredictable ifs took 1656 msec; answer was 500000000
Unpredictable ifs took 0 msec; answer was 500000000
Same without ifs took 1969 msec; answer was 500000000
Unpredictable ifs took 0 msec; answer was 500000000

また、彼は-O3最適化のためにそのような結果を投稿しました:

Puzzling measurements:
Unpredictable ifs took 1890 msec; answer was 500000000
Unpredictable ifs took 2516 msec; answer was 500000000
Same without ifs took 1422 msec; answer was 500000000
Unpredictable ifs took 2516 msec; answer was 500000000

今、私は質問があります。ここで何が起こっているのですか?

より具体的には...固定関数はどのようにこれほど異なる時間を要するのでしょうか?私のコードに何か問題がありますか?Intelプロセッサにトリッキーなものはありますか?コンパイラは何か奇妙なことをしていますか?64ビットプロセッサで実行された32ビットコードが原因である可能性がありますか?

ご清聴ありがとうございました!

編集: g++-O1が他の2つの呼び出しで戻り値を再利用することを受け入れます。また、g++-O2とg++-O3には、最適化を除外する欠陥があることも認めます。測定された速度の大幅な多様性(450%!!!)は、依然として不思議なようです。

VS2010で作成されたコードの逆アセンブルを見ました。インラインでunpredictableIfs3回行いました。インライン化されたコードはかなり似ていました。ループは同じでした。インラインではありませんでしnoIfsた。それはnoIfs少し展開しました。1回の反復で4つのステップが必要です。増分をジャンプするために使用noIfs中に書かれたように計算します。unpredictableIfsjne

4

3 に答える 3

13

-O1を使用すると、gcc-4.7.1は1回だけ呼び出し、結果を再利用します。これは、gcc-4.7.1がunpredictableIfs純粋関数であると認識するため、呼び出されるたびに結果が同じになるためです。(私は、生成されたアセンブリを確認することで確認しました。)

最適化レベルが高くなると、関数はインライン化され、コンパイラーはそれが同じコードであることを認識しなくなるため、ソースに関数呼び出しが表示されるたびに実行されます。

それとは別に、私のgcc-4.7.1は、または(再利用の問題は別として、どちらも同じコードを生成します)を使用するunpredictableIfs場合に最適ですが、。を使用するとはるかに適切に処理されます。ただし、同じコードの異なる実行間のタイミングはここでは一貫しています-10ミリ秒(の粒度)が等しいか異なるため、について報告された時間の大幅な異なる原因が何であるかわかりません。-O1-O2noIfs-O3clockunpredictableIfs-O3

を使用-O2すると、forのループunpredictableIfsはで生成されたコードと同じになります-O1(レジスタスワッピングを除く)。

.L12:
    movl    %eax, %ecx
    andl    $1073741826, %ecx
    cmpl    $1, %ecx
    adcl    $0, %edx
    addl    $1, %eax
    cmpl    $1000000000, %eax
    jne .L12

そしてnoIfsそれは似ています:

.L15:
    xorl    %ecx, %ecx
    testl   $1073741826, %eax
    sete    %cl
    addl    $1, %eax
    addl    %ecx, %edx
    cmpl    $1000000000, %eax
    jne .L15

それがあった場所

.L7:
    testl   $1073741826, %edx
    sete    %cl
    movzbl  %cl, %ecx
    addl    %ecx, %eax
    addl    $1, %edx
    cmpl    $1000000000, %edx
    jne .L7

-O1。両方のループは同じ時間で実行されunpredictableIfs、少し速くなります。

を使用-O3すると、のループunpredictableIfsが悪化します。

.L14:
    leal    1(%rdx), %ecx
    testl   $1073741826, %eax
    cmove   %ecx, %edx
    addl    $1, %eax
    cmpl    $1000000000, %eax
    jne     .L14

そしてnoIfs(ここのセットアップコードを含む)のために、それはより良くなります:

    pxor    %xmm2, %xmm2
    movq    %rax, 32(%rsp)
    movdqa  .LC3(%rip), %xmm6
    xorl    %eax, %eax
    movdqa  .LC2(%rip), %xmm1
    movdqa  %xmm2, %xmm3
    movdqa  .LC4(%rip), %xmm5
    movdqa  .LC5(%rip), %xmm4
    .p2align 4,,10
    .p2align 3
.L18:
    movdqa  %xmm1, %xmm0
    addl    $1, %eax
    paddd   %xmm6, %xmm1
    cmpl    $250000000, %eax
    pand    %xmm5, %xmm0
    pcmpeqd %xmm3, %xmm0
    pand    %xmm4, %xmm0
    paddd   %xmm0, %xmm2
    jne .L18

.LC2:
    .long   0
    .long   1
    .long   2
    .long   3
    .align 16
.LC3:
    .long   4
    .long   4
    .long   4
    .long   4
    .align 16
.LC4:
    .long   1073741826
    .long   1073741826
    .long   1073741826
    .long   1073741826
    .align 16
.LC5:
    .long   1
    .long   1
    .long   1
    .long   1

一度に4回の反復を計算するため、そのときのnoIfsほぼ4倍の速度で実行されます。

于 2013-02-19T19:25:40.983 に答える
2

そうです、64ビットLinux上のgccからのアセンブラーコードを見ると、最初のケースは-O1で、関数UnpredictableIfsは実際に1回だけ呼び出され、結果が再利用されます。

-O2と-O3を使用すると、関数がインライン化され、所要時間は同じになります。また、どちらのコードにも実際の分岐はありませんが、2ビットのコードの変換は多少異なります。「sum」を更新する行を切り取っています[%edxどちらの場合も]

UnpredictableIfs:

movl    %eax, %ecx
andl    $1073741826, %ecx
cmpl    $1, %ecx
adcl    $0, %edx
addl    $1, %eax

NoIfs:

xorl    %ecx, %ecx
testl   $1073741826, %eax
sete    %cl
addl    $1, %eax
addl    %ecx, %edx

ご覧のとおり、まったく同じではありませんが、非常によく似ています。

于 2013-02-19T19:31:40.523 に答える
2

Windowsでの結果の範囲(1016ミリ秒から4797ミリ秒)について:clock()MSVCでは経過壁時間が返されることを知っておく必要があります。標準では、プロセスによって費やされたCPU時間clock()の概算を返す必要があり、他の実装はこれをより適切に実行します。

MSVCが壁時間を与えていることを考えると、テストの1回の反復の実行中にプロセスがプリエンプトされた場合、コードがほぼ同じCPU時間で実行されたとしても、はるかに大きな結果が得られる可能性があります。

またclock()、多くのWindows PCでは、解像度がかなりお粗末で、多くの場合11〜19ミリ秒であることに注意してください。十分な反復を行ったので、それは約1%にすぎないので、それは不一致の一部ではないと思いますが、ベンチマークを作成するときに注意することをお勧めします。移植性を求めているとのことですが、Windowsでより良い測定が必要な場合は、QueryPerformanceCounter壁時計の経過時間ですが、ほぼ確実にはるかに優れた解像度が得られるように使用できます。

更新: 1つのケースで長いランタイムが一貫して発生していることを知った後、VS2010を起動し、結果を再現しました。私は通常、一部の実行で約1000ミリ秒、他の実行で750ミリ秒、説明のつかない実行で5000ミリ秒以上の何かを得ていました。

観察:

  1. すべての場合において、unpredictableIfs()コードがインライン化されました。
  2. noIfs()コードを削除しても影響はありませんでした(したがって、長い時間はそのコードの副作用ではありませんでした)。
  3. スレッドアフィニティを単一のプロセッサに設定しても効果はありませんでした。
  4. 5000ミリ秒の時間は常に後のインスタンスでした。後のインスタンスには、ループの開始 lea ecx,[ecx]に追加の命令があることに注意しました。なぜそれが5倍の違いを生むのかわかりません。それ以外は、初期のインスタンスと後のインスタンスは同じコードでした。
  5. および変数volatileからを削除すると、長時間の実行が少なくなり、750ミリ秒の実行が多くなり、1000ミリ秒の実行はありませんでした。(生成されたループコードは、すべての場合でまったく同じように見えますが、sではありません。)startstoplea
  6. volatile変数からを削除するsumと(ただし、クロックタイマー用に保持されます)、長時間の実行はどの位置でも発生する可能性があります。
  7. すべてのvolatile修飾子を削除すると、一貫性のある高速(750ミリ秒)の実行が得られます。(コードは以前のコードと同じように見えますが、代わりにedi選択されました。)sumecx

MSVCでパフォーマンスに予測できない結果が生じることを除いて、これらすべてから何を結論付けるかはvolatileわかりません。したがって、必要な場合にのみ適用する必要があります。

更新2:逆アセンブルはほとんど同じですが、揮発性の使用に関連する一貫した実行時の違いが見られます。

揮発性の場合:

Puzzling measurements:
Unpredictable ifs took 643 msec; answer was 500000000
Unpredictable ifs took 1248 msec; answer was 500000000
Unpredictable ifs took 605 msec; answer was 500000000
Unpredictable ifs took 4611 msec; answer was 500000000
Unpredictable ifs took 4706 msec; answer was 500000000
Unpredictable ifs took 4516 msec; answer was 500000000
Unpredictable ifs took 4382 msec; answer was 500000000

各インスタンスの逆アセンブリは次のようになります。

    start = clock();
010D1015  mov         esi,dword ptr [__imp__clock (10D20A0h)]  
010D101B  add         esp,4  
010D101E  call        esi  
010D1020  mov         dword ptr [start],eax  
    sum = unpredictableIfs();
010D1023  xor         ecx,ecx  
010D1025  xor         eax,eax  
010D1027  test        eax,40000002h  
010D102C  jne         main+2Fh (10D102Fh)  
010D102E  inc         ecx  
010D102F  inc         eax  
010D1030  cmp         eax,3B9ACA00h  
010D1035  jl          main+27h (10D1027h)  
010D1037  mov         dword ptr [sum],ecx  
    stop = clock();
010D103A  call        esi  
010D103C  mov         dword ptr [stop],eax  

揮発性なし:

Puzzling measurements:
Unpredictable ifs took 644 msec; answer was 500000000
Unpredictable ifs took 624 msec; answer was 500000000
Unpredictable ifs took 624 msec; answer was 500000000
Unpredictable ifs took 605 msec; answer was 500000000
Unpredictable ifs took 599 msec; answer was 500000000
Unpredictable ifs took 599 msec; answer was 500000000
Unpredictable ifs took 599 msec; answer was 500000000

    start = clock();
00321014  mov         esi,dword ptr [__imp__clock (3220A0h)]  
0032101A  add         esp,4  
0032101D  call        esi  
0032101F  mov         dword ptr [start],eax  
    sum = unpredictableIfs();
00321022  xor         ebx,ebx  
00321024  xor         eax,eax  
00321026  test        eax,40000002h  
0032102B  jne         main+2Eh (32102Eh)  
0032102D  inc         ebx  
0032102E  inc         eax  
0032102F  cmp         eax,3B9ACA00h  
00321034  jl          main+26h (321026h)  
    stop = clock();
00321036  call        esi
// The only optimization I see is here, where eax isn't explicitly stored
// in stop but is instead immediately used to compute the value for the
// printf that follows.

レジスターの選択を除いて、大きな違いは見られません。

于 2013-02-20T13:56:49.653 に答える