Что является более эффективным, случай переключения или std :: map

Question

Я думаю о токенизаторе здесь.
Каждый токен вызывает отдельную функцию внутри парсера.
Что эффективнее:

• Карта std :: functions / boost :: functions
• Корпус переключателя

Answer 1

Я бы посоветовал прочитать switch () или справочную таблицу? от Джоэла по программному обеспечению. В частности, этот ответ интересен:

"Яркий пример того, как люди тратят время пытаясь оптимизировать наименьшее существенная вещь. "

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

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

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

Но, как уже упоминалось, я уверен, что эти данные не имеют отношения к вашему коду. Это мелкие детали, и вам не следует слишком на них фокусироваться. Интерпретатор Python использует переключатели, потому что они думают, что это делает код более читабельным. Почему бы вам не выбрать наиболее удобное для вас использование? Влияние на производительность будет довольно незначительным, вам лучше сосредоточиться на удобочитаемости кода;)

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

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

Подводя итог, мы имеем:

• стоимость (Hash_table) >> стоимость (direct_lookup_table)
• стоимость (direct_lookup_table) ~ = стоимость (переключатель), если ваш компилятор переводит переключатели в таблицы поиска.
• cost (switch) >> cost (direct_lookup_table) (O (N) vs O (1)), если ваш компилятор не переводит переключатели и не использует условные выражения, но я не могу представить, чтобы какой-либо компилятор делал это.
• Но прямая многопоточность делает код менее читабельным.

Answer 2

STL Map, поставляемая с Visual Studio 2008, будет давать вам O (log (n)) для каждого вызова функции, поскольку она скрывает древовидную структуру. В современном компиляторе (в зависимости от реализации) оператор switch даст вам O (1), а компилятор преобразует его в какую-то таблицу поиска. Так что, в общем, переключение происходит быстрее.

Однако , учтите следующие факты:

Разница между картой и коммутатором заключается в том, что: карта может быть построена динамически, а коммутатор - нет. Map может содержать любой произвольный тип в качестве ключа, в то время как switch очень ограничен примитивными типами c ++ (char, int, enum и т. Д.).

Кстати, вы можете использовать хеш-карту для достижения почти O (1) диспетчеризации (хотя, в зависимости от реализации хеш-таблицы, иногда это может быть O (n) в худшем случае). Несмотря на то, что переключатель все равно будет быстрее.

Редактировать

Я пишу следующее только для развлечения и для обсуждения

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

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

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

Редактировать : Из-за некоторых комментариев, приведенных ниже, изменено Предложение о том, что компиляторы всегда будут переводить переключатель в LUT.

Answer 3

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

Answer 4

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

Для быстрого переключения ваши значения должны соответствовать следующему правилу: они должны быть последовательными, то есть, например, 0,1,2,3,4. Вы можете оставить некоторые значения, но такие вещи, как 0,1,2,34,43, вряд ли будут оптимизированы.

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

Answer 5

Вы не говорите, какой у вас тип токенов. Если они не являются целыми числами, у вас нет выбора - переключатели работают только с целочисленными типами.

Answer 6

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

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

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

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