30

コードの一部で対数関数を使用する必要がありますが、底は問題ではありません。そのため、大きな違いが見つかった場合は、パフォーマンスによってlog()、log2()、およびから選択することにしました。log10()(これらの関数をそれぞれln、lb、および と呼びlgます)。

なぜ私はこれについて大騒ぎしているのですか？最適化アルゴリズムの反復ごとに 400,000,000 回も関数を呼び出すためです。これはオプションでも、私の質問のトピックでもありません。

次のように、いくつかの非常に基本的なテストを設定しました。

timespec start, end;
double sum = 0, m;

clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
for (int n = 1; n < INT_MAX; ++n)
{
    m = n * 10.1;
    sum += log(m);
}
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

cout << "ln=";
cout << diff(start, end).tv_sec << ":" << diff(start, end).tv_nsec << endl;

... // likewise for log2 and log10

( timespec diff(timespec start, timespec end)必要に応じて....)

以下の結果が得られました。

GCC v4.6.3

-O0
ln=140:516853107
lb=155:878100147
lg=173:534086352

-O1
ln=133:948317112
lb=144:78885393
lg=163:870021712

-O2
ln=9:108117039
lb=9:134447209
lg=4:87951676

-O3
ln=9:102016996
lb=9:204672042
lg=4:153153558

でコンパイルした出力を見てきましたが-S、違いを完全に理解するのに十分なほどアセンブラを把握していません。-S出力: -O0 -S、-O3 -S

lgO2/O3 での最適化が優れているのはなぜですか?

編集:ソース コード、3 番目のループのタイプミスに注意してください。drhirsch と janneb の回答から多くのことを学びましたが、質問が閉じられたため、最も近いと思われる回答を受け入れました。

4

4 に答える 4

6

これは、Cライブラリのlog（）関数の実装、コンパイラのバージョン、ハードウェアアーキテクチャなどに依存します。とにかく、以下では、glibc2.11を使用してx86-64でGCC4.4を使用しています。

行を追加するように例を変更する

cout << "sum=" << sum << endl;

これにより、コンパイラがlog（）呼び出しを最適化できなくなります。コメントで述べたように、次のタイミングが得られます（1秒のみ、-O2）。

  • ログ：98秒
  • log2：105秒
  • log10：120秒

これらのタイミングは、元の投稿の-O0および-O1のタイミングとほぼ一致しているようです。より高い最適化レベルでは、ログ評価が最適化されるため、-O2と-O3の結果は大きく異なります。

さらに、「perf」プロファイラーを使用したログの例を見ると、レポートの上位5人の違反者は次のとおりです。


# Samples: 3259205
#
# Overhead         Command              Shared Object  Symbol
# ........  ..............  .........................  ......
#
    87.96%             log  /lib/libm-2.11.1.so        [.] __ieee754_log
     5.51%             log  /lib/libm-2.11.1.so        [.] __log
     2.88%             log  ./log                      [.] main
     2.84%             log  /lib/libm-2.11.1.so        [.] __isnan
     0.69%             log  ./log                      [.] log@plt

mainを除いて、他のすべてのシンボルはlog（）呼び出しに関連しています。これらを要約すると、この例の合計実行時間の97％がlog（）に費やされていると結論付けることができます。

__ieee754_logの実装は、ここglibcgitリポジトリにあります。同様に、他の実装はlog2、log10です。以前のリンクはHEADバージョンへのリンクであることに注意してください。リリースされたバージョンについては、対応するブランチを参照してください。

于 2012-05-30T08:09:39.237 に答える
5

残念ながら、OP は元のコードを表示できませんでした。彼はコードを難読化し、アセンブリにわずかに変換することを選択しました。

アセンブリコードでは、OPがリンクされています（私による注釈）：

.L10:
    cvtsi2sd %ebx, %xmm0         // convert i to double
    xorpd    %xmm1, %xmm1        // zero 
    mulsd    .LC0(%rip), %xmm0   // multiply i with 10.1
    ucomisd   %xmm0, %xmm1       // compare with zero
    jae       .L31               // always below, never jump

    addl    $1, %ebx             // i++
    cmpl    $2147483647, %ebx    // end of for loop
    jne     .L10
    ...
.L31:
    call    log10, log2, whatever...  // this point is never reached

への呼び出しが実行されないことがわかりlogます。特に、gdb を使用してステップ スルーする場合はそうです。コードで実行されるのは、2 31の乗算と double の比較だけです。

-O2これはまた、誰かがこれを奇妙に感じた場合に備えて、 でコンパイルするとログ関数の実行速度が 30 倍も驚くほど速くなることも説明しています。

編集：

for (int n = 1; n < INT_MAX; ++n)
{
    m = n * 10.1;
    sum += log(m);
}

コンパイラは、呼び出しが常に成功することを証明できないため、ループを完全に最適化することはできませんlog。引数が負の場合、副作用があります。そこで、彼女はループをゼロとの比較に置き換えます。これlogは、乗算の結果がゼロ以下またはゼロ未満の場合にのみ実行されます。つまり、実行されることはありません:-)

ループに残っているのは、乗算と、結果が負になる可能性があるかどうかのテストです。

コンパイラ オプションを追加すると、興味深い結果が得-ffast-mathられます。これにより、コンパイラは厳密な IEEE 準拠から解放されます。

ln=0:000000944
lb=0:000000475
lg=0:000000357
于 2012-05-30T12:35:46.737 に答える
4

私はいくつかのことに気づきました。（GCC 4.5.3）をコンパイルすると、アセンブラリスト-O3 -Sをg++ logflt.S -lrt使用して動作を再現できます。私のタイミングは次のとおりです。

ln=6:984160044
lb=6:950842852
lg=3:64288522

次に、で出力を調べましたobjdump -SC a.out。.S私は（まだ）理解していない構造があるので、ファイルを調べるよりもこれを好みます。コードはあまり読みやすいものではありませんが、次のことがわかります。

呼び出す前、logまたはlog2引数を使用して変換する前

400900:       f2 0f 2a c3             cvtsi2sd %ebx,%xmm0
400904:       66 0f 57 c9             xorpd  %xmm1,%xmm1
400908:       f2 0f 59 05 60 04 00    mulsd  0x460(%rip),%xmm0
40090f:       00 
400910:       66 0f 2e c8             ucomisd %xmm0,%xmm1

0x460(%rip)は、16進値を指している相対アドレスです0000 00000000 33333333 33332440。これは16バイトのSSEdoubleペアであり、そこから1つのdoubleのみが重要です（コードはスカラーSSEを使用しています）。このダブルは10.1です。mulsdしたがって、C++行で乗算を実行しますm = n * 10.1;。

log10異なります：

400a40:       f2 0f 2a c3             cvtsi2sd %ebx,%xmm0
400a44:       66 0f 57 c9             xorpd  %xmm1,%xmm1
400a48:       66 0f 2e c8             ucomisd %xmm0,%xmm1

log10掛け算を忘れた方もいらっしゃると思います！だからあなたはlog10同じ値で何度も何度も呼び出しています...CPUがそれを最適化するのに十分賢いのであれば私は驚かないでしょう。

編集：あなたの他のリスト（-O0 -S）では乗算が正しく実行されているので、これが問題であると確信しています-あなたのコードを投稿して、他の人に私が間違っていることを証明させてください！

EDIT2：GCCがこの乗算を取り除くことができる1つの方法は、次のIDを使用することです。

log(n * 10.1) = log(n) + log(10.1)

しかし、その場合log(10.1)は一度計算する必要があり、これはコードではありません。また、GCCがそれを行うのではlog10なく、logとのために行うのではないかと疑っていlog2ます。

于 2012-05-30T08:20:08.600 に答える
3

あなたは問題に間違ってアプローチしており、結論に飛びついています。

プロファイリングにはクロックを使用するだけでは不十分です。クロック (gprof または AQTime7) の代わりに適切なプロファイラーを使用します。プロファイラーは、行ごとのタイミングを提供できる必要があります。問題は、ボトルネックがログ関数内にあると想定していることです。ただし、int から float への変換はそれほど高速ではなく、ボトルネックになる可能性もあります。もう 1 つのことは、gcc には読み取り可能なソース コードが付属していることです。

ここで、ボトルネックが実際にログ関数内にあると仮定します。

ご存じのとおり、double の精度には制限があります。10 進数で 15..17 桁しかありません。これは、対数の底が大きいほど、精度の限界に達したときに状況に早く到達することを意味します。

つまり== 、しかし==と10^(log10(2^32) + 10^-15) - 2^32== 、また、対数の底が大きい場合、対数関数が適切な結果を「検索」しようとすると、丸めのために予測結果を変更できなくなる状況にすぐに遭遇することを意味しますオフエラー。ただし、これはまだ推測にすぎません。9.8895 * 10^-62^(log2(2^32) + 10^-15) - 2^322.977 * 10^-6100^(log100(2^32) + 10^-15) - 2^320.00001977log2(INT_MAX) > log10(INT_MAX)

対数を計算する方法は他にもあります。たとえば、log10(x) == ln(x)/ln(10)対数関数がこのように計算していた場合、ほぼ同様のタイミングが得られます。

私のお勧めは、(時間を無駄にするのをやめて) クロック関数以外のものでプログラムをプロファイリングすることです (車輪の再発明は悪い考えであり、既存のプロファイリング ツールを使用しないことは車輪の再発明です.ログ関数内からのライン タイミング)、ログ関数の gcc ソース コードの読み取り (結局のところ、利用可能です) およびアセンブリ出力。アセンブリ出力を理解していない場合は、読み方を学ぶ良い機会になります。

より高速な対数関数を使用することが非常に重要であり、アルゴリズムの最適化が実際に不可能な場合 (たとえば、対数が実際にボトルネックである場合は、結果をキャッシュすることができます)、より高速なアルゴリズムの実装を見つけようとすることができますが、私があなただった場合この場合、たとえばタスクを並列化するなどして、問題にハードウェアを投入するだけです。

于 2012-05-30T07:37:23.140 に答える