В компьютерном программировании таблица ветвлений или таблица переходов — это метод передачи управления программой ( ветвления ) в другую часть программы (или другую программу, которая могла быть динамически загружена) с использованием таблицы инструкций ветвления или перехода . Это форма многоканального ветвления . Конструкция таблицы ветвлений обычно используется при программировании на языке ассемблера , но также может быть сгенерирована компиляторами , особенно при реализации оптимизированных операторов switch, значения которых плотно упакованы вместе. [1]
Таблица ветвлений состоит из последовательного списка инструкций безусловного ветвления , которые разветвляются с использованием смещения , созданного путем умножения последовательного индекса на длину инструкции (количество байтов в памяти, занимаемых каждой инструкцией ветвления). Она основана на том факте, что инструкции машинного кода для ветвления имеют фиксированную длину и могут быть выполнены чрезвычайно эффективно большинством оборудования, и наиболее полезна при работе с необработанными значениями данных , которые могут быть легко преобразованы в последовательные значения индекса. При наличии таких данных таблица ветвлений может быть чрезвычайно эффективной. Обычно она состоит из следующих 3 шагов:
Следующий псевдокод иллюстрирует концепцию
... validate x /* преобразуем x в 0 (недопустимо) или 1,2,3, в зависимости от значения..) */ y = x * 4 ; /* умножаем на длину инструкции ветвления (например, 4 ) */ goto next + y ; /* переходим в «таблицу» инструкций ветвления */ /* начало таблицы ветвления */ next : goto codebad ; /* x= 0 (недопустимо) */ goto codeone ; /* x= 1 */ goto codetwo ; /* x= 2 */ ... остальная часть таблицы ветвления codebad : /* работаем с недопустимым вводом */ Другой метод реализации таблицы ветвлений — массив указателей , из которого извлекается адрес требуемой функции . Первоначально известный как вектор переноса , этот метод также в последнее время известен под другими названиями, такими как « таблица диспетчеризации » или « таблица виртуальных методов », но по сути выполняющий ту же самую цель. Этот метод функции указателя может привести к экономии одной машинной инструкции и избежать косвенного перехода (к одной из инструкций ветвления).
Полученный список указателей на функции практически идентичен прямому потоковому коду и концептуально похож на управляющую таблицу .
Фактический метод, используемый для реализации таблицы ветвлений, обычно основан на:
Использование таблиц ветвлений и других необработанных кодировок данных было распространено на заре вычислений, когда память была дорогой, процессоры были медленнее, а компактное представление данных и эффективный выбор альтернатив были важны. В настоящее время они по-прежнему широко используются в:
Преимущества таблиц ветвлений включают в себя:
Ifутверждениями)Для библиотечных функций, где на них можно ссылаться с помощью целого числа :
Кроме того, вызов функций по номеру (индексу в таблице) иногда может быть полезен в некоторых случаях при обычном программировании приложений.
Простой пример использования таблицы ветвлений в языке ассемблера 8-битного Microchip PIC :
movf INDEX , W ; Переместить значение индекса в регистр W (рабочий) из памяти addwf PCL , F ; добавить его в счетчик программ. Каждая инструкция PIC — это один байт ; поэтому нет необходимости выполнять какое-либо умножение. ; Большинство архитектур преобразуют индекс каким-либо образом перед ; добавлением его в счетчик программ. table ; Таблица ветвлений начинается здесь с этой метки goto index_zero ; каждая из этих инструкций goto является безусловным переходом goto index_one ; кода. goto index_two goto index_three index_zero ; Здесь добавляется код для выполнения любого действия, которое требуется, когда ИНДЕКС = ноль return индекс_один ... Примечание: этот код будет работать только если PCL < (table + index_last). Чтобы обеспечить это условие, мы можем использовать директиву "org". А если GOTO (например, PIC18F) составляет 2 байта, это ограничивает количество записей в таблице до менее 128.
Еще один простой пример, на этот раз демонстрирующий таблицу переходов, а не просто таблицу ветвлений. Это позволяет вызывать программные блоки за пределами текущей активной процедуры/функции:
#include <stdio.h> #include <stdlib.h> typedef void ( * Handler )( void ); /* Указатель на функцию-обработчик */ /* Функции */ void func3 ( void ) { printf ( "3 \n " ); } void func2 ( void ) { printf ( "2 \n " ); } void func1 ( void ) { printf ( "1 \n " ); } void func0 ( void ) { printf ( "0 \n " ); } Обработчик jump_table [ 4 ] = { func0 , func1 , func2 , func3 }; int main ( int argc , char ** argv ) { int value ; /* Преобразовать первый аргумент в целое число 0-3 (модуль) */ value = atoi ( argv [ 1 ]) % 4 ; /* Вызов соответствующей функции (func0 - func3) */ jump_table [ value ](); вернуть 0 ; } PL/I реализует таблицу переходов как массив переменных меток . Они могут быть инициализированы необычным способом с помощью индексированной метки оператора. Переменные меток PL/I не просто являются адресом оператора, но обычно содержат дополнительную информацию о состоянии блока кода, к которому они принадлежат. Без необычной инициализации это также можно было бы закодировать с помощью вызовов и массива переменных входа.
объявить этикетку лаборатории (10); объявить x фиксированным двоичным; перейти в лаб(x); lab(1): /* код для выбора 1 */ ; ... lab(2): /* код для варианта 2 */ ; ...
Программисты часто оставляют решение о том, создавать или нет таблицу ветвлений, компилятору, полагая, что он вполне способен сделать правильный выбор из известных ключей поиска. Это может быть справедливо для оптимизирующих компиляторов для относительно простых случаев, когда диапазон ключей поиска ограничен. Однако компиляторы не так разумны, как люди, и не могут обладать глубоким знанием «контекста», полагая, что диапазон возможных целочисленных значений ключа поиска, таких как 1, 2, 4, 6, 7, 20, 23, 40, 42, 50 и 1000, сгенерирует таблицу ветвлений с чрезмерно большим количеством пустых записей (900+) с очень небольшим преимуществом. Хороший оптимизирующий компилятор может затем предварительно отсортировать значения и сгенерировать код для двоичного поиска с отсечкой, как «второй лучший» вариант. Фактически, приложение может быть очень «критично по времени», а требования к памяти могут вообще не быть проблемой. [2]
Однако немного «здравого смысла» может превратить этот конкретный случай и многие другие подобные случаи в простой двухэтапный процесс с очень большой потенциальной экономией, в конечном итоге оставляя окончательный выбор за компилятором, но существенно «помогая ему в принятии решения»:
Вариации по схожим направлениям могут использоваться в случаях, когда имеются два набора коротких диапазонов с большим разрывом между диапазонами.
Хотя сейчас эта техника известна как «таблицы ветвлений», ранние пользователи компиляторов называли реализацию « вычисляемым GoTo », ссылаясь на инструкцию, найденную в серии компиляторов Fortran. [3] [4] В конечном итоге эта инструкция была устарела в Fortran 90 (в пользу операторов SELECT и CASE на уровне исходного кода). [5]
Если для таблицы ветвей не существует очевидного целочисленного значения, оно, тем не менее, может быть создано из ключа поиска (или части ключа поиска) с помощью некоторой формы арифметического преобразования или может быть просто номером строки базы данных или номером записи в массиве, содержащем ключ поиска, найденный во время предыдущей проверки ключа.
В некоторых случаях для формирования индекса может потребоваться хэш -таблица . Однако для однобайтовых входных значений, таких как AZ (или первый байт более длинного ключа), содержимое самого байта ( необработанные данные ) может использоваться в двухшаговом процессе « тривиальной хэш-функции » для получения окончательного индекса для таблицы ветвлений с нулевыми пробелами.
Массив не будет больше (256 × 2) байт для хранения 16-битных беззнаковых (коротких) целых чисел для всех возможных 8-битных байтов. Если проверка не требуется и используются только заглавные буквы, размер массива может быть таким же маленьким, как (26 × 2) = 52 байта.
Хотя техника ветвления с использованием таблицы ветвлений чаще всего используется исключительно для изменения потока программы — для перехода к метке программы, которая является безусловным ветвлением — та же техника может использоваться и для других целей. Например, ее можно использовать для выбора начальной точки в последовательности повторяющихся инструкций, где пропуск является нормой и намеренным. Это может использоваться, например, оптимизирующими компиляторами или JIT -компиляторами при разворачивании цикла .
