В компьютерном программировании , таблица ветви или таблица скачка представляет собой способ передачи управления программы ( ветвление ) в другую часть программы (или другой программы , которые могут быть динамически загружаемой) с использованием таблицы ветвления или прыгать инструкции . Это форма разветвленной ветки . Конструкция таблицы переходов обычно используется при программировании на языке ассемблера, но также может создаваться компиляторами , особенно при реализации оптимизированных операторов переключения , значения которых плотно упакованы вместе. [1]
Типовая реализация
Таблица ветви состоит из последовательного списка безусловных отраслевых инструкций, разветвляются в используя смещение , созданное умножения на последовательный индекс по длине инструкции (число байт в памяти , занимаемом каждую инструкция ветвления). Он основан на том факте, что инструкции машинного кода для ветвления имеют фиксированную длину и могут быть чрезвычайно эффективно выполнены на большинстве аппаратных средств и наиболее полезны при работе со значениями необработанных данных, которые можно легко преобразовать в значения последовательных индексов. С такими данными таблица переходов может быть чрезвычайно эффективной. Обычно он состоит из следующих 3 шагов:
- необязательная проверка входных данных, чтобы убедиться, что они приемлемы (это может происходить бесплатно как часть следующего шага, если входные данные являются однобайтными и используется 256-байтовая таблица преобразования для непосредственного получения смещения, указанного ниже). Также, если нет сомнений в значениях входных данных, этот шаг можно пропустить.
- преобразовать данные в смещение в таблице переходов . Обычно это включает в себя умножение или сдвиг (эффективное умножение на степень 2), чтобы учесть длину инструкции. Если используется статическая таблица перевода, это умножение может выполняться вручную или компилятором без каких-либо затрат времени выполнения.
- переход к адресу, составленному из базового адреса таблицы переходов плюс только что сгенерированное смещение. Иногда это включает добавление смещения в регистр программного счетчика (если в некоторых наборах инструкций инструкция перехода не допускает дополнительный индексный регистр). Этот конечный адрес обычно указывает на одну из последовательности инструкций безусловного перехода или инструкцию сразу после них (сохранение одной записи в таблице).
Следующий псевдокод иллюстрирует концепцию
... проверить x / * преобразовать x в 0 (недействительно) или 1,2,3, в зависимости от значения ..) * / y = x * 4 ; / * умножение на длину инструкции перехода (например, 4) * / goto next + y ; / * переход в 'таблицу' инструкций перехода * / / * начало таблицы перехода * / next : goto codebad ; / * x = 0 ( неверно ) * / goto codeone ; / * x = 1 * / goto codetwo ; / * Х = 2 * / ... остальные из ветви таблицы codebad : / * Сделка с недопустимым вводом * /
Альтернативная реализация с использованием адресов
Другой способ реализации таблицы ветви с массивом из указателей , из которых требуемых функционального направления извлекается адрес. Этот метод также в последнее время известен под такими разными именами, как « таблица диспетчеризации » или « таблица виртуальных методов », но, по сути, выполняет ту же самую цель. Этот метод функции указателя может привести к сохранению одной машинной инструкции и позволяет избежать косвенного перехода (к одной из инструкций ветвления).
Результирующий список указателей на функции почти идентичен прямому многопоточному коду и концептуально аналогичен управляющей таблице .
Фактический метод, используемый для реализации таблицы переходов, обычно основан на:
- архитектура процессора, на котором должен выполняться код,
- будь то компилируемый или интерпретируемый язык и
- вовлечено ли позднее связывание или нет.
История
Использование таблиц переходов и другого кодирования необработанных данных было обычным явлением на заре вычислений, когда память была дорогой, процессоры были медленнее, а компактное представление данных и эффективный выбор альтернатив были важны. В настоящее время они все еще широко используются в:
- встроенное программирование
- разработка операционной системы . Во многих операционных системах на системные вызовы и библиотечные функции можно ссылаться с помощью целочисленного индекса в таблице переходов.
- некоторые компьютерные архитектуры, такие как IBM / 360, используют таблицы ветвлений для диспетчеризации прерываний
Преимущества
К преимуществам отраслевых таблиц можно отнести:
- компактная структура кода (несмотря на повторяющиеся коды операций ветвления)
- сокращенные исходные заявления (по сравнению с повторяющимися
If
заявлениями) - снижение требований к индивидуальному тестированию кодов возврата (если используется на месте вызова для определения последующего выполнения программы )
- Алгоритмическая эффективность и эффективность кода (данные необходимо кодировать только один раз, а код таблицы переходов обычно компактный), а также возможность достижения высоких степеней сжатия данных . Например, при сжатии названий стран в коды стран строка, такая как «Центральноафриканская Республика», может быть сжата до единого индекса, что дает значительную экономию, особенно когда строка встречается много раз. Кроме того, этот же индекс можно использовать для доступа к связанным данным в отдельных таблицах, что дополнительно снижает требования к хранению.
Для библиотечных функций, где на них можно ссылаться целым числом :
- улучшить совместимость с последующими версиями программного обеспечения. Если код функции и адрес ее точки входа изменяются, нужно настраивать только инструкцию перехода в таблице переходов; прикладное программное обеспечение, скомпилированное для библиотеки или для операционной системы, не требует модификации.
Кроме того, вызов функций по номеру (указателю в таблице) иногда может быть полезен в некоторых случаях в обычном прикладном программировании.
Недостатки
- Дополнительный уровень косвенности , который обычно незначительно снижает производительность.
- Ограничения в некоторых языках программирования, хотя обычно существуют альтернативные способы реализации базовой концепции многостороннего ветвления.
Пример
Простой пример использования таблицы переходов на 8-битном ассемблере Microchip PIC :
movf INDEX , W ; Переместите значение индекса в регистр W (рабочий) из памяти addwf PCL , F ; добавить его в счетчик программы. Каждая инструкция PIC - это один байт ; поэтому нет необходимости производить какое-либо умножение. ; Большинство архитектур раньше каким-либо образом преобразуют индекс ; добавляя его к счетчику программы. стол ; Таблица переходов начинается здесь с этой метки goto index_zero ; каждая из этих инструкций goto является безусловным переходом goto index_one ; кода. goto index_two goto index_three index_zero ; Сюда добавляется код для выполнения любых действий, которые требуются, когда INDEX = нулевой возврат. index_one ...
Примечание: этот код будет работать, только если PCL <(table + index_last). Чтобы обеспечить это условие, мы можем использовать директиву org. И если GOTO (например, PIC18F) составляет 2 байта, это ограничивает количество записей в таблице до менее 128.
Пример таблицы переходов на C
Еще один простой пример, на этот раз демонстрирующий таблицу переходов, а не простую таблицу переходов. Это позволяет вызывать программные блоки вне текущей активной процедуры / функции:
#include #include typedef void ( * Обработчик ) ( void ); / * Указатель на функцию-обработчик * // * Функции * / void func3 ( void ) { printf ( "3 \ n " ); } void func2 ( void ) { printf ( "2 \ п " ); } void func1 ( void ) { printf ( "1 \ п " ); } void func0 ( void ) { printf ( "0 \ п " ); }Обработчик jump_table [ 4 ] = { func0 , func1 , func2 , func3 };int main ( int argc , char ** argv ) { значение int ; / * Преобразование первого аргумента в целое число от 0 до 3 (модуль) * / value = atoi ( argv [ 1 ]) % 4 ; / * Вызов соответствующей функции (func0 thru func3) * / jump_table [ value ] (); возврат 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]
Создание индекса для таблицы переходов
Если для таблицы ветвления нет очевидного целочисленного значения, оно может быть создано из ключа поиска (или части ключа поиска) с помощью некоторой формы арифметического преобразования или может быть просто номером строки в базе данных или номером записи в массиве, содержащем ключ поиска, найденный во время предыдущей проверки ключа.
В некоторых случаях для формирования индекса может потребоваться хеш-таблица . Однако для однобайтовых входных значений, таких как AZ (или первый байт более длинного ключа), содержимое самого байта ( необработанные данные ) можно использовать в двухэтапном процессе « тривиальной хеш-функции » для получения окончательный индекс для таблицы переходов с нулевыми пробелами.
- Преобразуйте символ необработанных данных в его числовой эквивалент (пример ASCII 'A' ==> 65 десятичный, 0x41 шестнадцатеричный)
- Используйте числовое целочисленное значение в качестве индекса в массиве из 256 байт, чтобы получить второй индекс (недопустимые записи 0; представляют пробелы, в противном случае 1, 2, 3 и т. Д.)
Размер массива не должен превышать (256 x 2) байтов - для хранения всех возможных 16-разрядных целых чисел без знака (коротких). Если проверка не требуется и используется только верхний регистр, размер массива может быть таким маленьким, как (26 x 2) = 52 байта.
Другое использование техники
Хотя метод ветвления с использованием таблицы переходов чаще всего используется исключительно с целью изменения потока программы - для перехода к метке программы, которая является безусловным переходом, - этот же метод можно использовать для других целей. Например, его можно использовать для выбора начальной точки в последовательности повторяющихся инструкций, где пропуск является нормальным и преднамеренным. Это можно использовать, например, для оптимизации компиляторов или JIT- компиляторов при развертывании цикла .
Смотрите также
- Таблица отправки - таблица ветвей с другим именем, используемым для позднего связывания.
- Массивы указателей на функции адресов к функциям, используемые в таблицах переходов
- Косвенная ветвь
- Таблица поиска - массив элементов для сопоставления, иногда содержащий предварительно рассчитанные результаты.
- Оператор переключения - условный оператор на языке высокого уровня, который может генерировать таблицу ветвлений.
- Таблица виртуальных методов - таблица ветвей с другим именем с динамически назначаемыми указателями для диспетчеризации (см. Таблицу диспетчеризации)
Рекомендации
- ^ Пейдж, Дэниел (2009). Практическое введение в компьютерную архитектуру . Springer Science & Business Media. п. 479. ISBN 9781848822559.
- ^ Джонс, Найджел (1 мая 1999 г.). «Как создавать таблицы переходов с помощью массивов указателей функций в C и C ++» . Архивировано из оригинального 12 февраля 2012 года . Проверено 12 июля 2008 года .
- ^ «Альтернативные точки входа (ВХОД)» . Использование и перенос GNU Fortran . Фонд свободного программного обеспечения. 2001-06-07 . Проверено 25 ноября 2016 . CS1 maint: обескураженный параметр ( ссылка )
- ^ Томас, Р. Р. (1976-04-29). "Компиляторы и загрузчики FORTRAN" . ACD: Технический документ № 42 . ACD . Проверено 10 апреля 2009 . CS1 maint: обескураженный параметр ( ссылка )
- ^ «Краткое введение в Fortran 90» . Уменьшенные / устаревшие / избыточные функции . Проверено 10 апреля 2009 . CS1 maint: обескураженный параметр ( ссылка )
Внешние ссылки
- [1] Пример таблицы переходов в Викиучебнике для IBM S / 360
- [2] Примеры и аргументы для таблиц перехода через массивы указателей функций в C / C ++
- [3] Пример кода, сгенерированный таблицей ветвления 'Switch / Case' в C, по сравнению с IF / ELSE.
- [4] Пример кода, созданного для индексации массива, если размер структуры делится на степень 2 или иначе.
- [5] «Массивы указателей на функции» Найджела Джонса.