Телепортируюсь из темы Генерация статического кода из ДКА, switch или goto, что лучше?, сюда.
Мною было решено для генерации статического кода из ДКА использовать switch.
Т.е. например имея след. ДКА  будет сгенерирован примерно след. код
Как узнать, какое максимальное количество case'ов можно использовать в switch'е при этом не теряя эффективности switch'a/производительности?

попробовать сравнить?
на самом деле насколько мне представляется switch это замаскированное использование goto, ибо правила игры те же

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

Вот только как?
индексы могут идти не по порядку, а полностью вразброс.
И все-же как бы компилятор не оптимизировал, наверняка есть предел оптимального количества case'ов.
Представим наихудший вариант, все индексы нелинейны и расположение case'ов хаотично... какой в данном случае будет примерный лимит кол. case'ов с которым производительность не будет падать? спасибо.

Это сообщение отредактировал(а) rudvil - 22.3.2011, 00:47

Вопрос не совсем корректен. Зависит от реализации компилятора.
Но, чисто по опыту могу сказать, что большие свитчи (по крайней мере на MSVS) довольно быстры 

gcc и msvc, остальное не интересует.
Вопрос не о совсем-совсем макс. кол. case'ов в switch'е, это можно в документации найти, а о максимально оптимальном кол. при котором не будет падения производительности.

Добавлено @ 01:01
Цитирую neutrino, из Генерация статического кода из ДКА, switch или goto, что лучше? собственно поэтому и решил создать тему, актуально ли это?

Это сообщение отредактировал(а) rudvil - 22.3.2011, 01:03

rudvil, еще раз. Свитчи это не та причина от которой может серьезно упать производительность. Можете не бояться. (в разумных пределах конечно   )

Надеюсь что это так, утешили - спасибо.   

Ну уж в любом случае быстрее кучи if'ов

Здесь похожая тема поднималась
forum.vingrad.ru/forum/topic-296638/view-all/hl/switch/index.html

rudvil, в двух словах:
1. свитчи для последовательного набора вариантов (или очень близкого к нему) будут преобразованы в таблицу, что в итоге приведет к константному времени перехода к нужной ветке.
2. свитчи для случайного набора вариантов (которые совсем не похожи на линейную последовательность) будут преобразованы в бинарный поиск (поиск делением пополам), таким образом, время перехода к нужному элементу будет логарифмически (по основанию 2) зависеть от количества элементов (например, если элементов будет 256, то в худшем случае поиск займет 8 итераций).
3. если свитч маленький, и варианты 1 и 2 не подходят, то используется банальные if/else.

Это сообщение отредактировал(а) bsa - 22.3.2011, 10:52

Чем же? По крайней мере, ЦД обычно реализуют таки через loop (бесконечный цикл) и if - elseif - else.

Это сообщение отредактировал(а) kemiisto - 22.3.2011, 11:05

Если в цикле Дейкстры условия разнозначные (if str="abc", if a==b, if x<y), то по другому и не сделаешь, а если сравнение целочисленного типа с константами (например с enum'ом), и их не два-три, то лучше использовать switch.
Нет ?

kemiisto, ответ на ваш вопрос содержится прямо над ним
Иными словами, если допустим есть 128 кейсов, то для выбора подходящего нужно будет сделать 7 сравнений.
Если же это писать в if'aх, то в среднем нужно будет 64 ифа. И чем больше кейсов, тем ощутемее разници.
log2(N) против (N)

А если числа идут подряд (или с равными промежутками), то вообще строится таблица: (1) против (N)

Cамо-собой это при идеальном оптимизаторе. В реале конечно не так красиво, но создатели компиляторов к этому стремятся  

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

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

ну про идеальный сильно загнуто..  такого в природе не существует.. 

Во-первых, зависит от реализации. Значит в общем случае неверно.
Во-вторых, я в упор не вижу пруфов с исходниками GCC, например, с этими вашими таблицами переходов. Вы проверяли? Или так. Кто-то где-то написал... Болтовню вижу, пруфо - нет.
В-третьих, бенчмарков я тоже не увидел. Для закрытых реализаций полагаться больше не на что.
В-четвёртых, я не понял насчёт 64 if'ов. Да, я в курсе, что С++ - язык калека и что даже "честного" многоветочного if там нет. Но неужели ваш хвалёный оптимизатор неспособен распознать такую ситуацию? Вы уверены? Исходники смотрели? Тесты?

Пока пруфы не запилите, я буду считать вас пустословами.  

kemiisto, я часто слышу от вас такие слова. А какой язык вы считаете достойным почитания? просто интересно.

Ну просто Первое, что попалось на глаза
Уже даже при 5 кейсах свитч обгоняет ифы.
Впрочем, дальше искать не стал, так как я ничего никому доказывать не собираюсь.
Если вам действительно интересно, все сможете найти.

если вкусы не изменились, то Оберон.

Почитания - никакой. 


Ты мало бываешь в Интернетах. Эти слова уже лет 20 как повсюду.  Я вообще иногда не уверен, что появилось раньше - С++ или негативное к нему отношение.  Но ни каждому дано увидеть и услышать. Я уж молчу про сравнить, понять, сделать выводы...


1) Это результаты на конкретной реализации. Не указано какой.
2) Нет ключей компилятора (настроек проекта).
3) Of course, this wouldn’t even be noticeable in most applications.
4) [...] timings may vary quite a bit [...]


Запомни, как писать эту фразу правильно в Интернетах: "Я сливаю базар."  

а что нужно доказывать? тут ктото диссертацию пишет? ТС видимо ожидал ответа нечто вроде "при 20ти"  

Ну недолго ему (C++) осталось. Еще лет 20 и все перейдут на оберон.

http://forum.vingrad.ru/index.php?showtopi...t&p=2130619

borisbn, ну вот уже что-то. Хорошо, показана эта самая таблица смещений, или как вы её там называете. Теперь надобно на рельном (из практики) конечном автомате показать, что будет:

• Существенный значимый выигрышь в скорости; т.е. начинаем с 2x при времени выполнения алгоритма ~5-10 минут.
• Этот участок кода будет лимитирующим для скорости выполнения программы в целом. ТС ведь не "КА в себе" пишет. Для начала стоит посмотреть, стоит ли игра свеч.

volatile, заметь, ты сейчас отвечал не мне. Т.к.

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

  
я ничего не путаю, вопрос тс ведь был :

т.е. вопрос не о выйгрыше,а об отсутствии проигрыша.. 

Путаешь.  ТС ответ уже получил. Сейчас мв обсуждаем вот это:

   
Но т.к.  мне ничего не остается как, использовать switch.
Не заморачиваться же с goto  

Это сообщение отредактировал(а) rudvil - 23.3.2011, 12:49

причем тут goto? все операторы ветвлений (условий и циклов) реализуются через (условные) переходы. Поэтому самостоятельно связываться с goto смысла в 99,99% случаев нет никакого.

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