7

私は次のようなものに単純化できるC++アプリケーションを持っています:

class AbstractWidget {
 public:
  virtual ~AbstractWidget() {}
  virtual void foo() {}
  virtual void bar() {}
  // (other virtual methods)
};

class WidgetCollection {
 private:
  vector<AbstractWidget*> widgets;

 public:
  void addWidget(AbstractWidget* widget) {
    widgets.push_back(widget);
  }

  void fooAll() {
    for (unsigned int i = 0; i < widgets.size(); i++) {
      widgets[i]->foo();
    }
  }

  void barAll() {
    for (unsigned int i = 0; i < widgets.size(); i++) {
      widgets[i]->bar();
    }
  }

  // (other *All() methods)
};

私のアプリケーションはパフォーマンスが重要です。コレクションには通常、何千ものウィジェットがあります。AbstractWidget(数十ある)から派生したクラスは、通常、仮想関数の多くをオーバーライドしないままにします。オーバーライドされるものは、通常、非常に高速な実装になります。

これを考えると、いくつかの巧妙なメタプログラミングでシステムを最適化できると思います。目標は、コードを管理しやすくしながら、関数のインライン化を活用し、仮想関数の呼び出しを回避することです。不思議なことに繰り返されるテンプレートパターンを調べました(説明については、ここを参照してください)。これは私が望むことをほぼ実行しているようですが、完全ではありません。

ここでCRTPを機能させる方法はありますか?または、誰かが考えることができる他の賢い解決策はありますか?

4

6 に答える 6

7

シミュレートされた動的バインディング(CRTPの他の使用法があります)は、基本クラスがそれ自体をポリモーフィックであると考える場合に使用されますが、クライアントは実際には1つの特定の派生クラスのみを考慮します。したがって、たとえば、プラットフォーム固有の機能へのインターフェイスを表すクラスがあり、特定のプラットフォームに必要な実装は1つだけです。このパターンのポイントは、基本クラスをテンプレート化することです。これにより、複数の派生クラスが存在する場合でも、基本クラスはコンパイル時にどれが使用されているかを認識します。

たとえば、のコンテナがある場合など、ランタイムポリモーフィズムが本当に必要な場合は役に立ちませんAbstractWidget*。各要素は、いくつかの派生クラスの1つである可能性があり、それらを反復処理する必要があります。CRTP(または任意のテンプレートコード)でbase<derived1>base<derived2>は無関係のクラスです。したがって、ともそうderived1ですderived2。それらに別の共通の基本クラスがない限り、それらの間に動的なポリモーフィズムはありませんが、仮想呼び出しを開始したところに戻ります。

ベクトルをいくつかのベクトルに置き換えることで、スピードアップが得られる場合があります。1つは既知の派生クラスごとに、もう1つは後で新しい派生クラスを追加してコンテナを更新しない場合に使用します。次に、addWidgetはウィジェットへの(遅い)typeidチェックまたは仮想呼び出しを実行して、ウィジェットを正しいコンテナーに追加します。呼び出し元がランタイムクラスを知っている場合に備えて、オーバーロードが発生する可能性があります。WidgetIKnowAboutのサブクラスを誤ってWidgetIKnowAbout*ベクトルに追加しないように注意してください。fooAllまたbarAll、各コンテナをループして、非仮想関数fooImplbarImpl関数を(高速で)呼び出し、インライン化することができます。次に、仮想または関数を呼び出して、うまくいけばはるかに小さいAbstractWidget*ベクトルをループします。foobar

少し面倒で純粋なOOではありませんが、ほとんどすべてのウィジェットがコンテナが認識しているクラスに属している場合は、パフォーマンスが向上する可能性があります。

ほとんどのウィジェットがコンテナが認識できない可能性のあるクラスに属している場合(たとえば、ウィジェットが異なるライブラリにあるため)、インライン化できない可能性があることに注意してください(ダイナミックリンカがインライン化できない場合。私の場合はできません)。メンバー関数ポインターをいじることで仮想呼び出しのオーバーヘッドを減らすことができますが、ゲインはほぼ確実に無視できるか、さらにはマイナスになります。仮想呼び出しのオーバーヘッドのほとんどは、仮想ルックアップではなく呼び出し自体にあり、関数ポインターを介した呼び出しはインライン化されません。

別の見方をすると、コードをインライン化する場合、実際のマシンコードはタイプごとに異なる必要があることを意味します。これは、コレクションから引き出されたポインターのタイプに応じて、ループを通過するたびにマシンコードがROM内で明らかに変更できないため、複数のループまたはスイッチを含むループのいずれかが必要であることを意味します。

おそらく、オブジェクトには、ループがRAMにコピーし、実行可能マークを付けてジャンプするasmコードが含まれている可能性があります。しかし、それはC++メンバー関数ではありません。そして、それは移植可能に行うことはできません。そして、それはおそらく高速ではないでしょう、コピーとicacheの無効化ではどうでしょう。これが仮想通話が存在する理由です...

于 2009-06-16T17:05:43.960 に答える
5

CRTPまたはコンパイル時のポリモーフィズムは、コンパイル時にすべての型を知っている場合に使用します。addWidget実行時にウィジェットのリストを収集するために使用している限りfooAll、実行時barAllにその同種のウィジェットのリストのメンバーを処理する必要がある限り、実行時にさまざまなタイプを処理できる必要があります。したがって、あなたが提示した問題については、ランタイムポリモーフィズムを使用して立ち往生していると思います。

もちろん、標準的な答えは、実行時のポリモーフィズムのパフォーマンスが問題であることを確認してから、それを回避しようとすることです...

実行時の多形性を本当に回避する必要がある場合は、次のいずれかの解決策が機能する可能性があります。

オプション1:ウィジェットのコンパイル時コレクションを使用する

WidgetCollectionのメンバーがコンパイル時にわかっている場合は、テンプレートを非常に簡単に使用できます。

template<typename F>
void WidgetCollection(F functor)
{
  functor(widgetA);
  functor(widgetB);
  functor(widgetC);
}

// Make Foo a functor that's specialized as needed, then...

void FooAll()
{
  WidgetCollection(Foo);
}

オプション2:ランタイムポリモーフィズムを無料の関数に置き換えます

class AbstractWidget {
 public:
  virtual AbstractWidget() {}
  // (other virtual methods)
};

class WidgetCollection {
 private:
  vector<AbstractWidget*> defaultFooableWidgets;
  vector<AbstractWidget*> customFooableWidgets1;
  vector<AbstractWidget*> customFooableWidgets2;      

 public:
  void addWidget(AbstractWidget* widget) {
    // decide which FooableWidgets list to push widget onto
  }

  void fooAll() {
    for (unsigned int i = 0; i < defaultFooableWidgets.size(); i++) {
      defaultFoo(defaultFooableWidgets[i]);
    }
    for (unsigned int i = 0; i < customFooableWidgets1.size(); i++) {
      customFoo1(customFooableWidgets1[i]);
    }
    for (unsigned int i = 0; i < customFooableWidgets2.size(); i++) {
      customFoo2(customFooableWidgets2[i]);
    }
  }
};

醜い、そして実際にはOOではありません。テンプレートは、すべての特殊なケースをリストする必要性を減らすことで、これを支援することができます。次のようなものを試してください(完全にテストされていません)が、この場合はインライン化されていません。

class AbstractWidget {
 public:
  virtual AbstractWidget() {}
};

class WidgetCollection {
 private:
  map<void(AbstractWidget*), vector<AbstractWidget*> > fooWidgets;

 public:
  template<typename T>
  void addWidget(T* widget) {
    fooWidgets[TemplateSpecializationFunctionGivingWhichFooToUse<widget>()].push_back(widget);
  }

  void fooAll() {
    for (map<void(AbstractWidget*), vector<AbstractWidget*> >::const_iterator i = fooWidgets.begin(); i != fooWidgets.end(); i++) {
      for (unsigned int j = 0; j < i->second.size(); j++) {
        (*i->first)(i->second[j]);
      }
    }
  }
};

オプション3:OOを排除する

OOは、複雑さを管理し、変化に直面しても安定性を維持するのに役立つため、便利です。あなたが説明しているように見える状況(その振る舞いは一般に変わらず、メンバーメソッドは非常に単純な何千ものウィジェット)では、管理するのにそれほど複雑さや変更がない場合があります。その場合は、OOは必要ないかもしれません。

このソリューションは、「仮想」メソッドと既知のサブクラス(OOではない)の静的リストを維持する必要があり、仮想関数呼び出しをインライン関数へのジャンプテーブルに置き換えることができることを除いて、ランタイムポリモーフィズムと同じです。

class AbstractWidget {
 public:
  enum WidgetType { CONCRETE_1, CONCRETE_2 };
  WidgetType type;
};

class WidgetCollection {
 private:
  vector<AbstractWidget*> mWidgets;

 public:
  void addWidget(AbstractWidget* widget) {
    widgets.push_back(widget);
  }

  void fooAll() {
    for (unsigned int i = 0; i < widgets.size(); i++) {
      switch(widgets[i]->type) {
        // insert handling (such as calls to inline free functions) here
      }
    }
  }
};
于 2009-06-16T17:00:28.037 に答える
4

簡単な答えはノーです。

長い答え(または他のいくつかの答えにまだ短いキャンパー:-)

実行時に実行する関数(つまり、仮想関数)を動的に把握しようとしています。ベクトル(コンパイル時にメンバーを決定できない)がある場合は、何を試しても関数をインライン化する方法を理解できません。

それに対する唯一の注意点は、ベクトルに常に同じ要素が含まれている場合です(つまり、実行時に実行されるコンパイル時間を計算できます)。次に、これをやり直すことができますが、要素(おそらくすべての要素をメンバーとして持つ構造)を保持するために、ベクトル以外の何かが必要になります。

また、仮想ディスパッチがボトルネックだと本当に思いますか?
個人的に私はそれを非常に疑っています。

于 2009-06-16T17:39:44.267 に答える
3

ここで発生する問題は、にありますWidgetCollection::widgets。ベクトルには1つのタイプのアイテムのみを含めることができ、CRTPを使用するには、それぞれAbstractWidgetが異なるタイプを持ち、目的の派生タイプによってテンプレート化されている必要があります。つまり、次AbstractWidgetのようになります。

template< class Derived >
class AbstractWidget {
    ...
    void foo() {
        static_cast< Derived* >( this )->foo_impl();
    }        
    ...
}

つまり、タイプがAbstractWidget異なると、それぞれが異なるDerivedタイプを構成しAbstractWidget< Derived >ます。これらすべてを単一のベクトルに格納することは機能しません。したがって、この場合、仮想関数が進むべき道のように見えます。

于 2009-06-16T16:56:13.563 に答える
3

それらのベクトルが必要な場合は違います。STLコンテナーは完全に同種です。つまり、widgetAとwidgetBを同じコンテナーに格納する必要がある場合は、それらを共通の親から継承する必要があります。また、widgetA :: bar()がwidgetB :: bar()とは異なる処理を行う場合は、関数を仮想化する必要があります。

すべてのウィジェットが同じコンテナーにある必要がありますか?あなたは次のようなことをすることができます

vector<widgetA> widget_a_collection;
vector<widgetB> widget_b_collection;

そして、関数は仮想である必要はありません。

于 2009-06-16T16:57:38.023 に答える
1

そのような努力をすべて行った後でも、パフォーマンスに違いは見られない可能性があります。

これは、最適化するための絶対に間違った方法です。コードのランダムな行を変更してロジックのバグを修正しませんか?いいえ、それはばかげています。実際に問題を引き起こしている行を最初に見つけるまで、コードを「修正」しません。では、なぜパフォーマンスのバグを別の方法で処理するのでしょうか。

アプリケーションのプロファイルを作成し、実際のボトルネックがどこにあるかを見つける必要があります。次に、そのコードを高速化し、プロファイラーを再実行します。パフォーマンスのバグ(実行が遅すぎる)がなくなるまで繰り返します。

于 2009-06-16T17:48:04.300 に答える