stringtranslate.com

Таблица филиалов

В компьютерном программировании таблица ветвей или таблица переходов — это метод передачи программного управления ( ветвления ) другой части программы (или другой программе, которая могла быть динамически загружена) с использованием таблицы инструкций ветвления или перехода . Это форма многосторонней ветки . Конструкция таблицы ветвей обычно используется при программировании на языке ассемблера , но также может создаваться компиляторами , особенно при реализации оптимизированных операторов переключения , значения которых плотно упакованы вместе. [1]

Типичная реализация

Таблица ветвления состоит из последовательного списка инструкций безусловного ветвления , который разветвляется с использованием смещения , созданного путем умножения последовательного индекса на длину инструкции (количество байтов в памяти, занимаемых каждой командой ветвления). Он основан на том факте, что инструкции машинного кода для ветвления имеют фиксированную длину и могут чрезвычайно эффективно выполняться большинством аппаратных средств, а также наиболее полезны при работе со значениями необработанных данных , которые можно легко преобразовать в значения последовательного индекса. Учитывая такие данные, таблица ветвей может быть чрезвычайно эффективной. Обычно он состоит из следующих 3 шагов:

  1. опциональная проверка входных данных, чтобы убедиться в их приемлемости (это может произойти бесплатно как часть следующего шага, если входные данные представляют собой один байт и для непосредственного получения смещения, указанного ниже, используется 256-байтовая таблица преобразования). Также, если нет сомнений в значениях входных данных, этот шаг можно пропустить.
  2. преобразовать данные в смещение в таблице ветвей. Обычно это включает в себя умножение или сдвиг (фактически умножение на степень 2), чтобы принять во внимание длину инструкции. Если используется статическая таблица преобразования, это умножение может выполняться вручную или с помощью компилятора без каких-либо затрат времени выполнения.
  3. переход по адресу, состоящему из базового адреса таблицы ветвей плюс только что сгенерированное смещение. Иногда это включает в себя добавление смещения в регистр счетчика программы (если только в некоторых наборах команд инструкция ветвления не позволяет использовать дополнительный индексный регистр). Этот конечный адрес обычно указывает на одну из последовательности инструкций безусловного перехода или на команду, следующую за ними (сохраняя одну запись в таблице).

Следующий псевдокод иллюстрирует концепцию

 ... проверить x /* преобразовать x в 0 (недопустимое) или 1,2,3, в зависимости от значения..) */ y = x * 4 ; /* умножаем на длину инструкции перехода (например, 4) */ goto next + y ; /* переход в «таблицу» инструкций перехода */ /* начало таблицы переходов */ next : goto codebad ; /* x= 0 (неверно) */ goto codeone ; /* x= 1 */ перейти к коду два ; /* x= 2 */ ... остальная часть таблицы ветвей codebad : /* обработка недопустимого ввода */

Альтернативная реализация с использованием адресов

Другой метод реализации таблицы ветвей — использование массива указателей , из которого извлекается адрес требуемой функции . Первоначально известный как вектор переноса , в последнее время этот метод также известен под такими разными названиями, как « таблица диспетчеризации » или « таблица виртуальных методов », но по сути выполняет одну и ту же цель. Этот метод функции указателя может привести к сохранению одной машинной инструкции и позволяет избежать косвенного перехода (к одной из инструкций ветвления).

Результирующий список указателей на функции почти идентичен прямому многопоточному коду и концептуально подобен управляющей таблице .

Фактический метод, используемый для реализации таблицы ветвей, обычно основан на:

История

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

Преимущества

К преимуществам таблиц ветвей относятся:

Для библиотечных функций, где на них можно ссылаться целым числом :

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

Недостатки

Пример

Простой пример использования таблицы ветвей на 8-битном языке ассемблера Microchip PIC :

 movf ИНДЕКС , Вт ; Переместить значение индекса в регистр W (рабочий) из памяти addwf PCL , F ; добавьте его в счетчик программ. Каждая инструкция PIC имеет размер одного байта ; поэтому нет необходимости выполнять какое-либо умножение. ; Большинство архитектур заранее каким-то образом преобразуют индекс ; добавив его в счетчик программ.         стол ; Таблица ветвей начинается здесь с метки goto index_zero ; каждая из этих инструкций перехода является безусловным переходом перехода index_one ; кода. перейти к index_two перейти к index_three            индекс_ноль ; Здесь добавляется код для выполнения любого действия, которое требуется, когда ИНДЕКС = нулевой возврат.   индекс_один ...

Примечание: этот код будет работать только в том случае, если PCL < (table + index_last). Чтобы обеспечить это условие, мы можем использовать директиву «org». А если GOTO (например, PIC18F) имеет размер 2 байта, это ограничивает количество записей таблицы до значения менее 128.

Пример таблицы переходов на C

Еще один простой пример, на этот раз демонстрирующий таблицу переходов, а не просто таблицу ветвей. Это позволяет вызывать программные блоки за пределами текущей активной процедуры/функции:

#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 реализует таблицу переходов как массив переменных-меток . Их можно инициализировать необычным способом, используя метку оператора с индексом. Переменные меток PL/I — это не просто адрес оператора, но обычно содержат дополнительную информацию о состоянии блока кода, которому они принадлежат. Без необычной инициализации это также можно было бы закодировать с помощью вызовов и массива входных переменных.

 объявить этикетку лаборатории (10); объявить x фиксированным двоичным кодом; перейти в лабораторию (х); lab(1): /* код для выбора 1 */ ; ... lab(2): /* код для варианта 2 */ ; ...

Таблицы ветвей, созданные компилятором

Программисты часто оставляют решение о создании таблицы ветвей компилятору, полагая, что он вполне способен сделать правильный выбор из известных ключей поиска. Это может быть справедливо для оптимизации компиляторов для относительно простых случаев, когда диапазон ключей поиска ограничен. Однако компиляторы не так умны, как люди, и не могут обладать глубокими знаниями «контекста», полагая, что диапазон возможных целочисленных значений ключа поиска, таких как 1, 2, 4, 6, 7, 20, 23, 40, 42, 50 и 1000 создадут таблицу ветвей с чрезмерно большим количеством пустых записей (900+) с очень небольшим преимуществом. Хороший оптимизирующий компилятор может затем предварительно отсортировать значения и сгенерировать код для двоичного поиска, что является «вторым лучшим» вариантом. Фактически, приложение может быть очень «критичным ко времени», и требования к памяти могут вообще не быть проблемой. [2]

Однако немного «здравого смысла» может превратить этот конкретный случай и многие другие подобные случаи в простой двухэтапный процесс с очень большой потенциальной экономией, при этом в конечном итоге оставляя окончательный выбор за составителем, но «помогая ему в принятии решения». значительно:

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

Вычисленный переход

Хотя этот метод теперь известен как «таблицы ветвей», первые пользователи компиляторов называли реализацию « вычисленным GoTo », ссылаясь на инструкцию, найденную в серии компиляторов Fortran. [3] [4] В конечном итоге эта инструкция была признана устаревшей в Фортране 90 (в пользу операторов SELECT и CASE на уровне исходного кода). [5]

Создание индекса для таблицы ветвей

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

В некоторых случаях для формирования индекса может потребоваться хеш -таблица . Однако для однобайтовых входных значений, таких как AZ (или первый байт более длинного ключа), содержимое самого байта ( необработанные данные ) может использоваться в двухэтапном « тривиальном хеш-функции » для получения конечный индекс для таблицы ветвей с нулевыми пробелами.

  1. Преобразуйте символ необработанных данных в его числовой эквивалент (пример ASCII 'A' ==> 65 десятичный, 0x41 шестнадцатеричный).
  2. Используйте числовое целое значение в качестве индекса в 256-байтовом массиве, чтобы получить второй индекс (недопустимые записи 0; представляют пробелы, в противном случае 1, 2, 3 и т. д.).

Массив будет не больше (256 x 2) байтов, чтобы вместить все возможные 16-битные беззнаковые (короткие) целые числа. Если проверка не требуется и используются только заглавные буквы, размер массива может составлять всего (26 x 2) = 52 байта.

Другое использование техники

Хотя метод ветвления с использованием таблицы ветвей чаще всего используется исключительно с целью изменения хода выполнения программы — для перехода к метке программы, которая является безусловным переходом, — тот же метод можно использовать и для других целей. Например, его можно использовать для выбора начальной точки в последовательности повторяющихся инструкций, где пропуск является нормой и намеренно. Это можно использовать, например, для оптимизации компиляторов или JIT- компиляторов при развертывании цикла .

Смотрите также

Рекомендации

  1. ^ Пейдж, Дэниел (2009). Практическое введение в архитектуру компьютера . Springer Science & Business Media. п. 479. ИСБН 9781848822559.
  2. ↑ Джонс, Найджел (1 мая 1999 г.). «Как создавать таблицы переходов с помощью массивов указателей функций в C и C++». Архивировано из оригинала 12 февраля 2012 года . Проверено 12 июля 2008 г.
  3. ^ «Альтернативные точки входа (ВХОД)» . Использование и портирование GNU Fortran . Фонд свободного программного обеспечения. 07.06.2001 . Проверено 25 ноября 2016 г.
  4. ^ Томас, RE (29 апреля 1976 г.). «Компиляторы и загрузчики FORTRAN». ACD: Инженерный документ № 42 . АКД . Проверено 10 апреля 2009 г.
  5. ^ «Краткое введение в Фортран 90». Уменьшенные/устаревшие/избыточные функции . Проверено 10 апреля 2009 г.

Внешние ссылки

Викискладе есть медиафайлы по теме таблицы Branch .