Подтвердить что ты не робот

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

В другом потоке мне сказали, что 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 в таблицы перехода. Поскольку это может быть неправильно, я хотел бы знать, почему!

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

4b9b3361

Ответ 1

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

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

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

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

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

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

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


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

Ответ 2

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

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

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

Ответ 3

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

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

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

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

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

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

Ответ 4

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

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

lookUpTable[state]();

Скомпилирует (из окна разборки в 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 и т.д.), То, если вы сначала закажете переключатель с наиболее вероятным случаем, тогда переключатель будет быстрее в долгосрочной перспективе. Для крайнего случая, когда у вас есть только несколько случаев, коммутатор (вероятно) будет быстрее в любом случае для большинства исполнений и более читабельным и менее подверженным ошибкам.

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

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

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

Ответ 5

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


Я поставил код на godbolt с обеими функциями в одном модуле компиляции, чтобы увидеть, как он действительно скомпилирован. Я немного расширил функции, так что это были не только два случая.

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: bounds, нулевой верхний 32-разрядный регистр arg с mov, а затем косвенно-косвенный переход с индексированным режимом адресации.


ARM:

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

Как сказал Олаф, он делает встроенную таблицу из 1B записей. Он не переходит непосредственно к целевой функции, а вместо этого к обычной команде перехода (например, b func3). Это нормальный безусловный переход, поскольку он является хвостом. Для каждой записи в таблице требуется значительно больше кода, если fsm_switch делает что-либо после вызова (или встроено в большую функцию).

fsm_switch:
        cmp     r0, #3    @ state,
        bhi     .L5       @
        tbb     [pc, r0]  @ state
       @@ There no section .rodata directive here: the table is in-line with the code, so there no need for base pointer to be loaded into a reg.  And apparently it 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 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

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

Ответ 6

Чтобы иметь еще больше выходных данных компилятора, вот что получается компилятором 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-оптимизации. Мы видим, что коммутатор не преобразован в таблицу перехода, даже если компилятор имеет возможность.