C++:交换机语句与查找表的性能

Question

我试图比较switch语句和查找表的性能，如下所示。

这是使用switch语句的代码

#include <stdio.h>
int main()
{
int n = 3;
for (long i = 0; i < 10000000; ++i) {  
switch (n) {
case 0:
printf("Alpha");
break;
case 1:
printf("Beta");
break;
case 2:
printf("Gamma");
break;
case 3:
printf("Delta");
break;
default:
break;
}
}
return 0;
}

以下是使用查找表的代码：

#include <stdio.h>
static char const * const Greek[4] = {
"Alpha",
"Beta",
"Gamma",
"Delta"
};
int main()
{
int n = 3;
for (long i = 0; i < 10000000; ++i) {  
if (n >= 0 && n < 4) {
printf(Greek[n]);
}
}
return 0;
}

我在 ubuntu 14.04 上运行两个程序，gcc 版本 4.8.4，使用 perf 版本 4.4.13 来分析性能。结果：

• 切换语句：6.764077822 秒
• 查找表：6.665140483 秒

我不知道为什么开关语句的运行速度比查找表慢。众所周知，使用跳转表的 Switch 语句，我认为它应该比我的程序中的查找表运行得更快(它有额外的 if 语句(。

Answer 1

如果使用优化进行编译，则代码没有开关和查找表。我只是一个 for 循环，它使用相同的固定字符串多次调用printf()。事实上，任何最不合理的编译器都会检测到n = 3永远不会更改并对其进行优化。也许您可以在循环内添加一个n = rand() % 4;。

另一方面，如果您没有使用优化进行编译，则采用计时是没有意义的。

谈到你的问题，我希望查找表比 switch 语句更快，因为 switch 语句将完全破坏分支预测，而 if 将没有问题，始终为真。

Answer 2

您的基准测试完全不足以衡量switch/lookup-table 性能：几乎所有时间都花在printf()调用中。如果switch/lookup-table 差异有任何影响，则由于总运行时间较大，它与测量噪声相比相形见绌。

---

供参考：我预计在热、紧密的循环中的表查找只有大约十个时钟周期。在 2 GHz CPU 上，所有 10000000 次迭代只需 0.05 秒(粗略估计，很容易出错两倍，但这不会影响整体评估(。这是您总运行时间的 1%！