4

我正在使用 DAG（有向无环图）来表示和评估表达式；每个节点代表一个操作（+、-、/、*、accumulate 等），整个表达式的评估是通过按拓扑排序顺序依次评估每个节点来实现的。每个节点都继承一个基类并根据它所代表的运算符RefNode实现一个虚函数evaluate 。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 没有。虽然这很小，但整个计算图主要是附加节点，因此有很大一部分时间可以节省。

4

1 回答 1

0

正如评论中提到的，您需要在编译时知道该图以删除虚拟调度。为此，您只需要使用std::tuple：

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

然后，您只需要删除virtualandoverride关键字，并删除基类中的空函数。

你会发现基于范围的 for 循环还不支持元组。要对其进行迭代，您将需要该函数：

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();
});
于 2017-02-27T15:06:11.203 回答