函数数组的性能：if语句和switch语句的对比

Question

我正在编写代码中非常关键的性能部分，我有一个疯狂的想法，即用函数指针数组替换 case 语句（或 if 语句）。

让我演示一下；这是正常版本：

while(statement)
{
    /* 'option' changes on every iteration */

    switch(option)
    {
        case 0: /* simple task */ break;
        case 1: /* simple task */ break;
        case 2: /* simple task */ break;
        case 3: /* simple task */ break;
    }
}

以下是“回调函数”版本：

void task0(void) {
    /* simple task */
}

void task1(void) {
    /* simple task */
}

void task2(void) {
    /* simple task */
}

void task3(void) {
    /* simple task */
}

void (*task[4]) (void);

task[0] = task0;
task[1] = task1;
task[2] = task2;
task[3] = task3;

while(statement)
{
    /* 'option' changes on every iteration */

    /* and now we call the function with 'case' number */
    (*task[option]) ();
}

哪个版本会更快？函数调用的开销是否抵消了普通switch（或if）语句的速度优势？

当然，后一种版本不太易读，但我正在尽力提高所有速度。

在我准备好之前，我将对此进行基准测试，但如果有人已经回答了，那我就不必麻烦了。

- OptimizingBastard

---

我的猜测是开关速度会更快——没有函数调用，缓存缺失也会更少。但是，需要测试一下，因为像往常一样，“这取决于情况”。 - Erik

我不认为这会有太大的区别（如果有的话）。话虽如此，你试过运行它们来看哪个更快吗？ - abeln

除非你的任务函数非常微小，否则几条指令的差异都不会有太大影响。 - Paul R

任务函数非常小。它们通常只是一个赋值或小的短循环（几次迭代）。任务函数总是操作全局变量。 - OptimizingBastard

这不是一个疯狂的想法。这实际上是一个相当广为人知的技术。 - JeremyP

哦，出于某种原因我之前没有遇到过它。如果这是一个相当知名的技术，那么它一定有一些好处。这种设计通常在哪些地方使用？ - OptimizingBastard

Answer 1

我认为在最后，你的switch语句会是最快的，因为函数指针有查找函数和调用函数本身的“开销”。而switch只是一个直接的jmp表。当然，这取决于不同的事情，只有测试才能给你答案。这是我的两分钱。

- Tony The Lion

---

我认为case和if语句最大的问题在于，如果所需操作在列表末尾，则查找正确的case需要更长时间。 - OptimizingBastard

@OptimizingBastard - 请查看http://en.wikipedia.org/wiki/Branch_table#Compiler_generated_branch_tables，了解编译器并不总是生成长串的if/else语句。最好的建议是测试和测量两种方法。 - AShelly

我认为使用switch-case语句的最大优点是其更易于阅读。我仍然对许多人在处理函数指针以及函数指针数组时遇到问题感到惊讶。应该始终考虑可读性。 - Anthony

Answer 2

哪个版本更快取决于具体情况。naive实现的switch是一个庞大的if ... else if ... else if ...结构，平均执行时间为O(n)，其中n是案例数量。而使用jump table，则是O(1)，因此如果有许多不同的case，并且后面的case使用次数越多，那么使用jump table的可能性就越高。对于少量案例或者第一个case被选择的情况下，naive实现更好。但这一问题还会变得更加复杂，因为编译器在认为使用jump table更快时，即使你编写了switch语句，也可能选择使用jump table。

唯一知道应该选择哪种方法的方式是对代码进行性能测试。

- JeremyP

---

平均情况下，使用n个案例需要O(n)的时间。除非您只使用第n个案例，否则它不会像O(n/2)那样。 - conradkleinespel

@conradk 在“大O符号”表示法中，O(n * k)其中k是一个常数，等同于O(n)。 - JeremyP

哦，好的。谢谢@JeremyP。 - conradkleinespel

Answer 3

如果你的编译器至少具备基本的优化能力，那么 switch 语句应该被编译成一个 分支表，它本质上与函数数组相同。

- Anon

---

我认为GCC 4.x应该可以处理它。我必须说这是一个相当聪明的技巧。我发现**-Os标志生成带有switch语句的最快代码，但-O3**标志生成带有if-else语句的更快代码。 - OptimizingBastard

Answer 4

首先，我会随机暂停几次，以确保在这个分派中花费足够的时间才值得优化它。

其次，如果是这样，由于每个分支花费的周期非常少，您希望使用跳转表来跳转到所需的分支。 switch语句存在的原因是建议编译器生成一个跳转表，如果switch值是紧凑的，则可以生成一个跳转表。

switch值列表有多长？如果很短，if-ladder仍然可能更快，特别是如果将最常用的代码放在顶部。 if-ladder的替代方法（我从未实际看到任何人使用过）是if-tree，即二叉树的代码等价物。

您可能不想要一个函数指针数组。 是的，它是一个函数指针的数组引用，但是调用函数需要几个指令的开销，而且听起来这可能会超过每个函数内部执行的少量工作。

无论如何，查看汇编语言或单步执行指令级别将为您提供关于其效率的良好想法。

- Mike Dunlavey

Answer 5

一个好的编译器会将一个数值范围较小的 switch 语句编译成一个条件判断，看这个值是否在该范围内（有时可以进行优化），然后跳转到一个跳转表。这几乎肯定比函数调用（直接或间接）更快，因为：

1. 跳转比调用要便宜得多（调用必须保存调用破坏的寄存器，调整堆栈等）。
2. switch 语句中的代码可以利用调用者已经缓存的表达式值。

可能有一种极其先进的编译器能够确定通过函数指针调用只引用了一小组静态链接函数之一，并因此大量优化，甚至消除调用并用跳转替换它们。但我不会指望它。

- R.. GitHub STOP HELPING ICE

Answer 6

我最近看到了这篇文章，因为我也在思考同样的问题。最终我花时间试了一下。当然，它的效果取决于你正在做什么，但对于我的虚拟机来说，它加速了不少（15-25%），并且让我简化了一些代码（这可能是加速的主要原因）。例如（为了清晰起见，代码已经简化），一个“for”循环可以轻松地使用for循环实现：

void OpFor( Frame* frame, Instruction* &code )
{
  i32 start = GET_OP_A(code);
  i32 stop_value = GET_OP_B(code);
  i32 step = GET_OP_C(code);
  // instruction count (ie. block size)
  u32 i_count = GET_OP_D(code);
  // pointer to end of block (NOP if it branches)
  Instruction* end = code + i_count;

  if( step > 0 )
  {
    for( u32 i = start; i < stop_value; i += step )
    {
      // rewind instruction pointer
      Instruction* cur = code;

      // execute code inside for loop
      while(cur != end)
      {
        cur->func(frame, cur);
        ++cur;
      }
    }
  }
  else
    // same with <=
}

- Anon