C嵌入式软件中的查找表与开关语句比较

Question

C嵌入式软件中的查找表与开关语句比较

cperformanceswitch-statementembeddedlookup-tables

41

在另一个帖子中，有人告诉我，在速度和紧凑性方面，查找表可能比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 语句转换为跳转表。但这种想法可能是错误的，我想知道原因！

谢谢您的帮助！

- Plouff

14

我们无法给你一个确定的答案，因为它取决于很多因素，但主要取决于你所使用的编译器。相反，你应该指示编译器在使用优化标志的情况下输出两种情况的汇编代码，并自行比较它们。 - nos

2

你应该看一下关于switch语句的以下文章：http://lazarenko.me/switch/ - Guillaume George

3

有些编译器会将简单的switch语句转换为查找表。这个问题没有一个通用的答案。 - Sebastian Mach

1

@Olaf：不确定为什么你要教我这个练习已经有20多年了，特别是因为它并不普遍适用于每个开关和所有优化标志，并且取决于成本/效益启发式。并非每个LUT都是一种优化，同样，并非每个硬编码的if-else结构都是。 - Sebastian Mach

2

很多编译器无法内联函数指针调用（可能需要多个实现特定选项），因此错过了与内联相关的任何优化...这只是需要记住的一些事情。 - technosaurus

显示剩余8条评论

6个回答

16

首先，在一些处理器上，间接调用（例如通过指针）- 像您的查找表示例中的调用 - 是昂贵的（流水线中断、TLB、缓存效应）。对于间接跳转也可能是如此...

其次，一款优秀的编译器可能会将对开关示例中func1()的调用进行内联；这样你就不需要为内联函数运行任何序言或结语代码。

您需要进行基准测试才能确定，因为性能受到许多其他因素的影响。还可以参见此处（以及那里的引用）。

- Basile Starynkevitch

谢谢，这正是我在查找的答案！我不知道间接调用会导致管线中断、TLB和缓存效应等问题。但现在，我需要弄清楚它的含义……一开始我有一个问题，现在我又多了3个问题！谢谢;)！ - Plouff

@BarryTheHatchet：我在谈论这个问题：https://dev59.com/vJTfa4cB1Zd3GeqPU7y9。我不认为你在这里发表了评论。你在谈论哪个线程？这可能对我很有趣 :)。 - Plouff

@Plouff 好的，可能是另一篇帖子吧。巧合！ - Lightness Races in Orbit

6

使用函数指针的LUT强制编译器使用该策略。理论上，它可以将开关版本编译为与LUT版本基本相同的代码（现在两者都添加了越界检查）。实际上，gcc或clang没有选择这样做，因此值得查看汇编输出以查看发生了什么。

（更新：gcc -fpie （在大多数现代Linux发行版上默认启用）喜欢制作相对偏移量表，而不是绝对函数指针，因此rodata也是位置无关的。 GCC跳转表初始化代码生成movsxd和add？这可能是一种错过优化，有关链接到gcc错误报告的我的答案，请手动创建一个函数指针数组来解决这个问题。）

我在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内核中的likely()和unlikely()宏是如何工作的以及它们的好处是什么？

x86

在x86上，clang为switch制作了自己的LUT表，但条目是指针，指向函数内部而不是最终的函数指针。因此，对于clang-3.7，switch编译成的代码严格比手动实现的LUT更糟糕。无论哪种情况，x86 CPU往往具有可以处理间接调用/跳转的分支预测，至少如果易于预测的话。

GCC使用一系列条件分支（但不幸的是，在x86上，GCC不能直接使用条件分支进行尾调用，这在我看来在x86上是安全的）。它按顺序检查1，＜1，2，3，并使用大多数未使用的分支进行匹配。

它们对LUT制作基本相同的代码：边界检查，使用mov清零参数寄存器的上32位，然后使用索引寻址模式进行内存间接跳转。

ARM：

GCC 4.8.2使用-mcpu=cortex-m4 -O2生成有趣的代码。

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

如果在这个表格目的地条目后进行了任何操作（例如在这种情况下调用非内联函数，如果声明了但未定义void prevent_tailcall(void);），或者如果此操作被内联到较大的函数中，则fsm_switch需要

@@ 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上进行类似分析的答案。

- Peter Cordes

2

这是另一个很棒的答案，非常感谢！我想知道是否可以通过汇编语言看到所有内容。现在我知道你必须知道硬件如何处理你提供的汇编代码！所以你回答了我另一个问题：这个问题的答案不仅取决于你使用的编译器，还取决于硬件。因此，唯一完全有效的解决方案是基准测试而不是代码分析（除非你绝对了解所有硬件机制）。再次感谢！ - Plouff

1

我想再次向您致敬，感谢您发现了likely()和tall call effects！ - Plouff

@Plouff：实际上，查看汇编并了解在各种硬件系列中哪些是慢的可以替代基准测试。大多数人没有每个x86微架构都有一个基准测试农场。虽然对于嵌入式系统，您当然可以在目标平台上进行基准测试。 - Peter Cordes

是的，这就是我想说的：）。在我的情况下，除非我花很多时间研究目标架构，否则基准测试将是唯一的解决方案！ - Plouff

1

在许多基于缓慢闪存代码存储的平台上，手动使用表格将允许控制表格是存储在快速RAM还是缓慢闪存中。我认为我从未见过编译器具有以这种方式控制switch语句代码生成的选项。 - supercat

3

msc的回答和评论为您提供了关于性能可能不如预期的好提示。基准测试是规则，但结果会因架构不同而异，并且可能会随着编译器和其配置以及所选选项的其他版本而发生变化。

请注意，您的两个代码片段对state的验证不相同：

如果state不是定义值之一，则switch将优雅地什么也不做，
跳转表版本将对除FUNC1和FUNC2之外的所有值调用未定义的行为。

没有通用的方法可以初始化跳转表并带有虚拟函数指针，而不对FUNC_COUNT进行假设。为了获得相同的行为，跳转表版本应该如下所示：

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

尝试对此进行基准测试并检查汇编代码。这是一个方便的在线编译器：http://gcc.godbolt.org/#

- chqrlie

在这个问题中，我想把重点放在查找表和开关上。但你是对的：状态验证也有其成本！我添加了一些细节，以更好地反映我使用的实现。到目前为止，有趣的是，在我得到的3个答案中，总是有相同的建议：基准测试！感谢在线编译器，这将是一个非常有用的链接！！ - Plouff

1

在正确的实现中（即包括捕获无效状态和紧凑的开关），两者都会导致相似的结构。详细信息更多地涉及硬件架构，从Flash读取数据的方式，访问类型等。 - too honest for this site

3

在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程序字闪存页中，则由于必须使地址生成单元从正确的页面读取或设置PC进行长调用而产生更大的开销。）

另一方面，只要整个switch语句适合某个特定大小，编译器将生成测试和相对分支的代码，每个case需要三个（或可能四个）周期，直到找到为真的那个。

例如，以下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更可能发生，情况2比情况3更可能发生等），则如果您按最可能的情况对开关进行排序，则开关在长期内将更快。对于只有少数情况的边缘情况，开关（可能）无论如何都会更快，对于大多数执行来说更易读且更少出错。

如果开关中只有几种情况，或某些情况比其他情况更常见，则测试和开关的分支所需的时间可能比使用查找表少。另一方面，如果您有超过一把手的情况发生的频率相似，则平均而言，查找表最终可能会更快。

提示：除非您知道查找表肯定会更快并且运行所需的时间很重要，否则请使用开关。

编辑：我的开关示例有点不公平，因为我忽略了原始问题并将情况的“主体”内联以突出使用开关而不是查找表的真正优势。如果开关也必须进行调用，则它仅在第一种情况下具有优势！

- Evil Dog Pie

感谢这个案例研究。目前我大约有20个状态（即情况）。将来可能会更多。我看到你的回答唯一的问题是编译器没有将switch转换成跳转表。那将会很好。此外，就像你所说，switch没有子程序调用开销，但这些示例仍然提供了一个好的理解。再次感谢！ - Plouff

1

@Plouff 您是正确的，Microchip编译器不会将switch语句转换为跳转表，因为两个指令的测试和分支序列更有效率。这为开发人员提供了根据其需求选择解决方案的选择。 - Evil Dog Pie

@Plouff 我选择忽略用例中的调用，因为你的示例代码暗示了使用情况是一个状态机。对于这些情况，我通常会尝试在switch语句的case中保持状态转换处理内联（以便封装状态管理），并根据需要将特定的状态转换处理委托给其他函数。这也允许代码在可能的情况下利用switch比跳转表更好的（微小）性能优势。不过这都很主观，我毫不怀疑你的项目有不同的要求。 :-) - Evil Dog Pie

谢谢提供详细信息。你认为大约20个州是很多吗？ - Plouff

1

通常是这样的。但如果有一两个状态明显比其他状态更频繁发生，我会期望 switch 语句更高效一些。不过，采用跳转表还是 switch 语句取决于编译器和目标处理器。你可以让编译器输出一个包含已编译汇编指令的“中间”文件。看看文件并比较两者是否值得。但除非你确定需要优化，否则最好把时间花在其他事情上，因为两者之间的差异非常小。 - Evil Dog Pie

好的，谢谢您的反馈：）。就像我之前说过的，我现在不太需要这种优化。但是将来可能会需要。 - Plouff

2

为了获得更多的编译器输出，以下是使用@PeterCordes示例代码生成的TI C28x编译器产生的内容：

_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 优化。我们可以看到，即使编译器有能力，这个 switch 语句也没有被转换成跳转表。

- Plouff

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- too honest for this site · Accepted Answer

作为评论的原始作者，我必须补充一个非常重要的问题，这是您在问题中没有提到的。那就是原始问题涉及嵌入式系统。假设这是一个典型的裸机系统带有集成闪存，与我将集中讨论的个人电脑有很大的区别。

这种嵌入式系统通常具有以下限制:

没有CPU缓存。
闪存对于更高（即> ca. 32 MHz）的CPU时钟需要等待状态。实际比率取决于芯片设计、低功耗/高速工艺、工作电压等。
为了隐藏等待状态，闪存具有比CPU总线更宽的读取线。
这仅对具有指令预取的线性代码有效。
数据访问会干扰指令预取或被阻塞直到完成。
闪存可能有一个内部非常小的指令缓存。
如果有任何，那么数据缓存甚至更小。
小缓存会导致更频繁的崩溃（在另一次使用之前替换以前的条目）。

例如对于STM32F4xx，以150MHz / 3.3V为例，读取128位（4个字）需要6个时钟。因此，如果需要数据访问，则很可能会添加超过12个时钟的延迟以获取所有数据（还涉及其他周期）。

假设对于实际问题的紧凑状态代码，这对Cortex-M4架构有以下影响:

查找表：读取函数地址是一种数据访问。具有上述所有含义。
另一方面，开关使用特殊的“表查找”指令，该指令使用指令右侧的代码空间数据。因此，可能已经预取了前几个条目。其他条目不会中断预取。此外，访问是代码访问，因此数据进入闪存的指令缓存。

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

由于上述和其他因素的影响，估计很难说。这在很大程度上取决于您的平台和代码结构。但是假设给定系统，则开关很有可能更快（顺便说一下，更清晰）。