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

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

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

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

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

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

 ... validate x                    /* transform x to 0 (invalid) or 1,2,3, according to value..)    */
       y = x * 4;                  /* multiply by branch instruction length (e.g. 4 )               */
       goto next + y;              /* branch into 'table' of branch instructions                    */
 /* start of branch table */
 next: goto codebad;               /* x= 0  (invalid)                                               */
       goto codeone;               /* x= 1                                                          */
       goto codetwo;               /* x= 2                                                          */
 ... rest of branch table
 codebad:                          /* deal with invalid input                                       */

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

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

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

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

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

История

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

встроенное программирование
разработка операционной системы . Во многих операционных системах как системные вызовы , так и библиотечные функции могут ссылаться на целочисленный индекс в таблице ветвей.
некоторые компьютерные архитектуры, такие как IBM/360, используют таблицы ветвей для диспетчеризации прерываний.

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

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

компактная структура кода (несмотря на повторяющиеся коды операций ветвления)
сокращенные исходные данные (по сравнению с повторяющимися If заявления)
снижение требований к индивидуальной проверке кодов возврата (если они используются на месте вызова для определения последующего хода программы )
Алгоритмическая эффективность и эффективность кода (данные необходимо закодировать только один раз, а код таблицы ветвей обычно компактен), а также возможность достижения высоких коэффициентов сжатия данных . Например, при сжатии названий стран в коды стран такую строку, как «Центральноафриканская Республика», можно сжать до одного индекса, что приводит к значительной экономии, особенно если строка появляется много раз. Кроме того, этот же индекс можно использовать для доступа к связанным данным в отдельных таблицах, что еще больше снижает требования к хранению.

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

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

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

Недостатки

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

Пример

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

     movf    INDEX,W     ; Move the index value into the W (working) register from memory
     addwf   PCL,F       ; add it to the program counter. Each PIC instruction is one byte
                         ; so there is no need to perform any multiplication. 
                         ; Most architectures will transform the index in some way before 
                         ; adding it to the program counter.

 table                   ; The branch table begins here with this label
     goto    index_zero  ; each of these goto instructions is an unconditional branch
     goto    index_one   ; of code.
     goto    index_two
     goto    index_three

 index_zero
     ; Code is added here to perform whatever action is required when INDEX = zero
     return

 index_one
 ...

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

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

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

#include <stdio.h>
#include <stdlib.h>

typedef void (*Handler)(void);    /* A pointer to a handler function */

/* The functions */
void func3 (void) { printf( "3\n" ); }
void func2 (void) { printf( "2\n" ); }
void func1 (void) { printf( "1\n" ); }
void func0 (void) { printf( "0\n" ); }

Handler jump_table[4] = {func0, func1, func2, func3};

int main (int argc, char **argv) {
    int value;

    /* Convert first argument to 0-3 integer (modulus) */
    value = atoi(argv[1]) % 4;

    /* Call appropriate function (func0 thru func3) */
    jump_table[value]();

    return 0;
}

Пример таблицы переходов в PL/I

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

    declare lab (10) label;
    declare x fixed binary;
    goto lab(x);
  lab(1): /* code for choice 1 */ ;
    ...
  lab(2): /* code for choice 2 */ ;
    ...

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

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

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

Сначала проверьте ключ поиска = 1000 и выполните соответствующий переход.
Позвольте компилятору «выбрать» создание таблицы ветвей по оставшимся ключам поиска (1–50).

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

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

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

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

[1] Пример таблицы ветвей в Wikibooks для IBM S/360.
[2] Примеры и аргументы для таблиц переходов через массивы указателей функций в C / C++.
[3] Пример кода, созданного с помощью таблицы ветвей Switch/Case на языке C, в сравнении с IF/ELSE.
[4] Пример кода, созданного для индексации массива, если размер структуры делится на степени 2 или нет.
[5] «Массивы указателей на функции», Найджел Джонс.

[1] Пейдж, Дэниел (2009). Практическое введение в архитектуру компьютера . Springer Science & Business Media. п. 479. ИСБН 9781848822559 .

[2] Джонс, Найджел (1 мая 1999 г.). «Как создавать таблицы переходов с помощью массивов указателей функций в C и C++» . Архивировано из оригинала 12 февраля 2012 года . Проверено 12 июля 2008 г.

[GNU-3] «Альтернативные точки входа (ВХОД)» . Использование и портирование GNU Fortran . Фонд свободного программного обеспечения. 07.06.2001 . Проверено 25 ноября 2016 г.

[RET-4] Томас, Р.Э. (29 апреля 1976 г.). «Компиляторы и загрузчики ФОРТРАНа» . ACD: Инженерный документ № 42 . АКД . Проверено 10 апреля 2009 г.

[F90-5] «Краткое введение в Фортран 90» . Уменьшающиеся/устаревшие/избыточные функции . Проверено 10 апреля 2009 г.

[1]

[2]

[3]

[4]

[5]