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

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

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

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

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

C++

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++

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

loc_F8:                                 ; CODE XREF: _main+6Ej
.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

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	11.06.2015, 16:05	22
	Сообщение от Tulosba В данном случае, почти таким же Ну так каким же всё-таки (я то сам не большой умелец в плюсах)? 0

@ct0r Игогошка! 1801 / 708 / 44 Регистрация: 19.08.2012 Сообщений: 1,367
	11.06.2015, 16:27	23
	Сообщение от Kastaneda То, что метод часто дергается - это рантайм информация. Во время компиляции этой информации нет. В JIT'ах как раз это используется. Например в Java если метод "прогрелся" он отправляется на компиляцию в первый компилятор (JIT), ему передается профилировачная информация, собранная интерпретатором (информация о раличных ветвлениях, проваливаний в if/else, попадания в catch блок, etc). Задача этого компилятора скомпилировать метод быстро, при этом на выходе получается не очень быстрый код. В этот код также встраивается профилирование. Когда скомпилированный метод стал горячим, он подается второму второму компилятору, вместе с собранной профилировачной информацией. Задача второго компилятора выдать максимально быстрый код, поэтому он компилирует очень медленно (применяется максимум оптимизаций), но на выходе получается чистый быстрый код. В том же g++ можно использовать PGO. 1

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

@DrOffset 18844 / 9843 / 2408 Регистрация: 30.01.2014 Сообщений: 17,284
	11.06.2015, 20:12	29
	Сообщение от castaway но ведь hash в compile-time не посчитается. Посчитается для литералов в compile-time. Для входной строки в swicth - один проход по строке. Это быстрее, чем n-раз сравнивать c n литералами (n-проходов в худшем случае). Добавлено через 1 минуту Сообщение от rikimaru2013 Вы это сами писали или есть где почитать про такой путь оптимизации строкового свича? Писал сам. Но подход старый как мир. Просто раньше не было красивого способа посчитать hash от литерала в ct (см. boost::mpl::string), поэтому это не пользовалось популярностью. 0

@DrOffset 18844 / 9843 / 2408 Регистрация: 30.01.2014 Сообщений: 17,284
	11.06.2015, 20:26	31
	Сообщение от castaway Вот мне это и интересно. Ну так strcmp тоже требует пройтись по строке. Так что вариант без хеша будет лучше только в том случае, если мы на первом же сравнении попали в нужный вариант. Если нужный вариант где-то в конце цепочки, то будет как минимум не хуже (особенно если есть несколько строк, начинающихся на одну и ту же букву). Добавлено через 6 минут rikimaru2013, Ты главное не думай, что это какая-то панацея. Полно вариантов, когда это решение может оказаться хуже, например, тернарного дерева поиска. Думать всегда нужно головой и профилировать 0

Tulosba :) 4773 / 3267 / 497 Регистрация: 19.02.2013 Сообщений: 9,046
	11.06.2015, 15:43	21
	Сообщение от Evg Каким будет C++'най аналог C'ной конструкции В данном случае, почти таким же. Т.к. тут нет как таковой работы со строками. 0

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	11.06.2015, 18:53	24
	Сообщение было отмечено 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

@DrOffset 18844 / 9843 / 2408 Регистрация: 30.01.2014 Сообщений: 17,284
	11.06.2015, 19:58	26
	Сообщение от Evg можно ускорить Сообщение от castaway немного укорить Если именно такой код ускорять (подчеркиваю, именно такой, с заведомо известными литералами, коих немного), то тогда уж лучше так. 2

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

@castaway 4985 / 3092 / 456 Регистрация: 10.11.2010 Сообщений: 11,169 Записей в блоге: 10
	11.06.2015, 20:15	30
	Сообщение от DrOffset Для входной строки в swicth - один проход по строке. Это быстрее, чем n-раз сравнивать c n литералами (n-проходов в худшем случае). Вот мне это и интересно. 0

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	11.06.2015, 20:41	33
	Сообщение от rikimaru2013 DrOffset, во уже что-то сладенькое Здесь есть очень важный момент: входная строка должна быть не произвольной, а только одной из 30 допустимых. В противном случае есть риск, что две разные строки могут дать одинаковых хэш-код Добавлено через 2 минуты Правда ещё надо прикинуть, сколько тактов занимает вычисление хэш-кода. Т.е. выбор между #24 и #26, думается, будет не всегда однозначный и зависит от конкретных значений строковых литералов 0

@DrOffset 18844 / 9843 / 2408 Регистрация: 30.01.2014 Сообщений: 17,284
	11.06.2015, 20:46	34
	Сообщение от castaway Для меня далеко не очевидно что быстрее твой вариант, даже если это на самом деле так. На коротких примерах не будет видно профита. Можно взять, например, несколько строк, начинающихся одинаково. Но если для тебя это дело принципа, что ты аж в ассемблер полез, доказать, что код не быстрее, пусть будет так. Мне лень спорить, если честно. На всякий случай, если ты воспринял это как попытку принизить вариант Evg или твой, то ты ошибся. Сообщение от Evg Здесь есть очень важный момент: входная строка должна быть не произвольной, а только одной из 30 допустимых. Там об этом написано Сообщение от DrOffset заранее известным строкам Можно конечно и добавить дополнительное сравнение со строкой, как в хэш-контейнерах делают. 0

@castaway 4985 / 3092 / 456 Регистрация: 10.11.2010 Сообщений: 11,169 Записей в блоге: 10
	11.06.2015, 20:49	35
	Сообщение от DrOffset На всякий случай, если ты воспринял это как попытку принизить вариант Evg или твой, ... Нет. Нет конечно. Просто решил порассуждать. Разве тебе самому это не интересно? 0

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	11.06.2015, 20:50	36
	Сообщение от DrOffset Там об этом написано Формулировка такая, что для того, кто этого не знает, это далеко не очевидно Сообщение от DrOffset Можно конечно и добавить дополнительное сравнение со строкой, как в хэш-контейнерах делают Тогда это будет практически однозначно медленнее, чем switch с первой буквой 1

@DrOffset 18844 / 9843 / 2408 Регистрация: 30.01.2014 Сообщений: 17,284
	11.06.2015, 21:03	37
	Не по теме: Сообщение от Evg будет не всегда однозначный и зависит от конкретных значений строковых литералов Да, слово "лучше" в моей фразе было лишнее. Скажем так, это _иногда_ может быть полезным. Добавлено через 3 минуты Сообщение от Evg Тогда это будет практически однозначно медленнее, чем switch с первой буквой В том примере - да. Ты же сам написал Сообщение от Evg зависит от конкретных значений строковых литералов Так-то можно придумать пример, где и твой вариант будет очень медленным. Например 30 строк, различающихся только в последних буквах. Единственное, что стоит ТС вынести из нашего разговора, так это то, что нужно думать головой, прежде чем применять тот или иной способ. Добавлено через 6 минут Сообщение от castaway Разве тебе самому это не интересно? Я имел опыт реального выигрыша от подобной техники в одном из проектов. Я точно знаю, что этот способ имеет право на жизнь (ну возможно не в таком примитивном виде). А то, что всегда можно найти такой набор данных, где какой-либо способ будет очень плох - написано в любом учебнике по алгоритмам. Так что, если ты сейчас докажешь, что на нашем наборе данных (кстати набора-то вроде нет?) этот способ хуже - я не удивлюсь. Если окажется, что они равны или он лучше - ну что ж, бывает. 0

Evg 21279 / 8301 / 637 Регистрация: 30.03.2009 Сообщений: 22,659 Записей в блоге: 30
	12.06.2015, 00:24	38
	Сообщение от DrOffset Так-то можно придумать пример, где и твой вариант будет очень медленным Естественно. Тут даже алгоритмом назвать сложно. Попытка решить конкретную проблему для почти конкретных входных данных. Я вот думал, что может быть можно сделать гибрид из двух способов, но толку от этого по ходу не будет. Всегда приходится либо вычислять хэш, либо сравнивать, т.е. где-то сэкономить не получается Сообщение от DrOffset Единственное, что стоит ТС вынести из нашего разговора, так это то, что нужно думать головой, прежде чем применять тот или иной способ Всё равно, когда показаны разные способы и как-то их вслух обсудили - на мой взгляд это помогает лучше прочувствовать ситуацию, чем когда просто дали код и сиди и думай над ним (или тупо передрать) Добавлено через 10 минут Если строки может быть только одной из 30 и никакой другой, то в качестве хэш-функции можно попробовать подогнать что-то типа "str[0] + str[3] - str[2]". Наверняка при некоторой ловкости рук можно получить ну очень короткий вариант и он будет работать с термоядерной скоростью 1

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

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

Решение