在計算圖中避免虛函數調用

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]在我的系統上進行一次加法操作需要約2.3ns的虛擬功能和1.1ns的無需。雖然這很小，但整個計算圖大部分是加法節點，因此有很大一部分時間需要保存。

Answer 1

正如在評論中提到的那樣，您需要在編譯時瞭解該圖以移除虛擬調度。要做到這一點，你只需要使用一個std::tuple：

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

然後，你只需要刪除virtual和override關鍵字，並在基類中刪除空函數。你會發現基於循環的range不支持元組。要重複它，你將需要功能：

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(); 
});