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

Question

Скажем, у меня есть вызов виртуальной функции foo () для абстрактного указателя базового класса, mypointer-> foo (). Когда мое приложение запускается, основываясь на содержимом файла, оно решает создать экземпляр конкретного конкретного класса и назначает mypointer этому экземпляру. На протяжении всей жизни приложения mypointer будет всегда указывать на объекты этого конкретного типа. У меня нет способа узнать, что это за конкретный тип (он может быть создан на фабрике в динамически загружаемой библиотеке). Я только знаю, что тип останется прежним после первого создания экземпляра конкретного типа. Указатель не всегда может указывать на один и тот же объект, но объект всегда будет иметь один и тот же конкретный тип. Обратите внимание, что тип технически определяется во время выполнения, поскольку он основан на содержимом файла, но после запуска (файл загружается) тип фиксируется.

Однако в C ++ я плачу за поиск виртуальных функций каждый раз, когда вызывается foo в течение всего времени работы приложения. Компилятор не может оптимизировать внешний вид, потому что у него нет возможности узнать, что конкретный тип не изменится во время выполнения (даже если это был самый удивительный компилятор за всю историю, он не может спекулировать на поведении динамически загружаемого библиотеки). В JIT-скомпилированном языке, таком как Java или .NET, JIT может обнаружить, что один и тот же тип используется снова и снова, и выполнить встроенное кэширование . Я в основном ищу способ сделать это вручную для конкретных указателей в C ++.

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

Обновление: для скептиков: если бы это не стоило оптимизировать, то я сомневаюсь, что современные JIT-ы это сделают. Как вы думаете, инженеры Sun и MS тратили свое время на внедрение встроенного кэширования и не тестировали его для обеспечения улучшения?

Answer 1

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

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

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

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

Answer 2

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

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

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

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

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

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

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

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

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

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

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

Answer 3

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

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

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

Answer 4

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

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

Answer 5

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

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

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

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

Answer 7

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

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

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.

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

Answer 8

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

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

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

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

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

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

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

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

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

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

Answer 9

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

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

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

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