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

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

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

　　C++的多態(tài)性是C++實現(xiàn)面向?qū)ο蠹夹g(shù)的基礎(chǔ)。具體的說，通過一個指向基類的指針調(diào)用虛成員函數(shù)的時候，運行時系統(tǒng)將能夠根據(jù)指針所指向的實際對象調(diào)用恰當?shù)某蓡T函數(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
　　...
　　請注意代碼中突出注釋的兩行，雖然其表面語法完全相同，但是卻分別調(diào)用了不同的函數(shù)實現(xiàn)。所謂的“多態(tài)”即就此而言。這些知識是每一個C++開發(fā)者都熟知的。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　解決思路和建議

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

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

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