c переключать и прыгать таблицы
Насколько я понимаю, оператор switch в c / c ++ иногда компилируется в таблицу переходов.
У меня вопрос, есть ли какие-нибудь правила большого пальца, чтобы это гарантировать?
В моем случае я делаю что-то вроде этого:
enum myenum{
MY_CASE0= 0,
MY_CASE0= 1,
.
.
.
};
switch(foo)
{
case MY_CASE0:
//do stuff
break;
case MY_CASE1:
//do stuff
break;
.
.
.
}
Я покрываю все случаи от 1 до n по порядку. Можно ли предположить, что он скомпилируется в таблицу переходов?
Оригинальный код был длинным и грязным if else заявление, так что по крайней мере я получаю некоторую читаемость.
Решение
Хороший компилятор может и будет выбирать между таблицей переходов, цепочкой if / else или комбинацией. Плохо спроектированный компилятор не может сделать такой выбор — и может даже создать очень плохой код для блоков переключателей. Но любой достойный компилятор должен создавать эффективный код для блоков переключателей. T
Здесь основным фактором принятия решения является то, что компилятор может выбрать, если / иначе, когда числа находятся далеко друг от друга [и нетривиально (например, делится на 2, 4, 8, 16, 256 и т. д.), чтобы они стали ближе к значению], например,
switch(x)
{
case 1:
...
case 4912:
...
case 11211:
...
case 19102:
...
}
потребуется таблица переходов не менее 19102 * 2 байта.
С другой стороны, если числа близки друг к другу, компилятор обычно использует таблицу переходов.
Даже если это if/else Тип дизайна, он обычно выполняет «бинарный поиск» — если мы возьмем приведенный выше пример:
if (x <= 4912)
{
if (x == 1)
{
....
}
else if (x == 4912)
{
....
}
} else {
if (x == 11211)
{
....
}
else if (x == 19102)
{
...
}
}
Если у нас будет много случаев, этот подход будет достаточно глубоким, и люди, вероятно, потеряются после трех или четырех уровней глубины (имея в виду, что каждый из них начинается в какой-то момент в СРЕДНЕМ диапазоне), но он уменьшает количество тестов по log2 (n), где n — количество вариантов. Это, конечно, намного эффективнее, чем наивный подход
if (x == first value) ...
else if (x == second value) ...
else if (x == third value) ...
..
else if (x == nth value) ...
else ...
Это может быть немного лучше, если определенные значения помещаются в начало цепочки if-else, но это предполагает, что вы можете определить, что является наиболее распространенным, перед запуском кода.
Если производительность имеет решающее значение для вашего случая, то вам нужно сравнить две альтернативы. Но я предполагаю, что простое написание кода в качестве переключателя сделает код более понятным и в то же время будет работать по крайней мере так же быстро, если не быстрее.
Другие решения
Компиляторы, безусловно, могут преобразовать любой переключатель C / C ++ в таблицу переходов, но компилятор сделает это для эффективности. Спросите себя, что бы я сделал, если бы писал компилятор и только что построил дерево разбора для оператора switch / case? Я изучил проектирование и конструирование компилятора, и вот некоторые из решений,
Как помочь компилятору решить реализовать таблицу переходов:
- значения регистра являются маленькими целыми числами (0,1,2,3, …)
- значения регистра находятся в компактном диапазоне (несколько отверстий, помните, по умолчанию это опция)
- Есть достаточно случаев, чтобы сделать оптимизацию стоящей (> N, проверьте исходный код компилятора, чтобы найти константу)
- умные компиляторы могут вычесть / добавить константу к индексу перемычки, если диапазон компактен (например: 1000, 1001, 1002, 1003, 1004, 1005 и т. д.)
- избежать падения и передачи контроля (перейти, продолжить)
- только один перерыв в конце каждого случая
Хотя механика может отличаться в разных компиляторах, компилятор по существу создает неназванные функции (ну, может быть, это не функция, потому что компилятор может использовать переход в блок кода и переход из блока кода, или может быть умным и использовать jsr и return)
Определенный способ получить таблицу переходов — написать ее. Это массив указателей на функции, проиндексированный по желаемому значению.
Как?
Определите typedef для вашего указателя функции, Понимание typedefs для указателей на функции в C,
typedef void (* FunkPtr) (double a1, double a2);
FunkPtr JumpTable[] = {
function_name_0,
function_name_1,
function_name_2,
...
function_name_n
};
Конечно, вы уже определили имя_функции_ {0..n}, поэтому компилятор может найти адрес вызываемой функции.
Я оставлю вызов функции-указателя и проверку границ в качестве упражнения для читателя.
Принятый подход полностью зависит от компилятора.
Но учтите, что из-за вашего break заявления, это не отражает чистый прыгать стол на ассемблере, поэтому я бы поставил против него. Но это всего лишь пари; Я не пишу компиляторы C ++.
С switch, вы тестируете только одно условие (как бы тщательно оно ни было), но с if / else вы тестируете несколько; хотя вы можете оптимизировать, поставив на первый план наиболее вероятные случаи. Это может быть быстрее, чем сложный switch, Это, вероятно, основные соображения оптимизации для вас; Я бы не стал слишком беспокоиться о выборе компилятора.