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

「水曜日」シーズン1の中心には大きなミステリーがあります

「水曜日」シーズン1の中心には大きなミステリーがあります

Netflixの「水曜日」は、典型的な10代のドラマ以上のものであり、実際、シーズン1にはその中心に大きなミステリーがあります.

ボディーランゲージの専門家は、州訪問中にカミラ・パーカー・ボウルズが輝くことを可能にした微妙なケイト・ミドルトンの動きを指摘しています

ボディーランゲージの専門家は、州訪問中にカミラ・パーカー・ボウルズが輝くことを可能にした微妙なケイト・ミドルトンの動きを指摘しています

ケイト・ミドルトンは、州の夕食会と州の訪問中にカミラ・パーカー・ボウルズからスポットライトを奪いたくなかった、と専門家は言う.

一部のファンがハリー・スタイルズとオリビア・ワイルドの「非常に友好的な」休憩が永続的であることを望んでいる理由

一部のファンがハリー・スタイルズとオリビア・ワイルドの「非常に友好的な」休憩が永続的であることを望んでいる理由

一部のファンが、オリビア・ワイルドが彼女とハリー・スタイルズとの間の「難しい」が「非常に友好的」な分割を恒久的にすることを望んでいる理由を見つけてください.

エリザベス女王の死後、ケイト・ミドルトンはまだ「非常に困難な時期」を過ごしている、と王室の専門家が明らかにする 

エリザベス女王の死後、ケイト・ミドルトンはまだ「非常に困難な時期」を過ごしている、と王室の専門家が明らかにする&nbsp;

エリザベス女王の死後、ケイト・ミドルトンが舞台裏で「非常に困難な時期」を過ごしていたと伝えられている理由を調べてください.

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

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

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

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

HMSプリンスオブウェールズの橋はスターウォーズからまっすぐです

HMSプリンスオブウェールズの橋はスターウォーズからまっすぐです

BAE Systems Maritimeは昨日、英国海軍の2番目のクイーンエリザベスクラスの空母であるHMSプリンスオブウェールズのブリッジモジュールを展開しました。公海を航海するよりも、アウターリムの惑星を周回してタイファイターを発射する必要があるようです。70,000の排水量のトン運搬船は、2020年に就役し、姉のエリザベス女王と同様に、約40機の航空機を運ぶ予定です。

ルイビルはサヨナラゲームでウェイクフォレストを倒すために家を盗んだ

ルイビルはサヨナラゲームでウェイクフォレストを倒すために家を盗んだ

ルイビルは、通常の大学野球の強みであるピッチング、ディフェンス、スマートベースランニングを通じて、全国ランキングのトップ5と19-2の会議記録への道を歩みました。昨夜、彼らは野球の最もエキサイティングなプレーの1つである盗塁を使用して、ウェイクフォレストのスイープを完了しました。

おいしいツイストのためにコーンブレッドであなたの次のサンドイッチを作りましょう

おいしいツイストのためにコーンブレッドであなたの次のサンドイッチを作りましょう

粗いパン粉とふわふわの食感のコーンブレッドは、唐辛子を吸い上げるのに理想的な乗り物です。しかし、それだけではありません。

別の驚くべきマーベルヒーローがキャプテンアメリカに参加します:シビルウォー!

別の驚くべきマーベルヒーローがキャプテンアメリカに参加します:シビルウォー!

ニール・ブロムカンプが、チャッピーが第10地区をどのように遅らせたのかについて話します。フォースの覚醒の噂は、次の予告編に何を期待するかについてのいじめを提供します。

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、子供向けのパズルの本の序文を書き、ジョージ王子、シャーロット王女、ルイ王子と一緒にテキストを読むと述べた.

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

Yak's Produce は、数十個のつぶれたメロンを野生動物のリハビリ専門家であるレスリー グリーンと彼女のルイジアナ州の救助施設で暮らす 42 匹の動物に寄付しました。

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

8 枚目のスタジオ アルバムのリリースに向けて準備を進めているデミ ロヴァートは、「スーパー グレート ガイ」と付き合っている、と情報筋は PEOPLE に確認しています。

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

イーサン プラスの誕生日のお祝いは、TLC のウェルカム トゥ プラスビルのシーズン 4 のフィナーレで、戦争中の母親のキム プラスと妻のオリビア プラスを結びつけました。

仕事の生産性を高める 8 つのシンプルなホーム オフィスのセットアップのアイデア

仕事の生産性を高める 8 つのシンプルなホーム オフィスのセットアップのアイデア

ホームオフィスのセットアップ術を極めよう!AppExert の開発者は、家族全員が一緒にいる場合でも、在宅勤務の技術を習得しています。祖父や曽祖父が共同家族で暮らしていた頃の記憶がよみがえりました。

2022 年、私たちのデジタル ライフはどこで終わり、「リアル ライフ」はどこから始まるのでしょうか?

20 年前のタイムトラベラーでさえ、日常生活におけるデジタルおよびインターネットベースのサービスの重要性に驚くことでしょう。MySpace、eBay、Napster などのプラットフォームは、高速化に焦点を合わせた世界がどのようなものになるかを示してくれました。

ニューロマーケティングの秘密科学

ニューロマーケティングの秘密科学

マーケティング担当者が人間の欲望を操作するために使用する、最先端の (気味が悪いと言う人もいます) メソッドを探ります。カートをいっぱいにして 3 桁の領収書を持って店を出る前に、ほんの数点の商品を買いに行ったことはありませんか? あなたは一人じゃない。

地理情報システムの日: GIS 開発者として学ぶべき最高の技術スタック

地理情報システムの日: GIS 開発者として学ぶべき最高の技術スタック

私たちが住んでいる世界を確実に理解するには、データが必要です。ただし、空間参照がない場合、このデータは地理的コンテキストがないと役に立たなくなる可能性があります。

Language