ここで不思議な繰り返しテンプレートパターンを使用できますか(C ++)?
-
05-07-2019 - |
質問
次のように単純化できる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を機能させる方法はありますか?または、誰もが考えることができる他の賢い解決策はありますか?
解決
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]);
}
}
};
Uい、実際にはオブジェクト指向ではありません。テンプレートは、すべての特殊なケースをリストする必要性を減らすことでこれを支援できます。次のようなもの(完全に未テスト)を試してみてください。ただし、この場合はインライン化されません。
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は、複雑さの管理に役立ち、変更に直面しても安定性を維持できるので便利です。あなたが記述しているように見える状況-ふるまいが一般に変化せず、メンバーメソッドが非常に単純な数千のウィジェット-あなたはあまり管理する複雑さや変更がないかもしれません。その場合、オブジェクト指向は必要ないかもしれません。
このソリューションは、<!> quot; virtual <!> quot;の静的リストを維持する必要があることを除いて、ランタイムポリモーフィズムと同じです。メソッドと既知のサブクラス(オブジェクト指向ではない)を使用して、仮想関数呼び出しをインライン関数へのジャンプテーブルに置き換えることができます。
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
}
}
}
};
他のヒント
シミュレートされた動的バインディング(CRTPのその他の用途があります)は、ベースクラスがそれ自身をポリモーフィックであると見なしますが、クライアントは実際には1つの特定の派生クラス。そのため、たとえば、プラットフォーム固有の機能へのインターフェースを表すクラスがあり、特定のプラットフォームで必要な実装は1つだけです。パターンのポイントは、基本クラスをテンプレート化することです。これにより、複数の派生クラスが存在する場合でも、基本クラスはコンパイル時に使用中のクラスを認識します。
たとえばAbstractWidget*
のコンテナがある場合など、実行時のポリモーフィズムが本当に必要な場合、各要素はいくつかの派生クラスの1つである可能性があるため、それらを反復する必要はありません。 CRTP(またはテンプレートコード)では、base<derived1>
とbase<derived2>
は無関係なクラスです。したがって、derived1
およびderived2
も同様です。別の共通の基本クラスがない限り、それらの間に動的なポリモーフィズムはありませんが、仮想呼び出しを開始した場所に戻ります。
ベクトルを複数のベクトルに置き換えることで、速度が向上する場合があります:知っている各派生クラスに1つと、後で新しい派生クラスを追加してコンテナを更新しない場合に使用する一般的な1つです。次に、addWidgetは(遅い)typeid
チェックまたはウィジェットの仮想呼び出しを行って、ウィジェットを正しいコンテナーに追加します。また、呼び出し側がランタイムクラスを認識しているときのために、いくつかのオーバーロードがあります。誤ってWidgetIKnowAbout
のサブクラスをWidgetIKnowAbout*
ベクトルに追加しないように注意してください。 fooAll
およびbarAll
は、各コンテナを順番にループして、非仮想のfooImpl
およびbarImpl
関数を(高速で)呼び出してからインライン化します。次に、できればはるかに小さいfoo
ベクトルをループ処理し、仮想bar
または<=>関数を呼び出します。
少し複雑で純粋なオブジェクト指向ではありませんが、ほとんどすべてのウィジェットがコンテナが知っているクラスに属している場合、パフォーマンスが向上する可能性があります。
ほとんどのウィジェットがコンテナがおそらく知らないクラスに属している場合(たとえば、異なるライブラリにあるため)、インライン化することはできないことに注意してください(動的リンカーがインライン化できない限り。 t)。メンバー関数のポインターをいじって仮想呼び出しのオーバーヘッドを減らすことができますが、ほとんど確実に無視できるほどのマイナスのゲインになります。仮想呼び出しのオーバーヘッドのほとんどは、仮想ルックアップではなく呼び出し自体にあり、関数ポインターを介した呼び出しはインライン化されません。
別の方法を見てください。コードをインライン化する場合、実際のマシンコードはタイプごとに異なっている必要があります。これは、コレクションから引き出されたポインターの種類に応じて、ループを通過するたびにマシンコードがROMで変更できないため、複数のループ、またはスイッチを含むループのいずれかが必要であることを意味します。
まあ、おそらくオブジェクトにはループがRAMにコピーし、実行可能とマークしてジャンプするasmコードが含まれていると思います。しかし、それはC ++メンバー関数ではありません。そして、移植性はありません。そして、コピーやicacheの無効化ではどうでしょうか。これが仮想呼び出しが存在する理由です...
短い答えはノーです。
長い回答(または、他のいくつかの回答にまだ短い回答:-)
実行時に実行する関数(つまり、仮想関数とは)を動的に把握しようとしています。ベクター(コンパイル時にメンバーを決定できない)がある場合、何を試しても関数をインライン化する方法を見つけることはできません。
唯一のキャビアは、ベクトルに常に同じ要素が含まれている場合です(つまり、実行時に実行されるものをコンパイル時に解決できます)。その後、これをやり直すことができますが、要素(おそらくすべての要素をメンバーとして持つ構造体)を保持するためにベクター以外の要素が必要になります。
また、仮想ディスパッチがボトルネックだと本当に思いますか?
個人的には非常に疑っています。
ここで発生する問題はWidgetCollection::widgets
にあります。ベクターには1つのタイプのアイテムのみを含めることができ、CRTPを使用するには、各AbstractWidget
に異なるタイプが必要であり、目的の派生タイプによってテンプレート化されている必要があります。つまり、Derived
は次のようになります:
template< class Derived >
class AbstractWidget {
...
void foo() {
static_cast< Derived* >( this )->foo_impl();
}
...
}
これは、異なるAbstractWidget< Derived >
タイプを持つ各<=>が異なるタイプ<=>を構成することを意味します。これらすべてを単一のベクターに保存することはできません。したがって、この場合、仮想関数を使用する方法のように見えます。
それらのベクトルが必要な場合は別です。 STLコンテナは完全に同種です。つまり、同じコンテナにwidgetAとwidgetBを格納する必要がある場合、それらは共通の親から継承される必要があります。また、widgetA :: bar()がwidgetB :: bar()とは異なる処理を行う場合、関数を仮想化する必要があります。
すべてのウィジェットを同じコンテナに入れる必要がありますか?次のようなことができます
vector<widgetA> widget_a_collection;
vector<widgetB> widget_b_collection;
そして、関数は仮想である必要はありません。
オッズは、すべての努力を行った後、パフォーマンスの違いは見られないということです。
これは絶対に最適化するための間違った方法です。ランダムなコード行を変更しても論理的なバグは修正されませんか?いいえ、それはばかげています。 <!> quot; fix <!> quot;どの行が実際に問題を引き起こしているのかを最初に見つけるまでコードを作成します。では、なぜパフォーマンスバグを異なる方法で処理するのですか?
アプリケーションのプロファイルを作成し、実際のボトルネックがどこにあるかを見つける必要があります。次に、そのコードを高速化し、プロファイラーを再実行します。パフォーマンスのバグ(実行が遅すぎる)がなくなるまで繰り返します。