GCCがa * a * a * a * a * aを(a * a * a)*(a * a * a)に最適化しないのはなぜですか?

2161
xis 2011-06-22 08:49.

私は科学的応用でいくつかの数値最適化を行っています。私が気づいたことの1つは、GCCが呼び出しpow(a,2)をコンパイルして最適化することですa*aが、呼び出しpow(a,6)は最適化されておらず、実際にはライブラリ関数を呼び出すpowため、パフォーマンスが大幅に低下します。(対照的に、実行可能ファイルであるIntel C ++コンパイラは、iccのライブラリ呼び出しを排除しますpow(a,6)。)

私が興味を持っているのは、GCC4.5.1とオプション " "pow(a,6)a*a*a*a*a*a使用するように置き換えた場合-O3 -lm -funroll-loops -msse4、5つのmulsd命令を使用することです。

movapd  %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13

私が書くと(a*a*a)*(a*a*a)

movapd  %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm13, %xmm13

乗算命令の数を3に減らしiccます。同様の動作をします。

コンパイラがこの最適化のトリックを認識しないのはなぜですか?

12 answers

2779
Lambdageek 2011-06-22 08:56.

浮動小数点演算は結合法則ではないためです。浮動小数点乗算でオペランドをグループ化する方法は、回答の数値精度に影響を与えます。

その結果、ほとんどのコンパイラは、答えが同じままであることが確実でない限り、または数値の精度を気にしないと言わない限り、浮動小数点計算の並べ替えについて非常に保守的です。たとえば、次のオプションGCCは浮動小数点演算を再結合することを可能にするGCCの、あるいは速度に対する精度の一層積極的なトレードオフを可能にするオプション。-fassociative-math-ffast-math

666
Stephen Canon 2011-06-23 05:32.

Lambdageekは、浮動小数点数には結合法則が適用されないため、a*a*a*a*a*atoの「最適化」によって(a*a*a)*(a*a*a)値が変わる可能性があることを正しく指摘しています。これが、C99で許可されていない理由です(ユーザーがコンパイラフラグまたはプラグマを介して特に許可していない限り)。一般に、プログラマーが理由で自分がしたことを書いたと想定されており、コンパイラーはそれを尊重する必要があります。必要に応じて(a*a*a)*(a*a*a)、それを書いてください。

しかし、それは書くのが面倒かもしれません。コンパイラーは、使用するときに[あなたが考えていること]を正しく実行できないのはなぜpow(a,6)ですか?それは間違ったことだからです。優れた数学ライブラリを備えたプラットフォームでpow(a,6)は、a*a*a*a*a*aまたはのいずれよりもはるかに正確です(a*a*a)*(a*a*a)。いくつかのデータを提供するために、Mac Proで小さな実験を実行し、[1,2)の間のすべての単精度浮動小数点数のa ^ 6を評価する際の最悪のエラーを測定しました。

worst relative error using    powf(a, 6.f): 5.96e-08
worst relative error using (a*a*a)*(a*a*a): 2.94e-07
worst relative error using     a*a*a*a*a*a: 2.58e-07

pow乗算ツリーの代わりに使用すると、エラー限界が4分の1に減少します。コンパイラーは、ユーザーによってライセンスされていない限り、エラーを増やす「最適化」を行うべきではありません(そして一般的には行いません-ffast-math)。

GCCは__builtin_powi(x,n)、の代わりにpow( )、インライン乗算ツリーを生成する必要があることに注意してください。精度とパフォーマンスのトレードオフを行いたいが、高速計算を有効にしたくない場合に使用します。

175
sanjoyd 2011-06-23 12:39.

別の同様のケース:ほとんどのコンパイラは最適化a + b + c + dせず(a + b) + (c + d)(2番目の式をより適切にパイプライン化できるため、これは最適化です)、指定されたとおりに(つまり、として(((a + b) + c) + d))評価します。これもコーナーケースによるものです。

float a = 1e35, b = 1e-5, c = -1e35, d = 1e-5;
printf("%e %e\n", a + b + c + d, (a + b) + (c + d));

この出力 1.000000e-05 0.000000e+00

81
Szabolcs 2011-06-24 01:44.

Fortran(科学計算用に設計された)には組み込みの累乗演算子があり、私が知る限り、Fortranコンパイラーは通常、あなたが説明するのと同様の方法で整数乗への累乗を最適化します。残念ながら、C / C ++にはパワー演算子はなく、ライブラリ関数のみがありますpow()。これは、スマートコンパイラがpow特別に処理し、特別な場合に高速に計算することを妨げるものではありませんが、あまり一般的ではないようです...

数年前、私は整数の累乗を最適な方法で計算するのをより便利にすることを試みていました、そして次のことを思いつきました。それはCではなくC ++であり、それでもコンパイラが物事を最適化/インライン化する方法についていくらか賢いことに依存しています。とにかく、あなたがそれが実際に役立つと思うかもしれないことを願っています:

template<unsigned N> struct power_impl;

template<unsigned N> struct power_impl {
    template<typename T>
    static T calc(const T &x) {
        if (N%2 == 0)
            return power_impl<N/2>::calc(x*x);
        else if (N%3 == 0)
            return power_impl<N/3>::calc(x*x*x);
        return power_impl<N-1>::calc(x)*x;
    }
};

template<> struct power_impl<0> {
    template<typename T>
    static T calc(const T &) { return 1; }
};

template<unsigned N, typename T>
inline T power(const T &x) {
    return power_impl<N>::calc(x);
}

好奇心旺盛な人のための明確化:これはパワーを計算するための最適な方法を見つけられませんが、最適な解を見つけることはNP完全問題であり、これはとにかく小さなパワーに対してのみ行う価値があるので(を使用powするのではなく)、大騒ぎする理由はありません詳細と。

次に、それをとして使用しますpower<6>(a)

これにより、累乗を簡単に入力でき(aparensで6を綴る必要はありません)、補正された加算-ffast-mathなどの精度に依存するものがない場合でも、この種の最適化を行うことができます(演算の順序が重要な例) 。

これがC ++であることを忘れて、Cプログラムで使用することもできます(C ++コンパイラでコンパイルする場合)。

これがお役に立てば幸いです。

編集:

これは私が私のコンパイラから得たものです:

の場合a*a*a*a*a*a

    movapd  %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0

の場合(a*a*a)*(a*a*a)

    movapd  %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm0, %xmm0

の場合power<6>(a)

    mulsd   %xmm0, %xmm0
    movapd  %xmm0, %xmm1
    mulsd   %xmm0, %xmm1
    mulsd   %xmm0, %xmm1
65
picomancer 2014-03-29 20:51.

GCCは、実際にはaが整数の場合に最適化a*a*a*a*a*a(a*a*a)*(a*a*a)ます。私はこのコマンドで試しました:

$ echo 'int f(int x) { return x*x*x*x*x*x; }' | gcc -o - -O2 -S -masm=intel -x c -

gccフラグはたくさんありますが、派手なものはありません。それらは次のことを意味します:stdinから読み取ります。O2最適化レベルを使用します。バイナリの代わりにアセンブリ言語リストを出力します。リストはIntelアセンブリ言語構文を使用する必要があります。入力はC言語です(通常、言語は入力ファイル拡張子から推測されますが、stdinから読み取る場合はファイル拡張子はありません)。stdoutに書き込みます。

これが出力の重要な部分です。アセンブリ言語で何が起こっているかを示すコメントをいくつか付けて注釈を付けました。

; x is in edi to begin with.  eax will be used as a temporary register.
mov  eax, edi  ; temp = x
imul eax, edi  ; temp = x * temp
imul eax, edi  ; temp = x * temp
imul eax, eax  ; temp = temp * temp

Ubuntuの派生物であるLinuxMint 16PetraでシステムGCCを使用しています。gccバージョンは次のとおりです。

$ gcc --version
gcc (Ubuntu/Linaro 4.8.1-10ubuntu9) 4.8.1

他の投稿者が指摘しているように、浮動小数点演算は結合法則ではないため、このオプションは浮動小数点では使用できません。

52
Noname 2011-06-24 00:07.

32ビット浮動小数点数(1.024など)は1.024ではないためです。コンピューターでは、1.024は(1.024-e)から(1.024 + e)までの間隔です。ここで、「e」はエラーを表します。一部の人々はこれに気づかず、また、a * aの*は、任意精度の数値にエラーが付加されることなく、それらの数値の乗算を表すと信じています。一部の人がこれに気付かない理由は、おそらく小学校で行った数学の計算です。エラーを付けずに理想的な数だけを操作し、乗算を実行するときに「e」を単に無視しても問題ないと信じています。「floata = 1.2」、「a * a * a」、および同様のCコードに暗黙的に含まれる「e」は表示されません。

プログラマーの大多数が、C式a * a * a * a * a * aが実際には理想的な数値で機能していないという考えを認識している(そして実行できる)場合、GCCコンパイラーは自由に「a * a」を最適化できます。 * a * a * a * a "を" t =(a * a); t * t * t "と言います。これは、必要な乗算の数が少なくなります。しかし残念ながら、GCCコンパイラーは、コードを書いているプログラマーが「a」がエラーの有無にかかわらず数値であると考えているかどうかを知りません。そのため、GCCはソースコードがどのように見えるかだけを実行します。これは、GCCが「肉眼」で見るものだからです。

...自分がどのようなプログラマーであるがわかったら、「-ffast-math」スイッチを使用して、「ねえ、GCC、私が何をしているのか知っている!」とGCCに伝えることができます。これにより、GCCはa * a * a * a * a * aを別のテキストに変換できます-a * a * a * a * a * aとは異なって見えますが、エラー間隔内で数値を計算しますa * a * a * a * a * a。これは問題ありません。理想的な数値ではなく、間隔を使用して作業していることがすでにわかっているからです。

37
vinc17 2014-06-28 11:03.

浮動式の縮小について言及しているポスターはまだありません(ISO C標準、6.5p8および7.12.2)。場合はFP_CONTRACT、プラグマに設定されON、コンパイラは、次のような表現を考えるために許可されているa*a*a*a*a*a単一の丸めと正確に評価したかのように、単一の操作など。たとえば、コンパイラはそれをより高速でより正確な内部べき関数に置き換えることができます。動作はプログラマーによってソースコードで直接制御されるため、これは特に興味深いものですが、エンドユーザーが提供するコンパイラオプションが誤って使用される場合があります。

FP_CONTRACTプラグマのデフォルト状態は実装定義であるため、コンパイラーはデフォルトでそのような最適化を行うことができます。したがって、IEEE 754ルールに厳密に従う必要があるポータブルコードは、明示的にに設定する必要がありOFFます。

コンパイラーがこのプラグマをサポートしていない場合、開発者がをに設定することを選択した場合に備えて、そのような最適化を回避することによって保守的にする必要がありますOFF

GCCはこのプラグマをサポートしていませんが、デフォルトのオプションでは、ON;であると想定しています。したがって、ハードウェアFMAを持つターゲットの場合a*b+c、fma(a、b、c)への変換を防ぎたい場合は、-ffp-contract=off(プラグマを明示的に設定するOFF)または-std=c99(GCCにいくつかに準拠するように指示する)などのオプションを提供する必要があります。したがって、C標準バージョン(ここではC99)は、上記の段落に従います。過去には、後者のオプションは変換を妨げていませんでした。つまり、GCCはこの点で準拠していませんでした。https://gcc.gnu.org/bugzilla/show_bug.cgi?id=37845

29
Bjorn 2011-06-24 02:44.

Lambdageekが指摘したように、フロート乗算は結合法則ではなく、精度が低くなる可能性がありますが、精度が高くなると、決定論的なアプリケーションが必要になるため、最適化に反対することができます。たとえば、ゲームシミュレーションクライアント/サーバーでは、すべてのクライアントが同じ世界をシミュレートする必要があり、浮動小数点計算を決定論的にする必要があります。

29
CoffeDeveloper 2015-01-04 06:40.

「pow」のようなライブラリ関数は、通常、エラーを最小限に抑えるように注意深く作成されています(一般的な場合)。これは通常、スプラインを使用して関数を近似することで実現されます(Pascalのコメントによると、最も一般的な実装はRemezアルゴリズムを使用しているようです)。

基本的に次の操作:

pow(x,y);

単一の乗算または除算の誤差とほぼ同じ大きさの固有の誤差があります

次の操作中:

float a=someValue;
float b=a*a*a*a*a*a;

単一の乗算または除算のエラーの5倍を超える固有のエラーがあります(5つの乗算を組み合わせているため)。

コンパイラーは、実行している最適化の種類に本当に注意する必要があります。

  1. 最適化pow(a,6)するa*a*a*a*a*aとパフォーマンス向上する可能性がありますが、浮動小数点数の精度が大幅に低下します。
  2. 「a」はエラーなしで乗算できる特別な値(2の累乗または小さな整数)であるため、最適化a*a*a*a*a*aするpow(a,6)と実際に精度が低下する可能性がある場合
  3. 最適化pow(a,6)する(a*a*a)*(a*a*a)(a*a)*(a*a)*(a*a)、それでもpow機能と比較して精度が低下する可能性がある場合。

一般に、任意の浮動小数点値の場合、「pow」は最終的に記述できるどの関数よりも精度が高いことを知っていますが、特殊なケースでは、複数の乗算の方が精度とパフォーマンスが優れている場合があります。最終的にコードにコメントを付けて、他の誰もそのコードを「最適化」しないようにします。

最適化するのに意味がある唯一のこと(個人的な意見、および特定の最適化またはコンパイラフラグがないGCCでの選択)は、「pow(a、2)」を「a * a」に置き換えることです。これは、コンパイラベンダーが行うべき唯一の正気なことです。

28
Mark Ransom 2011-06-22 08:52.

このケースが最適化されるとはまったく思っていませんでした。式に、操作全体を削除するために再グループ化できる部分式が含まれていることはめったにありません。コンパイラの作成者は、めったに遭遇しないエッジケースをカバーするのではなく、目立った改善をもたらす可能性が高い領域に時間を費やすことを期待します。

他の回答から、この式が適切なコンパイラスイッチで実際に最適化できることを知って驚いた。最適化が簡単であるか、はるかに一般的な最適化のエッジケースであるか、コンパイラの作成者が非常に徹底していたかのいずれかです。

ここで行ったように、コンパイラにヒントを提供することに何の問題もありません。ステートメントと式を再配置して、それらがどのような違いをもたらすかを確認することは、マイクロ最適化プロセスの通常の予想される部分です。

コンパイラーは、(適切なスイッチなしで)一貫性のない結果を提供するために2つの式を検討することで正当化される場合がありますが、その制限に拘束される必要はありません。違いは非常に小さいので、違いが重要な場合は、そもそも標準の浮動小数点演算を使用しないでください。

21
Rastaban 2013-10-02 09:33.

この質問に対する良い答えはすでにいくつかありますが、完全を期すために、C標準の該当するセクションは5.1.2.2.3 / 15(これは、のセクション1.9 / 9と同じです)であることを指摘したいと思います。 C ++ 11標準)。このセクションでは、演算子は、実際に結合的または可換である場合にのみ再グループ化できると述べています。

12
Charles 2016-06-17 08:44.

gccは、浮動小数点数の場合でも、実際にこの最適化を実行できます。例えば、

double foo(double a) {
  return a*a*a*a*a*a;
}

になります

foo(double):
    mulsd   %xmm0, %xmm0
    movapd  %xmm0, %xmm1
    mulsd   %xmm0, %xmm1
    mulsd   %xmm1, %xmm0
    ret

-O -funsafe-math-optimizations。ただし、この並べ替えはIEEE-754に違反するため、フラグが必要です。

Peter Cordesがコメントで指摘したように、符号付き整数-funsafe-math-optimizationsは、オーバーフローがない場合に正確に保持され、オーバーフローがある場合は未定義の動作が発生するため、この最適化を実行できます。だからあなたは得る

foo(long):
    movq    %rdi, %rax
    imulq   %rdi, %rax
    imulq   %rdi, %rax
    imulq   %rax, %rax
    ret

だけで-O。符号なし整数の場合、2のmod乗で動作するため、オーバーフローが発生した場合でも自由に並べ替えることができるため、さらに簡単です。

Related questions

MORE COOL STUFF

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは、夫に会ったとき、典型的な交際のアドバイスに逆らいました。

マイケルシーンが非営利の俳優である理由

マイケルシーンが非営利の俳優である理由

マイケルシーンは非営利の俳優ですが、それは正確にはどういう意味ですか?

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

特徴的なスターのコリン・エッグレスフィールドは、RomaDrama Liveでのスリル満点のファンとの出会いについて料理しました!加えて、大会での彼のINSPIREプログラム。

「たどりつけば」をオンラインでストリーミングできない理由

「たどりつけば」をオンラインでストリーミングできない理由

ノーザンエクスポージャーが90年代の最も人気のある番組の1つになった理由を確認するには、Blu-rayまたはDVDプレーヤーをほこりで払う必要があります。

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖は、世界で2番目に大きいボイリング湖です。そこにたどり着くまでのトレッキングは大変で長いですが、努力する価値は十分にあります。

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

サロンからのヘアトリミングや個人的な寄付は、油流出を吸収して環境を保護するのに役立つマットとして再利用できます。

ホワイトハウスの最も記憶に残る結婚式を見てください

ホワイトハウスの最も記憶に残る結婚式を見てください

過去200年以上の間にホワイトハウスで結婚したのはほんの数人です。彼らは誰でしたか、そしてそこで結婚式を獲得するために何が必要ですか?

ジェイ・ブルースはどうやら子供を妊娠することによってメッツから離れて取引されていることを祝った

ジェイ・ブルースはどうやら子供を妊娠することによってメッツから離れて取引されていることを祝った

あなたが一時的に会っていなかったとき。シーズン11-1を開始したチームであるニューヨークメッツは、日曜日の午後にフィラデルフィアで行われた最後の11試合の9試合目を失いました。

スティーブンキングのアウトサイダーはトランプ時代のそれです

スティーブンキングのアウトサイダーはトランプ時代のそれです

スティーブン・キングのアウトサイダーは、多くの点で先祖返りの小説であり、80年代の全盛期から引き裂かれたように見える生き物の特徴であり、おそらくセル以来の彼の最もパルプのような本ですが、今日の恐怖の中で間違いなく設立された作品です。表面上は、形を変えるペニーワイズのような子供たちの殺人者を中心としており、その最も暗い脅威は、封じ込められず、神経質に平凡なものよりも幻想的で打ち負かされません。

スティーブンユニバースは、強烈な内部エピソードのペアで、それ自体のバックストーリーをさりげなく粉砕します

スティーブンユニバースは、強烈な内部エピソードのペアで、それ自体のバックストーリーをさりげなく粉砕します

スティーブンユニバースビーチシティのエピソードが実行されるたびに、いくつかのクライマックスイベントが発生し、スティーブンユニバースのより広い神話に対する理解の一部が失われます。これはあなたが期待していたことですか?今日のエピソードは両方とも、容赦なくゆっくりと、シーズンの終盤の主要な部分を設定する決定的な結論に向かって進みます。そして、ロナウドは、静かな納屋が倒れているのを発見した夜中にスティーブンを捕まえるためにやって来ます。月に。

ディズニーワールドの旅行のヒントを教えてください

ディズニーワールドの旅行のヒントを教えてください

「光が触れるものはすべて私たちの王国です。」今週のHackYour Cityでは、1つのテーマパークを取り上げます。

Zendaya Wishes Boyfriend Tom Holland Happy Birthday with Cuddly Photo: He 'Makes Me the Happiest'

Zendaya Wishes Boyfriend Tom Holland Happy Birthday with Cuddly Photo: He 'Makes Me the Happiest'

Zendaya shared a sweet photo in honor of boyfriend Tom Holland's 26th birthday Wednesday

小さな女性:脳卒中を患った後に病院から解放されたアトランタのジューシーな赤ちゃん:「まだ癒し」

小さな女性:脳卒中を患った後に病院から解放されたアトランタのジューシーな赤ちゃん:「まだ癒し」

シーレン「Ms.JuicyBaby」ピアソンは、先月脳卒中で入院した後、「もう一度たくさんのことをする方法を学ばなければならない」ため、言語療法を受けていることを明らかにしました。

エマストーンは彼女のクリフサイドマリブビーチハウスを420万ドルでリストアップしています—中を見てください!

エマストーンは彼女のクリフサイドマリブビーチハウスを420万ドルでリストアップしています—中を見てください!

オスカー受賞者の世紀半ばの家には、3つのベッドルーム、2つのバス、オーシャンフロントの景色があります。

ジーニー・メイ・ジェンキンスは、母乳育児の経験の中で、彼女は「本当に、本当に落ち込んでいる」と言います

ジーニー・メイ・ジェンキンスは、母乳育児の経験の中で、彼女は「本当に、本当に落ち込んでいる」と言います

ジーニー・メイ・ジェンキンスは、生後4か月の娘、モナコに母乳育児をしていると語った。

Come diventare Web Developer?

Come diventare Web Developer?

Vorresti diventare web developer e non sai da dove cominciare?! Qui troverai tutte le risposte necessarie, anche io non sapevo che strada intraprendere ma voglio aiutarti a non commettere i miei stessi errori. Cosa imparare? Le competenza essenziali per qualsiasi web developer sono almeno tre.

投資ノート:Bioscout AU$300万シード

投資ノート:Bioscout AU$300万シード

Bioscoutは、農家を運転席に置くという使命を負っています。Artesian(GrainInnovate)やUniseedと並んで、最新のシードラウンドでチームを支援できることをうれしく思います。問題真菌症による重大な作物の損失は、農民にとって試練であることが証明されています。

リトルマーケットリサーチ1| 2022年のクイックグリンプス遠隔医療市場

リトルマーケットリサーチ1| 2022年のクイックグリンプス遠隔医療市場

遠隔医療は、パンデミック後の時代では新しいものではなく、時代遅れの分野でもありません。しかし、業界を詳しく見ると、需要と供給の強力な持続可能性と、米国で絶え間ない革命となる強力な潜在的成長曲線を示しています。

スタートアップ資金調達環境:タイのスタートアップエコシステムの次は何ですか?

スタートアップ資金調達環境:タイのスタートアップエコシステムの次は何ですか?

2021年は、世界的なベンチャーキャピタル(VC)の資金調達にとって記録的な年でした。DealStreetAsiaによると、東南アジアも例外ではなく、この地域では年間で記録的な25の新しいユニコーンが採掘されました。

Language