7

コードを書いていると、特定の関数呼び出しの値を複数回使用していることに気付くことがよくあります。明らかな最適化は、これらの繰り返し使用される値を変数に取り込むことであることに気付きました。これ（疑似コード）：

function add1(foo){ foo + 1; }
...
do_something(foo(1));
do_something_else(foo(1));

なる:

function add1(foo){ foo + 1; }
...
bar = foo(1);
do_something(bar);
do_something_else(bar);

ただし、これを明示的に行うと、私の経験ではコードが読みにくくなります。選択した言語が関数に副作用を与えることを許可している場合、コンパイラはこの種の最適化を実行できないと思いました。

最近私はこれを調べました、そして私が正しく理解していれば、この最適化は関数が純粋でなければならない言語に対して行う/行うことができます. それは私を驚かせませんが、おそらくこれは不純な関数に対しても行うことができます。いくつかの簡単な Google 検索で、次のスニペットを見つけました: GCC 4.7 Fortran の改善

フロントエンドの最適化を実行する場合、 -faggressive-function-elimination オプションを使用すると、純粋でない関数であっても重複する関数呼び出しを削除できます。

コンパイラの最適化 (ウィキペディア)

たとえば、一部の言語では、関数に副作用を持たせることが許可されていません。したがって、プログラムが同じ関数を同じ引数で複数回呼び出した場合、コンパイラは、関数の結果を 1 回だけ計算する必要があると即座に推測できます。関数が副作用を持つことを許可されている言語では、別の戦略が可能です。オプティマイザは、どの関数に副作用がないかを判断し、そのような最適化を副作用のない関数に制限できます。この最適化は、オプティマイザーが呼び出された関数にアクセスできる場合にのみ可能です。

私の理解では、これはオプティマイザーが関数が純粋かどうかを判断し、関数が純粋であるときにこの最適化を実行できることを意味します。これは、同じ入力が与えられたときに関数が常に同じ出力を生成し、副作用がない場合、純粋と見なされる両方の条件を満たしているためです。

これらの 2 つのスニペットから、2 つの疑問が生じます。

  1. 関数が純粋でない場合、コンパイラはどのようにしてこの最適化を安全に行うことができますか? (-faggressive-function-eliminationのように)
  2. コンパイラは、関数が純粋かどうかをどのように判断できますか? (ウィキペディアの記事で提案されている戦略のように)

そして最後に：

  • この種の最適化はどの言語にも適用できますか、それとも特定の条件が満たされた場合にのみ適用できますか?
  • この最適化は、非常に単純な関数でも価値のあるものですか?
  • スタックからの値の保存と取得で発生するオーバーヘッドはどれくらいですか?

これらがばかげた、または非論理的な質問である場合は、お詫び申し上げます。それらは、私が最近気になっていることのほんの一部です。:)

4

1 に答える 1

2

免責事項: 私はコンパイラー/オプティマイザーの専門家ではありません。私は生成されたコードをのぞき見する傾向があり、そのようなものについて読むのが好きです。したがって、それは自動ではありません。-faggressive-function-elimination については、クイック検索ではあまりヒットしませんでした。

オプティマイザは

  • 関数呼び出しのインライン化を試みます (リンク時のコード生成では、これはコンパイル ユニット間でも機能します)。
  • 一般的な部分式の削除と、場合によっては副作用の並べ替えを実行します。

例を少し変更して、C++ で実行します。

extern volatile int RW_A = 0;  // see note below

int foo(int a)  { return a * a; }
void bar(int x) { RW_A = x; }

int _tmain(int argc, _TCHAR* argv[])
{
   bar(foo(2));
   bar(foo(2));
}

(疑似コード) に解決

<register> = 4;
RW_A = register;
RW_A = register;

(注: volatile 変数からの読み取りと書き込みは「観察可能な副作用」であり、オプティマイザはコードで指定された順序で保持する必要があります。)

の例を変更しfooて副作用を持たせる:

extern volatile int RW_A = 0;
extern volatile int RW_B = 0;
int accu = 1;

int foo(int a)  { accu *= 2; return a * a; }
void bar(int x) { RW_A = x; }

int _tmain(int argc, _TCHAR* argv[])
{
   bar(foo(2));
   bar(foo(2));

   RW_B = accu;
   return 0;
}

次の疑似コードを生成します。

registerA = accu;
registerA += registerA;
accu = registerA;

registerA += registerA;
registerC = 4;
accu = registerA;

RW_A = registerC;
RW_A = registerC;

RW_B = registerA;

一般的な部分式の削除がまだ行われており、副作用から分離されていることがわかります。インライン化と並べ替えにより、副作用を「純粋な」部分から分離できます。

コンパイラは を読み込んで熱心に書き戻すことに注意してくださいaccu。これは必要ありません。ここでの根拠はわかりません。

結論として：

コンパイラは純度をテストする必要はありません。保存する必要がある副作用を特定し、残りを好みに合わせて変換できます。

このような最適化は、些細な関数であっても価値があります。

  • CPU とメモリは共有リソースであり、使用したものが他の誰かから奪われる可能性があります
  • バッテリー寿命
  • マイナーな最適化は、より大きな最適化へのゲートウェイになる可能性があります

通常、スタック メモリ アクセスのオーバーヘッドは ~1 サイクルです。これは、通常、スタックの最上位が既にレベル 1 キャッシュにあるためです。通常は太字にする必要があることに注意してください。読み取り/書き込みが最適化される可能性があるため、「さらに良い」場合もあれば、L1 キャッシュへの負荷が増加して他の重要なデータが L2 にフラッシュされるため、さらに悪い場合もあります。

どこが限界？

理論的には、コンパイル時間。実際には、オプティマイザーの予測可能性と正確性は追加のトレードオフです。

VC2008 を使用したすべてのテスト、「リリース」ビルドのデフォルトの最適化設定。

于 2012-09-20T08:59:48.373 に答える