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

@nexen · Регистрация: 27.01.2012

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

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

p.s И на всех ли языках применяются оптимизации подобного рода, если применяются вообще?

@Kuzia domovenok · 21.08.2013, 17:27

Наверное предложенных тобой оптимизаций нет - это было бы глупо.
Следовательно остальные вопросы отпадают

@nexen · 21.08.2013, 17:30 **[ТС]**

Kuzia domovenok, почему "это было бы глупо"? Скажем, есть N-дцать уникальных поведений относительно какого-нибудь параметра, скажем, ID. Почему бы и не выйти сразу на нужный кусок кода, вместо перебора if-ом каждого?

@CheshireCat · 21.08.2013, 17:35

Сильно зависит от используемого компилятора.

Мне приходилось разбирать дизассемблированный код нескольких компиляторов, и очень часто я сталкивался с "таблицей переходов" - по коду совершенно очевидно было, что это именно switch(...) в исходном коде. Ну а методы вычисления нужного адреса - они, естессно, были разными.....

@Kastaneda · 21.08.2013, 17:41

Подобных оптимизаций нет по причине того, что конструкция switch() - это не аналогия if()else if() ....
Благодаря внутреннему устройству switch(){} и так уже "оптимизирован" дальше некуда. Долго объяснять, поищи, вроде у Evg'а в блоге была статья про это, он там популярно объясняет. И то, что он там расказывает - это не фишка какого-то одного отдельно взятого компилятора С++. В JVM (виртуальная машина Java, если не в курсе) switch так же устроен (в общих чертах).

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

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

поищи, вроде у Evg'а в блоге

вот нашел https://www.cyberforum.ru/blogs/18334/blog91.html

@Kuzia domovenok · 21.08.2013, 18:02

Сообщение от 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

Не по теме:

Сообщение от Kuzia domovenok

Что-то я никогда не видел switchа даже на полсотни пунктов.

NppBigSwitch.cpp полсотни точно есть :)

@Kuzia domovenok · 21.08.2013, 18:15

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

NppBigSwitch.cpp полсотни точно есть

в том то и дело, что даже, имея массив из полусотни пунктов, говорить о том, какой алгоритм поиска будет на нём быстрее бессмысленно. Очень даже возможно, что линейный поиск обгонит бинарный.

@gray_fox · 21.08.2013, 18:18

Сообщение от Kuzia domovenok

в том то и дело, что даже, имея массив из полусотни пунктов, говорить о том, какой алгоритм поиска будет на нём быстрее бессмысленно. Очень даже возможно, что линейный поиск обгонит бинарный.

Не спорю...

@salam · 21.08.2013, 18:29

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

применяется ли оптимизация компилятором в виде двоичного поиска по case'ам switch'а

это ведь и правда глупо...

@fasked · 21.08.2013, 19:22

Сообщение от 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 инструкций.

@nexen · 23.08.2013, 13:02 **[ТС]**

fasked, то, что хотел узнать. Спасибо

@Styletto · 07.11.2019, 04:43

Все гораздо проще. Делается поиск по строке одной командой repe cmps(b/w). Строка составлена из byte, short или long, куда занесены последовательно значения case. В результате выполнения команды имеем индекс элемента массива переходов. Дальше сдвиг влево на 2 или 3 бита и косвенная адресация перехода со смещением. Если значения case 64 битные, и их много, то то же самое через регистры и команды SSE.

@TheCalligrapher · 07.11.2019, 05:03

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

Собственно, применяется ли оптимизация компилятором в виде двоичного поиска по case'ам switch'а[...]

Никто не знает применяется ли она или нет. Это зависит от конкретного компилятора, конкретных его настроек и конкретного кода. Вопрос не имеет смысла.

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

p.s И на всех ли языках применяются оптимизации подобного рода, если применяются вообще?

Оптимизации не имеют никакого отношения к языкам. Оптимизации определяются конкретными реализациями.

@Kuzia domovenok · 07.11.2019, 22:07

TheCalligrapher, закопай тему, автор сто лет в обед уже как забыл про неё. Хочешь что-то сказать - говори Styletto, это он зарегался на форуме, чтобы апнуть рандомную тему из 2013г

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@nexen 187 / 180 / 25 Регистрация: 27.01.2012 Сообщений: 1,335

	switch - оптимизация компилятора 21.08.2013, 17:10. Показов 3883. Ответов 14 Метки нет (Все метки) Собственно, применяется ли оптимизация компилятором в виде двоичного поиска по case'ам switch'а, если я указывал case'ы в порядке возрастания и, при этом, после каждого case свой break? А если вразброс, но так же с break (он их отсортирует)? А если все case'ы представляют из себя возрастающую последовательность с шагом 1 (будет ли оно приведено в массив "указателей" на код с O(1)-индексацией)? А если шаг 2/3/4..? Предположим, что ключи заданы на "hard"-оптимизацию p.s И на всех ли языках применяются оптимизации подобного рода, если применяются вообще? 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,531 Записей в блоге: 1
	21.08.2013, 17:27
	Наверное предложенных тобой оптимизаций нет - это было бы глупо. Следовательно остальные вопросы отпадают 0

@nexen 187 / 180 / 25 Регистрация: 27.01.2012 Сообщений: 1,335
	21.08.2013, 17:30 [ТС]
	Kuzia domovenok, почему "это было бы глупо"? Скажем, есть N-дцать уникальных поведений относительно какого-нибудь параметра, скажем, ID. Почему бы и не выйти сразу на нужный кусок кода, вместо перебора if-ом каждого? 0

@CheshireCat 2924 / 1274 / 114 Регистрация: 27.05.2008 Сообщений: 3,465
	21.08.2013, 17:35
	Сильно зависит от используемого компилятора. Мне приходилось разбирать дизассемблированный код нескольких компиляторов, и очень часто я сталкивался с "таблицей переходов" - по коду совершенно очевидно было, что это именно switch(...) в исходном коде. Ну а методы вычисления нужного адреса - они, естессно, были разными..... 1

@nexen 187 / 180 / 25 Регистрация: 27.01.2012 Сообщений: 1,335
	23.08.2013, 13:02 [ТС]
	fasked, то, что хотел узнать. Спасибо 0

@Styletto 0 / 0 / 0 Регистрация: 10.11.2015 Сообщений: 1
	07.11.2019, 04:43
	Все гораздо проще. Делается поиск по строке одной командой repe cmps(b/w). Строка составлена из byte, short или long, куда занесены последовательно значения case. В результате выполнения команды имеем индекс элемента массива переходов. Дальше сдвиг влево на 2 или 3 бита и косвенная адресация перехода со смещением. Если значения case 64 битные, и их много, то то же самое через регистры и команды SSE. 0

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,531 Записей в блоге: 1
	07.11.2019, 22:07
	TheCalligrapher, закопай тему, автор сто лет в обед уже как забыл про неё. Хочешь что-то сказать - говори Styletto, это он зарегался на форуме, чтобы апнуть рандомную тему из 2013г 0