c переключать и прыгать таблицы

Question

Насколько я понимаю, оператор 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 заявление, так что по крайней мере я получаю некоторую читаемость.

Answer 1

Хороший компилятор может и будет выбирать между таблицей переходов, цепочкой 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, но это предполагает, что вы можете определить, что является наиболее распространенным, перед запуском кода.

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

Answer 2

Компиляторы, безусловно, могут преобразовать любой переключатель C/C++ в таблицу переходов, но компилятор сделает это для эффективности. Спросите себя, что бы я сделал, если бы писал компилятор и только что построил дерево разбора для оператора switch/case? Я изучил проектирование и конструирование компилятора, и вот некоторые из решений,

Как помочь компилятору решить реализовать таблицу переходов:

• значения регистра являются маленькими целыми числами (0,1,2,3,...)
• значения регистра находятся в компактном диапазоне (несколько отверстий, помните, по умолчанию это опция)
• есть достаточно случаев, чтобы сделать оптимизацию полезной (> N, проверьте исходный код компилятора, чтобы найти постоянную)
• умные компиляторы могут вычесть / добавить константу к индексу перемычки, если диапазон компактен (например: 1000, 1001, 1002, 1003, 1004, 1005 и т. д.)
• избежать падения и передачи контроля (перейти, продолжить)
• только один перерыв в конце каждого случая

Хотя механика может отличаться в разных компиляторах, компилятор по существу создает неназванные функции (ну, может быть, это не функция, потому что компилятор может использовать переход в блок кода и переход из блока кода или может быть умным и использовать jsr и return)

Определенный способ получить таблицу переходов - написать ее. Это массив указателей на функции, проиндексированный по желаемому значению.

Как?

Определите typedef для вашего указателя функции, Понимание typedef для указателей на функции в C,

typedef void (* FunkPtr) (double a1, double a2);

FunkPtr JumpTable[] = {
    function_name_0,
    function_name_1,
    function_name_2,
    ...
    function_name_n
};

Конечно, вы уже определили имя_функции_{0..n}, поэтому компилятор может найти адрес вызываемой функции.

Я оставлю вызов функции-указателя и проверку границ в качестве упражнения для читателя.

Answer 3

Принятый подход полностью зависит от компилятора.

Но учтите, что из-за вашего break Заявления, он не отражает чистую таблицу переходов в ассемблере, поэтому я бы сделал ставку против этого. Но это всего лишь пари; Я не пишу компиляторы C++.

С switch, вы тестируете только одно условие (как бы тщательно оно ни было), но с if / else вы тестируете несколько; хотя вы можете оптимизировать, поставив наиболее вероятные случаи на первое место. Это может быть быстрее, чем сложный switch, Это, вероятно, основные соображения оптимизации для вас; Я бы не стал слишком беспокоиться о выборе компилятора.