Можете ли вы кэшировать поиск виртуальной функции на С++?

Ответ 1

Существует две стоимости вызова виртуальной функции: просмотр vtable и вызов функции.

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

Я действительно тестировал это в прошлом, хотя и на языке программирования D, а не на С++. Когда в настройках компилятора была отключена вставка, я вызывал одну и ту же функцию в цикле несколько миллионов раз, тайминги находились в пределах друг от друга независимо от того, была ли эта функция виртуальной или нет.

Вторая и более важная стоимость виртуальных функций заключается в том, что они предотвращают вложение функции в большинстве случаев. Это еще более важно, чем кажется, потому что inlining - это оптимизация, которая может включать в некоторых случаях несколько других оптимизаций, таких как постоянное складывание. Невозможно встроить функцию без перекомпиляции кода. JITs обойти это, потому что они постоянно перекомпилируют код во время выполнения вашего приложения.

Ответ 2

Почему виртуальный вызов стоит дорого? Потому что вы просто не знаете цель ветки, пока код не будет выполнен во время выполнения. Даже современные процессоры по-прежнему отлично справляются с виртуальными вызовами и косвенными вызовами. Нельзя просто сказать, что это ничего не стоит, потому что у нас просто быстрый процессор. Нет, это не так.

1. Как мы можем сделать это быстро?

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

Собственно, компиляторы, такие как Visual С++ PGO (оптимизация профилирования), имеют оптимизацию виртуальных вызовов (Ссылка), Если результат профилирования может перечислить цели горячей виртуальной функции, тогда он переводит на прямой вызов, который может быть встроен. Это также называется devirtualization. Его также можно найти в некоторых динамических оптимизаторах Java.

2. Тем, кто говорит, что это не нужно

Если вы используете языки script, С# и заботу об эффективности кодирования, да, это бесполезно. Тем не менее, любой, кто хочет сохранить один цикл, чтобы получить лучшую производительность, тогда косвенная ветвь по-прежнему остается важной проблемой. Даже самые последние процессоры не подходят для обработки виртуальных вызовов. Хорошим примером может служить виртуальная машина или интерпретатор, который обычно имеет очень большой коммутационный регистр. Его производительность в значительной степени связана с правильным предсказанием непрямой ветки. Таким образом, вы не можете просто сказать, что это слишком низкоуровневое или не нужно. Есть сотни людей, которые пытаются улучшить производительность в нижней части. Вот почему вы можете просто игнорировать такие детали:)

3. Некоторые скучные компьютерные архитектурные факты, связанные с виртуальными функциями

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

В предсказании ветвления существуют два предсказания: (1) направление (т.е. ветвь берется? или не принимается? двоичный ответ) и (2) цель ветвления (т.е. куда я пойду? это не бинарный ответ). Основываясь на предсказании, процессор спекулятивно выполняет код. Если спекуляция неверна, тогда откаты CPU и перезапускаются из неверно предсказанной ветки. Это полностью скрыто от представления программиста. Таким образом, вы действительно не знаете, что происходит внутри CPU, если вы не профилируете VTune, что дает вероятности неверного прогноза отрасли.

В общем, предсказание направления ветвления является очень точным (95% +), но все же трудно предсказать цели ветвления, особенно виртуальные вызовы и случай переключения (т.е. таблицу перехода). Vrtual call - это непрямая ветвь, которая требует большей загрузки памяти, а также CPU требует предсказания целевой ветки. Современные процессоры, такие как Intel Nehalem и AMD Phenom, имеют специализированную целевую таблицу непрямых веток.

Однако, я не думаю, что поиск vtable несет много накладных расходов. Да, для этого требуется больше загрузки памяти, что может привести к провалу кеша. Но, как только vtable загрузится в кеш, тогда он сильно ударит кеш. Если вы также обеспокоены этой стоимостью, вы можете поместить предварительно загружаемый код для загрузки vtable заранее. Но реальная сложность вызова виртуальных функций заключается в том, что ЦП не может справиться с большими задачами, чтобы предсказать цель виртуального вызова, что может привести к тому, что трафик трубопровода часто возникает из-за неверного предсказания цели.

Ответ 3

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

• Предоставить функцию как часть DLL, которая внутренне просто вызывает правильную функцию-член напрямую. Вы оплачиваете косвенный скачок, но, по крайней мере, вы не оплачиваете стоимость поиска vtable. Ваш пробег может отличаться, но на некоторых платформах вы можете оптимизировать вызов косвенных функций.
• Перестройте приложение таким образом, чтобы вместо вызова функции-члена на экземпляр вы вызывали одну функцию, которая принимает коллекцию экземпляров. У Майка Актона есть замечательный post (с определенной платформой и типом приложения), почему и как вы должны это делать.

Ответ 4

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

Механизм отправки метода может быть реализован более чем одним способом, но обычно обнаруживается, что запись в виртуальной таблице не является фактическим методом вызова, а скорее некоторым промежуточным "батутным" кодом, вставленным компилятором, который перемещает указатель this до вызова фактического метода.

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

Ответ 5

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

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

class MyConcrete : public MyBase
{
public:
  static void foo_nonvirtual(MyBase* obj);
  virtual void foo()
  { foo_nonvirtual(this); }
};

void (*f_ptr)(MyBase* obj) = &MyConcrete::foo_nonvirtual;
// Call f_ptr instead of obj->foo() in your code.
// Still not as good a solution as restructuring the algorithm.

Помимо того, что сам алгоритм немного мудрее, я подозреваю, что любая попытка вручную оптимизировать вызов виртуальной функции вызовет больше проблем, чем решает.

Ответ 6

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

#include <iostream>

struct base;
struct der;

typedef void(base::*pt2base)();
typedef void(der::*pt2der)();

struct base {
    virtual pt2base method() = 0;
    virtual void testmethod() = 0;
    virtual ~base() {}
};

struct der : base {
    void testmethod() {
        std::cout << "Hello from der" << std::endl;
    }
    pt2der method() { **// this is invalid because pt2der isn't a covariant of pt2base**
        return &der::testmethod;
    }
};

Другой вариант должен состоять в том, чтобы объявить метод pt2base method(), но тогда возврат недействителен, потому что der:: testmethod не относится к типу pt2base.

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

Ответ 7

Недавно я задал очень похожий вопрос и получил ответ, что это возможно как расширение GCC, но не переносимо:

С++: указатель на мономорфную версию виртуальной функции-члена?

В частности, я также пробовал его с Clang и не поддерживает это расширение (хотя он поддерживает многие другие расширения GCC).

Ответ 8

Не могли бы вы использовать указатель метода?

Цель состоит в том, что компилятор загрузит указатель с указанием местоположения разрешенного метода или функции. Это произойдет один раз. После назначения код будет обращаться к методу более прямым образом.

Я знаю, что указатель на объект и доступ к методу через точку объекта вызывает полиморфизм во время выполнения. Однако должен быть способ загрузить указатель метода на разрешенный метод, избегая полиморфизма и напрямую вызывающего функцию.

Я проверил вики сообщества, чтобы обсудить больше.

Ответ 9

Итак, что вы в основном хотите сделать, это преобразовать полиморфизм во время выполнения в полиморфизм времени компиляции. Теперь вам все равно нужно создать приложение, чтобы он мог обрабатывать несколько "случаев", но как только он решил, какой случай применим к прогону, он будет на время.

Здесь показана модель случая полиморфизма времени выполнения:

struct Base {
  virtual void doit(int&)=0;
};

struct Foo : public Base {
  virtual void doit(int& n) {--n;}
};

struct Bar : public Base {
  virtual void doit(int& n) {++n;}
};

void work(Base* it,int& n) {
  for (unsigned int i=0;i<4000000000u;i++) it->doit(n);
}

int main(int argc,char**) {
  int n=0;

  if (argc>1)
    work(new Foo,n);
  else
    work(new Bar,n);

  return n;
}

Это займет ~ 14 секунд для выполнения на моем Core2, скомпилированном с опцией gcc 4.3.2 (32-разрядный Debian), -O3.

Теперь предположим, что мы заменим версию "work" на шаблонизированную версию (по шаблону на конкретный тип, над которой она будет работать):

template <typename T> void work(T* it,int& n) {
  for (unsigned int i=0;i<4000000000u;i++) it->T::doit(n);
}

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

Hey presto работает в 0,001s. Неплохой фактор ускорения для 2-х линейных изменений! Однако обратите внимание, что массовое ускорение полностью связано с компилятором, как только исключается возможность полиморфизма времени выполнения в функции work, просто оптимизируя цикл и компилируя результат непосредственно в код. Но это на самом деле делает важный момент: по моему опыту основные выгоды от использования такого рода трюк исходят из возможностей для улучшения вложения и оптимизации, которые они позволяют компилятору, когда генерируется менее полиморфная, более конкретная функция, а не простое удаление vtable indirection (что действительно очень дешево).

Но я действительно не рекомендую делать подобные вещи, если профилирование не означает, что полиморфизм во время выполнения действительно поражает вашу производительность. Он также укусит вас, как только кто-то подклассы Foo или Bar, и попытается передать это в функцию, фактически предназначенную для его базы.

Возможно, вы найдете этот связанный вопрос.