g++ 最佳化 switch-case 的一個小例子

最近看到一段程式如下:

bool isOkay(Type type) {
  switch (type) {
    case A:
    case C:
    case D:
    case E:
    case G:
    case I:
    case K:
    case L:
    case Y:
      return false;
    default:
      ;
  }
  return true;
}

原本想說 switch-case 和一串 if 沒差太多, 這樣寫應該比 set 慢。畢竟從演算法的角度來看, 前者是線式比對, 複雜度和 type 特例的數量成正比, 而 set 保證是 O(1)。

後來經 command 提醒, 想說搞不好 compiler 有做最佳化, 還是來看產生的組語好了。結果 compiler 真的有做最佳化, 從組語來看, switch 不見得會比較慢。觀察用的程式見這裡, 用 g++ -O2 產生的組語見這裡。

結論是:

• 寫成「一串 if」, 結果的確是一串 cmp 和 je, 複雜度如原本預期。
• 但是 switch 讓 compiler 知道比較同一個變數, compiler 有機會做最佳化, 變成少數幾個計算和比較。
• 使用 set 有額外呼叫函式的成本, 對於簡單計算的例子, 是不可忽略的額外成本。

使用 -O2 後, set 的版本有些複雜, 沒辦法藉由「大概看看+腦補推測」搞懂。實測的結果如下:

$ g++ -O2 benchmark_switch_cases_check.cpp -DSWITCH; time ./a.out;
1700000000

real    0m6.398s
user    0m6.396s
sys     0m0.000s
$ g++ -O2 benchmark_switch_cases_check.cpp -DALOTIF; time ./a.out
1700000000

real    0m8.392s
user    0m8.389s
sys     0m0.000s
$ g++ -O2 benchmark_switch_cases_check.cpp -DIF; time ./a.out
1700000000

real    0m8.402s
user    0m8.389s
sys     0m0.008s
$ g++ -O2 benchmark_switch_cases_check.cpp ; time ./a.out
1700000000

real    0m10.092s
user    0m10.089s
sys     0m0.000s

所花時間是竟然是 switch < if < set。

演算法分析可以去掉明顯的壞主意, 但是 compiler 做了太多事, 單就演算法分析不足以推斷出實務上的好壞, 果然還是需要實測來最佳化效能。