9

C-StdlibのようなコールバックとしてC-Functionpointerを受け取る典型的な関数を考えると、qsort()どのコンパイラーもインライン化を使用してコードを最適化できますか？できないと思いますが、これは正しいですか？

int cmp(void* pa, void* pb) { /*...*/ }
int func() {
  int vec[1000];
  qsort(vec, 1000, sizeof(int), &cmp);
}

さて、外部ライブラリの関数ですが、 LTOqsort()でさえここでは役に立たないと思いますよね？

しかしmy_qsort()、同じコンパイルユニットで定義した場合、コンパイラでインライン化は可能でしょうか？

int cmp(void* pa, void* pb) { /*...*/ }
void my_qsort(int* vec, int n, int sz, (void*)(void*,void*)) { /* ... */ }
int func() {
  int vec[1000];
  my_qsort(vec, 1000, sizeof(int), &cmp);
}

それは何か違いがありますか？コールバックとしてのC関数ポインターの使用は、コンパイラーがインライン化するのを妨げる要因だと思います。正しい？

（ C ++でFunctorsを使用する理由を確実に理解したいだけです）

4

3 に答える 3

7

いいえ、少なくとも従来のツールチェーンの仕組みでは不可能です。従来の操作の順序は、すべてのコンパイルが実行されてから、リンクが実行されるというものです。

比較関数をインラインで生成するには、コンパイラは最初にqsortそれ自体のコードをインラインで生成する必要があります（の各インスタンスqsortは通常、異なる比較関数を使用するため）。ただし、のようなものの場合qsort、コードの記述について考える前に、通常はコンパイルされて標準ライブラリに配置されます。コードをコンパイルすると、qsortはオブジェクトファイルとしてのみ使用できます。

そのため、このようなことを行う可能性さえあるためには、コンパイラではなくリンカーにインライン化機能を組み込む必要があります。少なくとも理論的には可能ですが、それは明らかに自明ではありません。少なくとも私の見積もりでは、ソースコードを操作する場合よりもほぼ確実に困難です。また、リンカでコンパイラのような機能をかなり複製する必要があります。また、リンカが機能するのに十分な情報をリンカに提供するために、オブジェクトファイルにかなりの量の追加情報を追加する必要があります。

編集：おそらく、コメントチェーンが言葉遣いだけで本格的な議論にならないように、もっと詳しく説明する必要があります。

伝統的に、リンカーは基本的にかなり単純な種類の獣です。これは、次の4つの主要な要素に分割できるオブジェクトファイルから始まります。

  1. オブジェクトファイルから生成中の実行可能ファイルにコピーされる（特に指示されている場合を除き、変更されない）ビットのコレクション。
  2. オブジェクトファイルに含まれるシンボルのリスト。
  3. によって使用されるシンボルのリストは、オブジェクトファイルによって提供されません。
  4. アドレスを書き込む必要がある修正プログラムのリスト。

次に、リンカは、あるファイルでエクスポートされ、別のファイルで使用されるシンボルの照合を開始します。次に、ライブラリ（または複数のライブラリ）内のオブジェクトファイルを調べて、さらに多くのシンボルを解決します。ファイルを追加するたびに、必要なシンボルのリストも追加し、それらを満たすことができる他のオブジェクトファイルを再帰的に検索します。

すべてのシンボルを提供するオブジェクトファイルが見つかると、それぞれのビット部分のコレクションを出力ファイルにコピーし、修正レコードが指示する場所に、特定のシンボルに割り当てられた相対アドレスを書き込みます（たとえば、と呼ばれるとprintf、実行可能ファイルのどこを構成するビットをコピーしたかがprintfわかり、そのアドレスを呼び出しに入力します）。かなり最近のケースでは、ライブラリからビットをコピーするのではなく、共有オブジェクト/ DLLへの参照を実行可能ファイルに埋め込み、ローダーに任せて、実行時にそのファイルを実際に検索/ロードして、実際のコードを提供することができます。シンボル。

ただし、特に、リンカは従来、コピーするビットのブロックの実際の内容を認識していません。（たとえば）まったく同じリンカーをかなり合理的に使用して、多数の異なるプロセッサーのコードを処理できます。それらがすべて同じオブジェクトと実行可能ファイル形式を使用している限り、問題ありません。

リンク時間の最適化は、それを少なくともある程度変更します。明らかに、コードを最適化するには、従来はリンク時間と見なされていた時間に発生する、ある種の追加のインテリジェンスが必要です。これを行うには（少なくとも）2つの方法があります。

  1. リンカーにかなりの追加インテリジェンスを組み込む
  2. インテリジェンスをコンパイラーに保持し、リンカーにそれを呼び出して最適化を実行させます。

それらの両方の例があります-LLVM（1つの明白な例のために）はほとんど前者を取ります。フロントエンドコンパイラはLLVMコードを発行し、LLVMはそれを最適化された実行可能ファイルに変換するために多くのインテリジェンス/作業を投入します。GIMPLEを使用するgccは、後者のルートを取ります。GIMPLEレコードは、基本的に、多数のオブジェクトファイルのビットをコンパイラにフィードバックし、コンパイラに最適化させてから、結果をリンカーにフィードバックするのに十分な情報をリンカーに提供します。実際に実行可能ファイルにコピーします。

おそらく、これら2つは基本的に同等であるという哲学的な見方を思いつくことができると思いますが、両方を実装した人なら誰でも同意するのではないかと思います。

さて、（おそらく、とにかく）これらのいずれかが手元の最適化を実装するのに十分であることは事実です。個人的には、この最適化を自分のために実装している人はいないと思います。あなたがそれに取り掛かるとき、qsortそしてbsearchそれが通常適用される/通常適用されるであろうほとんど唯一の合理的に一般的な機能です。ほとんどの実用的な目的では、それはあなたがのためだけに最適化を実装することを意味しますqsort。

一方、関連するツールにインライン関数とリンク時間の最適化を生成する機能が含まれている場合、この特定のタイプの最適化が多かれ少なかれ偶然の側面として発生する可能性が少なくとも合理的にあると思います。 2つが一緒になる効果。

少なくとも理論的には、それはそれが起こる可能性があることを意味します。ただし、考慮すべきもう1つの問題があります。手元の最適化とは完全に独立しているため、多くのコンパイラは再帰関数のインラインコードを生成しません。それを試みるためにも、コンパイラは最初に再帰関数を反復形式に変換する必要があります。これは末尾再帰の場合にはかなり一般的ですが、クイックソートは末尾再帰ではありません。ほぼ唯一の選択肢は、qsort最初から再帰的ではない実装です。それは確かに可能ですが、確かにかなり珍しいことです。

そのため、ツールチェーンがコールバックのインライン生成をサポートできる場合でも、おそらくそうではありませんqsort（これは、私が個人的にテストした唯一のケースです）。ただし、良くも悪くも、qsortこの種の機能のうち、どちらかが重要になるほど一般的なのはほぼ唯一の機能です。

于 2011-03-13T17:13:35.553 に答える
4

はい、コールバックをインライン化するコンパイラがあります。GCCは、同じコンパイルユニットで定義されている関数に対して、そしておそらくLTOを使用しているときにこれを確実に実行できます（これは検証していませんが、原則としてそのような最適化を妨げるものはありません）。

ただし、これが可能かどうかはqsort()、標準ライブラリの実装の詳細です。標準ライブラリ関数は、関数として提供される場合がありますinline。実際、関数のようなマクロによってシャドウされる可能性があります。したがって、コンパイラは自由にこの場合、比較関数へのインライン呼び出しを含む特殊なバージョンを生成します。

于 2011-03-14T10:12:11.660 に答える
1

あなたが述べるケースは、関数ポインタよりもC++でファンクタを使用する必要がある複数の理由の1つです。

コンパイラがコールバックを使用して関数をインライン化できるかどうかはかなり複雑で、さまざまな状況に依存することがよくあります。

いくつかの些細な例では、コンパイラは、呼び出される関数を決定できるため、呼び出しを確実にインライン化できます。他のプログラムでは、呼び出される関数がランタイムパラメータに依存する可能性があり、コンパイラが検出できなかったエイリアシングや、オプティマイザが使用している黒魔術が存在する可能性があります。

于 2011-03-13T16:36:20.253 に答える