Оптимизируется ли компилятором конструкция switch-case? Работа со строками через ID объекта или hash

@rikimaru2013 · Регистрация: 30.11.2013

Студворк — интернет-сервис помощи студентам

Добрый вечер,

1) Определён ли порядок выбора switch (согласно стандарта кажись неопределён, но все компиляторы я уверен в этом тривиальном вопросе работают в примерно одном русле)
2) какие варианты оптимизации кода

C++
1
2
3
4
5
6
7
8
9
10
11
12
void foo(const string& val)
{
    if(val == "first")
    {
 
    }
    else if(val == "second")
    {
 
    }
    ...
}

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

C++
1
const string temp = "privet";

Tulosba · 11.06.2015, 15:43

Сообщение от Evg

Каким будет C++'най аналог C'ной конструкции

В данном случае, почти таким же. Т.к. тут нет как таковой работы со строками.

Evg · 11.06.2015, 16:05

Сообщение от Tulosba

В данном случае, почти таким же

Ну так каким же всё-таки (я то сам не большой умелец в плюсах)?

@ct0r · 11.06.2015, 16:27

Сообщение от Kastaneda

То, что метод часто дергается - это рантайм информация. Во время компиляции этой информации нет. В JIT'ах как раз это используется. Например в Java если метод "прогрелся" он отправляется на компиляцию в первый компилятор (JIT), ему передается профилировачная информация, собранная интерпретатором (информация о раличных ветвлениях, проваливаний в if/else, попадания в catch блок, etc). Задача этого компилятора скомпилировать метод быстро, при этом на выходе получается не очень быстрый код. В этот код также встраивается профилирование. Когда скомпилированный метод стал горячим, он подается второму второму компилятору, вместе с собранной профилировачной информацией. Задача второго компилятора выдать максимально быстрый код, поэтому он компилирует очень медленно (применяется максимум оптимизаций), но на выходе получается чистый быстрый код.

В том же g++ можно использовать PGO.

Evg · 11.06.2015, 18:53

Кстати, код

C++
if (str == "one")
{
  ...
} else if ( str = "two")
{
  ...
} else if ( str = "three")
{
  ...
} else if ( str = "four")
{
...
// длинная цепочка сравнений

можно ускорить, переписав:

C++
switch (str[0])
{
  case 'o':
    if (str == "one")
    {
      ...
    }
    break;
  case 't':
    if (str == "two")
    {
      ...
    } else if (str == "three")
    {
      ...
    }
    break;
  case 'f':
    if (str == "four")
    {
      ...
    }
    break;
}

при длинной цепочке сравнений вынесенное в switch предварительное сравнение первой буквы должно в целом ускорить

@castaway · 11.06.2015, 19:20

Тогда можно еще попробовать немного укорить:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
switch (str[0])
{
  case 'o':
    if ( std::string( &str[1] ) == "ne" )
    {
      ...
    }
    break;
  case 't':
    if ( std::string( &str[1] ) == "wo" )
    {
      ...
    } else if ( std::string( &str[1] ) == "hree" )
    {
      ...
    }
    break;
  case 'f':
    if ( std::string( &str[1] ) == "our" )
    {
      ...
    }
    break;
}

Хотя через strcmp я думаю будет быстрее.

@DrOffset · 11.06.2015, 19:58

Сообщение от Evg

можно ускорить

Сообщение от castaway

немного укорить

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

@castaway · 11.06.2015, 20:08

DrOffset, но ведь hash в compile-time не посчитается. Сколько на это времени уйдёт?

@rikimaru2013 · 11.06.2015, 20:10 **[ТС]**

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

@DrOffset · 11.06.2015, 20:12

Сообщение от castaway

но ведь hash в compile-time не посчитается.

Посчитается для литералов в compile-time. Для входной строки в swicth - один проход по строке. Это быстрее, чем n-раз сравнивать c n литералами (n-проходов в худшем случае).

Добавлено через 1 минуту

Сообщение от rikimaru2013

Вы это сами писали или есть где почитать про такой путь оптимизации строкового свича?

Писал сам. Но подход старый как мир.
Просто раньше не было красивого способа посчитать hash от литерала в ct (см. boost::mpl::string), поэтому это не пользовалось популярностью.

@castaway · 11.06.2015, 20:15

Сообщение от DrOffset

Для входной строки в swicth - один проход по строке. Это быстрее, чем n-раз сравнивать c n литералами (n-проходов в худшем случае).

Вот мне это и интересно.

@DrOffset · 11.06.2015, 20:26

Сообщение от castaway

Вот мне это и интересно.

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

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

@castaway · 11.06.2015, 20:38

Сообщение от DrOffset

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

В твоём случае, все сложные вычисления произойдут в самом начале в любом случае, при чём это не просто пройтись по строке и сравнить каждую букву, в GCC с -O3 на ассемблере вычисление хеша будет выглядеть примерно так:

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
loc_F8:                                 ; CODE XREF: _main+6Ej
.text.startup:000000F8                 mov     ebx, eax
.text.startup:000000FA                 mov     ecx, eax
.text.startup:000000FC                 add     edx, 1
.text.startup:000000FF                 shr     ecx, 2
.text.startup:00000102                 shl     ebx, 6
.text.startup:00000105                 lea     ebx, [ebx+ecx-61C88647h]
.text.startup:0000010C                 movsx   ecx, byte ptr [edx-1]
.text.startup:00000110                 add     ecx, ebx
.text.startup:00000112                 xor     eax, ecx
.text.startup:00000114                 cmp     esi, edx
.text.startup:00000116                 jnz     short loc_F8

Сама обработка switch будет выглядеть примерно одинакова для обеих случаев.
А вот потом уже: у тебя - результат, не у тебя - посимвольное сравнение оставшихся символов.

Так что быстрее, код на ассемблере (который выше), или посимвольное сравнение в конце (что не в твоём коде)?
Для меня далеко не очевидно что быстрее твой вариант, даже если это на самом деле так.

Evg · 11.06.2015, 20:41

Сообщение от rikimaru2013

DrOffset, во уже что-то сладенькое

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

Добавлено через 2 минуты
Правда ещё надо прикинуть, сколько тактов занимает вычисление хэш-кода. Т.е. выбор между #24 и #26, думается, будет не всегда однозначный и зависит от конкретных значений строковых литералов

@DrOffset · 11.06.2015, 20:46

Сообщение от castaway

Для меня далеко не очевидно что быстрее твой вариант, даже если это на самом деле так.

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

Сообщение от Evg

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

Там об этом написано

Сообщение от DrOffset

заранее известным строкам

Можно конечно и добавить дополнительное сравнение со строкой, как в хэш-контейнерах делают.

@castaway · 11.06.2015, 20:49

Сообщение от DrOffset

На всякий случай, если ты воспринял это как попытку принизить вариант Evg или твой, ...

Нет. Нет конечно. Просто решил порассуждать. Разве тебе самому это не интересно?

Evg · 11.06.2015, 20:50

Сообщение от DrOffset

Там об этом написано

Формулировка такая, что для того, кто этого не знает, это далеко не очевидно

Сообщение от DrOffset

Можно конечно и добавить дополнительное сравнение со строкой, как в хэш-контейнерах делают

Тогда это будет практически однозначно медленнее, чем switch с первой буквой

@DrOffset · 11.06.2015, 21:03

Не по теме:

Сообщение от Evg

будет не всегда однозначный и зависит от конкретных значений строковых литералов

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

Добавлено через 3 минуты

Сообщение от Evg

Тогда это будет практически однозначно медленнее, чем switch с первой буквой

В том примере - да. Ты же сам написал

Сообщение от Evg

зависит от конкретных значений строковых литералов

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

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

Добавлено через 6 минут

Сообщение от castaway

Разве тебе самому это не интересно?

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

Evg · 12.06.2015, 00:24

Сообщение от DrOffset

Так-то можно придумать пример, где и твой вариант будет очень медленным

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

Сообщение от DrOffset

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

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

Добавлено через 10 минут
Если строки может быть только одной из 30 и никакой другой, то в качестве хэш-функции можно попробовать подогнать что-то типа "str[0] + str[3] - str[2]". Наверняка при некоторой ловкости рук можно получить ну очень короткий вариант и он будет работать с термоядерной скоростью

@gazlan · 12.06.2015, 02:41

Классические решения для мэппинга строк в индекс, это Hash и Trie.
Perfect hash function
Trie
MARISA: Matching Algorithm with Recursively Implemented StorAge

Новые блоги и статьи Все статьи Все блоги /
Книги по геймдизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .	Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .
Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .	Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .	Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .

Evg 21287 / 8312 / 637 Регистрация: 30.03.2009 Сообщений: 22,671 Записей в блоге: 30
	11.06.2015, 18:53
	Сообщение было отмечено DrOffset как решение Решение Кстати, код C++ if (str == "one") { ... } else if ( str = "two") { ... } else if ( str = "three") { ... } else if ( str = "four") { ... // длинная цепочка сравнений можно ускорить, переписав: C++ switch (str[0]) { case 'o': if (str == "one") { ... } break; case 't': if (str == "two") { ... } else if (str == "three") { ... } break; case 'f': if (str == "four") { ... } break; } при длинной цепочке сравнений вынесенное в switch предварительное сравнение первой буквы должно в целом ускорить 1

@castaway 4986 / 3093 / 456 Регистрация: 10.11.2010 Сообщений: 11,170 Записей в блоге: 10
	11.06.2015, 20:08
	DrOffset, но ведь hash в compile-time не посчитается. Сколько на это времени уйдёт? 0

@rikimaru2013 2549 / 1208 / 358 Регистрация: 30.11.2013 Сообщений: 3,826
	11.06.2015, 20:10 [ТС]
	DrOffset, во уже что-то сладенькое. Вы это сами писали или есть где почитать про такой путь оптимизации строкового свича? 0

@gazlan 3178 / 1937 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	12.06.2015, 02:41
	Классические решения для мэппинга строк в индекс, это Hash и Trie. Perfect hash function Trie MARISA: Matching Algorithm with Recursively Implemented StorAge 0

Оптимизируется ли компилятором конструкция switch-case? Работа со строками через ID объекта или hash

Решение