19

C および C++ コンパイラは通常、関数との比較を最適化しますか?

たとえば、このページsizeでは、C++ の std::lists の関数が、いくつかの標準ライブラリの実装で線形複雑度 O(N) を持つことができることを示唆しています (これは、リンクされたリストでは意味があります)。

しかし、その場合、myListが巨大なリストである場合、このようなものはどうなるでしょうか?

    if (myList.size() < 5) return 1;
    else return 2;

size() 関数は、N 個のリスト メンバーをすべて見つけてカウントしますか? それとも、5 つのメンバーを見つけた後に短絡するように最適化しますか?

4

4 に答える 4

15

がインライン化されている場合、理論的には可能性が存在size()しますが、最適化を実行するには、コンパイラが

  1. 具体的に「より小さい」条件をテストしていることを検出します
  2. ループ (この議論のためにループが存在すると仮定します) の結果、変数が単調に増加することを証明してください。
  3. ループ本体に目に見える副作用がないことを証明する

これは、IMHO に頼るべきものであり、他のコンテキストでも「明らかに有用」ではない機能が含まれています。コンパイラ ベンダーのリソースは限られているため、これらの前提条件を実装し、コンパイラにすべての部分をまとめてこのケースを最適化させるには、正当な理由が必要であることに注意してください。

これが誰かにとってのパフォーマンスの問題であったとしても、問題はコードで簡単に解決できるので、そのような正当化があるとは思いません。いいえ、通常、このようなケースが最適化されるとは思わないでください。

于 2012-05-11T11:24:01.883 に答える
11

実際、C++11 ではstd::list最適化されsize()、一定時間で返されます。

C++03 の場合、size()毎回要素をカウントする必要があるため、実際には線形時間で動作します。

size() 関数は、N 個のリスト メンバーをすべて見つけてカウントしますか? それとも、5 つのメンバーを見つけた後に短絡するように最適化しますか?

この種の最適化が実際に起こっているのを見たことはありません。それは確かに合法ですが、実際にこのようなものを実装するコンパイラがあるとは思えません。

于 2012-05-11T11:21:00.333 に答える
2

いいえコンパイラが、結果の使用方法に応じて関数の動作を変えることができるかどうかを尋ねています。これは、呼び出し元と関数が同時にコンパイルされるインライン関数に対してのみ実行される可能性があります。それを超えるものについては、かなりのストレッチのようです。

于 2012-05-11T17:31:03.470 に答える
2

myList.size() 関数自体は、使用目的のためにコンパイルする方法がないため、全体のサイズを決定します。あなたが提案している最適化を得るためには、一般的なのではなく、専用の述語関数が必要size()ですbool sizeLessThan(int);。

于 2012-05-11T11:22:15.470 に答える