使用 C 語言實作查表法取代 switch

就階層面來看, C 語言是個不高不低的語言,造成許多語法其實都可以有其他不凡的實作方式。尤其是一個看似基本且常用的方法,其實可能大量的暗藏玄機,值得我們惡搞。而對多數人來說,有一個一定不陌生的語法『 switch 』就相當有趣。在某些情況下,是否能利用『查表法』取代 switch,得到程式效能上的提升?此議題相當具有可探討性。

這是一個簡單使用 switch 語法的例子(switch_sample.c):
#include <stdio.h>

int main(int argc, char** argv)
{
int i;

if (argc<2)
return 1;

i = atoi(argv[1]);
switch(i) {
case 0:
printf("Hello! Mr. Zero\n");
break;
case 1:
printf("Hello! Mr. One\n");
break;
}

return 0;
}

編譯:
# gcc -o switch_sample switch_sample.c

實際執行:
# ./switch_sample 0
Hello! Mr. Zero
# ./switch_sample 1
Hello! Mr. One

仔細觀察該程式的內部運作,發現 switch 語法在編譯後實際執行時,是使用一連串的『比對』、『判斷』和『跳越』動作來達成任務,其實相當耗 CPU 的執行時間和寶貴的運算資源,若是 switch 的『設計龐大』,對 CPU 來說也是個相當可觀的負擔,尤其在許多 Embedded System 上會特別有明顯的影響。

由於 switch 的 CPU 時間消耗驚人,利用查表法來減少些比對判斷或許是個可行的方法。一般來說的查表法,是因為我們的資料需要『大量的運算』才能產生,所以『事先』計算好並建成一個數據表放在程式內部,以便程式在『真正執行』時直接快速提取其結果使用,而不必當場計算所需要的數據。又因查表的過程中,是直接對某個 pointer+N 去做存取資料,所以速度極快。

尋思,建表除了擺放一般數據之外,是否可以建立一個 function address 的表?並藉由表內的 address 直接 call function 執行動作?如此便可省下一大筆 CPU 判斷指令的執行時間。

經過實作(table_sample.c):
#include <stdio.h>

void switch_zero(void)
{
printf("Hello! Mr. Zero\n");
}

void switch_one(void)
{
printf("Hello! Mr. One\n");
}

int main(int argc, char** argv)
{
int i;
/* 定義一個表儲存函式位置 */
void (* switch_function[])() = { switch_zero, switch_one };

if (argc<2)
return 1;

i = atoi(argv[1]);
/* 直接 call 對應之函式 */
switch_function[i]();

return 0;
}

編譯:
# gcc -o table_sample table_sample.c

實際執行:
# ./table_sample 0
Hello! Mr. Zero
# ./table_sample 1
Hello! Mr. One

實作結果很順利,跑出了預期的結果。雖然分別寫成 function 時稍嫌麻煩,但若碰到大量 switch-case 的情況,相信效能會和辛苦成正比才是。

留言

  1. "仔細觀察該程式的內部運作,發現 switch 語法在編譯後實際執行時,是使用一連串的『比對』、『判斷』和『跳越』動作來達成任務,其實相當耗 CPU 的執行時間和寶貴的運算資源"

    想請教一下上面這個結論怎麼來的?

    不知你是否聽過branch table(jump table)這個東東,正常的compiler optimization 開下去switch的語法都會以branch table來實現。

    我稍微加大你的switch block,再加一些有的沒的case和default,以gcc 3.4.6 -02做實驗(因為我也沒看過真的assembly code 長什麼樣子...:P)在main function 看到的code 是長這樣

    -------------------------------------
    400537: bf 91 06 40 00 mov $0x400691,%edi
    40053c: eb ed jmp 40052b (main+0x2b)
    40053e: bf a1 06 40 00 mov $0x4006a1,%edi
    400543: eb e6 jmp 40052b (main+0x2b)
    400545: bf b0 06 40 00 mov $0x4006b0,%edi
    40054a: eb df jmp 40052b (main+0x2b)
    40054c: bf c1 06 40 00 mov $0x4006c1,%edi
    400551: eb d8 jmp 40052b (main+0x2b)
    400553: bf d1 06 40 00 mov $0x4006d1,%edi
    400558: eb d1 jmp 40052b (main+0x2b)
    40055a: bf e0 06 40 00 mov $0x4006e0,%edi
    40055f: eb ca jmp 40052b (main+0x2b)
    400561: bf f1 06 40 00 mov $0x4006f1,%edi
    400566: eb c3 jmp 40052b (main+0x2b)
    400568: bf 02 07 40 00 mov $0x400702,%edi
    40056d: eb bc jmp 40052b (main+0x2b)
    40056f: bf 12 07 40 00 mov $0x400712,%edi
    400574: eb b5 jmp 40052b (main+0x2b)
    400576: bf 21 07 40 00 mov $0x400721,%edi
    40057b: eb ae jmp 40052b (main+0x2b)
    40057d: bf 30 07 40 00 mov $0x400730,%edi
    400582: eb a7 jmp 40052b (main+0x2b)
    -------------------------------------------
    ps:應該是中括號啦,不過打不出來..

    另外個人覺得用function pointer array 的缺點是:
    1 index 不能太離散,比如說 1-1000但是可能只有100 值需要處理
    2 不能inline 啦

    小小意見..:P

    回覆刪除
  2. :D
    不是使用 pointer array 的方式,過程中會有 JNZ 等此類的命令存在,要是再有許多的內部動作,連帶著和該暫存器相關的 pop/push 數量也是可預見的,雖然大部份情況是可接受的。抱歉遺漏些數據,之後補上,可再多做說明。

    另外,你講的沒錯,現在的 compiler 已經能幫助開發者做許多的『優化』,多數情況都會有很好的處理,本文目的是在探討優化的範疇。

    至於 inline 的問題,其實是要看當時情況取捨,我想各有優缺取捨,尤其是在特殊硬體或有限制性的環境。不是每種方法都適用於所有的地方。

    回覆刪除
  3. 效能不會和辛苦成正比,浪費的開發時間才會。

    pointer array performance 效能很好,function table 則否。

    當數值連續時,很多 compiler 會自己轉查表。
    至於 function table,前面有人提到,會沒有 inlining,這是其一
    另外,switch 是一連串的 cmp, jz, cmp, jz, cmp, jz,
    順利的話,一整串下來,只會有數值符合的那一次 jmp

    但 function table,則是 cmp, push(or mov), function pointer 載入到 register,call, ret, pop, 配上來自迴圈的 jnz, jb or loop (執行 n 次)

    call 絕對比 jmp 來得昂貴許多,
    何況 switch 這種狀況通常是 near jump
    而你的 functions,若是很不幸的話,worst case 可能全部在不同的 page 上...

    另外,case 可以連續好幾個不接 break,這是另一個優點。(雖然 pointer array 也可以好幾個 pointer 指向同一個地方)

    結論:除非是 case 內數值大部分連續,可以用 pointer array,否則你就是在浪費時間,而且還幫你的程式減速...

    不過,使用 function table 可以提供比 switch case 更好的可讀性和可維護性,所以很多時候仍然是相當好用

    雖然理論上在 n 很大的時候,複雜度是相同,但 real world application 在這種小地方是真的會有差。

    回覆刪除
  4. 最重要的是 jnz ...etc 的開銷,每一次指令其實都罷佔了 CPU 機械周期,若其中又碰上一些 call 或 jmp , pop/push 到堆疊的開銷也是不可忽視的。

    不過要符合這種情況使用,而且是否真的有效率,還是要靠當時狀況而定,這只是一種優化的可能手段。

    但據說 gcc4 的優化已經處理很好,不過我沒仔細測過並玩弄一下就是了。

    回覆刪除
  5. switch case 不只是jnz而已~他還需要準備一個table,一樣要耗掉mov這種指令,根據我們實作的效果if 加上 switch才是最省的方式,把常用的case用if取代掉,其他的用switch,不過此方法前提是switch裡的case有超多的。

    回覆刪除

張貼留言

這個網誌中的熱門文章

有趣的邏輯問題:是誰在說謊

Web 技術中的 Session 是什麼?

淺談 USB 通訊架構之定義(二)

淺談 USB 通訊架構之定義(一)

Reverse SSH Tunnel 反向打洞實錄