跳到主要內容

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 做了太多事, 單就演算法分析不足以推斷出實務上的好壞, 果然還是需要實測來最佳化效能。

留言

這個網誌中的熱門文章

(C/C++ ) 如何在 Linux 上使用自行編譯的第三方函式庫

以使用 LevelDB 為例。 抓好並編好相關檔案,編譯方式見第三方函式庫附的說明:$ ls include/ # header files leveldb/ $ ls out-shared/libleveldb.so* # shared library out-shared/libleveldb.so@ out-shared/libleveldb.so.1@ out-shared/libleveldb.so.1.20* 下面的例子用 clang++ 編譯,這裡用到的參數和 g++ 一樣。 問題一:找不到 header$ clang++ sample.cpp sample.cpp:5:10: fatal error: 'leveldb/db.h' file not found #include "leveldb/db.h" ^ 1 error generated. 解法:用 -I 指定 header 位置 問題二:找不到 shared library$ clang++ sample.cpp -I include/ /tmp/sample-2e7dd8.o: In function `main': sample.cpp:(.text+0x1e): undefined reference to `leveldb::Options::Options()' sample.cpp:(.text+0x6f): undefined reference to `leveldb::DB::Open(leveldb::Options const&, std::string const&, leveldb::DB**)' sample.cpp:(.text+0x10c): undefined reference to `leveldb::Status::ToString() const' sample.cpp:(.text+0x7d0): undefined reference to `leveldb::Status::ToString() const' clang: error: linker command failed with exit code 1 (u…

熟悉系統工具好處多多

記一下以前很困擾, 現在秒殺的小事。 更新這篇的時候, 忘了函式庫用的 man page 裝在那個 package。以前就會想辦法 google, 運氣好一下會找到, 運氣不好會多找一會兒。 這回我想到新作法:$ strace -e open man 3 printf > /dev/null # 發現是讀 /usr/share/man/man3/printf.3.gz $ dpkg --search /usr/share/man/man3/printf.3.gz # 找到套件名稱 manpages-dev $ aptitude show manpages-dev # 確認描述符合, 收工

virtualbox 使用 USB 裝置

2012-12-16 更新 現在 (4.x 版) 似乎無需做任何設定, 只要有裝 Oracle VM VirtualBox Extension Pack, 在 VirtualBox 視窗右下角按 USB 的圖示, 再點目標裝置, 即可加入或移除該裝置 同一時間只有 host 或 guest 可擁有該裝置, 所以從 guest OS 移除, 相當於接回 host OS 目前 VirtualBox 只支援 USB 2.0 的插槽, 若偵測不到時, 注意一下是否為這個問題 有時拔拔插插, VirtualBox 會進入奇怪的狀態, 接上去 guest OS 無法連接且跳出 device is busy 的錯誤訊息。試看看拔除該裝置, 重開 guest OS (續上則) 若重開 guest OS 無效, 並且 host OS 已移除該裝置, VirtualBox 的 USB 清單卻仍顯示 "captured", 試看看拔除該裝置, 重開 host OS原文網路上搜一下, 比較多是 Ubuntu 當 host 的解法, 我的情況是 Win7 當 host, Ubuntu 當 guest。 這兩篇說明很詳細《Learn How to Set Up USB and Networking Options in VirtualBox》《幻影千瞳的部落格: VirtualBox 使用筆記(二):使用 USB 裝置》 現在的版本圖形介面很好用了, 不用像第二篇說的那樣用指令操作。這裡記下我的操作步驟: 關掉 guest OS 在 VirtualBox 選單, 選擇 guest OS -> Settings -> USB -> Enable USB 2.0 會出現訊息框, 說明要安裝 Oracle VM VirtualBox Extension Pack。下載後安裝它 host OS 插入 USB 隨身碟 在 VirtualBox 選單, 選擇 guest OS -> Settings -> USB, 點右邊有綠色 "+" 的 USB 頭的圖示, 選擇該 USB 隨身碟, 加入它的 filter 從 host OS 移除 USB 隨身碟 開啟 guest OS 插入 USB 隨身碟, 於是 guest OS 會自動偵測…