Эффективность switch в C

Методы есть. Самы простой - написать кучу if-ов с else-ами, заботав метод двоичного поиска. Но это за тебя и компилятор сделает.

<offtop>

blacktiger, ты конфуист?

</offtop>

>blacktiger, ты конфуист?

Нет, я каратист. Но с ником это никак не связано :)

интересный вопрос. актуальный для GUI events loops.
когда-то верил, что switch очень эффективный, что-то типа
доступа к эллементу массива по его индексу, и возможно
"hardware accelerated". один случай поверг мою веру.
switch с большим числом cases (даже пустых) может "заметно"
тормозить event loop. Однако во всех GUI events loops,
которые видел (qt, fox-toolkit, gdk-x11, gdk-win32 ...)
не припоминаю никакой optimization - везде "тупой" switch.
Может кто-нибудь опровергнет ...

Смотри на то, как писан интерпретатор шитого байткода в OCaml, с использованием GCC-шных расширений.

> Смотри на то, как писан интерпретатор шитого байткода в OCaml, с использованием GCC-шных расширений
имеется ввиду это?
http://camlcvs.inria.fr/cgi-bin/cvsweb/ocaml/byterun/interp.c?rev=1.91;conten...

Именно.

спасибо за ссылку, обязательно разберусь. Я слышал краем уха об direct threading, только вот реализацию увидел впервые. Еще вопрос - этот прием, я так понял что там вся загвоздка в безусловных переходах, действительно будет работать только под gcc или существует возможность портировать на другие компиляторы - в частности интересует VC++ (не сочтите за офтопик, просто интересно кросс-платформенное решение).

Только GCC. Для других компиляторов тот же код компилится через switch...

Не пойму одного, что мешает сделать массив обработчиков байт кода?

typedef void (*Opcode)(); Opcode opcode_handlers[????] = { ... };

....

opcode_handlers[opcode_to_handle]();

....

По идее, умный компилятор должен уметь разворачивать switch в дерево if-ов или даже в таблицу (если значения плотно лежат).

Более того, смутно вспоминая свой реверс-инжинириг старой игрушки, я вспоминаю, что некоторые switch-и там были откомпилированны именно так - таблицей (правда, это было так только в ситуации, когда ключи представляли собой один непрерывный промежуток). А ведь компилятор был даже более ранний, чем Borland C++ 3.1 :)

Сильно зависит от компилятора. Как правило есть два варианта: либо развернуть все в цепочку if'ов, либо через хэш-таблицу. AFAIK практически все компилтяторы умеют делать последнее. Еще есть такое _негласное_ правило - предполагается, что значения ближе к началу switch'а совпадают чаще, и компилятор может на это полагаться...

>Сильно зависит от компилятора. Как правило есть два варианта: либо развернуть все в цепочку if'ов [...]

Можно в сбалансированное бинарное дерево. Правда, в общем случае хорошо сбалансированное дерево можно построить только имея статистику.

> Можно в сбалансированное бинарное дерево.

Какие компиляторы это умеют?

>Какие компиляторы это умеют?

Не знаю. Вроде как .NET JIT такое делает, но не уверен.

Вызов функций в стиле opcode_handlers[opcode_to_handle]();
штука относительно дорогая.
switch оказывается в несколько раз дешевле.
Большинство компиляторов имеет автоматические средства для выбора
способа генерации кода. Т.е. switch в зависимости от состава case
либо генерируется в таблицу (с одним if перед обращением к таблице
для отсечения выходящих за диапазон) - что предпочтительнее,
либо в набор if-ов. Правда и набор if-ов оптимизируется с учетом
того, что используется одно и то же значение для сравнения.
Таблица генерируется и в том случае, когда бывают некоторые разрывы,
никто не мешает добавить пару скрытых goto в таблице на default.
Естественно, что вычисляемые goto *label[n] могут и выигрывать
и слегка проигрывать switch в различных ситуациях.
Возможность игры на макро полезна.

>Вызов функций в стиле opcode_handlers[opcode_to_handle](); штука относительно дорогая.

Но ведь прыжок по таблице - это то же самое. Единственное, что код весь рядом находится, а не раскидан по разным функциям.

>Вызов функций в стиле opcode_handlers[opcode_to_handle](); штука относительно дорогая.

>Но ведь прыжок по таблице - это то же самое. Единственное, что код весь рядом находится, а не раскидан по разным функциям.

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

>Т.е. switch в зависимости от состава case либо генерируется в таблицу (с одним if перед обращением к таблице для отсечения выходящих за диапазон) - что предпочтительнее, либо в набор if-ов.

Т.е. если у меня варианты case лежат в непрерывном диапазоне, то я могу расчитывать на нормальную оптимизацию со стороны компилятора?

В большинстве компиляторов - да (в gcc в частности).