Vftable рейтинг производительности против оператора switch

Вопрос на С++. У меня есть система, в которой у меня будут сотни мини-подклассов данного суперкласса. У всех у них будет метод "foo", который что-то делает. Или... Я собираюсь иметь один класс с целым числом, называемым "type", и использовать гигантский оператор switch, чтобы решить, что делать, когда я foo.

Производительность здесь огромная. Чрезвычайно важно.

Вопрос в том, каковы преимущества производительности/штрафы за использование оператора switch или разрешение С++ делать это через vftable? Если у меня это как оператор switch, я могу поместить часто возникающий foo вверху оператора switch и менее общие в нижней части, надеюсь, сокращая сравнение. Попытка получить такой эффект с помощью vftable неизбежно зависит от компилятора, даже если я смогу понять, как это сделать...

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

Ответ 1

Если у меня это как оператор switch, я могу поместить часто возникающий foo вверху оператора switch и менее общие в нижней части, надеюсь, что это сократит сравнение.

Оператор

A switch обычно компилируется в таблицу вместо блока if-else условностей, как предполагает ваш вопрос. На практике виртуальная таблица и таблица перехода switch должны иметь схожую производительность, хотя тест, если вы действительно обеспокоены.

Ответ 2

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

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

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

Множество кода, использующего виртуальную диспетчеризацию, требует использования схем распределения на основе кучи. Динамическое распределение памяти является узким местом во многих приложениях на С++.

Ответ 3

Компилятор определяет, как обрабатываются операторы switch, но есть несколько основных методов, которые они используют.

if-else binary-sort: сравнение выполняется как серия if-else, но в двоичном виде, например, производительность сопоставима с поиском на карте из N элементов
таблица перехода: если элементы находятся достаточно близко, будет создана таблица адресов. Поиск выполняется в постоянное время

В тех случаях, когда операторы case находятся в инструкции switch, не имеет никакого значения в обоих случаях.

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

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

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

Ответ 4

К другим ответам здесь я бы добавил еще два.

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

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

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

Счастливый взлом!

Ответ 5

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

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

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