Таблица поиска и коммутатор в встроенном программном обеспечении C

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

Поэтому я хотел бы понять различия между этим:

Справочная таблица

 static void func1(){} static void func2(){} typedef enum { FUNC1, FUNC2, FUNC_COUNT } state_e; typedef void (*func_t)(void); const func_t lookUpTable[FUNC_COUNT] = { [FUNC1] = &func1, [FUNC2] = &func2 }; void fsm(state_e state) { if (state < FUNC_COUNT) lookUpTable[state](); else ;// Error handling } 

и это:

переключатель

 static void func1(){} static void func2(){} void fsm(int state) { switch(state) { case FUNC1: func1(); break; case FUNC2: func2(); break; default: ;// Error handling } } 

Я думал, что таблица поиска была быстрее, поскольку компиляторы пытаются по возможности преобразовать операторы switch в таблицы перехода. Поскольку это может быть неправильно, я хотел бы знать, почему!

Спасибо за вашу помощь!

Поскольку я был оригинальным автором комментария, я должен добавить очень важный вопрос, который вы не упомянули в своем вопросе. То есть оригинал был о встроенной системе. Предполагая, что это типичная голая металлическая система со встроенной вспышкой, есть очень важные отличия от ПК, на котором я сосредоточусь.

Такие встроенные системы обычно имеют следующие ограничения.

  • нет кеша ЦП.
  • Flash требует waitstates для более высоких (т.е.> около 32 МГц) часов процессора. Фактическое соотношение зависит от конструкции матрицы, низкой мощности / высокоскоростного процесса, рабочего напряжения и т. Д.
  • Чтобы скрыть waitstates, Flash имеет более широкие строки чтения, чем CPU-bus.
  • Это работает только для линейного кода с предварительной выборкой команд.
  • Доступ к данным нарушает предварительную выборку инструкций или останавливается до ее завершения.
  • Flash может иметь внутренний очень маленький кеш команд.
  • Если вообще есть, то есть еще меньше кэша данных.
  • Маленькие тайники приводят к более частым сбоям (заменяя предыдущую запись до того, как она была использована в другой раз).

Например, для STM32F4xx чтение занимает 6 тактов при 150 МГц / 3,3 В для 128 бит (4 слова). Поэтому, если требуется доступ к данным, есть вероятность, что он добавляет более 12 часов задержки для всех данных, которые будут получены (есть дополнительные циклы).

Предполагая компактные государственные коды, для реальной проблемы это имеет следующие эффекты для этой архитектуры (Cortex-M4):

  • Lookup-table: чтение адреса функции – это доступ к данным. Со всеми последствиями, упомянутыми выше.
  • Коммутатор otoh использует специальную инструкцию «table-lookup», которая использует данные кодового пространства прямо за инструкцией. Таким образом, первые записи, возможно, уже предварительно загружены. Другие записи не прерывают предварительную выборку. Также доступ – это код-acces, поэтому данные поступают в кэш команд Flash.

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


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

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

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

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

Ответ msc и комментарии дают вам хорошие подсказки относительно того, почему производительность может быть не такой, какой вы ожидаете. Бенчмаркинг – это правило, но результаты будут варьироваться от одной архитектуры к другой и могут изменяться с другими версиями компилятора и, конечно же, выбирать его конфигурацию и параметры.

Обратите внимание, однако, что ваши 2 части кода не выполняют одну и ту же проверку в state :

  • Коммутатор изящно ничего не делает, state не является одним из определенных значений,
  • Версия таблицы перехода вызовет неопределенное поведение для всех, кроме двух значений FUNC1 и FUNC2 .

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

 void fsm(int state) { if (state >= 0 && state < FUNC_COUNT && lookUpTable[state] != NULL) lookUpTable[state](); } 

Попробуйте сравнить это и проверить код сборки. Вот удобный онлайн-компилятор для этого: http://gcc.godbolt.org/#

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

Например, на dsPIC33E512MU810, используя XC16 (v1.24), обратный код:

 lookUpTable[state](); 

Скомпилирует (из windows parsingки в MPLAB-X):

 ! lookUpTable[state](); 0x2D20: MOV [W14], W4 ; get state from stack-frame (not counted) 0x2D22: ADD W4, W4, W5 ; 1 cycle (addresses are 16 bit aligned) 0x2D24: MOV #0xA238, W4 ; 1 cycle (get base address of look-up table) 0x2D26: ADD W5, W4, W4 ; 1 cycle (get address of entry in table) 0x2D28: MOV [W4], W4 ; 1 cycle (get address of the function) 0x2D2A: CALL W4 ; 2 cycles (push PC+2 set PC=W4) 

… и каждая (пустая, не-ничего) функция компилируется в:

 !static void func1() !{} 0x2D0A: LNK #0x0 ; 1 cycle (set up stack frame) ! Function body goes here 0x2D0C: ULNK ; 1 cycle (un-link frame pointer) 0x2D0E: RETURN ; 3 cycles 

Для всех случаев это всего 11 инструктивных циклов накладных расходов, и все они одинаковы. (Примечание. Если таблица или функции, которые она содержит, не находятся на одной странице 32K программных слов Flash, из-за необходимости получить модуль генерации адресов для чтения с правильной страницы или для настройки ПК, чтобы сделать длинный звонок.)

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

Например, оператор switch:

 switch(state) { case FUNC1: state++; break; case FUNC2: state--; break; default: break; } 

Скомпилирует:

 ! switch(state) 0x2D2C: MOV [W14], W4 ; get state from stack-frame (not counted) 0x2D2E: SUB W4, #0x0, [W15] ; 1 cycle (compare with first case) 0x2D30: BRA Z, 0x2D38 ; 1 cycle (if branch not taken, or 2 if it is) 0x2D32: SUB W4, #0x1, [W15] ; 1 cycle (compare with second case) 0x2D34: BRA Z, 0x2D3C ; 1 cycle (if branch not taken, or 2 if it is) ! { ! case FUNC1: state++; break; 0x2D38: INC [W14], [W14] ; To stop the switch being optimised out 0x2D3A: BRA 0x2D40 ; 2 cycles (go to end of switch) ! case FUNC2: state--; break; 0x2D3C: DEC [W14], [W14] ; To stop the switch being optimised out 0x2D3E: NOP ; compiler did a fall-through (for some reason) ! default: break; 0x2D36: BRA 0x2D40 ; 2 cycles (go to end of switch) ! } 

Это накладные расходы в 5 циклов, если первый случай взят 7, если второй случай взят и т. Д., Что означает, что они разрываются даже в четвертом случае.

Это означает, что знание ваших данных во время разработки будет иметь существенное влияние на долгосрочную скорость. Если у вас есть значительное число (более 4 случаев), и все они происходят с одинаковой частотой, то в конечном итоге таблица поиска будет быстрее. Если частота случаев значительно отличается (например, случай 1 более вероятен, чем случай 2, что более вероятно, чем случай 3 и т. Д.), То, если вы сначала закажете переключатель с наиболее вероятным случаем, тогда переключатель будет быстрее в долгосрочной перспективе. Для случая с краем, когда у вас есть только несколько случаев, коммутатор (вероятно) будет быстрее в любом случае для большинства исполнений и более читабельным и менее подверженным ошибкам.

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

Совет. Идите с помощью переключателя, если вы не знаете, что поиск определенно будет быстрее, и время, которое требуется для запуска, важно.

Изменить: мой пример переключения немного несправедлив, поскольку я проигнорировал исходный вопрос и вложил в «тело» случаев, чтобы подчеркнуть реальное преимущество использования переключателя в поиске. Если коммутатор должен выполнить вызов, тогда он имеет только преимущество для первого случая!

Использование LUT указателей функций заставляет компилятор использовать эту страtagsю. Он мог бы теоретически скомпилировать версию коммутатора по существу тем же самым кодом, что и версия LUT (теперь вы добавили проверки вне пределов для обоих). На практике это не то, что gcc или clang предпочитают делать, поэтому стоит посмотреть на выход asm, чтобы увидеть, что произошло.

(обновление: gcc -fpie (по умолчанию на большинстве современных дистрибутивов Linux) любит создавать таблицы относительных смещений, а не абсолютные указатели на функции, поэтому rodata также не зависит от позиции. Код инициализации таблицы перехода GCC, генерирующий movsxd и добавляемый? Это может быть пропущенная оптимизация, см. Мой ответ там для ссылок на отчеты об ошибках 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(); } 

См. Также Как работают macros вероятного () и маловероятного () в ядре Linux и какова их польза?


x86

На x86 clang делает свой собственный LUT для коммутатора, но записи являются указателями внутри функции, а не конечными указателями функций . Итак, для clang-3.7 коммутатор, похоже, компилируется в код, который строго хуже, чем реализованный вручную LUT. В любом случае, процессоры x86 имеют тенденцию к outlookированию ветвлений, которые могут обрабатывать косвенные вызовы / скачки, по крайней мере, если их легко предсказать.

GCC использует последовательность условных ветвей ( но, к сожалению, не требует прямого вызова с условными ветвями, который AFAICT безопасен на x86 . Он проверяет 1, <1, 2, 3, в этом порядке, в основном не принятые ветви до он находит совпадение.

Они делают по существу идентичный код для проверки LUT: bounds, нулевой верхний 32-разрядный регистр arg с mov , а затем косвенно-косвенный переход с индексированным режимом адресации.


РУКА:

gcc 4.8.2 с -mcpu=cortex-m4 -O2 делает интересный код.

Как сказал Олаф, он делает встроенную таблицу из 1B записей . Он не переходит непосредственно к целевой функции, а вместо этого к обычной инструкции перехода (например, 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, если есть большая разница между тем, насколько хорошо работает outlookирование ветвления для tbb сравнению с полным непрямым прыжком или вызовом ( blx ), на легком ядре ARM. Доступ к данным для загрузки таблицы может быть более значительным, чем двухступенчатый переход к команде перехода, которую вы получаете с помощью switch .

Я читал, что непрямые ветви плохо outlookируются на ARM. Надеюсь, это не плохо, если косвенная ветвь имеет одну и ту же цель каждый раз. Но если нет, я бы предположил, что большинство ядер ARM не найдут даже коротких шаблонов, как это делают большие ядра x86.

Прибор fetch / decoding занимает больше времени на x86, поэтому более важно избегать пузырьков в streamе команд. Это одна из причин, почему процессоры 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 

См . Ответ Майка SST для аналогичного анализа на Microchip dsPIC.

Чтобы иметь еще больше выходов компилятора, вот что получается компилятором TI C28x с использованием кода примера @PeterCordes:

 _fsm_switch: CMPB AL,#0 ; [CPU_] |62| BF $C$L3,EQ ; [CPU_] |62| ; branchcc occurs ; [] |62| CMPB AL,#1 ; [CPU_] |62| BF $C$L2,EQ ; [CPU_] |62| ; branchcc occurs ; [] |62| CMPB AL,#2 ; [CPU_] |62| BF $C$L1,EQ ; [CPU_] |62| ; branchcc occurs ; [] |62| CMPB AL,#3 ; [CPU_] |62| BF $C$L4,NEQ ; [CPU_] |62| ; branchcc occurs ; [] |62| LCR #_func3 ; [CPU_] |66| ; call occurs [#_func3] ; [] |66| B $C$L4,UNC ; [CPU_] |66| ; branch occurs ; [] |66| $C$L1: LCR #_func2 ; [CPU_] |65| ; call occurs [#_func2] ; [] |65| B $C$L4,UNC ; [CPU_] |65| ; branch occurs ; [] |65| $C$L2: LCR #_func1 ; [CPU_] |64| ; call occurs [#_func1] ; [] |64| B $C$L4,UNC ; [CPU_] |64| ; branch occurs ; [] |64| $C$L3: LCR #_func0 ; [CPU_] |63| ; call occurs [#_func0] ; [] |63| $C$L4: LCR #_prevent_tailcall ; [CPU_] |69| ; call occurs [#_prevent_tailcall] ; [] |69| LRETR ; [CPU_] ; return occurs ; [] _fsm_lut: ;* AL assigned to _state CMPB AL,#4 ; [CPU_] |84| BF $C$L5,HIS ; [CPU_] |84| ; branchcc occurs ; [] |84| CLRC SXM ; [CPU_] MOVL XAR4,#_lookUpTable ; [CPU_U] |85| MOV ACC,AL << 1 ; [CPU_] |85| ADDL XAR4,ACC ; [CPU_] |85| MOVL XAR7,*+XAR4[0] ; [CPU_] |85| LCR *XAR7 ; [CPU_] |85| ; call occurs [XAR7] ; [] |85| $C$L5: LCR #_prevent_tailcall ; [CPU_] |88| ; call occurs [#_prevent_tailcall] ; [] |88| LRETR ; [CPU_] ; return occurs ; [] 

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