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

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

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

Собственно, применяется ли оптимизация компилятором в виде двоичного поиска по 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

switch(i) {
case 0:
case 1:
case 2:
case 3:
}

то будет использоваться таблица, соответственно время поиска О(1). Если же

C

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г

@TheCalligrapher Вездепух 11695 / 6374 / 1724 Регистрация: 18.10.2014 Сообщений: 16,068
	07.11.2019, 05:03	14
	Сообщение от nexen Собственно, применяется ли оптимизация компилятором в виде двоичного поиска по case'ам switch'а[...] Никто не знает применяется ли она или нет. Это зависит от конкретного компилятора, конкретных его настроек и конкретного кода. Вопрос не имеет смысла. Сообщение от nexen p.s И на всех ли языках применяются оптимизации подобного рода, если применяются вообще? Оптимизации не имеют никакого отношения к языкам. Оптимизации определяются конкретными реализациями. 0

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

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

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

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

@Kastaneda 5231 / 3204 / 362 Регистрация: 12.12.2009 Сообщений: 8,116 Записей в блоге: 2
	21.08.2013, 17:41	5
	Подобных оптимизаций нет по причине того, что конструкция switch() - это не аналогия if()else if() .... Благодаря внутреннему устройству switch(){} и так уже "оптимизирован" дальше некуда. Долго объяснять, поищи, вроде у Evg'а в блоге была статья про это, он там популярно объясняет. И то, что он там расказывает - это не фишка какого-то одного отдельно взятого компилятора С++. В JVM (виртуальная машина Java, если не в курсе) switch так же устроен (в общих чертах). Добавлено через 2 минуты Сообщение от Kastaneda поищи, вроде у Evg'а в блоге вот нашел https://www.cyberforum.ru/blogs/18334/blog91.html 1

@Kuzia domovenok 4064 / 3318 / 924 Регистрация: 25.03.2012 Сообщений: 12,493 Записей в блоге: 1
	21.08.2013, 18:02	6
	Сообщение от nexen Kuzia domovenok, почему "это было бы глупо"? Скажем, есть N-дцать уникальных поведений относительно какого-нибудь параметра, скажем, ID. Почему бы и не выйти сразу на нужный кусок кода, вместо перебора if-ом каждого? ну не знаю... Если нужен поиск значения, я и пользую явно бинарный поиск значения, использую всякие std::map std::bsearch. А поведение switch, я уверен, должно быть прописано в стандарте: переход на метку и последовательное выполнение всего кода после неё. Автор и сам понимает, что в противном случае возникает вопрос. А как выполнить код всех case'ов именно в том порядке, как они написаны? Ведь switch исполняет не один case, а все casы, что идут за совпавшим. Добавлено через 17 минут кроме того, то, что бинарный поиск O(log N) "быстрее" линейного O(N) - это всего лишь оценка сложности алгоритма. Реальный прирост скорости будет заметен только на довольно больших N. Что-то я никогда не видел switchа даже на полсотни пунктов. 0

@gray_fox
	21.08.2013, 18:10 #7
	Не по теме: Сообщение от Kuzia domovenok Что-то я никогда не видел switchа даже на полсотни пунктов. NppBigSwitch.cpp полсотни точно есть :) 0

@Kuzia domovenok 4064 / 3318 / 924 Регистрация: 25.03.2012 Сообщений: 12,493 Записей в блоге: 1
	21.08.2013, 18:15	8
	Сообщение от gray_fox NppBigSwitch.cpp полсотни точно есть в том то и дело, что даже, имея массив из полусотни пунктов, говорить о том, какой алгоритм поиска будет на нём быстрее бессмысленно. Очень даже возможно, что линейный поиск обгонит бинарный. 0

@gray_fox What a waste! 1608 / 1300 / 180 Регистрация: 21.04.2012 Сообщений: 2,729
	21.08.2013, 18:18	9
	Сообщение от Kuzia domovenok в том то и дело, что даже, имея массив из полусотни пунктов, говорить о том, какой алгоритм поиска будет на нём быстрее бессмысленно. Очень даже возможно, что линейный поиск обгонит бинарный. Не спорю... 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	21.08.2013, 18:29	10
	Сообщение от nexen применяется ли оптимизация компилятором в виде двоичного поиска по case'ам switch'а это ведь и правда глупо... 0

	07.11.2019, 22:07

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

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