2008年7月1日 星期二

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

Standard
就階層面來看, 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 的情況,相信效能會和辛苦成正比才是。