c++ - 仮想関数ルックアップをC++でキャッシュできますか？

Question

抽象基本クラスポインタmypointer->foo（）で仮想関数呼び出しfoo（）があるとします。アプリが起動すると、ファイルの内容に基づいて、特定の具象クラスをインスタンス化することを選択し、そのインスタンスにmypointerを割り当てます。アプリの残りの人生の間、mypointerは常にその具体的なタイプのオブジェクトを指します。この具象型が何であるかを知る方法はありません（動的にロードされたライブラリのファクトリによってインスタンス化される可能性があります）。具象型のインスタンスが最初に作成された後、型が同じままになることを私は知っています。ポインタが常に同じオブジェクトを指しているとは限りませんが、オブジェクトは常に同じ具象型になります。タイプはファイルの内容に基づいているため、技術的には「実行時」に決定されますが、「起動」（ファイルがロードされる）後はタイプが固定されることに注意してください。

ただし、C ++では、アプリの全期間にわたってfooが呼び出されるたびに、仮想関数のルックアップコストを支払います。実行時に具象型が変化しないことを知る方法がないため、コンパイラーはルックアップを最適化できません（これまでで最も素晴らしいコンパイラーであったとしても、動的にロードされた動作を推測することはできません）ライブラリ）。Javaや.NETなどのJITコンパイル言語では、JITは同じタイプが何度も使用されていることを検出し、インラインキャッシュを実行できます。私は基本的に、C++の特定のポインターに対して手動でそれを行う方法を探しています。

このルックアップをキャッシュするC++の方法はありますか？私は、解決策がかなりハックなものかもしれないことを理解しています。ABI /コンパイラの関連する側面を検出する構成テストを記述して、実際に移植可能でなくても「実質的に移植可能」であるようにすることができれば、ABI/コンパイラ固有のハックを受け入れるつもりです。

更新：否定論者へ：これが最適化する価値がなかったとしたら、現代のJITがそれを行うとは思えません。SunとMSのエンジニアは、インラインキャッシュの実装に時間を浪費しており、改善があったことを確認するためにベンチマークを行っていなかったと思いますか？

Answer 1

仮想関数呼び出しには、vtable ルックアップと関数呼び出しの 2 つのコストがあります。

vtable ルックアップは、ハードウェアによって既に処理されています。最新の CPU (非常に単純な組み込み CPU で作業していないと仮定して) は、分岐予測子で仮想関数のアドレスを予測し、配列ルックアップと並行して投機的に実行します。 vtable ルックアップが関数の投機的実行と並行して行われるという事実は、説明した状況でループで実行された場合、仮想関数呼び出しは、直接の非インライン関数呼び出しと比較してオーバーヘッドがゼロに近いことを意味します。

C ++ではなくDプログラミング言語ではありますが、実際にこれを過去にテストしました。コンパイラの設定でインライン化が無効になっていて、ループ内で同じ関数を数百万回呼び出した場合、関数が仮想であるかどうかに関係なく、タイミングは互いにイプシロン内でした。

仮想関数の 2 番目のより重要なコストは、ほとんどの場合、関数のインライン化が妨げられることです。インライン化は、場合によっては定数の折りたたみなど、他のいくつかの最適化を有効にできる最適化であるため、これは思ったよりもさらに重要です。コードを再コンパイルせずに関数をインライン化する方法はありません。JIT は、アプリケーションの実行中に常にコードを再コンパイルしているため、これを回避します。

Answer 2

なぜ仮想通話は高価なのですか? コードが実行時に実行されるまで、分岐先がわからないからです。最新の CPU でさえ、仮想呼び出しと間接呼び出しを完全に処理しています。より高速な CPU があるからといって、単純にコストがかからないとは言えません。いいえそうではありません。

1. どうすれば高速化できますか?

あなたはすでに問題をかなり深く理解しています。ただし、仮想関数呼び出しが予測しやすい場合は、ソフトウェア レベルの最適化を実行できるとしか言えません。しかし、そうでない場合 (つまり、仮想関数のターゲットがまったくわからない場合)、今のところ良い解決策はないと思います。たとえCPUであっても、このような極端なケースを予測することは困難です。

実際、Visual C++ の PGO (プロファイリングに基づく最適化) などのコンパイラには、仮想呼び出しスペキュレーションの最適化 (リンク) があります。プロファイリング結果がホット仮想関数ターゲットを列挙できる場合、インライン化できる直接呼び出しに変換されます。これは、非仮想化とも呼ばれます。これは、一部の Java 動的オプティマイザーにも見られます。

2. 必要ないと言う方へ

スクリプト言語や C# を使っていて、コーディングの効率を気にしているのなら、それは無価値です。ただし、単一サイクルを節約してパフォーマンスを向上させたいと考えている人にとって、間接分岐は依然として重要な問題です。最新の CPU でさえ、仮想呼び出しの処理には適していません。1 つの良い例は、通常、非常に大きなスイッチケースを持つ仮想マシンまたはインタープリターです。そのパフォーマンスは、間接分岐の正しい予測にかなり関連しています。ですから、単純にレベルが低すぎる、必要がないなどとは言えません。底辺でパフォーマンスを改善しようとしている人は何百人もいます。そのため、そのような詳細は単に無視できます:)

3. 仮想機能に関連するいくつかの退屈なコンピューター アーキテクチャの事実

dsimcha は、CPU が仮想呼び出しを効果的に処理する方法について、適切な回答を書いています。しかし、それは正確には正しくありません。まず、最新のすべての CPU には分岐予測機能があります。これは、分岐の結果を文字通り予測して、パイプラインのスループット (または、命令レベルでのより多くの並列処理、またはILP )を向上させます。単一のスレッドから ILP を抽出できます (分岐予測は、より高い ILP を取得するための最も重要な要素です)。

分岐予測には 2 つの予測があります: (1) 方向 (つまり、分岐が行われるかどうかのバイナリ回答) と (2) 分岐ターゲット (つまり、どこに行くか? バイナリ回答ではない)。予測に基づいて、CPUは投機的にコードを実行します。推測が正しくない場合、CPU はロールバックし、予測を誤った分岐から再起動します。これは、プログラマの視点から完全に隠されています。そのため、分岐予測の誤り率を示す VTune を使用してプロファイリングしない限り、CPU 内で何が起こっているのかを実際に知ることはできません。

一般に、分岐方向の予測は非常に正確 (95% 以上) ですが、分岐ターゲット、特に仮想呼び出しとスイッチ ケース (つまり、ジャンプ テーブル) を予測することは依然として困難です。仮想呼び出しは、より多くのメモリ負荷を必要とする間接分岐であり、CPU も分岐先の予測を必要とします。Intel の Nehalem や AMD の Phenom などの最新の CPU には、特殊な間接分岐ターゲット テーブルがあります。

ただし、vtable を検索しても、多くのオーバーヘッドが発生するとは思いません。はい、キャッシュミスを引き起こす可能性のあるより多くのメモリ負荷が必要です。ただし、vtable がキャッシュに読み込まれると、ほぼキャッシュ ヒットになります。そのコストも気になる場合は、事前に vtable をロードするためのプリフェッチ コードを配置できます。しかし、仮想関数呼び出しの本当の難しさは、CPU が仮想呼び出しのターゲットを予測するのに十分な仕事をすることができないことです。これにより、ターゲットの予測ミスにより、パイプラインのドレインが頻繁に発生する可能性があります。

Answer 3

すべての答えは、仮想メソッドを呼び出すには、呼び出す実際のメソッドのアドレスを取得するだけでよいという最も単純なシナリオを扱っています。一般に、複数の仮想継承が機能する場合、仮想メソッドを呼び出すにはthisポインターをシフトする必要があります。

メソッドディスパッチメカニズムは複数の方法で実装できますが、仮想テーブルのエントリが実際に呼び出すメソッドではなく、thisポインターを再配置するコンパイラによって挿入された中間の「トランポリン」コードであることがよくあります。実際のメソッドを呼び出す前。

ディスパッチが最も単純で、追加のポインタ リダイレクトだけである場合、最適化しようとしても意味がありません。問題がより複雑な場合、解決策はコンパイラに依存し、ハッカー的になります。さらに、自分がどのシナリオにいるのかさえわかりません。オブジェクトが dll からロードされた場合、返された実際のインスタンスが単純な線形継承階層に属しているか、より複雑なシナリオに属しているかはわかりません。

Answer 4

したがって、これが (時期尚早の最適化の議論を避けるために) 解決したい基本的な問題であると仮定し、プラットフォームとコンパイラ固有のハッカーを無視すると、複雑さの反対側で次の 2 つのいずれかを行うことができます。

1. .dll の一部として、適切なメンバー関数を内部的に単純に直接呼び出す関数を提供します。間接ジャンプのコストはかかりますが、少なくとも vtable ルックアップのコストはかかりません。走行距離は異なる場合がありますが、特定のプラットフォームでは、間接関数呼び出しを最適化できます。
2. インスタンスごとにメンバー関数を呼び出す代わりに、インスタンスのコレクションを受け取る単一の関数を呼び出すように、アプリケーションを再構築します。Mike Acton は、なぜ、どのようにこれを行うべきかについて、(特定のプラットフォームとアプリケーションの種類を曲げて)素晴らしい投稿をしています。

Answer 5

I have seen situations where avoiding a virtual function call is beneficial. This does not look to me to be one of those cases because you really are using the function polymorphically. You are just chasing one extra address indirection, not a huge hit, and one that might be partially optimized away in some situations. If it really does matter, you may want to restructure your code so that type-dependent choices such as virtual function calls are made fewer times, pulled outside of loops.

If you really think it's worth giving it a shot, you can set a separate function pointer to a non-virtual function specific to the class. I might (but probably wouldn't) consider doing it this way.

class MyConcrete : public MyBase
{
public:
  static void foo_nonvirtual(MyBase* obj);
  virtual void foo()
  { foo_nonvirtual(this); }
};

void (*f_ptr)(MyBase* obj) = &MyConcrete::foo_nonvirtual;
// Call f_ptr instead of obj->foo() in your code.
// Still not as good a solution as restructuring the algorithm.

Other than making the algorithm itself a bit wiser, I suspect any attempt to manually optimize the virtual function call will cause more problems than it solves.

Answer 6

最近、非常によく似た質問をしたところ、GCC 拡張機能としては可能ですが、移植可能ではないという回答が得られました。

C++:仮想メンバー関数の単相バージョンへのポインター?

特に、Clang でも試してみましたが、この拡張機能はサポートされていません (他の多くの GCC 拡張機能をサポートしているにもかかわらず)。

Answer 7

したがって、基本的にやりたいことは、実行時ポリモーフィズムをコンパイル時ポリモーフィズムに変換することです。ここでも、複数の「ケース」を処理できるようにアプリをビルドする必要がありますが、実行に適用できるケースが決定されたら、それで終わりです。

ランタイム ポリモーフィズム ケースのモデルを次に示します。

struct Base {
  virtual void doit(int&)=0;
};

struct Foo : public Base {
  virtual void doit(int& n) {--n;}
};

struct Bar : public Base {
  virtual void doit(int& n) {++n;}
};

void work(Base* it,int& n) {
  for (unsigned int i=0;i<4000000000u;i++) it->doit(n);
}

int main(int argc,char**) {
  int n=0;

  if (argc>1)
    work(new Foo,n);
  else
    work(new Bar,n);

  return n;
}

これは、gcc 4.3.2 (32 ビット Debian) オプションでコンパイルされた Core2 で実行するのに ~14 秒かかり-O3ます。

ここで、「作業」バージョンをテンプレート化されたバージョン (作業対象の具象型でテンプレート化されたもの) に置き換えるとします。

template <typename T> void work(T* it,int& n) {
  for (unsigned int i=0;i<4000000000u;i++) it->T::doit(n);
}

mainを実際に更新する必要はありませんが、へのwork2 つの呼び出しにより、2 つの異なるタイプ固有の関数のインスタンス化と呼び出しがトリガーされることに注意してください (前の 1 つのポリモーフィック関数を参照してください)。

ちょっとプレストは0.001秒で実行されます。2 行の変更のスピードアップ要因としては悪くありません! ただし、大幅な速度向上は完全にコンパイラによるものであることに注意してください。work関数内のランタイム ポリモーフィズムの可能性が排除され、ループが最適化され、結果がコードに直接コンパイルされるだけです。しかし、それは実際には重要な点です。私の経験では、この種のトリックを使用することによる主な利点は、インライン化と最適化の改善の機会に由来しますvtable の間接化 (これは非常に安価です)。

しかし、実行時のポリモーフィズムが実際にパフォーマンスに影響を与えていることをプロファイリングが完全に示していない限り、このようなことを行うことはお勧めしません。Fooまた、誰かがサブクラス化したりBar、実際にそのベース用に意図された関数にそれを渡そうとすると すぐに、あなたを噛むでしょう.

この関連する質問も興味深いかもしれません。

Answer 8

メンバー関数へのポインターは共変の戻り値の型と見なされないため、メソッド ポインターは使用できません。以下の例を参照してください。

#include <iostream>

struct base;
struct der;

typedef void(base::*pt2base)();
typedef void(der::*pt2der)();

struct base {
    virtual pt2base method() = 0;
    virtual void testmethod() = 0;
    virtual ~base() {}
};

struct der : base {
    void testmethod() {
        std::cout << "Hello from der" << std::endl;
    }
    pt2der method() { **// this is invalid because pt2der isn't a covariant of pt2base**
        return &der::testmethod;
    }
};

もう 1 つのオプションは、メソッドを宣言することpt2base method()ですが、der::testmethod は pt2base 型ではないため、戻り値は無効になります。

また、基本型への ptr または参照を受け取ったメソッドがあったとしても、そのメソッドの派生型に動的にキャストして、節約しようとしているコストを追加する特にポリモーフィックな処理を行う必要があります。

Answer 9

メソッドポインタを使用できますか?

ここでの目的は、コンパイラが、解決されたメソッドまたは関数の場所をポインターにロードすることです。これは 1 回発生します。割り当ての後、コードはより直接的な方法でメソッドにアクセスします。

オブジェクトへのポインターと、オブジェクト ポイントを介してメソッドにアクセスすると、ランタイム ポリモーフィズムが呼び出されることを私は知っています。ただし、解決されたメソッドへのメソッド ポインターをロードして、ポリモーフィズムを回避し、関数を直接呼び出す方法が必要です。

コミュニティ wiki をチェックして、より多くの議論を紹介しました。