Lookup table 与 C 嵌入式软件中的 switch
Lookup table vs switch in C embedded software
在另一个线程中，有人告诉我 switch 在速度和紧凑性方面可能比 查找 table 更好。
所以我想了解这两者的区别：
查找table
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
}
}
我认为查找 table 更快，因为编译器尽可能将 switch 语句转换为跳转 table。
由于这可能是错误的，我想知道为什么！
感谢您的帮助！
msc 的回答和评论给了你很好的提示，说明为什么性能可能不是你所期望的。基准测试是规则，但结果会因架构而异，并且可能会随着编译器的其他版本以及其配置和选项的选择而变化。
但是请注意，您的 2 段代码不会对 state:
执行相同的验证
- 如果
state 不是定义的值之一，开关将优雅地不做任何事情，
- 跳转 table 版本将为除了
FUNC1 和 FUNC2. 这两个值之外的所有值调用未定义的行为
在不对 FUNC_COUNT 进行假设的情况下，没有使用虚拟函数指针初始化跳转 table 的通用方法。得到相同的行为，跳转 table 版本应该是这样的：
void fsm(int state) {
if (state >= 0 && state < FUNC_COUNT && lookUpTable[state] != NULL)
lookUpTable[state]();
}
尝试对此进行基准测试并检查汇编代码。这是一个方便的在线编译器：http://gcc.godbolt.org/#
首先，在 一些 处理器上，间接调用（例如通过指针）- 就像您 Lookup Table 中的那些示例 - 代价高昂（管道损坏、TLB、缓存效应）。间接跳转可能也是如此...
然后，一个好的优化编译器 可能 在您的 Switch 示例中内联对 func1() 的调用；那么您将不会 运行 内联函数的任何序言或结尾。
您需要进行基准测试 才能确定，因为许多其他因素对性能也很重要。另请参阅 （以及那里的参考）。
由于我是评论的原作者，所以我必须添加一个您在问题中没有提到的非常重要的问题。也就是说，原来是关于嵌入式系统的。假设这是一个典型的带有集成闪存的裸机系统，与我将重点关注的 PC 有非常重要的区别。
此类嵌入式系统通常具有以下限制。
- 无CPU缓存。
- Flash 需要更高（即 >ca. 32MHz）CPU 时钟的等待状态。实际比例取决于模具设计、低power/high速度工艺、工作电压等
- 为了隐藏等待状态，Flash 具有比 CPU 总线更宽的读取行。
- 这只适用于带指令预取的线性代码。
- 数据访问会干扰指令预取或在完成前停止。
- Flash 可能有一个非常小的内部指令缓存。
- 如果有的话，还有一个更小的数据缓存。
- 较小的缓存会导致更频繁的垃圾处理（替换以前的条目，然后再使用一次）。
例如STM32F4xx 在 150MHz/3.3V 下读取 128 位（4 个字）需要 6 个时钟。因此，如果需要进行数据访问，很有可能会为要获取的所有数据增加超过 12 个时钟的延迟（涉及额外的周期）。
假定状态代码紧凑，对于实际问题，这对该体系结构（Cortex-M4）有以下影响：
- Lookup-table: 读取函数地址是一个数据访问。具有上述所有含义。
- 开关 otoh 使用特殊的 "table-lookup" 指令，该指令在指令后面使用代码-space 数据。所以第一个条目可能已经预取。其他条目不会破坏预取。访问也是代码访问，因此数据进入闪存的指令缓存。
另请注意，switch不需要函数，因此编译器可以充分优化代码。这对于查找 table 是不可能的。至少不需要函数 entry/exit 的代码。
由于上述和其他因素，估计很难说。这在很大程度上取决于您的平台和代码结构。但是假设上面给出的系统，切换很可能更快（并且更清晰，顺便说一句。）。
在 Microchip dsPIC 系列设备上，查找 table 作为一组指令地址存储在闪存本身中。执行查找涉及从闪存中读取地址，然后调用例程。进行调用会增加另外几个周期来推送指令指针和其他一些琐碎的事情（例如设置堆栈帧）。
例如在dsPIC33E512MU810上，使用XC16 (v1.24)查找代码：
lookUpTable[state]();
编译为（来自 MPLAB-X 中的反汇编 window）：
! 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个指令周期的开销，而且它们都是相同的。 （注意：如果 table 或它包含的功能不在同一个 32K 程序字闪存页面中，由于必须让地址生成单元从正确的页面读取，将会有更大的开销，或设置 PC 以拨打长途电话。)
另一方面，如果整个 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 个案例）并且它们都以相似的频率出现，那么在长 运行 中查找 table 会更快。如果案例的频率明显不同（例如，案例 1 比案例 2 更有可能，案例 2 比案例 3 更有可能，等等）然后，如果您首先订购最有可能的案例的开关，那么开关将是在长 运行 中更快。对于只有少数情况的边缘情况，对于大多数执行而言，switch（可能）无论如何都会更快，并且更具可读性并且更不容易出错。
如果 switch 中只有少数 case，或者某些 case 比其他 case 发生的频率更高，那么进行 switch 的测试和分支可能比使用查找花费更少的周期 table.另一方面，如果您有多个以相似频率发生的案例，那么查找最终可能会平均更快。
提示：除非您知道查找肯定会更快并且 运行 所花费的时间很重要，否则请使用开关。
编辑： 我的 switch 示例有点不公平，因为我忽略了原始问题并内联 'body' 个案例以突出真实使用 switch 而不是查找的优势。如果交换机也必须进行呼叫，那么它只对第一种情况有优势！
使用函数指针的 LUT 会强制编译器使用该策略。理论上它 可以 将 switch 版本编译为与 LUT 版本基本相同的代码（现在您已经为两者添加了越界检查）。实际上，这不是 gcc 或 clang 选择做的事情，因此值得查看 asm 输出以了解发生了什么。
（更新：gcc -fpie（大多数现代 Linux 发行版默认开启）喜欢制作 table 相对偏移量，而不是绝对函数指针，因此 rodata也是与位置无关的。GCC Jump Table initialization code generating movsxd and add?。这可能是一个优化失误，请参阅我的回答以获取指向 gcc 错误报告的链接。手动创建一个函数指针数组可以解决这个问题。）
我把代码 on the Godbolt compiler explorer 和两个函数放在一个编译单元中（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();
}
另请参阅
How do the likely() and unlikely() macros in the Linux kernel work and what is their benefit?
x86
在 x86 上，clang 为开关创建自己的 LUT，但条目是指向函数内部的指针，而不是最终函数指针。所以对于 clang-3.7，switch 恰好编译成比手动实现的 LUT 更差的代码。无论哪种方式，x86 CPU 往往具有可以处理间接调用/跳转的分支预测，至少在它们易于预测的情况下是这样。
GCC 使用一系列条件分支 (but unfortunately doesn't tail-call directly with conditional branches, which AFAICT is safe on x86。它按顺序检查 1, <1, 2, 3，大部分是未采用的分支直到找到匹配项。
他们为 LUT 编写了基本相同的代码：边界检查，用 mov 将 arg 寄存器的高 32 位归零，然后使用索引寻址模式进行内存间接跳转。
手臂：
gcc 4.8.2 with -mcpu=cortex-m4 -O2 生成有趣的代码。
正如 Olaf 所说，它使 1B 条目 成为一个内联 table。它不会直接跳转到目标函数，而是跳转到一个普通的跳转指令（比如b func3）。这是正常的无条件跳转，因为它是尾调用。
每个 table 目标条目需要 significantly more code (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 如果在轻量级 ARM 内核上，tbb 的分支预测与完全间接跳转或调用 (blx) 之间存在很大差异。加载 table 的数据访问可能比使用 switch.
的两步跳转到分支指令更重要
我读到间接分支在 ARM 上的预测很差。如果间接分支每次都有相同的目标，我希望这还不错。但如果没有，我认为大多数 ARM 内核不会像大型 x86 内核那样找到短模式。
指令 fetch/decode 在 x86 上需要更长的时间，因此避免指令流中出现气泡更为重要。这就是 x86 CPU 具有如此出色的分支预测的原因之一。现代分支预测器甚至可以很好地处理间接分支的模式，基于该分支的历史 and/or 导致它的其他分支。
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
有关 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 优化。
我们可以看到即使编译器有能力，开关也没有转换成跳转table
在另一个线程中，有人告诉我 switch 在速度和紧凑性方面可能比 查找 table 更好。
所以我想了解这两者的区别：
查找table
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
}
}
我认为查找 table 更快，因为编译器尽可能将 switch 语句转换为跳转 table。 由于这可能是错误的，我想知道为什么！
感谢您的帮助！
msc 的回答和评论给了你很好的提示，说明为什么性能可能不是你所期望的。基准测试是规则，但结果会因架构而异，并且可能会随着编译器的其他版本以及其配置和选项的选择而变化。
但是请注意，您的 2 段代码不会对 state:
- 如果
state不是定义的值之一，开关将优雅地不做任何事情， - 跳转 table 版本将为除了
FUNC1和FUNC2. 这两个值之外的所有值调用未定义的行为
在不对 FUNC_COUNT 进行假设的情况下，没有使用虚拟函数指针初始化跳转 table 的通用方法。得到相同的行为，跳转 table 版本应该是这样的：
void fsm(int state) {
if (state >= 0 && state < FUNC_COUNT && lookUpTable[state] != NULL)
lookUpTable[state]();
}
尝试对此进行基准测试并检查汇编代码。这是一个方便的在线编译器：http://gcc.godbolt.org/#
首先，在 一些 处理器上，间接调用（例如通过指针）- 就像您 Lookup Table 中的那些示例 - 代价高昂（管道损坏、TLB、缓存效应）。间接跳转可能也是如此...
然后，一个好的优化编译器 可能 在您的 Switch 示例中内联对 func1() 的调用；那么您将不会 运行 内联函数的任何序言或结尾。
您需要进行基准测试 才能确定，因为许多其他因素对性能也很重要。另请参阅
由于我是评论的原作者，所以我必须添加一个您在问题中没有提到的非常重要的问题。也就是说，原来是关于嵌入式系统的。假设这是一个典型的带有集成闪存的裸机系统，与我将重点关注的 PC 有非常重要的区别。
此类嵌入式系统通常具有以下限制。
- 无CPU缓存。
- Flash 需要更高（即 >ca. 32MHz）CPU 时钟的等待状态。实际比例取决于模具设计、低power/high速度工艺、工作电压等
- 为了隐藏等待状态，Flash 具有比 CPU 总线更宽的读取行。
- 这只适用于带指令预取的线性代码。
- 数据访问会干扰指令预取或在完成前停止。
- Flash 可能有一个非常小的内部指令缓存。
- 如果有的话，还有一个更小的数据缓存。
- 较小的缓存会导致更频繁的垃圾处理（替换以前的条目，然后再使用一次）。
例如STM32F4xx 在 150MHz/3.3V 下读取 128 位（4 个字）需要 6 个时钟。因此，如果需要进行数据访问，很有可能会为要获取的所有数据增加超过 12 个时钟的延迟（涉及额外的周期）。
假定状态代码紧凑，对于实际问题，这对该体系结构（Cortex-M4）有以下影响：
- Lookup-table: 读取函数地址是一个数据访问。具有上述所有含义。
- 开关 otoh 使用特殊的 "table-lookup" 指令，该指令在指令后面使用代码-space 数据。所以第一个条目可能已经预取。其他条目不会破坏预取。访问也是代码访问，因此数据进入闪存的指令缓存。
另请注意，switch不需要函数，因此编译器可以充分优化代码。这对于查找 table 是不可能的。至少不需要函数 entry/exit 的代码。
由于上述和其他因素，估计很难说。这在很大程度上取决于您的平台和代码结构。但是假设上面给出的系统，切换很可能更快（并且更清晰，顺便说一句。）。
在 Microchip dsPIC 系列设备上，查找 table 作为一组指令地址存储在闪存本身中。执行查找涉及从闪存中读取地址，然后调用例程。进行调用会增加另外几个周期来推送指令指针和其他一些琐碎的事情（例如设置堆栈帧）。
例如在dsPIC33E512MU810上，使用XC16 (v1.24)查找代码：
lookUpTable[state]();
编译为（来自 MPLAB-X 中的反汇编 window）：
! 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个指令周期的开销，而且它们都是相同的。 （注意：如果 table 或它包含的功能不在同一个 32K 程序字闪存页面中，由于必须让地址生成单元从正确的页面读取，将会有更大的开销，或设置 PC 以拨打长途电话。)
另一方面，如果整个 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 个案例）并且它们都以相似的频率出现，那么在长 运行 中查找 table 会更快。如果案例的频率明显不同（例如，案例 1 比案例 2 更有可能，案例 2 比案例 3 更有可能，等等）然后，如果您首先订购最有可能的案例的开关，那么开关将是在长 运行 中更快。对于只有少数情况的边缘情况，对于大多数执行而言，switch（可能）无论如何都会更快，并且更具可读性并且更不容易出错。
如果 switch 中只有少数 case，或者某些 case 比其他 case 发生的频率更高，那么进行 switch 的测试和分支可能比使用查找花费更少的周期 table.另一方面，如果您有多个以相似频率发生的案例，那么查找最终可能会平均更快。
提示：除非您知道查找肯定会更快并且 运行 所花费的时间很重要，否则请使用开关。
编辑： 我的 switch 示例有点不公平，因为我忽略了原始问题并内联 'body' 个案例以突出真实使用 switch 而不是查找的优势。如果交换机也必须进行呼叫，那么它只对第一种情况有优势！
使用函数指针的 LUT 会强制编译器使用该策略。理论上它 可以 将 switch 版本编译为与 LUT 版本基本相同的代码（现在您已经为两者添加了越界检查）。实际上，这不是 gcc 或 clang 选择做的事情，因此值得查看 asm 输出以了解发生了什么。
（更新：gcc -fpie（大多数现代 Linux 发行版默认开启）喜欢制作 table 相对偏移量，而不是绝对函数指针，因此 rodata也是与位置无关的。GCC Jump Table initialization code generating movsxd and add?。这可能是一个优化失误，请参阅我的回答以获取指向 gcc 错误报告的链接。手动创建一个函数指针数组可以解决这个问题。）
我把代码 on the Godbolt compiler explorer 和两个函数放在一个编译单元中（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();
}
另请参阅 How do the likely() and unlikely() macros in the Linux kernel work and what is their benefit?
x86
在 x86 上，clang 为开关创建自己的 LUT，但条目是指向函数内部的指针，而不是最终函数指针。所以对于 clang-3.7，switch 恰好编译成比手动实现的 LUT 更差的代码。无论哪种方式，x86 CPU 往往具有可以处理间接调用/跳转的分支预测，至少在它们易于预测的情况下是这样。
GCC 使用一系列条件分支 (but unfortunately doesn't tail-call directly with conditional branches, which AFAICT is safe on x86。它按顺序检查 1, <1, 2, 3，大部分是未采用的分支直到找到匹配项。
他们为 LUT 编写了基本相同的代码：边界检查，用 mov 将 arg 寄存器的高 32 位归零，然后使用索引寻址模式进行内存间接跳转。
手臂：
gcc 4.8.2 with -mcpu=cortex-m4 -O2 生成有趣的代码。
正如 Olaf 所说，它使 1B 条目 成为一个内联 table。它不会直接跳转到目标函数，而是跳转到一个普通的跳转指令（比如b func3）。这是正常的无条件跳转，因为它是尾调用。
每个 table 目标条目需要 significantly more code (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 如果在轻量级 ARM 内核上，tbb 的分支预测与完全间接跳转或调用 (blx) 之间存在很大差异。加载 table 的数据访问可能比使用 switch.
我读到间接分支在 ARM 上的预测很差。如果间接分支每次都有相同的目标，我希望这还不错。但如果没有，我认为大多数 ARM 内核不会像大型 x86 内核那样找到短模式。
指令 fetch/decode 在 x86 上需要更长的时间，因此避免指令流中出现气泡更为重要。这就是 x86 CPU 具有如此出色的分支预测的原因之一。现代分支预测器甚至可以很好地处理间接分支的模式，基于该分支的历史 and/or 导致它的其他分支。
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
有关 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 优化。 我们可以看到即使编译器有能力，开关也没有转换成跳转table