Таблица ответвлений - Branch table

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

Типовая реализация

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

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

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

 ... 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                                       */

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

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

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

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

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

История

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

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

К преимуществам отраслевых таблиц можно отнести:

  • компактная структура кода (несмотря на повторяющиеся коды операций ветвления)
  • сокращенные исходные заявления (по сравнению с повторяющимися 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+) с очень небольшим преимуществом. Затем хороший оптимизирующий компилятор может предварительно отсортировать значения и сгенерировать код для двоичного поиска в качестве «второго лучшего» варианта. Фактически, приложение может быть очень «критичным по времени», и требования к памяти могут вообще не быть проблемой.

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

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

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

Вычисленный GoTo

Хотя сейчас этот метод известен как «таблицы ветвлений», первые пользователи компиляторов называли реализацию « вычисленным GoTo », ссылаясь на инструкцию, содержащуюся в серии компиляторов Fortran. В конечном итоге инструкция была объявлена ​​устаревшей в Fortran 90 (в пользу операторов SELECT & CASE на уровне исходного кода).

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

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

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

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

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

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

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

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

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

внешняя ссылка

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