Избегание повторного поиска в виртуальной таблице C ++

Question

У меня есть программа C ++, которая читает файл конфигурации при выполнении двоичного файла, создает несколько экземпляров дочерних классов на основе файла конфигурации, а затем периодически выполняет итерации по этим экземплярам и вызывает их соответствующие виртуальные функции.

Gprof говорит мне, что эти вызовы функций занимают много времени (вышеупомянутая итерация происходит очень часто), поэтому я хочу попытаться как-то избежать повторных вызовов виртуальных функций.

Код похож на последующий. Как только программа заполняет вектор v в начале программы, этот вектор больше не будет изменяться для остальной части программы, поэтому кажется неэффективным многократно выполнять поиск виртуальной таблицы каждый раз, когда я хочу вызвать f (). Я бы подумал, что должен быть способ как-то кешировать или сохранить указатели функций, но я не уверен, как.

Буду рад любым предложениям по ускорению. Спасибо!

Редактировать: Извините, я забыл упомянуть, что вызов функции f () для вектора экземпляров Child должен быть в порядке от 0 до v.size () - 1, поэтому я могу ' t сгруппировать элементы v, имеющие один и тот же производный тип.

Кроме того, это было построено с -O3 -std = c ++ 14

class Parent {
public:
    virtual void f() { } 
};

class Child1 : public Parent {
public:
    void f() { /* do stuff for child1 */ }
};

//...

class Child9 : public Parent {
public:
    void f() { /* do stuff for child9 */ }
};

int main() {
    vector<Parent*> v;

    // read config file and add Child instances to v based on the file contents

    while (true) {
        // do other stuff
        for (size_t i = 0; i != v.size(); ++i) {
             v[i]->f(); // expensive to do the same virtual table lookups every loop!
        }
    }
};

Answer 1

Основываясь на некоторых вопросах и ваших ответах в комментариях, вот несколько соображений.

1) Ваша проблема (если она есть, ваше решение может быть уже близко к оптимальному, в зависимости от детали, которые вы не упомянули), скорее всего, где-то еще, не в накладных расходах при вызове виртуальной функции.

Если вы действительно выполняете это в жестком l oop, и в реализациях мало что происходит f (), который затрагивает много памяти, ваши vtables, вероятно, остаются в кеше L1, и издержки виртуальных функций будут абсолютно минимальными, если таковые имеются, на современном оборудовании.

2) Вы говорите: Сами функции f () очень просты, например, одна из них просто умножает значения по двум адресам памяти и сохраняет продукт по третьему адресу »- это может быть не так невинно, как вы ожидаете. Для справки, переход к кэш-памяти L1 обойдется вам примерно в 3 цикла, а доступ к ОЗУ может стоить до 60-200, в зависимости от вашего оборудования.

Если у вас достаточно этих объектов (чтобы сохранить все память, на которую они ссылаются в кеше L1, невозможна), и области памяти, на которые они ссылаются, в основном случайны (так что предварительная выборка неэффективна), и / или вы касаетесь достаточного количества вещей в остальной части вашей программы (чтобы все соответствующие данные получали освобождается из кэша между циклами вашего вектора), стоимость извлечения и хранения значений из памяти и в нее / более низкие уровни кэша в худшем случае перевесят стоимость вызовов виртуальных функций на порядки.

3) Вы перебираете вектор указателей на объекты, а не на сами объекты.

В зависимости от того, как вы распределяете объекты и насколько они велики, это может не быть проблемой - предварительная выборка будет творить чудеса для Вы, если вы распределяете их в узком l oop, а ваш распределитель упаковывает их красиво у. Однако, если вы распределяете / освобождаете много других вещей и смешиваете распределение этих объектов между ними, они могут в конечном итоге располагаться редко и в основном в случайных местах в памяти; затем итерирование по ним в порядке создания потребует большого количества случайных чтений из памяти, что снова будет намного медленнее, чем издержки любой виртуальной функции.

4) Вы говорите «вызовы f () для вектора дети должны быть в порядке "- не так ли?

Если они это сделают, то вам в некотором смысле не повезло. Однако, если вы можете перестроить вашу систему так, чтобы их можно было упорядочивать по типу, тогда можно получить большую скорость в различных аспектах - вы, вероятно, могли бы выделить массив для каждого типа объекта (хороший, плотный в памяти), перебирайте их по порядку (удобен для предварительной выборки) и вызывайте ваши f () в группах для одного, хорошо известного типа (дружественный встраивание, дружественный кэш инструкций).

5) И наконец - если ни один из вышеперечисленных случаев не применим, и ваша проблема действительно заключается в вызовах виртуальных функций (маловероятно), тогда, да, вы можете попытаться сохранить указатель на точную функцию, которую вы должны вызывать для каждого объекта каким-либо образом - либо вручную, либо используя один из методов стирания типа / стирания / утки, которые предлагали другие.

Мой главный вопрос заключается в следующем - при изменении архитектуры вашей системы можно получить много преимуществ.

Помните: доступ к вещам, которые уже находятся в кеше L1 / L2 - это хорошо, необходимо go к L3 / RAM для данных хуже; доступ к памяти в последовательном порядке - это хорошо, перепрыгивание через память - плохо; вызов одного и того же метода в узком l oop, потенциально его вставка, это хорошо, вызов большого количества различных методов в узком l oop хуже.

Если это часть вашей программы, производительность которого действительно имеет значение, вы должны рассмотреть возможность изменения архитектуры вашей системы, чтобы учесть некоторые из ранее упомянутых оптимизаций. Я знаю, что это может показаться пугающим, но в эту игру мы играем. Иногда вам нужно пожертвовать «чистыми» OOP и абстракциями ради производительности, если проблема, которую вы решаете, позволяет это сделать.

Answer 2

Редактировать: для вектора произвольных дочерних типов, смешанных вместе, я рекомендую пойти с виртуальным вызовом.

---

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

template<class Child, class Range>
void f_for(Range& r) {
    for (Parent* p : r) {
        Child* c = static_cast<Child*>(p);
        c->Child::f(); // use static dispatch to avoid virtual lookup
    }
}

...

if (config)
    f_for<Child1>(v);
else
    f_for<Child2>(v);

Альтернативой явной отправке stati c может быть пометка дочернего класса или функции-члена окончательной.

Вы можете даже расширить часть stati c программа, так что вы можете использовать vector<Child1> или vector<Child2> напрямую, избегая лишнего косвенного обращения. На этом этапе наследование даже не требуется.