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

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

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

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

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

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

 ... подтверждать Икс                    / * преобразовываем x в 0 (неверно) или 1,2,3, в зависимости от значения ..) * /       у = Икс * 4;                  / * умножаем на длину инструкции перехода (например, 4) * /       идти к следующий + у;              / * переход в 'таблицу' инструкций перехода * / / * начало таблицы переходов * / следующий: идти к codebad;               / * x = 0 (неверно) * /       идти к codeone;               / * х = 1 * /       идти к codetwo;               / * х = 2 * / ... отдых из ответвляться стол codebad:                          / * обработаем неверный ввод * /

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

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

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

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

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

История

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

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

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

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

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

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

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

Недостатки

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

Пример

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

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

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

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

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

#включают <stdio.h>#включают <stdlib.h>typedef пустота (*Обработчик)(пустота);    / * Указатель на функцию-обработчик * // * Функции * /пустота func3 (пустота) { printf( "3 п" ); }пустота func2 (пустота) { printf( "2 п" ); }пустота func1 (пустота) { printf( "1 п" ); }пустота func0 (пустота) { printf( "0 п" ); }Обработчик jump_table[4] = {func0, func1, func2, func3};int главный (int argc, char **argv) {    int ценить;    / * Преобразование первого аргумента в целое число 0-3 (модуль) * /    ценить = ((атой(argv[1]) % 4) + 4) % 4;    / * Вызов соответствующей функции (func0 thru func3) * /    jump_table[ценить]();    возвращаться 0;}

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

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

    объявить ярлык lab (10); объявить фиксированный двоичный файл x; goto lab (x); lab (1): / * код для выбора 1 * /; ... lab (2): / * код для варианта 2 * /; ...

Сгенерированные компилятором таблицы ветвлений

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

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

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

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

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

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

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

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

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

  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. ISBN  9781848822559.
  2. ^ Джонс, Найджел (1 мая 1999 г.). "Как создавать таблицы переходов с помощью массивов указателей функций в C и C ++". Архивировано из оригинал 12 февраля 2012 г.. Получено 12 июля 2008.
  3. ^ «Альтернативные точки въезда (ВХОД)». Использование и перенос GNU Fortran. Фонд свободного программного обеспечения. 2001-06-07. Получено 2016-11-25.
  4. ^ Thomas, R.E. (1976-04-29). "Компиляторы и загрузчики FORTRAN". ACD: Технический документ № 42. ACD. Получено 2009-04-10.
  5. ^ "Краткое введение в Fortran 90". Уменьшенные / устаревшие / избыточные функции. Получено 2009-04-10.

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

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