Использование LUT указателей на функции заставляет компилятор использовать эту стратегию. Теоретически он может скомпилировать версию коммутатора, по сути, с тем же кодом, что и версия LUT (теперь, когда вы добавили проверки выхода за пределы к обеим). На практике это не то, что делают gcc или clang, поэтому стоит посмотреть на вывод asm, чтобы увидеть, что произошло.
(обновление: gcc -fpie (включен по умолчанию в большинстве современных дистрибутивов Linux) любит создавать таблицы относительных смещений вместо абсолютных указателей функций, поэтому родата также не зависит от позиции. Код инициализации таблицы переходов GCC, генерирующий movsxd и add?. Это может быть пропущенный- оптимизация, см. мой ответ там для ссылок на отчеты об ошибках gcc, Ручное создание массива указателей на функции может обойти это.)
Я поставил код <сильный> в проводнике компилятора Godbolt с обеими функциями в одном блоке компиляции (с выводом gcc и clang), чтобы увидеть, как он на самом деле компилируется. Я немного расширил функции, чтобы это было не просто два случая.
void fsm_switch(int state) {
switch(state) {
case FUNC0: func0(); break;
case FUNC1: func1(); break;
case FUNC2: func2(); break;
case FUNC3: func3(); break;
default: ;// Error handling
}
//prevent_tailcall();
}
void fsm_lut(state_e state) {
if (likely(state < FUNC_COUNT)) // without likely(), gcc puts the LUT on the taken side of this branch
lookUpTable[state]();
else
;// Error handling
//prevent_tailcall();
}
См. также Как в ядре Linux работают макросы вероятного() и маловероятного() и в чем их польза?
x86
В x86 clang создает собственный LUT для переключателя, но записи являются указателями внутри функции, а не конечными указателями функций. Таким образом, для clang-3.7 переключатель компилируется в код, который явно хуже, чем LUT, реализованный вручную. В любом случае, процессоры x86, как правило, имеют предсказание ветвлений, которое может обрабатывать косвенные вызовы/переходы, по крайней мере, если их легко предсказать.
GCC использует последовательность условных переходов (но, к сожалению, не 't tail-call напрямую с условными ветвями, что AFAICT безопасно на x86. Он проверяет 1, ‹1, 2, 3, в этом порядке, с в основном неиспользованными ветвями, пока не найдет совпадение.
Они делают практически идентичный код для LUT: проверка границ, обнуление старших 32-бит регистра arg с помощью mov, а затем косвенный переход к памяти с режимом индексированной адресации.
РУКА:
gcc 4.8.2 с -mcpu=cortex-m4 -O2 делает интересный код.
Как сказал Олаф, он создает встроенную таблицу из 1 миллиарда записей. Он не переходит непосредственно к целевой функции, а вместо этого переходит к обычной инструкции перехода (например, b func3). Это обычный безусловный прыжок, так как это хвостовой вызов.
Каждый нуждается запись в таблице назначения значительно больше кода (Godbolt), если fsm_switch делает что-либо после вызова (например, в этом случае вызов не встроенной функции, если void prevent_tailcall(void); объявлен, но не определен) или если это встроено в более крупную функцию.
@@ With void prevent_tailcall(void){} defined so it can inline:
@@ Unlike in the godbolt link, this is doing tailcalls.
fsm_switch:
cmp r0, #3 @ state,
bhi .L5 @
tbb [pc, r0] @ state
@@ There's no section .rodata directive here: the table is in-line with the code, so there's no need for base pointer to be loaded into a reg. And apparently it's even loaded from I-cache, not D-cache
.byte (.L7-.L8)/2
.byte (.L9-.L8)/2
.byte (.L10-.L8)/2
.byte (.L11-.L8)/2
.L11:
b func3 @ optimized tail-call
.L10:
b func2
.L9:
b func1
.L7:
b func0
.L5:
bx lr @ This is ARM's equivalent of an x86 ret insn
IDK, если есть большая разница между тем, насколько хорошо работает прогнозирование ветвлений для tbb, и полным непрямым переходом или вызовом (blx) на облегченном ядре ARM. Доступ к данным для загрузки таблицы может быть более важным, чем двухшаговый переход к инструкции ветвления, которую вы получаете с помощью switch.
Я читал, что непрямые ветки плохо прогнозируются на ARM. Я надеюсь, что это неплохо, если непрямая ветвь каждый раз имеет одну и ту же цель. Но если нет, я предполагаю, что большинство ядер ARM не найдут даже короткие шаблоны, как это сделают большие ядра x86.
Выборка/декодирование инструкций занимает больше времени на x86, поэтому более важно избегать пузырей в потоке инструкций. Это одна из причин, по которой процессоры x86 имеют такое хорошее предсказание переходов. Современные предсказатели ветвлений даже хорошо справляются с шаблонами для непрямых ветвей, основываясь на истории этой ветвления и/или других ветвей, ведущих к ней.
Функция LUT должна потратить пару инструкций на загрузку базового адреса LUT в регистр, но в остальном она очень похожа на x86:
fsm_lut:
cmp r0, #3 @ state,
bhi .L13 @,
movw r3, #:lower16:.LANCHOR0 @ tmp112,
movt r3, #:upper16:.LANCHOR0 @ tmp112,
ldr r3, [r3, r0, lsl #2] @ tmp113, lookUpTable
bx r3 @ indirect register sibling call @ tmp113
.L13:
bx lr @
@ in the .rodata section
lookUpTable:
.word func0
.word func1
.word func2
.word func3
См. Mike of SST answer для аналогичного анализ на Microchip dsPIC.
person
Peter Cordes
schedule
13.03.2016
switch; конечно, это зависит от этикеток. Может быть, я должен был использовать обычную практику или современное состояние, но это то, что есть. В любом случае, если ваш компилятор не делает этого для простогоswitchс увеличением (на одну) меток, вам следует взять современный. До сих пор существуют дорогие мусорные компиляторы, особенно в области встраиваемых систем. Во всяком случае, это не было целью моего комментария! - person too honest for this site schedule 08.03.2016