Форум программистов, компьютерный форум CyberForum.ru

switch - оптимизация компилятора - C++

Восстановить пароль Регистрация
 
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
21.08.2013, 17:10     switch - оптимизация компилятора #1
Собственно, применяется ли оптимизация компилятором в виде двоичного поиска по case'ам switch'а, если я указывал case'ы в порядке возрастания и, при этом, после каждого case свой break? А если вразброс, но так же с break (он их отсортирует)?
А если все case'ы представляют из себя возрастающую последовательность с шагом 1 (будет ли оно приведено в массив "указателей" на код с O(1)-индексацией)? А если шаг 2/3/4..?
Предположим, что ключи заданы на "hard"-оптимизацию

p.s И на всех ли языках применяются оптимизации подобного рода, если применяются вообще?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.08.2013, 17:10     switch - оптимизация компилятора
Посмотрите здесь:

C++ Проблемы компилятора с++
C++ ошибка компилятора
C++ Оптимальная конструкция switch-case-while / while-switch-case
C++ Ошибки компилятора
C++ Ошибки компилятора
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
21.08.2013, 17:27     switch - оптимизация компилятора #2
Наверное предложенных тобой оптимизаций нет - это было бы глупо.
Следовательно остальные вопросы отпадают
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
21.08.2013, 17:30  [ТС]     switch - оптимизация компилятора #3
Kuzia domovenok, почему "это было бы глупо"? Скажем, есть N-дцать уникальных поведений относительно какого-нибудь параметра, скажем, ID. Почему бы и не выйти сразу на нужный кусок кода, вместо перебора if-ом каждого?
CheshireCat
Эксперт С++
2907 / 1235 / 78
Регистрация: 27.05.2008
Сообщений: 3,307
21.08.2013, 17:35     switch - оптимизация компилятора #4
Сильно зависит от используемого компилятора.

Мне приходилось разбирать дизассемблированный код нескольких компиляторов, и очень часто я сталкивался с "таблицей переходов" - по коду совершенно очевидно было, что это именно switch(...) в исходном коде. Ну а методы вычисления нужного адреса - они, естессно, были разными.....
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
21.08.2013, 17:41     switch - оптимизация компилятора #5
Подобных оптимизаций нет по причине того, что конструкция switch() - это не аналогия if()else if() ....
Благодаря внутреннему устройству switch(){} и так уже "оптимизирован" дальше некуда. Долго объяснять, поищи, вроде у Evg'а в блоге была статья про это, он там популярно объясняет. И то, что он там расказывает - это не фишка какого-то одного отдельно взятого компилятора С++. В JVM (виртуальная машина Java, если не в курсе) switch так же устроен (в общих чертах).

Добавлено через 2 минуты
Цитата Сообщение от Kastaneda Посмотреть сообщение
поищи, вроде у Evg'а в блоге
вот нашел http://www.cyberforum.ru/blogs/18334/blog91.html
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
21.08.2013, 18:02     switch - оптимизация компилятора #6
Цитата Сообщение от nexen Посмотреть сообщение
Kuzia domovenok, почему "это было бы глупо"? Скажем, есть N-дцать уникальных поведений относительно какого-нибудь параметра, скажем, ID. Почему бы и не выйти сразу на нужный кусок кода, вместо перебора if-ом каждого?
ну не знаю... Если нужен поиск значения, я и пользую явно бинарный поиск значения, использую всякие std::map std::bsearch.
А поведение switch, я уверен, должно быть прописано в стандарте: переход на метку и последовательное выполнение всего кода после неё.
Автор и сам понимает, что в противном случае возникает вопрос. А как выполнить код всех case'ов именно в том порядке, как они написаны? Ведь switch исполняет не один case, а все casы, что идут за совпавшим.

Добавлено через 17 минут
кроме того, то, что бинарный поиск O(log N) "быстрее" линейного O(N) - это всего лишь оценка сложности алгоритма. Реальный прирост скорости будет заметен только на довольно больших N. Что-то я никогда не видел switchа даже на полсотни пунктов.
gray_fox
21.08.2013, 18:10
  #7

Не по теме:

Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Что-то я никогда не видел switchа даже на полсотни пунктов.
NppBigSwitch.cpp полсотни точно есть

Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
21.08.2013, 18:15     switch - оптимизация компилятора #8
Цитата Сообщение от gray_fox Посмотреть сообщение
NppBigSwitch.cpp полсотни точно есть
в том то и дело, что даже, имея массив из полусотни пунктов, говорить о том, какой алгоритм поиска будет на нём быстрее бессмысленно. Очень даже возможно, что линейный поиск обгонит бинарный.
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
21.08.2013, 18:18     switch - оптимизация компилятора #9
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
в том то и дело, что даже, имея массив из полусотни пунктов, говорить о том, какой алгоритм поиска будет на нём быстрее бессмысленно. Очень даже возможно, что линейный поиск обгонит бинарный.
Не спорю...
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
21.08.2013, 18:29     switch - оптимизация компилятора #10
Цитата Сообщение от nexen Посмотреть сообщение
применяется ли оптимизация компилятором в виде двоичного поиска по case'ам switch'а
это ведь и правда глупо...
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
21.08.2013, 19:22     switch - оптимизация компилятора #11
Цитата Сообщение от CheshireCat Посмотреть сообщение
очень часто я сталкивался с "таблицей переходов" - по коду совершенно очевидно было, что это именно switch(...) в исходном коде
gcc так себя ведет, если в значениях case нет больших разрывов, т.е. если:
C
1
2
3
4
5
6
switch(i) {
case 0:
case 1:
case 2:
case 3:
}
то будет использоваться таблица, соответственно время поиска О(1). Если же
C
1
2
3
4
5
6
switch(i) {
case 0:
case 100:
case 200:
case 300:
}
то может использоваться и линейный поиск - последовательный перебор с помощью cmp/jmp инструкций.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.08.2013, 13:02     switch - оптимизация компилятора
Еще ссылки по теме:

C++ Ошибка компилятора
C++ Выбор компилятора
C++ Switch case внутри switch case

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
23.08.2013, 13:02  [ТС]     switch - оптимизация компилятора #12
fasked, то, что хотел узнать. Спасибо
Yandex
Объявления
23.08.2013, 13:02     switch - оптимизация компилятора
Ответ Создать тему
Опции темы

Текущее время: 05:24. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru