在另一个帖子中，我被告知在速度和紧凑性方面，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语句转换为跳转表。既然这可能是错的，我想知道为什么！
谢谢你的帮助！
由于我是评论的原作者，我必须添加一个你在问题中没有提到的非常重要的问题。也就是说，原件是关于嵌入式系统的。假设这是一个典型的带有集成闪存的裸机系统，与我将集中精力的PC有很大的不同。
这种嵌入式系统通常具有以下约束。
对于例如STM32F4xx读取需要6个时钟，150MHz / 3.3V，128位（4个字）。因此，如果需要数据访问，很可能会为所有数据提取超过12个时钟延迟（涉及额外的周期）。
假设紧凑的状态码，对于实际问题，这对该架构（Cortex-M4）具有以下影响：
另请注意，switch不需要函数，因此编译器可以完全优化代码。这对于查找表是不可能的。至少不需要函数入口/出口的代码。
由于上述和其他因素，估计很难说。它在很大程度上取决于您的平台和代码结构。但假设上面给出的系统，开关很可能更快（更清晰，顺便说一下）。
首先，在某些处理器上，间接调用（例如通过指针） - 如查找表示例中的那些 - 成本很高（管道断裂，TLB，缓存效应）。间接跳跃也可能是真的......
然后，一个好的优化编译器可能会在Switch示例中内联对func1()的调用;那么你就不会为内联函数运行任何序言或结尾。
您需要确定基准，因为许多其他因素对性能至关重要。另见this（以及那里的参考）。
msc的答案和评论为您提供了很好的提示，说明为什么性能可能不是您所期望的。基准测试是规则，但结果会因架构而异，并且可能随编译器的其他版本而变化，当然也会选择其配置和选项。
但请注意，您的2段代码不会在state上执行相同的验证：
state不是定义的值之一，FUNC1和FUNC2之外的所有值的未定义行为。在没有对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读取地址然后调用例程。进行调用会增加另外一些循环来推动指令指针和其他位和bob（例如设置堆栈帧）的内务处理。
例如，在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更可能等），那么，如果您首先订购最可能案例的交换机，那么交换机将是从长远来看，速度更快。对于边缘情况，当您只有少数情况时，无论如何，对于大多数执行，交换机（可能）会更快，并且更易读，更不容易出错。
如果交换机中只有少数情况，或者某些情况比其他情况更频繁，那么进行测试和交换分支可能比使用查找表需要更少的周期。另一方面，如果你有少数情况发生频率相近，那么查找可能最终会更快。
提示：使用开关，除非您知道查找肯定会更快，并且运行所需的时间非常重要。
编辑：我的开关示例有点不公平，因为我忽略了原始问题，并在案例的“正文”中加入了突出显示使用开关查看的真正优势。如果开关也必须进行呼叫，那么它只对第一种情况有利！
使用函数指针的LUT迫使编译器使用该策略。从理论上讲，它可以将交换机版本编译为与LUT版本基本相同的代码（现在您已经为两者添加了越界检查）。在实践中，这不是gcc或clang选择做的，所以值得查看asm输出以查看发生了什么。
（更新：gcc -fpie（在大多数现代Linux发行版上默认启用）喜欢制作相对偏移的表，而不是绝对函数指针，所以rodata也是位置无关的.GCC Jump Table initialization code generating movsxd and add?。这可能是一个错过优化，见我在那里找到了gcc bug报告的链接。手动创建一个函数指针数组可以解决这个问题。）
我将代码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上，clang为开关创建了自己的LUT，但是条目是函数内的指针，而不是最终的函数指针。因此对于clang-3.7，交换机恰好编译为严格比手动实现的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与-mcpu=cortex-m4 -O2制作有趣的代码。
正如奥拉夫所说，它制作了一个1B条目的内联表。它不直接跳转到目标函数，而是跳转到正常的跳转指令（如b func3）。这是一个正常的无条件跳跃，因为它是一个尾调用。
如果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）之间的差异有很大差异。加载表的数据访问可能比使用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
有关Microchip dsPIC的类似分析，请参见Mike of SST's answer。
为了获得更多的编译器输出，这里是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优化。我们可以看到，即使编译器具有该功能，交换机也不会转换为跳转表。