喝咖啡加咖啡伴侣，学C程序设计配《C程序设计伴侣》——样章更新，当当网现已接受预订

folklore

回复 200# starwing83


    我是说switch是用级联的if实现的跳转表高效

folklore

回复 201# folklore


    倒，打字漏字，
比跳转表高效。

starwing83

回复 201# folklore


    switch有可能被优化成级联if，但是大多数情况下（几乎所有常见情况——即case分布均匀的情况），跳转表都几乎肯定比级联if要好，无论是最终产生的机器码数量还是执行速度上都是这样……为了达到这个效果C/C++甚至不允许case后面出现非int元素和非constexpr元素……

folklore

回复 203# starwing83


我本来也是这么想的，你忘了分支预测和函数指针的开销了。
最不好办是的函数指针，遇到这玩意，基本就无法做任何优化了。

folklore

回复 204# folklore


    原本我也怀疑为什么win32的消息loop为什么不做成跳转表，因为它有成千上成的分支。而跳转表基本上开销是固定的。

zhaohongjian000

回复 204# folklore

你不这么想编译器这么想。switch的case后面如果是多个连续的数，就极有可能被优化为跳表的形式。另外，你提到函数指针，是指什么情况？
   

folklore

回复 206# zhaohongjian000


    我明白了，你们讲的跳转表是指使用相对跳转指令跳转（JMP %Eax）。
这样的话，的确没有函数开销了。一般说跳转表，会是这样子的：

1. 
   
2. void (*fun_type[n](int))={fun1,fun2,fun3};
   
3. 
   
4. do{
   
5.   fun_type[callindex](tag);
   
6. }while();
   

复制代码

zhaohongjian000

folklore 发表于 2012-09-25 19:27
回复 206# zhaohongjian000

原来说的不是一个东西，我以为说的是编译器中的jump table。
这个用函数开销也太大了。

starwing83

回复 207# folklore


    你以为我们说的是什么东西？？switch必须是用这种跳转表实现的哇。其实本质上就是被inline掉的函数指针表。

liuiang

有人冲出来说：跳转表是O(1)，if分支是O(n)，这个问题就完美了~~~~~~~~