Кажется, что есть грубые эквиваленты инструкций, чтобы приравнять к стоимости пропущенных веток виртуальные функции имеют аналогичный компромисс:
- инструкция против пропуска кэша данных
- барьер оптимизации
Если вы посмотрите на что-то вроде:
if (x==1) {
p->do1();
}
else if (x==2) {
p->do2();
}
else if (x==3) {
p->do3();
}
...
У вас может быть массив функций-членов, или если многие функции зависят от одной и той же категоризации или существует более сложная категоризация, используйте виртуальные функции:
p->do()
Но, в общем, насколько дороги виртуальные функции по сравнению с ветвлением Трудно протестировать на достаточном количестве платформ для обобщения, поэтому мне было интересно, есть ли у кого-нибудь грубое эмпирическое правило (прекрасно, если бы это было так просто, как 4 if
с - точка останова)
В целом, виртуальные функции более понятны, и я склоняюсь к ним. Но у меня есть несколько критически важных разделов, в которых я могу изменить код с виртуальных функций на ветви. Я бы предпочел подумать об этом, прежде чем предпринять это. (это не тривиальное изменение или тестирование на нескольких платформах)
источник
Ответы:
Я хотел бы воспользоваться этими и без того превосходными ответами и признать, что я выбрал уродливый подход, работающий в обратном направлении с анти-паттерном изменения полиморфного кода
switches
илиif/else
переходов с измеряемой прибылью. Но я не делал это оптом, только для самых критических путей. Это не должно быть так черно-белым.Полиморфная Рефакторинг Условных Условий
Во-первых, стоит понять, почему полиморфизм может быть предпочтительнее с точки
switch
зренияif/else
удобства сопровождения, чем условное ветвление ( или куча утверждений). Основным преимуществом здесь является расширяемость .С помощью полиморфного кода мы можем ввести новый подтип в нашу кодовую базу, добавить его экземпляры в некоторую полиморфную структуру данных и сделать так, чтобы весь существующий полиморфный код по-прежнему работал автоматически без каких-либо изменений. Если у вас есть куча кода, разбросанного по большой кодовой базе, которая напоминает форму «Если этот тип -« foo », сделайте это» , вы можете столкнуться с ужасным бременем обновления 50 разрозненных разделов кода, чтобы представить новый тип вещей, и все же в конечном итоге не хватает нескольких.
Преимущества удобства сопровождения полиморфизма здесь естественным образом уменьшаются, если у вас есть только пара или даже один раздел вашей кодовой базы, который должен выполнять такие проверки типов.
Барьер оптимизации
Я бы посоветовал не смотреть на это с точки зрения разветвления и конвейеризации, а взглянуть на это больше с точки зрения проектирования компиляторов барьеров оптимизации. Существуют способы улучшить прогнозирование ветвлений, применимые к обоим случаям, например, сортировка данных на основе подтипа (если он входит в последовательность).
Что отличается между этими двумя стратегиями, так это количество информации, которое оптимизатор имеет заранее. Известный вызов функции предоставляет намного больше информации, косвенный вызов функции, который вызывает неизвестную функцию во время компиляции, приводит к барьеру оптимизации.
Когда вызываемая функция известна, компиляторы могут стереть структуру и сжать ее до дребезга, вставляя вызовы, устраняя потенциальные накладные расходы на псевдонимы, выполняя лучшую работу при распределении команд / регистров, возможно даже переставляя циклы и другие формы ветвей, генерируя сложные миниатюрные LUT, когда это уместно (что-то, что GCC 5.3 недавно удивило меня
switch
заявлением, используя жестко закодированные LUT данных для результатов, а не таблицу переходов).Некоторые из этих преимуществ теряются, когда мы начинаем вводить в микс неизвестные во время компиляции, как в случае косвенного вызова функции, и именно здесь условное ветвление может, скорее всего, дать преимущество.
Оптимизация памяти
Возьмите пример видеоигры, которая состоит в повторной обработке последовательности существ в тесном цикле. В таком случае у нас может быть какой-нибудь полиморфный контейнер, подобный этому:
Примечание: для простоты я избежал
unique_ptr
здесь.... где
Creature
полиморфный базовый тип. В этом случае одна из трудностей с полиморфными контейнерами заключается в том, что они часто хотят выделить память для каждого подтипа отдельно / индивидуально (например: использование броскаoperator new
по умолчанию для каждого отдельного существа).Это часто делает первую расстановку приоритетов для оптимизации (если она нам нужна) на основе памяти, а не ветвления. Одна стратегия здесь состоит в том, чтобы использовать фиксированный распределитель для каждого подтипа, поощряя непрерывное представление, выделяя большими порциями и объединяя память для каждого выделяемого подтипа. При такой стратегии это может определенно помочь отсортировать этот
creatures
контейнер по подтипу (а также по адресу), поскольку это не только возможно улучшает прогнозирование ветвления, но также улучшает местность ссылок (позволяя получить доступ к нескольким существам одного и того же подтипа из одной строки кэша до выселения).Частичная девиртуализация структур данных и циклов
Допустим, вы прошли через все эти движения и все еще желаете большей скорости. Стоит отметить, что каждый шаг, который мы предпринимаем здесь, ухудшает ремонтопригодность, и мы уже находимся на некоторой стадии измельчения металла с уменьшением производительности. Таким образом, если мы вступим на эту территорию, то должны быть довольно значительные требования к производительности, где мы готовы пожертвовать обслуживаемостью еще больше для все меньшего и меньшего прироста производительности.
Тем не менее, следующий шаг, который нужно попробовать (и всегда с готовностью поддержать наши изменения, если это не поможет вообще), может быть ручной девиртуализацией.
Тем не менее, мы не должны применять это мышление оптом. Продолжая наш пример, допустим, что эта видеоигра в основном состоит из людей. В таком случае мы можем девиртуализировать только человеческие существа, подняв их и создав отдельную структуру данных только для них.
Это подразумевает, что все области в нашей кодовой базе, которые должны обрабатывать существ, нуждаются в отдельном цикле особого случая для человеческих существ. Тем не менее, это устраняет динамические накладные расходы (или, возможно, более уместно, барьер оптимизации) для людей, которые, безусловно, являются наиболее распространенным типом существ. Если этих областей много, и мы можем себе это позволить, мы можем сделать это:
... если мы можем себе это позволить, менее критические пути могут остаться такими, как есть, и просто абстрактно обрабатывать все типы существ. Критические пути могут обрабатываться
humans
в одном цикле иother_creatures
во втором цикле.Мы можем расширить эту стратегию по мере необходимости и потенциально выжать некоторые выгоды таким образом, однако стоит отметить, насколько мы ухудшаем ремонтопригодность в процессе. Использование здесь шаблонов функций может помочь сгенерировать код для людей и существ без дублирования логики вручную.
Частичная девиртуализация классов
То, что я делал много лет назад, и которое было действительно грубым, и я даже не уверен, что это больше полезно (это было в эпоху C ++ 03), было частичной девиртуализацией класса. В этом случае мы уже хранили идентификатор класса с каждым экземпляром для других целей (доступ к которому осуществлялся через базовый класс, который не был виртуальным). Там мы сделали что-то похожее на это (моя память немного туманна):
... где
virtual_do_something
был реализован вызов не виртуальных версий в подклассе. Я знаю, что это грубо - делать явное статическое снижение, чтобы девиртуализировать вызов функции. Я понятия не имею, насколько это выгодно сейчас, так как я не пробовал подобные вещи годами. Благодаря использованию ориентированного на данные дизайна я обнаружил, что вышеупомянутая стратегия разделения структур данных и циклов в горячем / холодном режиме гораздо более полезна, открывая больше дверей для стратегий оптимизации (и гораздо менее уродливых).Оптовая Девиртуализация
Я должен признать, что я никогда не заходил так далеко, применяя мышление оптимизации, поэтому я понятия не имею о преимуществах. Я избегал косвенных функций в предвидении в тех случаях, когда я знал, что будет только один центральный набор условий (например, обработка событий только с одним событием обработки в центральном месте), но никогда не начинал с полиморфного мышления и оптимизировал полностью до здесь.
Теоретически, непосредственными преимуществами здесь может быть потенциально меньший способ идентификации типа, чем виртуального указателя (например, один байт, если вы можете согласиться с идеей, что существует 256 уникальных типов или меньше) в дополнение к полному устранению этих барьеров оптимизации ,
В некоторых случаях может также помочь написать более простой в обслуживании код (по сравнению с приведенными выше примерами оптимизированной ручной девиртуализации), если вы просто используете один центральный
switch
оператор, не разбивая структуры данных и циклы на основе подтипа, или если есть порядок -зависимость в тех случаях, когда вещи должны быть обработаны в точном порядке (даже если это заставляет нас разветвляться повсюду). Это может быть в тех случаях, когда у вас не так много мест, которые нужно сделатьswitch
.Я бы вообще не рекомендовал это даже с очень критичным к производительности мышлением, если это не достаточно просто для поддержания. «Простота обслуживания» будет зависеть от двух доминирующих факторов:
... все же я рекомендую описанный выше сценарий в большинстве случаев и, при необходимости, перебираю более эффективные решения путем частичной девиртуализации. Это дает вам гораздо больше передышки, чтобы сбалансировать потребности в расширяемости и обслуживании с производительностью.
Виртуальные функции и указатели на функции
Чтобы завершить это, я заметил здесь, что было некоторое обсуждение виртуальных функций и указателей на функции. Это правда, что для вызова виртуальных функций требуется немного больше работы, но это не значит, что они работают медленнее. Против интуитивно, это может даже сделать их быстрее.
Здесь это противоречит интуиции, потому что мы привыкли измерять затраты с точки зрения инструкций, не обращая внимания на динамику иерархии памяти, которая, как правило, оказывает гораздо более существенное влияние.
Если мы сравниваем a
class
с 20 виртуальными функциями против a, вstruct
котором хранится 20 указателей на функции, и оба экземпляра создаются несколько раз, то объем памяти каждогоclass
экземпляра в этом случае составляет 8 байт для виртуального указателя на 64-разрядных машинах, тогда как объем памяти накладные расходыstruct
составляют 160 байтов.Практические затраты могут быть намного больше обязательных и необязательных пропусков кэша с таблицей указателей функций по сравнению с классом, использующим виртуальные функции (и, возможно, сбои страниц при достаточно большом масштабе ввода). Эта стоимость имеет тенденцию затмевать немного дополнительную работу по индексированию виртуальной таблицы.
Я также имел дело с унаследованными кодовыми базами C (более старыми, чем я), в которых превращение таких,
structs
заполненных указателями функций, и создание их много раз фактически дало значительный прирост производительности (более 100% улучшений), превращая их в классы с виртуальными функциями, и из-за значительного сокращения использования памяти, увеличения кеш-памяти и т. д.С другой стороны, когда сравнения между яблоками и яблоками становятся больше, я также обнаружил, что противоположный способ перевода мышления с виртуальной функции C ++ на мышление с указателем на функцию в стиле C полезен в следующих типах сценариев:
... где класс хранил одну жалкую переопределяемую функцию (или две, если считать виртуальный деструктор). В этих случаях это может определенно помочь в критических путях превратить это в это:
... идеально за типобезопасным интерфейсом, чтобы скрывать опасные броски в / из
void*
.В тех случаях, когда у нас возникает искушение использовать класс с одной виртуальной функцией, это может быстро помочь вместо использования указателей на функции. Большая причина даже не обязательно заключается в снижении затрат на вызов указателя функции. Это потому, что мы больше не сталкиваемся с искушением распределить каждый отдельный функционоид по разрозненным областям кучи, если мы объединяем их в постоянную структуру. Такой подход может упростить предотвращение связанных с кучей и фрагментацию памяти, если данные экземпляра однородны, например, и меняется только поведение.
Так что определенно есть случаи, когда использование указателей функций может помочь, но часто я нахожу это наоборот, если мы сравниваем несколько таблиц указателей функций с одной виртуальной таблицей, для которой требуется только один указатель для каждого экземпляра класса. , Эта таблица часто будет находиться в одной или нескольких строках кэша L1, а также в узких циклах.
Вывод
Так или иначе, это мое маленькое вращение на эту тему. Я рекомендую рисковать в этих областях с осторожностью. Измерения доверия, а не инстинкт, и с учетом того, как эти оптимизации часто ухудшают удобство обслуживания, заходят настолько далеко, насколько вы можете себе позволить (и разумным путем было бы ошибиться на стороне обслуживания).
источник
Замечания:
Во многих случаях виртуальные функции работают быстрее, потому что поиск в vtable является
O(1)
операцией, аelse if()
лестница -O(n)
операцией. Однако это верно только в том случае, если распределение случаев является плоским.Для одного
if() ... else
условное условие быстрее, потому что вы сохраняете накладные расходы на вызов функции.Таким образом, при равномерном распределении случаев должна существовать точка безубыточности. Вопрос только в том, где он находится.
Если вы используете
switch()
вместоelse if()
лестничных или виртуальных вызовов функций, ваш компилятор может создать еще лучший код: он может выполнить ветвление в местоположение, которое ищется из таблицы, но не является вызовом функции. То есть у вас есть все свойства вызова виртуальной функции без дополнительных затрат на вызов функции.Если один из них является более частым, чем остальные, запуск
if() ... else
с этим случаем даст вам наилучшую производительность: вы выполните одну условную ветвь, которая в большинстве случаев правильно спрогнозирована.Ваш компилятор не знает об ожидаемом распределении падежей и будет предполагать плоское распределение.
Поскольку ваш компилятор, вероятно, имеет некоторые хорошие эвристики в отношении того, когда кодировать
switch()
какelse if()
лестницу или как поиск по таблице. Я склонен доверять его суждению, если вы не знаете, что распределение дел является предвзятым.Итак, мой совет:
Если один из случаев затмевает остальные с точки зрения частоты, используйте отсортированную
else if()
лестницу.В противном случае используйте
switch()
оператор, если только один из других методов не сделает ваш код более читабельным. Будьте уверены, что вы не купите незначительный прирост производительности со значительно сниженной читабельностью.Если вы использовали
switch()
и все еще не удовлетворены производительностью, проведите сравнение, но будьте готовы выяснить, что этоswitch()
была уже самая быстрая возможность.источник
O(1)
иO(n)
существуетk
так, чтоO(n)
функция больше, чемO(1)
функция для всехn >= k
. Вопрос только в том, есть ли у вас такое количество случаев. И да, я виделswitch()
заявления с таким количеством случаев, когдаelse if()
лестница определенно медленнее, чем вызов виртуальной функции или загруженная диспетчеризация.if
противswitch
или против виртуальных функций, основываясь на производительности. В очень редких случаях это может быть, но в большинстве случаев это не так.В общем да. Преимущества для технического обслуживания значительны (тестирование по отдельности, разделение задач, улучшенная модульность и расширяемость).
Если вы не профилировали свой код и не знаете, что отправка между ветвями ( оценка условий ) занимает больше времени, чем выполняемые вычисления ( код в ветвях ), оптимизируйте выполненные вычисления.
То есть правильный ответ на вопрос «насколько дороги виртуальные функции по сравнению с ветвлением» - это измерение и выяснение.
Практическое правило : если только у вас нет ситуации выше (различение ветвей дороже, чем вычисления ветвлений), оптимизируйте эту часть кода для обслуживания (используйте виртуальные функции).
Вы говорите, что хотите, чтобы этот раздел работал максимально быстро; Как быстро это? Каковы ваши конкретные требования?
Тогда используйте виртуальные функции. Это даже позволит вам оптимизировать для каждой платформы, если необходимо, и при этом сохранить клиентский код в чистоте.
источник
Другие ответы уже дают хорошие теоретические аргументы. Я хотел бы добавить результаты эксперимента, который я провел недавно, чтобы оценить, будет ли хорошей идеей реализовать виртуальную машину (ВМ), использующую большой
switch
размер кода операции, или, скорее, интерпретировать код операции как индекс в массив указателей на функции. Хотя это не совсем то же самое, чтоvirtual
вызов функции, я думаю, что это достаточно близко.Я написал скрипт Python для случайной генерации кода C ++ 14 для виртуальной машины с размером набора команд, выбранным случайным образом (хотя и неравномерно, с более плотной выборкой нижнего диапазона) между 1 и 10000. Созданная виртуальная машина всегда имела 128 регистров и не ОЗУ. Инструкции не имеют смысла и все имеют следующую форму.
Сценарий также генерирует процедуры отправки, используя
switch
оператор…... и массив указателей на функции.
Какая процедура отправки была сгенерирована, была выбрана случайным образом для каждой созданной виртуальной машины.
Для бенчмаркинга поток кодов операций был сгенерирован случайным образом отобранным (
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 инструкций.Весь исходный код для теста, а также полные экспериментальные данные и график высокого разрешения можно найти на моем сайте .
источник
В дополнение к хорошему ответу cmaster, за который я проголосовал, следует помнить, что указатели на функции обычно строго быстрее, чем на виртуальные. Диспетчеризация виртуальных функций обычно включает в себя сначала следование за указателем от объекта к виртуальной таблице, надлежащую индексацию, а затем разыменование указателя на функцию. Итак, последний шаг такой же, но изначально есть дополнительные шаги. Кроме того, виртуальные функции всегда принимают «this» в качестве аргумента, указатели на функции более гибкие.
Следует помнить еще одну вещь: если ваш критический путь включает в себя цикл, может быть полезно отсортировать цикл по назначению отправки. Очевидно, что это nlogn, тогда как обход цикла - только n, но если вы собираетесь проходить много раз, это может стоить того. Сортируя по назначению отправки, вы гарантируете, что один и тот же код выполняется многократно, сохраняя его горячим в icache, сводя к минимуму потери кэша.
Следует помнить о третьей стратегии: если вы решите отойти от виртуальных функций / указателей функций к стратегиям if / switch, вам также может быть полезен переход с полиморфных объектов на что-то вроде boost :: variable (которое также обеспечивает переключение). случай в виде абстракции посетителя). Полиморфные объекты должны храниться по базовому указателю, поэтому ваши данные повсюду в кеше. Это может легко оказать большее влияние на ваш критический путь, чем стоимость виртуального поиска. Принимая во внимание, что вариант хранится в строке как дискриминационный союз; он имеет размер, равный наибольшему типу данных (плюс небольшая константа). Если ваши объекты не сильно различаются по размеру, это отличный способ справиться с ними.
На самом деле, я не удивлюсь, если улучшение когерентности ваших данных окажет большее влияние, чем ваш первоначальный вопрос, поэтому я определенно рассмотрю этот вопрос.
источник
Могу я просто объяснить, почему я считаю, что это проблема XY ? (Вы не одиноки, спрашивая их.)
Я предполагаю, что ваша настоящая цель - сэкономить время в целом, а не просто понять, что происходит с отсутствием кэша и виртуальными функциями.
Вот пример реальной настройки производительности в реальном программном обеспечении.
В реальном программном обеспечении все делается так, что независимо от того, насколько опытен программист, это можно сделать лучше. Никто не знает, что это такое, пока программа не будет написана и не будет выполнена настройка производительности. Почти всегда есть несколько способов ускорить программу. В конце концов, чтобы сказать, что программа является оптимальной, вы говорите, что в пантеоне возможных программ, решающих вашу проблему, ни одна из них не займет меньше времени. В самом деле?
В примере, на который я ссылался, первоначально на «работу» уходило 2700 микросекунд. Серия из шести проблем была решена, обходя пиццу против часовой стрелки. Первое ускорение снимается в 33% случаев. Второй удалил 11%. Но обратите внимание, второй был не 11% в то время, когда он был найден, это было 16%, потому что первая проблема исчезла . Точно так же, третья проблема была увеличена с 7,4% до 13% (почти вдвое), потому что первые две проблемы исчезли.
В конце этот процесс увеличения позволил исключить все, кроме 3,7 микросекунд. Это 0,14% от исходного времени или ускорение в 730 раз.
Удаление изначально больших проблем дает умеренное ускорение, но они прокладывают путь для устранения последующих проблем. Эти более поздние проблемы могли первоначально быть незначительными частями, но после того, как ранние проблемы были устранены, эти маленькие становятся большими и могут привести к большим ускорениям. (Важно понимать, что, чтобы получить этот результат, нельзя пропустить ни одного, и этот пост показывает, насколько легко они могут быть.)
Была ли окончательная программа оптимальной? Возможно нет. Ни одно из ускорений не имело ничего общего с промахами кэша. Будет ли промах кеша иметь значение сейчас? Может быть.
РЕДАКТИРОВАТЬ: Я получаю отрицательные отзывы от людей, навязывающихся на «очень критических разделах» вопроса ОП. Вы не знаете, что что-то «крайне критично», пока не узнаете, на какую долю времени это приходится. Если средняя стоимость вызываемых методов составляет 10 или более циклов, то со временем метод отправки к ним, вероятно, не является «критическим» по сравнению с тем, что они фактически делают. Я вижу это снова и снова, когда люди воспринимают «нужную каждую наносекунду» как причину быть копеечным и глупым.
источник