原文發(fā)表于《程序員》 2005-11  楊喜敏 孟巖

面向?qū)ο蠹夹g(shù)最早出現(xiàn)于1960年代的Simula 67系統(tǒng)，并且在1970年代保羅阿托實(shí)驗(yàn)室開發(fā)的Smalltalk系統(tǒng)中發(fā)展成熟。然而對(duì)于大部分程序員來說，C++是第一個(gè)可用的面向?qū)ο蟪绦蛟O(shè)計(jì)語言。因此，我們關(guān)于面向?qū)ο蟮暮芏喔拍詈退枷胫苯觼碜杂贑++。但是，C++在實(shí)現(xiàn)面向?qū)ο笾嘘P(guān)鍵的多態(tài)性時(shí)，選擇了與Smalltalk完全不同的方案。其結(jié)果是，盡管在表面上兩者都實(shí)現(xiàn)了相似的多態(tài)性，但是在實(shí)踐中卻有著巨大的區(qū)別。具體的說，C++的多態(tài)性實(shí)現(xiàn)更加高效，但是并不適用于所有場(chǎng)合。很多經(jīng)驗(yàn)不足的C++開發(fā)者不明白這個(gè)道理，在不合適的場(chǎng)合強(qiáng)行使用C++的多態(tài)性機(jī)制，落入削足適履的陷阱而不能自拔。本文將詳細(xì)探討C++多態(tài)性技術(shù)的局限性及解決的辦法。

　　兩種不同虛方法調(diào)用實(shí)現(xiàn)技術(shù)

　　C++的多態(tài)性是C++實(shí)現(xiàn)面向?qū)ο蠹夹g(shù)的基礎(chǔ)。具體的說，通過一個(gè)指向基類的指針調(diào)用虛成員函數(shù)的時(shí)候，運(yùn)行時(shí)系統(tǒng)將能夠根據(jù)指針?biāo)赶虻膶?shí)際對(duì)象調(diào)用恰當(dāng)?shù)某蓡T函數(shù)實(shí)現(xiàn)。如下所示：

class Base {
　　public:
　　 virtual void vmf() { ... }
　　};
　　
　　class Derived : public Base {
　　public:
　　 virtual void vmf() { ... }
　　};
　　
　　Base* p = new Base();
　　p->vmf(); // 這里調(diào)用Base::vmf
　　p = new Derived();
　　p->vmf(); // 這里調(diào)用
// Derived::vmf
　　...
　　請(qǐng)注意代碼中突出注釋的兩行，雖然其表面語法完全相同，但是卻分別調(diào)用了不同的函數(shù)實(shí)現(xiàn)。所謂的“多態(tài)”即就此而言。這些知識(shí)是每一個(gè)C++開發(fā)者都熟知的。

　　現(xiàn)在我們假設(shè)自己是語言的實(shí)現(xiàn)者，我們應(yīng)當(dāng)如何來實(shí)現(xiàn)這種多態(tài)性？稍加思考，我們不難得到一個(gè)基本的思路。多態(tài)性的實(shí)現(xiàn)要求我們?cè)黾右粋€(gè)間接層，在這個(gè)間接層中攔截對(duì)于方法的調(diào)用，然后根據(jù)指針?biāo)赶虻膶?shí)際對(duì)象調(diào)用相應(yīng)的方法實(shí)現(xiàn)。在這個(gè)過程中我們?nèi)藶?br>增加的這個(gè)間接層非常重要，它需要完成以下幾項(xiàng)工作：

　　1. 獲知方法調(diào)用的全部信息，包括被調(diào)用的是哪個(gè)方法，傳入的實(shí)際參數(shù)有哪些。

　　2. 獲知調(diào)用發(fā)生時(shí)指針（引用）所指向的實(shí)際對(duì)象。

　　3. 根據(jù)第1、2步獲得的信息，找到合適的方法實(shí)現(xiàn)代碼，執(zhí)行調(diào)用。
　　
　　這里的關(guān)鍵在于如何在第3 步中找到合適的方法實(shí)現(xiàn)代碼。由于多態(tài)性是就對(duì)象而言的，因此我們?cè)谠O(shè)計(jì)時(shí)要把合適的方法實(shí)現(xiàn)代碼與對(duì)象綁定到一起。也就是說，必須在對(duì)象級(jí)別實(shí)現(xiàn)一個(gè)查找表結(jié)構(gòu)，根據(jù)1、2步獲得的對(duì)象和方法信息，在這個(gè)查找表中找到實(shí)際的方法代碼地址，并加以調(diào)用。現(xiàn)在問題變成了，我們應(yīng)當(dāng)根據(jù)什么信息進(jìn)行方法查找。對(duì)于這個(gè)問題有兩個(gè)不同的解決思路，一個(gè)是根據(jù)名稱進(jìn)行查找，另一個(gè)是根據(jù)位置進(jìn)行查找。粗看上去這兩種思路似乎沒什么大的差別，但是在實(shí)踐中，這兩種不同的實(shí)現(xiàn)思路導(dǎo)致了巨大的差別。下面我們?cè)敿?xì)地加以考察。

　　在Smalltalk、Python、Ruby等動(dòng)態(tài)面向?qū)ο笳Z言中，實(shí)際方法的查找是根據(jù)方法名稱進(jìn)行的，其查找表結(jié)構(gòu)如下：

　　由于這種查找表根據(jù)方法的名稱進(jìn)行方法查找，因此在查找過程中涉及字符串比較，效率較差。但是這種查找表有一個(gè)突出的優(yōu)點(diǎn)，就是有效空間利用率高。為了說明這一點(diǎn)，我們假設(shè)一個(gè)基類Base中有100個(gè)方法可供派生類改寫（因此所有Base對(duì)象所共享的方法查找表有100項(xiàng)），而它的一個(gè)派生類Derived僅僅只打算改寫其中5個(gè)方法，那么Derived類對(duì)象的方法查找表只需要5項(xiàng)。當(dāng)一個(gè)方法調(diào)用發(fā)生的時(shí)候，runtime根據(jù)被調(diào)用的方法名稱在這個(gè)長度為5 的方法查找表中進(jìn)行字符串查找，如果發(fā)現(xiàn)該方法在查找表中，則執(zhí)行調(diào)用，否則將調(diào)用轉(zhuǎn)寄（forward）給Base類執(zhí)行。這是虛方法調(diào)用的標(biāo)準(zhǔn)行為。當(dāng)派生類實(shí)際改寫的方法數(shù)量很少的時(shí)候，可以將查找表安排成線性表，查找時(shí)順序比較，這種情況下有效空間利用率達(dá)到100%。如果派生類實(shí)際改寫的方法數(shù)量較多，那么可以采用散列表，如果采用合理的散列函數(shù)，同樣可以在空間利用率很高（一般可接近75%）.. 的情況下實(shí)現(xiàn)方法的快速查找。應(yīng)當(dāng)注意到，由于編譯器可以很容易地獲得所有被改寫方法的名稱，因此可以執(zhí)行標(biāo)準(zhǔn)的gperf算法獲得最優(yōu)的散列函數(shù)。

　　事實(shí)上，我們還可以這樣理解這種方案的優(yōu)勢(shì)，把表中每一項(xiàng)的“方法名”項(xiàng)視為“方法地址”項(xiàng)的描述信息，因此可以認(rèn)為這種方案中的方法查找表攜帶自描述信息（或者稱為元數(shù)據(jù)）。基于這種攜帶自描述信息的數(shù)據(jù)結(jié)構(gòu)，可以實(shí)現(xiàn)豐富多彩的擴(kuò)展功能，比如在運(yùn)行時(shí)
插入新的方法，或者用戶層次上的方法調(diào)用截獲等。因此，我們可以說這一方案的適用面廣，強(qiáng)大靈活，但在執(zhí)行效率上并非最優(yōu)。

　　另一種虛方法查找方案則是C++ 開發(fā)者十分熟悉的，基于絕對(duì)位置的定位技術(shù)。其查找表結(jié)構(gòu)非常簡單，僅僅是一個(gè)存放了方法地址的指針數(shù)組。表中的每一項(xiàng)不具有自描述性，只有編譯器在編譯時(shí)知道它們究竟分別對(duì)應(yīng)著哪一個(gè)方法，并且將對(duì)于方法的調(diào)用代碼編譯成一個(gè)緊湊的指針+偏移的調(diào)用的硬編碼。這種查找表的最大特點(diǎn)就是高效率，基于這種查找表進(jìn)行方法調(diào)用僅僅需要多做一次數(shù)組內(nèi)的隨機(jī)訪問操作。在所有我們所能想到的“增加一個(gè)間接層”的方案中，這種方案在效率上是最高的。但是使用這種方案有一個(gè)限定，就是要求所有同族多態(tài)對(duì)象具有完全一樣的查找表。也就是說，你必須確保所有實(shí)現(xiàn)了某個(gè)接口的對(duì)象的虛方法查找表的第k 項(xiàng)都具有相同的語義。假設(shè)一個(gè)基類有100個(gè)可供改寫的虛方法，那么它的虛方法查找表共有100項(xiàng)（實(shí)際上就是100個(gè)指向方法入口地址的指針）。而其所有派生類對(duì)象都必須有結(jié)構(gòu)上完全相同的、長度至少為100項(xiàng)的虛方法查找表。現(xiàn)在假設(shè)我們開發(fā)的一個(gè)派生類中只改寫了基類的5個(gè)方法，那么這個(gè)派生類對(duì)象所共享的虛方法表仍然長達(dá)100項(xiàng)，只不過其中95項(xiàng)與其基類對(duì)象虛方法查找表中相應(yīng)的項(xiàng)一模一樣，只有5項(xiàng)具有實(shí)際意義——正是這5項(xiàng)的存在才使派生類的存在有了意義。

　　在這種情況下，該方法表的實(shí)際有效利用率只有可憐的5%。總的來說，這一方案執(zhí)行效率最優(yōu)，但是并不適用于所有的場(chǎng)合。

　　當(dāng)然，看上去上述兩種虛方法調(diào)用實(shí)現(xiàn)技術(shù)效果完全一樣，一切都被掩蓋在編譯器之下，與一般開發(fā)者毫無關(guān)系。但是，事實(shí)真的如此嗎？我們?cè)谙旅鏁?huì)看到，C++ 的這種查找表結(jié)構(gòu)構(gòu)成了C++應(yīng)用開發(fā)中最險(xiǎn)惡的技術(shù)陷阱之一。

　　兩種不同的多態(tài)性應(yīng)用場(chǎng)景

　　學(xué)習(xí)過數(shù)值分析的讀者應(yīng)該熟知，在矩陣運(yùn)算的電算求解領(lǐng)域，低階稠密矩陣的求解與高階稀疏矩陣的求解是性質(zhì)完全不同的兩個(gè)問題，其存儲(chǔ)方案和求解算法截然不同。非常有趣的是，在多態(tài)性的實(shí)際應(yīng)用中，也有著與矩陣問題類似的兩種性質(zhì)上截然不同的場(chǎng)景。
　　
    第一種場(chǎng)景中，我們所構(gòu)造的對(duì)象比較簡單，同一族系中兄弟類總數(shù)不多，而彼此之間的差異較大，因此對(duì)象中的虛方法數(shù)量少，而改寫率高。我們通常在教科書上所接觸的面向?qū)ο罄樱约霸谝话銘?yīng)用領(lǐng)域中接觸的對(duì)象都屬此類。

　　例如一個(gè)Modem類，即使其具有較多的特性，虛方法總數(shù)也很難超過20個(gè)，而不同的Modem類實(shí)現(xiàn)，可能會(huì)改寫其中大部分甚至全部虛方法。另一個(gè)例子是COM接口。由于COM組件思想基于接口，而一個(gè)粒度良好的接口必然是“瘦小精干”的。比如IMalloc接口只有6個(gè)方法（不包括從IUnknown繼承來的3 個(gè)方法），IPersistFile共5個(gè)方法，通常用戶自己寫的COM接口中的方法數(shù)量也不超過20。而在實(shí)現(xiàn)COM接口是，幾乎總是需要改寫全部方法。這與低階稠密矩陣非常相似，因此值得用最簡單直接的查找表結(jié)構(gòu)來實(shí)現(xiàn)——速度快，而且簡單直接。由于虛方法改寫率高，查找表中的有效利用率較高。這種場(chǎng)景是C++多態(tài)性實(shí)現(xiàn)技術(shù)大大的用武之地，可以說C++特色的虛方法調(diào)用機(jī)制就是用來應(yīng)對(duì)這種應(yīng)用的。

　　而第二種應(yīng)用場(chǎng)景截然不同，在這種場(chǎng)景中，對(duì)象比較復(fù)雜，特性稠密，行為變化多端，同一族系中兄弟對(duì)象數(shù)量龐大，而彼此之間大同小異。此種對(duì)象中的虛方法數(shù)量多，而改寫率低。GUI系統(tǒng)和視頻游戲是這種應(yīng)用場(chǎng)景的典型代表。由于我們整天與Windows 系統(tǒng)打交道，所以用WindowsGUI系統(tǒng)來說明這種場(chǎng)景是最合適不過的了。我們知道，在Windows圖形界面上的幾乎所有實(shí)體從概念上講都是Window對(duì)象，因此構(gòu)成了一個(gè)對(duì)象族系。這個(gè)族系有三個(gè)突出的特點(diǎn)。一是行為多，特征多變（或者說虛方法數(shù)量多）。Microsoft Windows系統(tǒng)直接定義了數(shù)百個(gè)窗口消息，并允許用戶使用WM_USER+n和WM_APP+n的方式定義新的消息，用面向?qū)ο蟮脑拋碚f，就相當(dāng)于給Windows系統(tǒng)中的所有Window對(duì)象定義了數(shù)百個(gè)可供改寫的虛方法，并且還允許用戶自由擴(kuò)展新的虛方法。

　　第二個(gè)特點(diǎn)是改寫率低，同族對(duì)象之間大同小異。通常我們對(duì)于絕大多數(shù)的窗口消息都是用DefWindowProc來統(tǒng)一處理，或者用SendMessage函數(shù)將消息轉(zhuǎn)發(fā)（委托）給系統(tǒng)提供的標(biāo)準(zhǔn)窗口對(duì)象處理，這也就是相當(dāng)于把這些消息交給基類窗口對(duì)象來處理，而只攔截（改寫）其中幾個(gè)至幾十個(gè)消息（方法）。相對(duì)于窗口對(duì)象族龐大的虛方法數(shù)量來說，改寫率通常不超過20%。第三個(gè)特點(diǎn)是同族兄弟類數(shù)量龐大。從標(biāo)準(zhǔn)窗口到異型窗口，從對(duì)話框到按鈕，從工具條到文本框，所有的一切都是Window，甚至于兩個(gè)按鈕看上去完全一樣，僅僅是caption不同，按下時(shí)執(zhí)行的操作不同，就需要用不同的類來構(gòu)造。因此在一個(gè)普通規(guī)模的應(yīng)用程序GUI界面系統(tǒng)中，構(gòu)造上百個(gè)大同小異的窗口類是并不奇怪的。任何一個(gè)對(duì)Win32 API有一定理解的開發(fā)者，對(duì)此都不難體會(huì)。

　　從第1節(jié)對(duì)于C++虛方法調(diào)用機(jī)制的介紹可以很容易地知道，C++那種基于絕對(duì)位置的、不帶任何自描述信息的查找表結(jié)構(gòu)，并不適用于上述的第二種場(chǎng)景。如果強(qiáng)行使用C++原生的對(duì)象模型來實(shí)現(xiàn)類似Windows的GUI系統(tǒng)，那么結(jié)果是這樣的：基類（不妨設(shè)為KWindow類）要定義1000個(gè)虛方法（其中應(yīng)該留出多少位置供用戶擴(kuò)展之需呢？），從而擁有一個(gè)長達(dá)1000的查找表，而所有的直接和間接派生類對(duì)象，為了保持與KWindow 在方法查找表結(jié)構(gòu)上的兼容，都要至少包容一個(gè)長達(dá)1000的查找表。

　　我們舉一個(gè)極端的例子來欣賞一下這種解決方案的荒謬性，假設(shè)有一個(gè)類KPushButton從KWindow中派生，并通過改寫20個(gè)虛方法實(shí)現(xiàn)了一個(gè)標(biāo)準(zhǔn)的按鈕控件，那么它的虛方法查找表中有多少項(xiàng)？對(duì)不起，不是20 項(xiàng)，而是至少1000項(xiàng)（如果它沒有加入新的方法的話），其中絕大多數(shù)僅僅是KWindow虛方法表的原封不動(dòng)的克隆，只有20項(xiàng)屬于它自己，只有這20項(xiàng)真正有意義，方法表中980項(xiàng)被浪費(fèi)掉了。它們唯一的意義在于占據(jù)一些位置，使得“指針加偏移”的計(jì)算能夠繼續(xù)準(zhǔn)確地尋址。你以為事情已經(jīng)很糟糕了？不，事實(shí)上還可以更糟糕！

　　假設(shè)你需要一個(gè)標(biāo)準(zhǔn)按鈕，它的外觀、顏色、文字和其他行為都與KPushButton完全一樣，僅僅是相應(yīng)CLICK事件的操作不同，你需要怎么辦？顯然是從KPushButton中派生自己的KMyPush-ButtonOK類，然后改寫其中的1 個(gè)方法（可能是叫做OnClick的）。那么在這個(gè)新的類中，虛方法表是多長呢？是1項(xiàng)嗎？不是。是20項(xiàng)嗎？也不是。實(shí)際上，是1000項(xiàng)！其中只有1項(xiàng)（OnClick）體現(xiàn)了它存在的意義，其他999項(xiàng)（在32位機(jī)器上占據(jù)3996個(gè)字節(jié)）幾乎完全被浪費(fèi)掉了！一個(gè)中等規(guī)模的應(yīng)用程序中安排幾十個(gè)界面，數(shù)百個(gè)自定制控件，則僅在虛方法表上浪費(fèi)的存儲(chǔ)空間即達(dá)到數(shù)百KB甚至1MB以上。也許這個(gè)數(shù)字在今天用GB 大筐裝主存的時(shí)代實(shí)在是小兒科，但是其背后所體現(xiàn)的思路之丑陋卻是任何一個(gè)有點(diǎn)良心的開發(fā)者（尤其是C++開發(fā)者）所不能容忍的。

　　也正是因?yàn)檫@個(gè)原因，從OWL 到VCL，.. 從MFC到Qt，以至于近幾年出現(xiàn)的GUI和游戲開發(fā)框架，所有涉及大量事件行為的C++ GUI Framework沒有一家使用標(biāo)準(zhǔn)的C++多態(tài)技術(shù)來構(gòu)造窗口類層次，而是各自為戰(zhàn)，發(fā)明出五花八門的技術(shù)來繞過這個(gè)暗礁。其中比較經(jīng)典的解決方案有三，分別以VCL 的動(dòng)態(tài)方法、MFC的全局事件查找表和Qt 的Signal/Slot為代表。而其背后的思想是一致的，用Grady Booch的一句話來總結(jié)，就是：“當(dāng)你發(fā)現(xiàn)系統(tǒng)中需要大量相似的小型類的時(shí)候，應(yīng)當(dāng)用大量相似的小型對(duì)象解決之。”2 也就是說，將一些本來會(huì)導(dǎo)致需要派生新類來解決的問題，用實(shí)例化新的對(duì)象來解決。這種思路幾乎必然導(dǎo)致類似C#中delegate那樣的機(jī)制成為必需品。可惜的是，標(biāo)準(zhǔn)C++ 不支持delegate。雖然C++社群里有很多人做了各種努力，應(yīng)用了諸如template、functor等高級(jí)技巧，但是在效果上距離真正的delegate還有差距。因此，為了保持解決方案的簡單，Borland C++Builder擴(kuò)展了__closure關(guān)鍵字，MFC發(fā)明出一大堆怪模怪樣的宏，Qt搞了一個(gè)moc前處理器，八仙過海，各顯神通。

　　讓我們小結(jié)一下，面向?qū)ο蠖鄳B(tài)性有兩種不同的應(yīng)用場(chǎng)景，而C++的標(biāo)準(zhǔn)多態(tài)技術(shù)只適合其中一種，對(duì)于另一種并不適合，必須以其他機(jī)制實(shí)現(xiàn)。

　　解決思路和建議

　　或許有讀者讀到這里，會(huì)對(duì)C++產(chǎn)生很大的懷疑。需要說明的是，C++選擇的多態(tài)性實(shí)現(xiàn)技術(shù)是完全符合C++哲學(xué)的。而且，C++允許你以各種可能的辦法來解決這個(gè)問題。時(shí)至今日，依靠各種成熟的GUI框架，大多數(shù)情況下我們可以自動(dòng)繞過暗礁。

　　問題的嚴(yán)重性在于，由于C++教育上的問題，很多開發(fā)者對(duì)于C++原生多態(tài)技術(shù)在上述第二種應(yīng)用場(chǎng)合中的局限性認(rèn)識(shí)不足，因此當(dāng)他們面臨類似的問題時(shí)，會(huì)不自覺地踏入陷阱中。在此我愿提醒C++開發(fā)者，當(dāng)你面對(duì)的系統(tǒng)中含有標(biāo)準(zhǔn)的事件處理特征，而且事件數(shù)量較大時(shí)，請(qǐng)慎重考慮你的類層次結(jié)構(gòu)設(shè)計(jì)。可以考慮模仿MFC或者Qt的解決方法，但在我看來，一個(gè)更加直接而且簡單的方法是，模擬本文第1節(jié)中描述的、基于字符串比較的方法查找表，用一個(gè)單一的消息分發(fā)對(duì)象來向各個(gè)對(duì)象分發(fā)消息。由于這個(gè)消息分發(fā)對(duì)象會(huì)經(jīng)常需要調(diào)整變化，將它單獨(dú)放在一個(gè)DLL 甚至COM組件中，在運(yùn)行時(shí)加載到進(jìn)程內(nèi)。這種方案不是最精巧的，但是在大多數(shù)情況下有效，并且實(shí)現(xiàn)起來比較簡單。限于篇幅，這里不詳細(xì)描述。

　　事實(shí)上，我本人認(rèn)為，C++語言應(yīng)當(dāng)從編譯器上解決這個(gè)問題。基本思路為，當(dāng)基類虛方法數(shù)量大而派生類改寫的方法數(shù)量小的時(shí)候（這個(gè)信息可以從編譯過程中得到），改變派生類對(duì)象的虛方法查找機(jī)制，改按位置查找為按被調(diào)用函數(shù)實(shí)際信息查找。這樣一來，派生類中的虛方法表可不必與基類保持結(jié)構(gòu)上的一致，從而避免了空間上的浪費(fèi)。這種思路跟Delphi/Object Pascal語言中dynamic關(guān)鍵字有相似之處。本文不再贅述