标 題: 更深入一點了解switch語句及c/c++對const的處理
發信站: BBS 水木清華站 (Thu Feb 24 20:58:16 2005), 站内
更深入一點了解 switch 語句 及 c/c++ 對 const 的處理
謝煜波
前段時間在論壇上看見台灣李維在 < <Borland傳奇> > 一書中對windows程式設計模式中,消息處理部分有如下的一些分析:
他說,在消息處理循環中,一般的形式是這樣的
MSG msg ;
switch( msg ){
case WM_XXXXXXX :
....
case WM_XXXXXXX :
....
case WM_XXXXXXX :
....
} ;
李維說,這種模式是很低效的,因應經過彙編後,這種C代碼會産生如下的彙編代碼
cmp .... .....
jnz .... .....
cmp .... .....
jnz .... .....
cmp .... .....
jnz .... .....
如果你的 case 足夠多,比如,你有一萬條消息需要處理,而不幸的是你把一條最常用的消息
放在了最後一位,那麼當這條消息要得到處理,會首先經過一萬次的cmp與jnz, 李維認為,這
是非常非常低效的,實在是低效的忍無可忍,無需再忍~~:P
在起初,我也是這樣認為的,但近來的閱讀及實驗卻發現,這種看法非常片面,今天就來談談這個問題( 所有實驗在 linux 平台下完成 )
首先看一到用 c 編寫的程式
int switch_test_first( int x )
{
int res ;
switch( x ){
case 100 :
res = 1 ;
break ;
case 102 :
res = 2 ;
break ;
case 103 :
res = 3 ;
break ;
}
return res ;
}
然後,我們用 gcc 将它編譯成彙編檔案( 使用 -S 開關 )
gcc -S ta.c
将得到如下的彙編檔案( ta.s )
.file "ta.c "
.text
.globl switch_test_first
.type switch_test_first,@function
switch_test_first:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
movl 8(%ebp), %eax
.file "ta.c "
.text
.globl switch_test_first
.type switch_test_first,@function
switch_test_first:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
movl 8(%ebp), %eax
movl %eax, -8(%ebp)
cmpl $102, -8(%ebp) // 1
je .L4 // 2
cmpl $102, -8(%ebp) // 3
jg .L8 // 4
cmpl $100, -8(%ebp) // 5
je .L3 // 6
jmp .L2 // 7
.L8:
cmpl $103, -8(%ebp)
je .L5
jmp .L2
.L3:
movl $1, -4(%ebp)
jmp .L2
.L4:
movl $2, -4(%ebp)
jmp .L2
.L5:
movl $3, -4(%ebp)
.L2:
movl -4(%ebp), %eax
leave
ret
.Lfe1:
.size switch_test_first,.Lfe1-switch_test_first
.ident "GCC: (GNU) 3.2.2 20030222 (Red Hat Linux 3.2.2-5) "
注意看檔案中 // 1 ~ // 7 的部份,從這個部份,我們可以看出,gcc确實是把一些case語句轉成了李維所說的那種方式進行處理,我們看見了代碼中存在有衆多的 cmpl 與 jmp 語句
這就相當于你使用if..else..一樣,但是否總是這樣呢?
我們下面改動一下 ta.c 這個檔案,在裡面再多加一些 case 語句
int switch_test_first( int x )
{
int res ;
switch( x ){
case 100 :
res = 1 ;
break ;
case 102 :
res = 2 ;
break ;
case 103 :
res = 3 ;
break ;
case 104 :
res = 4 ;
break ;
case 105 :
res = 5 ;
break ;
case 106 :
res = 6 ;
break ;
}
return res ;
}
這個 new_ta.c 與原來的 ta.c 在結構上完全相同,唯一不同的就是 case 語句的數量變多了,下面我們來編譯一下這個檔案
gcc -S new_ta.c
下面是我們産生的更新的彙編檔案
.file "new_ta.c "
.text
.globl switch_test_first
.type switch_test_first,@function
switch_test_first:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
movl 8(%ebp), %eax
subl $100, %eax
movl %eax, -8(%ebp)
cmpl $6, -8(%ebp)
ja .L2
movl -8(%ebp), %edx
movl .L9(,%edx,4), %eax
jmp *%eax
.section .rodata
.align 4
.align 4
.L9: // A
.long .L3
.long .L2
.long .L4
.long .L5
.long .L6
.long .L7
.long .L8
.text
.L3: // 1
movl $1, -4(%ebp)
jmp .L2
.L4: // 2
movl $2, -4(%ebp)
jmp .L2
.L5: // 3
movl $3, -4(%ebp)
jmp .L2 // 4
.L6:
movl $4, -4(%ebp)
jmp .L2 // 5
.L7:
movl $5, -4(%ebp) // 6
jmp .L2
.L8: // 7
movl $6, -4(%ebp)
.L2:
movl -4(%ebp), %eax
leave
ret
.Lfe1:
.size switch_test_first,.Lfe1-switch_test_first
.ident "GCC: (GNU) 3.2.2 20030222 (Red Hat Linux 3.2.2-5) "
仔細比較一下這個最新的 new_ta.s 與前面的 ta.s,精華全在裡面了!
首先 new_ta.s 比前面的 ta.s 多了一個 .L9 部分，而且它的 // 1 ~ // 7 中沒有了前面
ta.s 檔案中所存在的衆多的 cmpl 與 jmp 語句，那麼，現在這樣的代碼又是怎麼實作
switch 語句中的跳轉的呢？我們來仔細分析一下它新多出來的 .L9 部份。
.section .rodata
.align 4
.align 4
.L9:
.long .L3
.long .L2
.long .L4
.long .L5
.long .L6
.long .L7
.long .L8
.text
顯而易見，.L9 部份是一個我們最常見的資料結構——表，它的每一項都是一個标号，而這個标号，恰恰是每個 case 語句的入口标号！
這很容易讓我們想到，它很可能是用了一張表來存放所有的 case 語句的入口，然後，在
執行 switch 語句的時候就從這個表中直接檢出相應的 case 語句的入口位址，然後跳轉
到相應的 case 語句去執行，就像hash_table似的。具體是不是這樣呢？我們看看進入
switch 部份的代碼:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
movl 8(%ebp), %eax
subl $100, %eax
movl %eax, -8(%ebp)
cmpl $6, -8(%ebp)
ja .L2
movl -8(%ebp), %edx
movl .L9(,%edx,4), %eax // 1
jmp *%eax // 2
果然如此！首先在 // 1 處根據%edp的值（其值相當于表的下标）在.L9的表中找到相應
case 語句的入口位址，并把這個位址存到%eax中，然後通過 // 2 （這是一個間接跳轉
語句）轉到%eax存放的位址中，也即相應的case語句處。
C編譯器，果然聰明！
通過這個分析我們可以知道如下兩點：
1. 當 case 語句少的時候，C編譯器将其轉成 if..else.. 類型進行處理，運用較多的
cmp 與 jmp 語句 ，而當 case 語句較多的時候，C編譯器會出成一個跳轉表，而直
接通過跳轉表進行跳轉，這讓 switch 具有非常高的效律，而且效律幾乎不會因為
case 語句的增長而減小，李維所擔憂的問題是完全不會發生的
2. 可以問答下面幾個問題：
1. 為什麼 case 語句中需要的是整數類型而不能是其餘的類型？
這是因為，case 語句中的這個值是用來做跳轉表的下标的，是以，當然必須是整數
2. 為什麼 case 語句在不加break的時候具有直通性?
這是因為跳轉是在進入 switch 是計算出的，而不是在case語句中計算出的，整個
case 語句群就是一塊完整而連續的代碼，隻是switch讓其從不同的位置開始執行。
上面的内容，在《Computer Systems A Programmer 's Perspective》中有很詳細的論述，
感興趣可以去找來仔細看看~~~
既然，case 語句需要的是整數的常量值，那麼我們是否可用 const 類型呢？比如下面
一段代碼：
const int c_1 = 100 ;
const int c_2 = 102 ;
void test( int x )
{
switch( x ){
case c_1 :
++x ;
case c_2 :
--x ;
}
}
這段代碼，用 c 編譯器編譯，編譯器會提示錯誤，但在 c++ 編譯器中卻不會，這主要是由于 c , 與 c++ 編譯器對 const 這個東東的處理不同。我們來看看下面一段 c 程式
const int a = 15 ;
void f( int x )
{
x = a ;
}
同樣用 gcc 編譯
gcc -S const_c.c
然後，來看看它的彙編檔案
.file "const_c.c "
.globl a
.section .rodata
.align 4
.type a,@object
.size a,4
a: // 1
.long 15
.text
.globl f
.type f,@function
f:
pushl %ebp
movl %esp, %ebp
movl a, %eax // 2
movl %eax, 8(%ebp)
leave
ret
.Lfe1:
.size f,.Lfe1-f
.ident "GCC: (GNU) 3.2.2 20030222 (Red Hat Linux 3.2.2-5) "
注意 // 1 處，C 編譯器為 a 配置設定了位址，并把它的值設為 15 ，而在 // 2 處，它是将
a 這個位址中的值賦給了 %eax，這同一般的普通變量而非const 變量指派沒什麼兩樣
下面我們用 c++ 編譯器來編譯這段代碼，它産生的彙編檔案如下：
.file "const_cpp.cpp "
.text
.align 2
.globl _Z1fi
.type _Z1fi,@function
_Z1fi:
.LFB2:
pushl %ebp
.LCFI0:
movl %esp, %ebp
.LCFI1:
movl $15, 8(%ebp) // 1
leave
ret
.LFE2:
.Lfe1:
.size _Z1fi,.Lfe1-_Z1fi
.section .rodata
.align 4
.type a,@object
.size a,4
a:
.long 15
.ident "GCC: (GNU) 3.2.2 20030222 (Red Hat Linux 3.2.2-5) "
同樣注意// 1 處，它以經把 a 的值用 15 來取代了，
也就是說，在c中const變量的行為更像一個非const變量，而在cpp中，const變量的行為就像是#define
由于 c++ 中，const 變量的值是在編譯時就計算出來的，是以，它可以用在 case 語句中，而 c 中，const值在編譯時隻是一個變量的位址，是以，它無法用在 case 語句中.
-----------------------------------------------------------------------------
參考文獻： < <Computer Systems A Programmer 's Perspective> >
轉載請注明原作者，以出處~~
![linux-svn解除安裝與安裝[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)