Как избежать вызовов виртуальных функций в вычислительном графе

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,3 нс с виртуальными функциями и 1,1 нс без. Несмотря на то, что он небольшой, весь вычислительный граф в основном состоит из узлов сложения, и, следовательно, есть значительная часть времени, которая будет сохранена.

Answer 1

Как уже упоминалось в комментариях, вам нужно знать график во время компиляции, чтобы удалить виртуальную диспетчеризацию. Для этого вам нужно всего лишь использовать std::tuple:

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

Затем вам нужно только удалить virtual а также override ключевые слова и удаление пустой функции в базовом классе.

Вы обнаружите, что диапазон, основанный на цикле, пока не поддерживает кортежи. Чтобы выполнить итерацию, вам понадобится эта функция:

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