查找表与C嵌入式软件中的切换

Question

在另一个帖子中,我被告知在速度和紧凑性方面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语句转换为跳转表.既然这可能是错的,我想知道为什么!

谢谢你的帮助!

Answer 1

由于我是评论的原作者,我必须添加一个你在问题中没有提到的非常重要的问题.也就是说,原件是关于嵌入式系统的.假设这是一个典型的带有集成闪存的裸机系统,与我将集中精力的PC有很大的不同.

这种嵌入式系统通常具有以下约束.

• 没有CPU缓存.
• Flash要求等待时间更高(即>大约32MHz)CPU时钟.实际比例取决于芯片设计,低功耗/高速工艺,工作电压等.
• 为了隐藏等待状态,Flash具有比CPU总线更宽的读取线.
• 这仅适用于带指令预取的线性代码.
• 数据访问会干扰指令预取或停止直到完成.
• Flash可能具有内部非常小的指令缓存.
• 如果有的话,有一个更小的数据缓存.
• 小缓存导致更频繁的废弃(在之前的条目被替换之前替换之前的条目).

对于例如STM32F4xx,读取需要6个时钟,150MHz/3.3V,128位(4个字).因此,如果需要数据访问,很可能会为所有数据提取超过12个时钟延迟(涉及额外的周期).

假设紧凑的状态码,对于实际问题,这对该架构(Cortex-M4)具有以下影响:

• 查找表:读取函数地址是数据访问.具有上述所有含义.
• 开关otoh使用特殊的"表查找"指令,该指令使用指令后面的代码空间数据.所以第一个条目可能已经被预取.其他条目不会破坏预取.访问也是代码访问,因此数据进入Flash的指令缓存.

还要注意,switch不需要函数,因此编译器可以完全优化代码.这对于查找表是不可能的.至少不需要函数入口/出口的代码.

由于上述和其他因素,估计很难说.它在很大程度上取决于您的平台和代码结构.但假设上面给出的系统,开关很可能更快(更清晰,顺便说一下).

Answer 2

首先,在某些处理器上,间接调用(例如通过指针) - 如查找表示例中的那些- 成本很高(管道断裂,TLB,缓存效应).间接跳跃也可能是真的......

然后,一个好的优化编译器可能会func1()在您的Switch示例中内联调用; 那么你就不会为内联函数运行任何序言或结尾.

您需要确定基准,因为许多其他因素对性能至关重要.又见这(和有参考).

Answer 3

使用函数指针的 LUT 会强制编译器使用该策略。理论上它可以将 switch 版本编译为与 LUT 版本基本相同的代码（现在您已经为两者添加了越界检查）。实际上，这不是 gcc 或 clang 选择执行的操作，因此值得查看 asm 输出以了解发生了什么。

（更新：gcc -fpie（在大多数现代Linux发行版上默认打开）喜欢制作相对偏移量表，而不是绝对函数指针，因此rodata也是与位置无关的。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 内核中的 likely() 和unlikely() 宏如何工作以及它们的好处是什么？

x86

在 x86 上，clang为 switch 制作了自己的 LUT，但条目是指向函数内的指针，而不是最终的函数指针。因此，对于 clang-3.7，该开关恰好编译为比手动实现的 LUT 更差的代码。不管怎样，x86 CPU 往往具有可以处理间接调用/跳转的分支预测，至少如果它们很容易预测的话。

GCC 使用一系列条件分支（但不幸的是，它不会直接使用条件分支进行尾调用，AFAICT 在 x86 上是安全的。它按顺序检查 1、<1、2、3，直到大多数未采用的分支它找到一个匹配项。

他们为 LUT 编写了本质上相同的代码：边界检查、使用 arg 寄存器将 arg 寄存器的高 32 位归零mov，然后使用索引寻址模式进行内存间接跳转。

手臂：

gcc 4.8.2 编写-mcpu=cortex-m4 -O2了有趣的代码。

正如 Olaf 所说，它制作了一个 1B 条目的内联表。它不会直接跳转到目标函数，而是跳转到普通的跳转指令（如b func3）。这是一个正常的无条件跳转，因为它是一个尾部调用。

如果在调用后执行任何操作（例如在本例中声明但未定义的非内联函数调用），或者如果将其内联到更大的函数中，则每个表目标条目都需要更多的代码（Godbolt） 。fsm_switchvoid 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

我不知道，在轻量级 ARM 内核上，分支预测tbb与完全间接跳转或调用 ( )的工作效果是否存在很大差异。blx用于加载表的数据访问可能比通过switch.

我读到，在 ARM 上间接分支的预测很差。我希望如果间接分支每次都有相同的目标，那也不错。但如果没有，我认为大多数 ARM 内核都不会像大型 x86 内核那样找到短模式。

x86 上的指令获取/解码需要更长的时间，因此避免指令流中出现气泡更为重要。这就是 x86 CPU 具有如此良好的分支预测的原因之一。现代分支预测器甚至可以根据该分支和/或导致该分支的其他分支的历史，很好地处理间接分支的模式。

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 的 Mike 的回答，了解对 Microchip dsPIC 的类似分析。