問題タブ [compiler-optimization]

私はサードパーティのアウトソーシング会社から提供されたコードを確認していて、この小さな宝石に出くわしました。

私の質問は、コンパイラがこれを完全に最適化するかどうかです。Reflectorでコンパイルされたアセンブリを見ると、次のように表示されます。

iの宣言はメソッドの先頭に移動され、Exceptionタイプの追加の宣言もメソッドの先頭にあります。

したがって、このコードは実際には何も実行しないので、コンパイラーがこのコードが何も実行せず、最適化できることを確認できるほど賢いのかどうか疑問に思いました。

.

ここで私は空のベースの最適化について議論していましたが、MSaltersは次のような興味深いコメントを残しました。

sizeof(Class)==0、空であろうとなかろうと、どのクラスも持つことはできません。しかし、空の基本クラスのサブオブジェクトのサイズについて具体的に話しています。 独自の vtable も vtable ポインターも必要ありません。オフセット 0 にある vtable ポインターの一般的なレイアウトを想定します。これにより、サイズがゼロの基本クラスのサブオブジェクトがその vtable ポインターを派生クラスと共有することになります。問題ありません。いずれにせよ、それらは同一である必要があります。それが仮想関数のポイントです。

私の質問は具体的には次のとおりです。空のクラスを基本クラスとして使用すると、コンパイラが最適化される場合とそうでない場合があります。それが実際に何をするかをどのように判断しますか？

一般に、基本クラスのサブオブジェクトのサイズを知るにはどうすればよいでしょうか? ベースとして使用するかどうかに関係なく、ベース サブオブジェクトのサイズは同じですか? コンパイラは空の基本クラスのみで最適化しますか?

.

。

コンパイラがC++で記述されたコードを最適化できる/実行できるすべての可能な方法（または少なくとも人気のある方法）を知りたいですか？また、最適化がどのように正確に行われるか（それぞれの場合）を知りたいです！

これまでのところ、私は2つの最適化、つまり 空のベースの最適化（EBO）と戻り値の最適化（RVO）。他に何がありますか？「定数」最適化、「未使用変数」最適化について聞いたことがあります。彼らは何ですか？

。

次のコードを検討してください。

GCC 4.4.1 ( を使用-O2) では、 への呼び出しB::go()がインライン化されます (つまり、仮想ディスパッチは発生しません)。これは、コンパイラが実際に型変数a_refを指していることを認識していることを意味します。参照を使用して を指すことができますBが、コンパイラはこれが当てはまらないことを予測できるほどスマートであるため、関数呼び出しを完全に最適化し、関数をインライン化します。BC

すごい！それは信じられないほどの最適化です。

しかし、では、GCC が次のケースで同じことをしないのはなぜでしょうか?

何か案は？他のコンパイラはどうですか？この種の最適化は一般的ですか? （私はこの種のコンパイラの洞察に非常に慣れていないので、興味があります）

2 番目のケースが機能する場合、次のような非常に優れたテンプレートを作成できます。

これらのテンプレートは、多くの場合、仮想ディスパッチを回避するために使用できます。

それを実装することは実用的でしょうか？（そして、それがマイクロ最適化であると言い続けないでください..）

- 編集

static_ptr<>の問題は、私が公開した問題とは何の関係もないことに気付きました。ポインター型は保持されますが、インライン化されません。static_ptr_container<>::value が参照でもポインターでもないことを確認するために、GCCは必要なほど深くは行かないと思います。申し訳ありません。しかし、その質問はまだ答えられていません。

- 編集

static_ptr<>実際に動作するバージョンを作成しました。また、名前を少し変更しました。

唯一の弱点は、ユーザーがptr->value実際のオブジェクトを取得するためにアクセスする必要があることです。オーバーロードoperator ->()は GCC では機能しません。実際のオブジェクトへの参照を返すメソッドは、それがインラインの場合、最適化を中断します。お気の毒に..

とを使用したバイナリビルドが-fprofile-arcsあり-ftest-coverageます。バイナリは、プロセスを子プロセスとして生成するプロセスモニターによって実行されます。次に、プロセスを終了する場合は、プロセスモニターを通過する必要があります。プロセスにを送信しSIGKILLます。.gcdaこの場合、ファイルが生成されないことがわかりました。私に何ができる？

編集：実際には、プロセスモニターは最初にプロセスを終了させようとします。ただし、ユーザーがプロセスを停止するコマンドを発行したときでは_exitなく、ProcessMonitorライブラリ（各プロセスで使用）が呼び出されます。exitこれがすべてのトラブルの原因です。

Possible Duplicate:
Why does volatile exist?

I have never used it but I wonder why people use it? What does it exactly do? I searched the forum, I found it only C# or Java topics.

アルゴリズムをインライン化する論文の議論を知っている人はいますか? そして密接に関連しているのが、親子グラフとコールグラフの関係です。

背景:主にこれと他のいくつかの最適化の結果として、関数を積極的にインライン化するコンパイラーを作成しましたOcaml。これは、多くの状況で他のほとんどのプログラミング言語よりも高速なコードを生成します ( C.

問題 #1:アルゴリズムに再帰の問題があります。このため、私のルールは、無限再帰を防ぐために、子を親にインライン化することだけですが、これにより、兄弟関数が相互にインライン化されることはなくなります。

問題 #2:インライン操作を最適化する簡単な方法を知りません。私のアルゴリズムは、関数本体の可変表現を使用することが不可欠です。効率的な関数型インライン化アルゴリズムを作成することは、リモートでさえ可能ではないように思われるからです。呼び出しグラフがツリーの場合、ボトムアップのインライン化が最適であることは明らかです。

技術情報:インライン化は、いくつかのインライン化ステップで構成されます。問題は、ステップの順序です。

各ステップは次のように機能します。

• 型パラメーターと値パラメーターの両方を引数に置き換えることにより、関数のコピーをインライン化してベータ削減します。
• 次に、return ステートメントを新しい変数への代入に置き換え、その後に関数本体の末尾にジャンプします。
• 関数への元の呼び出しは、この本体に置き換えられます。
• しかし、まだ終わっていません。また、関数のすべての子を複製し、それらもベータ削減し、複製を呼び出し元の関数に再親化する必要があります。

複製操作により、再帰関数をインライン化することが非常に困難になります。すでに進行中のもののリストを保持し、この呼び出しを既に処理しているかどうかを確認するだけの通常のトリックは、単純な形式では機能しません。関数、および再帰ターゲットが複製された子に変更された可能性があります。ただし、その子は、親を呼び出す際に、その子を呼び出す元の親を呼び出しているため、再帰の展開は停止しません。前述のように、子への再帰呼び出しのインライン化のみを許可し、兄弟の再帰がインライン化されないようにすることで、この回帰を打破しました。

インライン化のコストは、garbage collect未使用の関数が必要になるため、さらに複雑になります。インライン化は潜在的に指数関数的であるため、これは不可欠です。関数へのすべての呼び出しがインライン化されている場合、関数がまだインライン化されていない場合は削除する必要があります。そうしないと、使用されなくなった関数にインライン化する時間が無駄になります。誰が何を呼び出しているかを実際に追跡することは非常に困難です。なぜなら、インライン化するとき、実際の関数表現ではなく、「解明されていない」表現で作業しているためです。たとえば、命令のリストが順次処理され、新しいリストが構築されます。また、一貫した命令リストが存在しない可能性もあります。

彼の ML コンパイラで、Steven Weeks は繰り返し適用される多数の小さな最適化を使用することを選択しました。これにより、最適化が記述しやすく、制御しやすくなりましたが、残念ながら、これは再帰アルゴリズムと比較して多くの最適化の機会を逃しています。

問題 #3:関数呼び出しをインライン化しても安全なのはいつですか?

この問題を一般的に説明すると、遅延関数型言語では、引数がクロージャでラップされ、アプリケーションをインライン化できます。これは Haskell の標準モデルです。ただし、なぜHaskellこんなに遅いのかについても説明しています。引数が既知の場合、クロージャーは必要ありません。その場合、パラメーターは、発生する引数で直接置き換えることができます (これは通常の順序beta-reductionです)。

ただし、引数の評価が終了しないことがわかっている場合は、代わりに熱心な評価を使用できます。パラメーターには式の値が一度割り当てられ、その後再利用されます。これら 2 つの手法のハイブリッドは、クロージャーを使用するが、結果をクロージャー オブジェクト内にキャッシュすることです。それでも、GHC は非常に効率的なコードを生成することに成功していません。特に、個別にコンパイルする場合は、明らかに非常に困難です。

Felix では、逆のアプローチを取りました。正確さを要求し、最適化がセマンティクスを保持していることを証明することによって徐々に効率を改善する代わりに、最適化がセマンティクスを定義することを義務付けます。これにより、特定のコードがどのように動作するかについての不確実性を犠牲にして、オプティマイザーの正しい動作が保証されます。この考え方は、デフォルトの最適化戦略が積極的すぎる場合に、オプティマイザーを意図したセマンティクスに強制的に準拠させる方法をプログラマーに提供することです。

たとえば、デフォルトのパラメーター受け渡しモードでは、コンパイラーは引数をクロージャーでラップするか、パラメーターを引数で置き換えるか、または引数をパラメーターに割り当てるかを選択できます。プログラマーがクロージャーを強制したい場合は、クロージャーを渡すだけです。プログラマーが熱心な評価を強制したい場合は、パラメーターをマークしますvar。

ここでの複雑さは、関数型プログラミング言語よりもはるかに大きくなります。Felix は、変数とポインターを使用する手続き型言語です。Haskell スタイルの型クラスもあります。これにより、インライン化ルーチンが非常に複雑になります。たとえば、型クラスのインスタンスは、可能な限り抽象関数を置き換えます (ポリモーフィック関数を呼び出すときの型の特殊化により、インライン化中にインスタンスを見つけることができる場合があるため、新しい関数があります。インライン化できます)。

明確にするために、さらにメモを追加する必要があります。

インライン化と、ユーザー定義の用語削減、型クラスのインスタンス化、変数削除のための線形データ フロー チェック、テール レコードの最適化などの他のいくつかの最適化が、指定された関数に対して一度に実行されます。

順序付けの問題は、さまざまな最適化を適用する順序ではなく、関数を順序付けすることです。

脳死アルゴリズムを使用して再帰を検出します。各関数によって直接使用されるすべてのリストを作成し、クロージャーを見つけて、関数が結果に含まれているかどうかを確認します。使用セットは最適化中に何度も構築されることに注意してください。これは深刻なボトルネックです。

関数が再帰的であるかどうかは、残念ながら変わる可能性があります。tail rec の最適化後、再帰関数が非再帰になる可能性があります。しかし、もっと難しいケースがあります: 型クラスの「仮想」関数をインスタンス化すると、再帰的でないように見えたものを再帰的にすることができます。

兄弟呼び出しに関しては、問題は、f が g を呼び出し、g が f を呼び出す f と g を指定すると、実際には f を g に、g を f .. に 1 回インライン化したいことです。私の無限回帰停止規則は、f が g の子である場合に相互に再帰的である場合にのみ、f の g へのインライン展開を許可することです。これにより、兄弟のインライン展開は除外されます。

基本的に、すべてのコードを「可能な限り」「平坦化」したいと考えています。

N簡単にするために、各行の行列のベクトルがあると仮定しMます。STLstd::accumulateを使用して、すべての行列の合計を計算しています。2 つの行列を (参照により) 受け取り、それらの合計を (参照により) 返すバイナリ ファンクターを渡します。完全な開示: libstdc++ 並列モードを使用しています。ファンクター内では、行を個別にループして合計を計算します。

各マトリックスは大きすぎてキャッシュに収まりませんが、行は非常にうまく収まります。そのため、ループの順序を変更して、外側のループがM行にインデックスを付け、内側のループがN行列にインデックスを付けるようにすることをお勧めします。ファンクターをインラインで定義することに加えて、このようなクロス関数境界ループの並べ替えを促進するために他にできることはありますか? もちろん、コードを再構築することもできますが、理想的には、STL アルゴリズムを使用できる単純な構造を維持したいと考えています。gcc 固有のものがあれば、それも気にしません。

私は実際に行列を扱っているわけではありません。これは単なる例ですが、同じ問題構造が適用されます。主な問題はパフォーマンスの問題です。実際のシナリオを説明するのは面倒ですが、核となる問題は次のとおりです。STL のアキュムレートは、次のオブジェクトに移動する前に 2 つのオブジェクトの追加を完了しようとするため、ネストされたループ間の順序付けを伴います。これはキャッシュ フレンドリーではありません。1 つのオブジェクトは大きすぎてキャッシュに保持できませんが、一部は保持できます。そのため、(すべてのオブジェクトに対して) 一度に 1 つの「部分」の「加算」を計算すると、実行を高速化できます。ループを手動で並べ替えると、FLOPS が大幅に改善されます。しかし、可能な限り STL レベルでコーディングできるように、コンパイラーに並べ替えを実行してもらいたいと考えています。だから私はこれを行うためのトリックを探しています。

今日のコードレビューで、私は次のコードに出くわしました（投稿用に少し変更されています）：

これは、新しいスレッドで実行されるコードの最初の数行です。別のスレッドでは、初期化が完了すると、に設定initializedされtrueます。

オプティマイザーがこれを無限ループに変える可能性があることは知っていますが、それを回避するための最良の方法は何ですか？

• volatile-有害と考えられる
• 変数を直接使用する代わりに関数を呼び出すisInitialized()-これはメモリバリアを保証しますか？関数が宣言された場合はどうなりますinlineか？

他に選択肢はありますか？

編集：

これについてはもっと早く言及する必要がありますが、これはWindows、Linux、Solarisなどで実行する必要のあるポータブルコードです。ポータブルスレッドライブラリには主にBoost.Threadを使用しています。

位置独立コードと共有オブジェクトが実際に何を意味するのか、誰でも説明してください。コンパイル後に作成されたオブジェクトコードが位置に依存しないかどうか。

ローカル/外部変数へのアクセスが位置に依存しないコードでどのように処理されるかについて誰かが説明すると役に立ちます。

また、実際の動的リンク/ロードの例/状況を探しています。