Таблица переходов / переход — это то же самое, что разыменование указателя на функцию?
Я пытался узнать, что такое таблицы переходов, и мне сложно что-то понять. Из многих примеров, которые я видел, они, кажется, в значительной степени сводятся к этому, или, по крайней мере, это одна из версий этого:
void func1() {};
void func2() {};
void func3() {};
int main()
{
void(*jumpTo[3])(void) = { func1, func2, func3 };
jumpTo[1]();
return 0;
}
Это всего лишь массив указателей на функции, которые индексируются по определенному значению / позиции. Так ли это, что таблица переходов просто индексирует массив указателей на функции? Мне действительно любопытно, потому что я видел, как многие люди говорили, что операторы switch часто компилируются в таблицы переходов для оценки производительности. Насколько я понимаю, переход к функции таким образом включает разыменование указателя и вызов функции.
Я думал, что оба они не так уж хороши для производительности.
В другом ответе на этом сайте говорилось, что, делая это таким образом, «вы добавляете накладные расходы на вызов функции, которые не обязательно имеют оператор switch». Как бы переключатель, который компилируется в таблицу переходов, избегал вызовов функций?
Кроме того, здесь часто встречается ответ: «Таблица перехода может быть либо массивом указателей на функции, либо массивом инструкций перехода по машинному коду.» Как бы вы перешли к инструкциям машинного кода вместо разыменования указателя? Это быстрее?
Разница между ними в том, что в приведенном выше примере указатель не нужно разыменовывать, потому что он может быть статически связан? В отличие от передачи случайного числа в качестве индекса во время выполнения?
Благодарю.
Решение
Таблица переходов и таблица функций в основном совпадают — это массив адресов. Таблица переходов содержит адреса goto — цели.
Единственное различие между ними заключается в том, как выполняется прыжок. Когда вызывается функция, адрес возврата помещается в стек, поэтому, когда функция завершается, она может вернуться.
Вот пример таблицы переходов:
#include <stdio.h>
int main(int argc, char *argv[])
{
switch (argc)
{
case 1:
printf("You provided no arguments.");
break;
case 2:
printf("You provided one argument.");
break;
case 3:
printf("You provided two arguments.");
break;
case 4:
printf("You provided three arguments.");
break;
case 5:
printf("You provided four arguments.");
break;
case 6:
printf("You provided five arguments.");
break;
default:
printf("You provided %d arguments.", argc-1);
break;
}
return 0;
}
Это компилируется в:
cmp edi, 6 ;Bounds check
ja .L2 ;jump to default branch
mov eax, edi
jmp [QWORD PTR .L4[0+rax*8]]
.L4:
.quad .L2 ;case 0 (same as default!!!)
.quad .L3 ;case 1
.quad .L5 ;case 2
.quad .L6 ;case 3
.quad .L7 ;case 4
.quad .L8 ;case 5
.quad .L9 ;case 6
Другие решения
Основное отличие состоит в том, что для таблицы переходов вы обычно можете использовать адресацию относительно счетчика программы, так что таблица не будет нуждаться в перемещениях и может жить в .text раздел (или какой-либо другой раздел, который не доступен для записи и общего доступа). Это потому, что типичная таблица переходов используется только в очень немногих местах в одних и тех же объектных файлах, и все смещения известны ассемблеру.
Если вместо этого у вас есть массив указателей на функции, то вам как-то нужно создавать настоящие указатели, а для этого нужна некоторая форма перемещения.
Вторая возможность, массив инструкций перехода, на самом деле не ограничена инструкциями перехода как таковой. Важной частью является то, что все целевые последовательности команд (кроме последней) имеют одинаковую длину, так что смещение для перехода может быть легко вычислено. Таким образом, таблица переходов не нужна, но требуется точная информация о ширине (и количестве) инструкций, что трудно гарантировать для большинства целей (архитектуры RISC могут иметь трудно предсказуемое эффективное число команд, когда дело доходит до загрузки констант). ). Это означает, что на практике этот подход ограничен очень специфической формой инструкции перехода для целей.
Обычно термин «таблица переходов» относится к методике, в которой существует более 2 ветвей / целей прыжка, и цель прыжка / перехода выбирается переменной путем вычисления положения в таблице, так или иначе. По сути, приведенный вами пример:
void(*jumpTo[3])(void) = { func1, func2, func3 };
jumpTo[1]();
в целом это использование таблицы переходов, а не просто разыменование указателя на функцию.
C предлагает и другие механизмы — например, регистр переключения часто компилируется в таблицу переходов, особенно если значения регистров имеют узкий диапазон и между ними мало пробелов. Еще одним механизмом, предоставляемым GCC в качестве нестандартного расширения, является использование goto метки как значения указателя с вычисляемым goto.