計算グラフの仮想関数呼び出しの回避

Question

私は式を表現し評価するためにDAG（有向非循環グラフ）を使用しています。各ノードは操作（+,-,/,*、蓄積など）を表し、表現全体の評価は、各ノードをトポロジカルにソートされた順序で順次評価することによって達成される。各ノードは基底クラスRefNodeを継承し、仮想関数がと評価され、それが表す演算子に従います。 Nodeクラスは、演算子を表すファンクタでテンプレート化されています。ノードの評価順序は、vector<RefNode*>に保持され、各要素には->evaluate()が呼び出されます。

いくつかのクイックプロファイリングでは、仮想ノードevaluateは、オーバーヘッドまたは分岐予測を破棄することによって、加算ノードを2倍[1]だけ減速させることを示しています。

最初のステップとして、タイプ情報を整数として符号化します。それに応じて、static_castが使用されます。これは助けになりましたが、それほど大変ではなく、私のコードの熱い部分を飛び回ることはありませんでした。

struct RefNode { 
    double output; 
    inline virtual void evaluate(){} 
}; 

template<class T> 
struct Node : RefNode { 
    double* inputs[NODE_INPUT_BUFFER_LENGTH]; 
    T evaluator; 
    inline void evaluate(){ evaluator(inputs, output); } 
}; 

struct Add { 
    inline void operator()(double** inputs, double &output) 
    { 
     output=*inputs[0]+*inputs[1]; 
    } 
}; 

評価は次のようになります。

Node<Add>* node_1 = ... 
Node<Add>* node_2 = ... 
std::vector<RefNode*> eval_vector; 

eval_vector.push_back(node_1); 
eval_vector.push_back(node_2); 

for (auto&& n : eval_vector) { 
    n->evaluate(); 
} 

私は心の性能にベアリング、以下の質問を持っている非常に重要です。

1. 私はこのような状況で仮想関数を避けることができる方法は？
2. そうでなければ、表現グラフを表現する方法を変更して、複数の操作をサポートする必要があります。そのうちのいくつかは状態を保持し、仮想関数呼び出しを避ける必要があります。
3. Tensorflow/Theanoなどの他のフレームワークはどのように計算グラフを表しますか？

[1]私のシステム上での1回の加算操作は、仮想関数と〜1.1nsを必要とせず〜2.3nsかかります。これは小さなものですが、計算グラフ全体はほとんどが加算ノードなので、保存する時間はかなりあります。

Answer 1

コメントに記載されているように、仮想ディスパッチを削除するには、コンパイル時にグラフを知る必要があります。あなただけvirtualとoverrideキーワードを削除する必要があり、その後

auto eval_vector = std::make_tuple(
    Node<Add>{ ... }, 
    Node<Add>{ ... }, 
    ... 
); 

、および基底クラスで空の除去機能：これを行うには、あなただけのstd::tupleを使用する必要があります。

ループベースの範囲はまだタプルをサポートしていないことがわかります。それを反復処理するには、その機能が必要になります。

template<typename T, typename F, std::size_t... S> 
void for_tuple(std::index_sequence<S...>, T&& tuple, F&& function) { 
    int unpack[] = {(static_cast<void>(
     function(std::get<S>(std::forward<T>(tuple)) 
    ), 0)..., 0}; 
    static_cast<void>(unpack); 
} 

template<typename T, typename F> 
void for_tuple(T&& tuple, F&& function) { 
    constexpr std::size_t N = std::tuple_size<std::remove_reference_t<T>>::value; 
    for_tuple(std::make_index_sequence<N>{}, std::forward<T>(tuple), std::forward<F>(function)); 
} 

あなたは、そのようなあなたのタプルに反復することができます

for_tuple(eval_vector, [](auto&& node){ 
    node.evaluate(); 
});