Вообще стоит ли использовать виртуальные функции, чтобы избежать ветвления?

21

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

  • инструкция против пропуска кэша данных
  • барьер оптимизации

Если вы посмотрите на что-то вроде:

if (x==1) {
   p->do1();
}
else if (x==2) {
   p->do2();
}
else if (x==3) {
   p->do3();
}
...

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

p->do()

Но, в общем, насколько дороги виртуальные функции по сравнению с ветвлением Трудно протестировать на достаточном количестве платформ для обобщения, поэтому мне было интересно, есть ли у кого-нибудь грубое эмпирическое правило (прекрасно, если бы это было так просто, как 4 ifс - точка останова)

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

Гленн Тейтельбаум
источник
12
Ну, а каковы ваши требования к производительности? У вас есть точные цифры, по которым вам нужно попасть, или вы занимаетесь преждевременной оптимизацией? И ветвление, и виртуальные методы чрезвычайно дешевы в общей схеме вещей (например, по сравнению с плохими алгоритмами, вводом-выводом или распределением кучи).
Амон
4
Делайте все , что более читаемым / гибкий / маловероятно , чтобы на пути будущих изменений, и как только вы это работает , то делать профилирование и посмотреть , если это на самом деле имеет значение. Обычно это не так.
Ixrec
1
Вопрос: «Но, в общем, насколько дороги виртуальные функции ...» Ответ: Косвенная ветвь (википедия)
rwong
1
Помните, что большинство ответов основаны на подсчете количества инструкций. Как низкоуровневый оптимизатор кода, я не доверяю количеству инструкций; Вы должны доказать их на конкретной архитектуре процессора - физически - в условиях эксперимента. Действительные ответы на этот вопрос должны быть эмпирическими и экспериментальными, а не теоретическими.
Руон
3
Проблема с этим вопросом в том, что он предполагает, что он достаточно большой, чтобы о нем беспокоиться. В реальном программном обеспечении проблемы с производительностью возникают большими частями, как кусочки пиццы разных размеров. Например, посмотрите здесь . Не думайте, что вы знаете, в чем заключается самая большая проблема - пусть программа скажет вам. Исправьте это, а затем позвольте ему сказать вам, что следующий. Сделайте это полдюжины раз, и вы можете оказаться там, где стоит беспокоиться о вызовах виртуальных функций. Они никогда не имеют, по моему опыту.
Майк Данлавей

Ответы:

21

Я хотел бы воспользоваться этими и без того превосходными ответами и признать, что я выбрал уродливый подход, работающий в обратном направлении с анти-паттерном изменения полиморфного кода switchesили if/elseпереходов с измеряемой прибылью. Но я не делал это оптом, только для самых критических путей. Это не должно быть так черно-белым.

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

Полиморфная Рефакторинг Условных Условий

Во-первых, стоит понять, почему полиморфизм может быть предпочтительнее с точки switchзрения if/elseудобства сопровождения, чем условное ветвление ( или куча утверждений). Основным преимуществом здесь является расширяемость .

С помощью полиморфного кода мы можем ввести новый подтип в нашу кодовую базу, добавить его экземпляры в некоторую полиморфную структуру данных и сделать так, чтобы весь существующий полиморфный код по-прежнему работал автоматически без каких-либо изменений. Если у вас есть куча кода, разбросанного по большой кодовой базе, которая напоминает форму «Если этот тип -« foo », сделайте это» , вы можете столкнуться с ужасным бременем обновления 50 разрозненных разделов кода, чтобы представить новый тип вещей, и все же в конечном итоге не хватает нескольких.

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

Барьер оптимизации

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

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

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

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

Оптимизация памяти

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

vector<Creature*> creatures;

Примечание: для простоты я избежал unique_ptrздесь.

... где Creatureполиморфный базовый тип. В этом случае одна из трудностей с полиморфными контейнерами заключается в том, что они часто хотят выделить память для каждого подтипа отдельно / индивидуально (например: использование броска operator newпо умолчанию для каждого отдельного существа).

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

Частичная девиртуализация структур данных и циклов

Допустим, вы прошли через все эти движения и все еще желаете большей скорости. Стоит отметить, что каждый шаг, который мы предпринимаем здесь, ухудшает ремонтопригодность, и мы уже находимся на некоторой стадии измельчения металла с уменьшением производительности. Таким образом, если мы вступим на эту территорию, то должны быть довольно значительные требования к производительности, где мы готовы пожертвовать обслуживаемостью еще больше для все меньшего и меньшего прироста производительности.

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

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

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

vector<Human> humans;               // common case
vector<Creature*> other_creatures;  // additional rare-case creatures

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

vector<Human> humans;               // common case
vector<Creature*> other_creatures;  // additional rare-case creatures
vector<Creature*> creatures;        // contains humans and other creatures

... если мы можем себе это позволить, менее критические пути могут остаться такими, как есть, и просто абстрактно обрабатывать все типы существ. Критические пути могут обрабатываться humansв одном цикле и other_creaturesво втором цикле.

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

Частичная девиртуализация классов

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

switch (obj->type())
{
   case id_common_type:
       static_cast<CommonType*>(obj)->non_virtual_do_something();
       break;
   ...
   default:
       obj->virtual_do_something();
       break;
}

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

Оптовая Девиртуализация

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

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

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

Я бы вообще не рекомендовал это даже с очень критичным к производительности мышлением, если это не достаточно просто для поддержания. «Простота обслуживания» будет зависеть от двух доминирующих факторов:

  • Отсутствие реальной потребности в расширяемости (например: точно знать, что вам нужно обрабатывать ровно 8 типов вещей, и никогда больше).
  • В вашем коде не так много мест, где нужно проверять эти типы (например, одно центральное место).

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

Виртуальные функции и указатели на функции

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

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

Если мы сравниваем a classс 20 виртуальными функциями против a, в structкотором хранится 20 указателей на функции, и оба экземпляра создаются несколько раз, то объем памяти каждого classэкземпляра в этом случае составляет 8 байт для виртуального указателя на 64-разрядных машинах, тогда как объем памяти накладные расходы structсоставляют 160 байтов.

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

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

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

class Functionoid
{
public:
    virtual ~Functionoid() {}
    virtual void operator()() = 0;
};

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

void (*func_ptr)(void* instance_data);

... идеально за типобезопасным интерфейсом, чтобы скрывать опасные броски в / из void*.

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

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

Вывод

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

marstato
источник
Виртуальные функции - это указатели на функции, просто реализованные в жизнеспособном классе. Когда вызывается виртуальная функция, она сначала просматривается в дочернем элементе и вверх по цепочке наследования. Вот почему глубокое наследование очень дорого и его обычно избегают в c ++.
Роберт Барон
@RobertBaron: я никогда не видел, чтобы виртуальные функции были реализованы, как вы сказали (= с помощью цепочки поиска по иерархии классов). Обычно компиляторы просто генерируют «сплющенную» vtable для каждого конкретного типа со всеми правильными указателями на функции, и во время выполнения вызов разрешается с помощью одного прямого поиска в таблице; штраф за глубокое наследование не взимается.
Matteo Italia
Маттео, это было объяснение, которое технический руководитель дал мне много лет назад. Конечно, это было для c ++, поэтому он, возможно, принимал во внимание последствия множественного наследования. Спасибо за разъяснение моего понимания того, как оптимизируются vtables.
Роберт Барон
Спасибо за хороший ответ (+1). Интересно, насколько это применимо к std :: visit вместо виртуальных функций?
DaveFar
13

Замечания:

  • Во многих случаях виртуальные функции работают быстрее, потому что поиск в vtable является O(1)операцией, а else if()лестница - O(n)операцией. Однако это верно только в том случае, если распределение случаев является плоским.

  • Для одного if() ... elseусловное условие быстрее, потому что вы сохраняете накладные расходы на вызов функции.

  • Таким образом, при равномерном распределении случаев должна существовать точка безубыточности. Вопрос только в том, где он находится.

  • Если вы используете switch()вместо else if()лестничных или виртуальных вызовов функций, ваш компилятор может создать еще лучший код: он может выполнить ветвление в местоположение, которое ищется из таблицы, но не является вызовом функции. То есть у вас есть все свойства вызова виртуальной функции без дополнительных затрат на вызов функции.

  • Если один из них является более частым, чем остальные, запуск if() ... elseс этим случаем даст вам наилучшую производительность: вы выполните одну условную ветвь, которая в большинстве случаев правильно спрогнозирована.

  • Ваш компилятор не знает об ожидаемом распределении падежей и будет предполагать плоское распределение.

Поскольку ваш компилятор, вероятно, имеет некоторые хорошие эвристики в отношении того, когда кодировать switch()как else if()лестницу или как поиск по таблице. Я склонен доверять его суждению, если вы не знаете, что распределение дел является предвзятым.

Итак, мой совет:

  • Если один из случаев затмевает остальные с точки зрения частоты, используйте отсортированную else if()лестницу.

  • В противном случае используйте switch()оператор, если только один из других методов не сделает ваш код более читабельным. Будьте уверены, что вы не купите незначительный прирост производительности со значительно сниженной читабельностью.

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

cmaster - восстановить монику
источник
2
Некоторые компиляторы позволяют аннотациям сообщать компилятору, какой случай более вероятен, и эти компиляторы могут создавать более быстрый код, если аннотация верна.
gnasher729
5
операция O (1) не обязательно быстрее в реальном времени выполнения, чем операция O (n) или даже O (n ^ 20).
whatsisname
2
@whatsisname Вот почему я сказал "для многих случаев". По определению O(1)и O(n)существует kтак, что O(n)функция больше, чем O(1)функция для всех n >= k. Вопрос только в том, есть ли у вас такое количество случаев. И да, я видел switch()заявления с таким количеством случаев, когда else if()лестница определенно медленнее, чем вызов виртуальной функции или загруженная диспетчеризация.
cmaster - восстановить монику
Проблема, с которой я сталкиваюсь в этом ответе, - это единственное предупреждение против принятия решения, основанного на совершенно несущественном выигрыше в производительности, которое скрыто где-то в следующем абзаце. Все остальное здесь делает вид, что может быть хорошей идеей принять решение о том, ifпротив switchили против виртуальных функций, основываясь на производительности. В очень редких случаях это может быть, но в большинстве случаев это не так.
Док Браун
7

Вообще стоит ли использовать виртуальные функции, чтобы избежать ветвления?

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

Но, в общем, насколько дороги виртуальные функции по сравнению с ветвлением Трудно протестировать на достаточном количестве платформ для обобщения, поэтому мне было интересно, если бы у кого-то было грубое эмпирическое правило (прекрасно, если бы это было так просто, как 4, если точка останова)

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

То есть правильный ответ на вопрос «насколько дороги виртуальные функции по сравнению с ветвлением» - это измерение и выяснение.

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

Вы говорите, что хотите, чтобы этот раздел работал максимально быстро; Как быстро это? Каковы ваши конкретные требования?

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

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

utnapistim
источник
Проделав большую часть технического обслуживания, я собираюсь вмешаться с некоторой осторожностью: виртуальные функции IMNSHO довольно плохи в обслуживании, именно из-за перечисленных вами преимуществ. Основная проблема заключается в их гибкости; Вы можете засунуть туда что угодно ... и люди это сделают. Статически рассуждать о динамической рассылке очень сложно. Однако в большинстве конкретных случаев код не нуждается в такой гибкости, а устранение гибкости во время выполнения может облегчить анализ кода. Однако я не хочу заходить так далеко, чтобы сказать, что вы никогда не должны использовать динамическую диспетчеризацию; это абсурд
Имон Нербонн
Самыми хорошими абстракциями для работы являются те, которые редки (т. Е. Кодовая база имеет только несколько непрозрачных абстракций), но все же супер-устойчива. По сути: не привязывайте что-либо к абстракции динамической диспетчеризации только потому, что она имеет подобную форму для одного конкретного случая; только сделать это , если вы не можете разумно представить любую причину для постоянно заботиться о каких - либо различиях между объектами совместных этим интерфейсом. Если вы не можете: лучше иметь не инкапсулирующий помощник, чем некачественную абстракцию. И даже тогда; есть компромисс между гибкостью времени выполнения и гибкостью кодовой базы.
Имон Нербонн
5

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

Я написал скрипт Python для случайной генерации кода C ++ 14 для виртуальной машины с размером набора команд, выбранным случайным образом (хотя и неравномерно, с более плотной выборкой нижнего диапазона) между 1 и 10000. Созданная виртуальная машина всегда имела 128 регистров и не ОЗУ. Инструкции не имеют смысла и все имеют следующую форму.

inline void
op0004(machine_state& state) noexcept
{
  const auto c = word_t {0xcf2802e8d0baca1dUL};
  const auto r1 = state.registers[58];
  const auto r2 = state.registers[69];
  const auto r3 = ((r1 + c) | r2);
  state.registers[6] = r3;
}

Сценарий также генерирует процедуры отправки, используя switchоператор…

inline int
dispatch(machine_state& state, const opcode_t opcode) noexcept
{
  switch (opcode)
  {
  case 0x0000: op0000(state); return 0;
  case 0x0001: op0001(state); return 0;
  // ...
  case 0x247a: op247a(state); return 0;
  case 0x247b: op247b(state); return 0;
  default:
    return -1;  // invalid opcode
  }
}

... и массив указателей на функции.

inline int
dispatch(machine_state& state, const opcode_t opcode) noexcept
{
  typedef void (* func_type)(machine_state&);
  static const func_type table[VM_NUM_INSTRUCTIONS] = {
    op0000,
    op0001,
    // ...
    op247a,
    op247b,
  };
  if (opcode >= VM_NUM_INSTRUCTIONS)
    return -1;  // invalid opcode
  table[opcode](state);
  return 0;
}

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

Для бенчмаркинга поток кодов операций был сгенерирован случайным образом отобранным ( std::random_device) случайным механизмом Mersenne twister ( std::mt19937_64).

Код для каждой виртуальной машины был скомпилирован с GCC 5.2.0 с помощью -DNDEBUG, -O3и -std=c++14переключатели. Сначала он был скомпилирован с использованием -fprofile-generateопций и данных профиля, собранных для имитации 1000 случайных инструкций. Затем код был перекомпилирован с -fprofile-useопцией, позволяющей оптимизировать на основе собранных данных профиля.

Затем ВМ выполнялась (в том же процессе) четыре раза для 50 000 000 циклов и измерялось время для каждого цикла. Первый запуск был отменен, чтобы устранить эффекты холодного кэша. PRNG не был повторно посеян между прогонами, чтобы они не выполняли ту же последовательность инструкций.

Используя эту настройку, было собрано 1000 точек данных для каждой процедуры диспетчеризации. Данные собирались на четырехъядерном APU AMD A8-6600K с 2048 КБ кеш-памяти под управлением 64-битной GNU / Linux без графического рабочего стола или других запущенных программ. Ниже показан график среднего времени ЦП (со стандартным отклонением) на инструкцию для каждой виртуальной машины.

введите описание изображения здесь

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

Весь исходный код для теста, а также полные экспериментальные данные и график высокого разрешения можно найти на моем сайте .

5gon12eder
источник
3

В дополнение к хорошему ответу cmaster, за который я проголосовал, следует помнить, что указатели на функции обычно строго быстрее, чем на виртуальные. Диспетчеризация виртуальных функций обычно включает в себя сначала следование за указателем от объекта к виртуальной таблице, надлежащую индексацию, а затем разыменование указателя на функцию. Итак, последний шаг такой же, но изначально есть дополнительные шаги. Кроме того, виртуальные функции всегда принимают «this» в качестве аргумента, указатели на функции более гибкие.

Следует помнить еще одну вещь: если ваш критический путь включает в себя цикл, может быть полезно отсортировать цикл по назначению отправки. Очевидно, что это nlogn, тогда как обход цикла - только n, но если вы собираетесь проходить много раз, это может стоить того. Сортируя по назначению отправки, вы гарантируете, что один и тот же код выполняется многократно, сохраняя его горячим в icache, сводя к минимуму потери кэша.

Следует помнить о третьей стратегии: если вы решите отойти от виртуальных функций / указателей функций к стратегиям if / switch, вам также может быть полезен переход с полиморфных объектов на что-то вроде boost :: variable (которое также обеспечивает переключение). случай в виде абстракции посетителя). Полиморфные объекты должны храниться по базовому указателю, поэтому ваши данные повсюду в кеше. Это может легко оказать большее влияние на ваш критический путь, чем стоимость виртуального поиска. Принимая во внимание, что вариант хранится в строке как дискриминационный союз; он имеет размер, равный наибольшему типу данных (плюс небольшая константа). Если ваши объекты не сильно различаются по размеру, это отличный способ справиться с ними.

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

Нир Фридман
источник
Я не знаю, что виртуальная функция включает в себя «дополнительные шаги», хотя. Учитывая, что макет класса известен во время компиляции, он по сути такой же, как и доступ к массиву. Т.е. есть указатель на вершину класса, и смещение функции известно, поэтому просто добавьте это, прочитайте результат, и это адрес. Не много накладных расходов.
1
Это включает в себя дополнительные шаги. Сам vtable содержит указатели на функции, поэтому, когда вы переходите в vtable, вы достигаете того же состояния, в котором вы начали с указателем на функцию. Все, прежде чем попасть в vtable, это дополнительная работа. Классы не содержат своих vtables, они содержат указатели на vtables, и последующий указатель является дополнительной разыменовкой. На самом деле, иногда существует третья разыменование, поскольку полиморфные классы обычно хранятся указателем базового класса, поэтому вам нужно разыменовать указатель, чтобы получить адрес vtable (чтобы разыменовать его ;-)).
Нир Фридман
С другой стороны, тот факт, что vtable хранится вне экземпляра, на самом деле может быть полезен для временной локализации по сравнению, скажем, с набором разрозненных структур указателей на функции, где каждый и каждый указатель на функцию хранится в отдельном адресе памяти. В таких случаях один vtable с миллионом vptr может легко превзойти миллион таблиц указателей функций (начиная только с потребления памяти). Здесь может быть что-то вроде путаницы - не так легко сломаться. Как правило, я согласен, что указатель на функцию часто немного дешевле, но не так просто поставить один над другим.
Я думаю, иными словами, когда виртуальные функции начинают быстро и значительно превосходить указатели на функции, это когда у вас есть куча задействованных экземпляров объектов (где каждый объект должен хранить либо несколько указателей на функции, либо один vptr). Указатели на функции, как правило, обходятся дешевле, если, скажем, в памяти хранится только один указатель на функцию, который будет называться целой кучей раз. В противном случае указатели на функции могут начать работать медленнее из-за избыточности данных и ошибок кэширования, которые возникают из-за избыточной загрузки памяти и обращения к одному и тому же адресу.
Конечно, с помощью указателей функций вы также можете хранить их в центральном месте, даже если они совместно используются миллионами отдельных объектов, чтобы избежать перегрузки памяти и получения большого количества пропусков кэша. Но затем они начинают становиться эквивалентными vpointers, включая доступ указателя к общему расположению в памяти, чтобы получить фактические адреса функций, которые мы хотим вызвать. Фундаментальный вопрос здесь: храните ли вы адрес функции ближе к данным, к которым вы сейчас обращаетесь, или в центральном месте? vtables позволяет только последнее. Указатели на функции позволяют использовать оба способа.
2

Могу я просто объяснить, почему я считаю, что это проблема XY ? (Вы не одиноки, спрашивая их.)

Я предполагаю, что ваша настоящая цель - сэкономить время в целом, а не просто понять, что происходит с отсутствием кэша и виртуальными функциями.

Вот пример реальной настройки производительности в реальном программном обеспечении.

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

В примере, на который я ссылался, первоначально на «работу» уходило 2700 микросекунд. Серия из шести проблем была решена, обходя пиццу против часовой стрелки. Первое ускорение снимается в 33% случаев. Второй удалил 11%. Но обратите внимание, второй был не 11% в то время, когда он был найден, это было 16%, потому что первая проблема исчезла . Точно так же, третья проблема была увеличена с 7,4% до 13% (почти вдвое), потому что первые две проблемы исчезли.

В конце этот процесс увеличения позволил исключить все, кроме 3,7 микросекунд. Это 0,14% от исходного времени или ускорение в 730 раз.

введите описание изображения здесь

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

введите описание изображения здесь

Была ли окончательная программа оптимальной? Возможно нет. Ни одно из ускорений не имело ничего общего с промахами кэша. Будет ли промах кеша иметь значение сейчас? Может быть.

РЕДАКТИРОВАТЬ: Я получаю отрицательные отзывы от людей, навязывающихся на «очень критических разделах» вопроса ОП. Вы не знаете, что что-то «крайне критично», пока не узнаете, на какую долю времени это приходится. Если средняя стоимость вызываемых методов составляет 10 или более циклов, то со временем метод отправки к ним, вероятно, не является «критическим» по сравнению с тем, что они фактически делают. Я вижу это снова и снова, когда люди воспринимают «нужную каждую наносекунду» как причину быть копеечным и глупым.

Майк Данлавей
источник
он уже сказал, что у него есть несколько «критических секций», которые требуют каждую последнюю наносекунду производительности. Так что это не ответ на вопрос, который он задал (даже если это был бы отличный ответ на чей-либо вопрос)
gbjbaanb
2
@gbjbaanb: Если каждая последняя наносекунда имеет значение, почему вопрос начинается с "в целом"? Это чепуха. Когда подсчитывают наносекунды, вы не можете искать общие ответы, вы смотрите на то, что делает компилятор, вы смотрите на то, что делает аппаратное обеспечение, вы пробуете вариации и измеряете каждую вариацию.
gnasher729
@ gnasher729 Не знаю, но почему это заканчивается «критическими разделами»? Я думаю, как и слэшдот, всегда нужно читать контент, а не только заголовок!
gbjbaanb
2
@gbjbaanb: Все говорят, что у них есть "очень критические секции". Откуда они знают? Я не знаю, что-то критичное, пока я не возьму, скажем, 10 образцов и увижу это на двух или более из них. В таком случае, если вызываемые методы принимают более 10 инструкций, издержки виртуальной функции, вероятно, незначительны.
Майк Данлавей
@ gnasher729: Ну, первое, что я делаю, это получаю образцы стеков, и на каждом из них изучаю, что делает программа и почему. Затем, если он проводит все свое время в листьях дерева вызовов, и все вызовы действительно неизбежны , имеет ли значение то, что делают компилятор и аппаратное обеспечение. Вы знаете только, что отправка метода имеет значение, если образцы попадают в процесс отправки метода.
Майк Данлавей