c switch and jump tables

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

Answer 1

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

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

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

Answer 2

Хороший компилятор может и будет выбирать между таблицей прыжков, цепью if/else или комбинацией. Плохо разработанный компилятор не может сделать такой выбор - и даже может создать очень плохой код для коммутационных блоков. Но любой достойный компилятор должен создать эффективный код для блоков-переключателей. T

Основным фактором принятия решения здесь является то, что компилятор может выбрать, если/else, когда числа находятся далеко друг от друга [и не тривиально (например, деление на 2, 4, 8, 16, 256 и т. Д.) Изменено на более близкое значение] , например

switch(x) 
{ 
    case 1: 
    ... 
    case 4912: 
    ... 
    case 11211: 
    ... 
    case 19102: 
    ... 
} 

потребует таблицы перехода не менее 19102 * 2 байта.

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

Даже если это if/else типа дизайна, он обычно будет делать «двоичный поиск» - если мы возьмем вышеприведенный пример:

if (x <= 4912) 
{ 
    if (x == 1) 
    { 
     .... 
    } 
    else if (x == 4912) 
    { 
     .... 
    } 
} else { 
    if (x == 11211) 
    { 
     .... 
    } 
    else if (x == 19102) 
    { 
     ... 
    } 
} 

Если у нас есть много случаев, этот подход будет гнездо достаточно глубоко , и люди, вероятно, потеряются после трех или четырех уровней глубины (имея в виду, что каждый из них начинается в какой-то точке MIDDLE диапазона), но он уменьшает количество тестов с помощью log2 (n), где n является количество вариантов. Это, конечно, гораздо более эффективное, чем наивный подход

if (x == first value) ... 
else if (x == second value) ... 
else if (x == third value) ... 
.. 
else if (x == nth value) ... 
else ... 

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

Если производительность КРИТИЧЕСКОГО для вашего случая, вам необходимо сравнить два варианта. Но я предполагаю, что просто написать код в качестве переключателя сделает код более понятным и в то же время будет работать как минимум так быстро, если не быстрее.

Answer 3

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

Как помочь компилятору решить осуществить прыжок таблицу:

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

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

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

Как?

Определение ЬурейеГо для указателя функции, Understanding typedefs for function pointers in C,

ЬурейеЙ пустоты (* FunkPtr) (двойная a1, a2 двойных);

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

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

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