Как работают прыжковые столы?
В следующем документе, страницы 4-5:
http://www.open-std.org/jtc1/sc22/wg21/docs/ESC_Boston_01_304_paper.pdf
typedef int (* jumpfnct)(void * param);
static int CaseError(void * param)
{
return -1;
}
static jumpfnct const jumptable[] =
{
CaseError, CaseError, ...
.
.
.
Case44, CaseError, ...
.
.
.
CaseError, Case255
};
result = index <= 0xFF ? jumptable[index](param) : -1;
он сравнивает IF-ELSE с SWITCH, а затем вводит эту «таблицу переходов». По-видимому, это самая быстрая реализация из трех. Что именно это? Я не вижу, как это может работать ??
Решение
Jumptable — это метод отображения некоторого входного целого числа на действие. Это связано с тем, что вы можете использовать входное целое число в качестве индекса массива.
Код устанавливает массив указателей на функции. Ваше входное целое число затем используется для выбора одного из этих указателей на функции. Как правило, это выглядит как указатель на функцию CaseError, Однако, время от времени, это будет другая функция, на которую указывают.
Он разработан таким образом, чтобы
jumptable[62] = Case62;
jumptable[95] = Case95;
jumptable[35] = Case35;
jumptable[34] = CaseError; /* For example... and so it goes on */
Таким образом, выбор правильной функции для вызова является постоянным временем … с помощью if-elses и select, время, необходимое для выбора правильной функции, зависит от входного целого числа … при условии, что компилятор не оптимизирует выбор до сама прыжковая таблица … если это для встроенного кода, то есть вероятность, что оптимизации такого рода были отключены … вам придется проверить.
Как только правильный указатель на функцию найден, последняя строка просто вызывает его:
result = index <= 0xFF ? jumptable[index](param) : -1;
становится
result = index <= 0xFF /* Check that the index is within
the range of the jump table */
? jumptable[index](param) /* jumptable[index] selects a function
then it gets called with (param) */
: -1; /* If the index is out of range, set result to be -1
Personally, I think a better choice would be to call
CaseError(param) here */
Другие решения
Jumpfnct — указатель на функцию. Jumptable это массив, который состоит из нескольких jumpfncts. Функции можно вызывать, просто ссылаясь на их позицию в массиве.
Например, jumptable0 выполнит первую функцию, передавая параметр. jumptable1 выполнит вторую функцию и т. д.
Если вы не знаете о указателях функций, вам не следует использовать этот прием. Они очень удобны, в узкой области.
Это очень быстро и эффективно, когда вы переключаетесь между большим количеством похожих вызовов функций. Вы добавляете накладные расходы на вызов функции, которые не обязательно должны иметь оператор switch, поэтому они могут не подходить при любых обстоятельствах. Если ваш код выглядит примерно так:
switch(x) {
case 1:
function1();
break;
case 2:
function2();
break;
...
}
Таблица прыжков может быть хорошей заменой. Если, однако, ваш переключатель выглядит примерно так:
switch(x) {
case 1:
y++;
break;
case 1023:
y--;
break;
...
}
Это, вероятно, не стоило бы делать.
Я использовал их в игрушечном переводчике языка FORTH, где они были неоценимы, но в большинстве случаев вы не увидите преимущества в скорости, которые делают их достойными использования. Используйте их, если это делает логику вашей программы более понятной, а не для оптимизации.
Эта таблица переходов возвращает указатель на функцию по индексу. Вы определяете эту таблицу таким образом, что недопустимые индексы указывают на функцию, которая возвращает некоторый недопустимый код (например, -1 в примере), а действительные индексы указывают на функции, которые необходимо вызвать.
строительство
jumptable[index]
возвращает указатель на функцию, и эта функция вызывается
jumptable[index](param)
где param это какой-то пользовательский параметр.
Jump-Table — это очевидная, но редко используемая оптимизация, которая почему-то, похоже, потеряла популярность.
Вкратце, вместо тестирования значения и выхода из блока switch / case или if-else для перехода к функции или пути к коду, вы создаете массив, который заполняется адресами функций, к которым программа может переходить.
После завершения эта схема исключает неустанное тестирование оператора с блоками if-else и switch / case. Код использует переменную, которая в противном случае была бы проверена с помощью if в качестве нижнего индекса в массиве указателей на функции, и непосредственно переходит к соответствующему коду — без ЛЮБОГО тестирования. Совершенно эффективная отрасль. Код ассемблера должен быть буквально прыжком.
Если вы профилируете код и найдете горячую точку, где программа тратит большую часть своего времени, посмотрите на этот вид оптимизации, чтобы повысить производительность. Немного из этого может иметь большое значение, если это часть горячей точки кода.
Спасибо за ссылку. Хорошая находка!
Как упомянуто в комментарии выше, является ли это решение более или менее эффективным, чем, например, оператор переключения, зависит от объема работы, необходимой для каждого случая.
Написание регулярного оператора switch для значений, которые вы хотите обработать, определенно станет более ясным способом увидеть, что делает код. Поэтому, если только требования к пространству или скорости не требуют более сложного решения, я бы предположил, что это не «лучшее» решение.
Таблицы функциональных указателей, однако, являются эффективным и хорошим способом решения определенных проблем. Я использую указатели функций в таблице довольно регулярно, чтобы делать такие вещи, как «Тест 11 различных решений проблемы», где у меня есть структура с именем функции и функции и, возможно, некоторыми параметрами. Затем у меня есть одна функция для измерения времени и циклический цикл по коду несколько миллионов раз (или что угодно, чтобы получить достаточно длинное измерение, чтобы иметь смысл)