C++多態技術的實現和反思
面向對象技術最早出現于1960年代的Simula 67系統，并且在1970年代保羅阿托實驗室開發的Smalltalk系統中發展成熟。然而對于大部分程序員來說，C++是第一個可用的面向對象程序設計語言。因此，我們關于面向對象的很多概念和思想直接來自于C++。但是，C++在實現面向對象中關鍵的多態性時，選擇了與Smalltalk完全不同的方案。其結果是，盡管在表面上兩者都實現了相似的多態性，但是在實踐中卻有著巨大的區別。具體的說，C++的多態性實現更加高效，但是并不適用于所有場合。很多經驗不足的C++開發者不明白這個道理，在不合適的場合強行使用C++的多態性機制，落入削足適履的陷阱而不能自拔。本文將詳細探討C++多態性技術的局限性及解決的辦法。
兩種不同虛方法調用實現技術
C++的多態性是C++實現面向對象技術的基礎。具體的說，通過一個指向基類的指針調用虛成員函數的時候，運行時系統將能夠根據指針所指向的實際對象調用恰當的成員函數實現。如下所示：
- class Base {
- public:
- virtual void vmf() { ... }
- };
- class Derived : public Base {
- public:
- virtual void vmf() { ... }
- };
- Base* p = new Base();
- p->vmf(); // 這里調用Base::vmf
- p = new Derived();
- p->vmf(); // 這里調用
- // Derived::vmf
- ...
請注意代碼中突出注釋的兩行，雖然其表面語法完全相同，但是卻分別調用了不同的函數實現。所謂的“多態”即就此而言。這些知識是每一個C++開發者都熟知的。
現在我們假設自己是語言的實現者，我們應當如何來實現這種多態性？稍加思考，我們不難得到一個基本的思路。多態性的實現要求我們增加一個間接層，在這個間接層中攔截對于方法的調用，然后根據指針所指向的實際對象調用相應的方法實現。在這個過程中我們人為
增加的這個間接層非常重要，它需要完成以下幾項工作：
1. 獲知方法調用的全部信息，包括被調用的是哪個方法，傳入的實際參數有哪些。
2. 獲知調用發生時指針（引用）所指向的實際對象。
3. 根據第1、2步獲得的信息，找到合適的方法實現代碼，執行調用。
這里的關鍵在于如何在第3 步中找到合適的方法實現代碼。由于多態性是就對象而言的，因此我們在設計時要把合適的方法實現代碼與對象綁定到一起。也就是說，必須在對象級別實現一個查找表結構，根據1、2步獲得的對象和方法信息，在這個查找表中找到實際的方法代碼地址，并加以調用。現在問題變成了，我們應當根據什么信息進行方法查找。對于這個問題有兩個不同的解決思路，一個是根據名稱進行查找，另一個是根據位置進行查找。粗看上去這兩種思路似乎沒什么大的差別，但是在實踐中，這兩種不同的實現思路導致了巨大的差別。下面我們詳細地加以考察。
在Smalltalk、Python、Ruby等動態面向對象語言中，實際方法的查找是根據方法名稱進行的，其查找表結構如下：
由于這種查找表根據方法的名稱進行方法查找，因此在查找過程中涉及字符串比較，效率較差。但是這種查找表有一個突出的優點，就是有效空間利用率高。為了說明這一點，我們假設一個基類Base中有100個方法可供派生類改寫（因此所有Base對象所共享的方法查找表有100項），而它的一個派生類Derived僅僅只打算改寫其中5個方法，那么Derived類對象的方法查找表只需要5項。當一個方法調用發生的時候，runtime根據被調用的方法名稱在這個長度為5 的方法查找表中進行字符串查找，如果發現該方法在查找表中，則執行調用，否則將調用轉寄（forward）給Base類執行。這是虛方法調用的標準行為。當派生類實際改寫的方法數量很少的時候，可以將查找表安排成線性表，查找時順序比較，這種情況下有效空間利用率達到100%。如果派生類實際改寫的方法數量較多，那么可以采用散列表，如果采用合理的散列函數，同樣可以在空間利用率很高（一般可接近75%）.. 的情況下實現方法的快速查找。應當注意到，由于編譯器可以很容易地獲得所有被改寫方法的名稱，因此可以執行標準的gperf算法獲得最優的散列函數。#p#
事實上，我們還可以這樣理解這種方案的優勢，把表中每一項的“方法名”項視為“方法地址”項的描述信息，因此可以認為這種方案中的方法查找表攜帶自描述信息（或者稱為元數據）。基于這種攜帶自描述信息的數據結構，可以實現豐富多彩的擴展功能，比如在運行時
插入新的方法，或者用戶層次上的方法調用截獲等。因此，我們可以說這一方案的適用面廣，強大靈活，但在執行效率上并非最優。
另一種虛方法查找方案則是C++ 開發者十分熟悉的，基于絕對位置的定位技術。其查找表結構非常簡單，僅僅是一個存放了方法地址的指針數組。表中的每一項不具有自描述性，只有編譯器在編譯時知道它們究竟分別對應著哪一個方法，并且將對于方法的調用代碼編譯成一個緊湊的指針+偏移的調用的硬編碼。這種查找表的最大特點就是高效率，基于這種查找表進行方法調用僅僅需要多做一次數組內的隨機訪問操作。在所有我們所能想到的“增加一個間接層”的方案中，這種方案在效率上是最高的。但是使用這種方案有一個限定，就是要求所有同族多態對象具有完全一樣的查找表。也就是說，你必須確保所有實現了某個接口的對象的虛方法查找表的第k 項都具有相同的語義。假設一個基類有100個可供改寫的虛方法，那么它的虛方法查找表共有100項（實際上就是100個指向方法入口地址的指針）。而其所有派生類對象都必須有結構上完全相同的、長度至少為100項的虛方法查找表。現在假設我們開發的一個派生類中只改寫了基類的5個方法，那么這個派生類對象所共享的虛方法表仍然長達100項，只不過其中95項與其基類對象虛方法查找表中相應的項一模一樣，只有5項具有實際意義——正是這5項的存在才使派生類的存在有了意義。
在這種情況下，該方法表的實際有效利用率只有可憐的5%。總的來說，這一方案執行效率最優，但是并不適用于所有的場合。
當然，看上去上述兩種虛方法調用實現技術效果完全一樣，一切都被掩蓋在編譯器之下，與一般開發者毫無關系。但是，事實真的如此嗎？我們在下面會看到，C++ 的這種查找表結構構成了C++應用開發中最險惡的技術陷阱之一。
兩種不同的多態性應用場景
學習過數值分析的讀者應該熟知，在矩陣運算的電算求解領域，低階稠密矩陣的求解與高階稀疏矩陣的求解是性質完全不同的兩個問題，其存儲方案和求解算法截然不同。非常有趣的是，在多態性的實際應用中，也有著與矩陣問題類似的兩種性質上截然不同的場景。
第一種場景中，我們所構造的對象比較簡單，同一族系中兄弟類總數不多，而彼此之間的差異較大，因此對象中的虛方法數量少，而改寫率高。我們通常在教科書上所接觸的面向對象例子，以及在一般應用領域中接觸的對象都屬此類。
例如一個Modem類，即使其具有較多的特性，虛方法總數也很難超過20個，而不同的Modem類實現，可能會改寫其中大部分甚至全部虛方法。另一個例子是COM接口。由于COM組件思想基于接口，而一個粒度良好的接口必然是“瘦小精干”的。比如IMalloc接口只有6個方法（不包括從IUnknown繼承來的3 個方法），IPersistFile共5個方法，通常用戶自己寫的COM接口中的方法數量也不超過20。而在實現COM接口是，幾乎總是需要改寫全部方法。這與低階稠密矩陣非常相似，因此值得用最簡單直接的查找表結構來實現——速度快，而且簡單直接。由于虛方法改寫率高，查找表中的有效利用率較高。這種場景是C++多態性實現技術大大的用武之地，可以說C++特色的虛方法調用機制就是用來應對這種應用的。
而第二種應用場景截然不同，在這種場景中，對象比較復雜，特性稠密，行為變化多端，同一族系中兄弟對象數量龐大，而彼此之間大同小異。此種對象中的虛方法數量多，而改寫率低。GUI系統和視頻游戲是這種應用場景的典型代表。由于我們整天與Windows 系統打交道，所以用Windows GUI系統來說明這種場景是最合適不過的了。我們知道，在Windows圖形界面上的幾乎所有實體從概念上講都是Window對象，因此構成了一個對象族系。這個族系有三個突出的特點。一是行為多，特征多變（或者說虛方法數量多）。Microsoft Windows系統直接定義了數百個窗口消息，并允許用戶使用WM_USER+n和WM_APP+n的方式定義新的消息，用面向對象的話來說，就相當于給Windows系統中的所有Window對象定義了數百個可供改寫的虛方法，并且還允許用戶自由擴展新的虛方法。#p#
第二個特點是改寫率低，同族對象之間大同小異。通常我們對于絕大多數的窗口消息都是用DefWindowProc來統一處理，或者用SendMessage函數將消息轉發（委托）給系統提供的標準窗口對象處理，這也就是相當于把這些消息交給基類窗口對象來處理，而只攔截（改寫）其中幾個至幾十個消息（方法）。相對于窗口對象族龐大的虛方法數量來說，改寫率通常不超過20%。第三個特點是同族兄弟類數量龐大。從標準窗口到異型窗口，從對話框到按鈕，從工具條到文本框，所有的一切都是Window，甚至于兩個按鈕看上去完全一樣，僅僅是caption不同，按下時執行的操作不同，就需要用不同的類來構造。因此在一個普通規模的應用程序GUI界面系統中，構造上百個大同小異的窗口類是并不奇怪的。任何一個對Win32 API有一定理解的開發者，對此都不難體會。
從第1節對于C++虛方法調用機制的介紹可以很容易地知道，C++那種基于絕對位置的、不帶任何自描述信息的查找表結構，并不適用于上述的第二種場景。如果強行使用C++原生的對象模型來實現類似Windows的GUI系統，那么結果是這樣的：基類（不妨設為KWindow類）要定義1000個虛方法（其中應該留出多少位置供用戶擴展之需呢？），從而擁有一個長達1000的查找表，而所有的直接和間接派生類對象，為了保持與KWindow 在方法查找表結構上的兼容，都要至少包容一個長達1000的查找表。
我們舉一個極端的例子來欣賞一下這種解決方案的荒謬性，假設有一個類KPushButton從KWindow中派生，并通過改寫20個虛方法實現了一個標準的按鈕控件，那么它的虛方法查找表中有多少項？對不起，不是20 項，而是至少1000項（如果它沒有加入新的方法的話），其中絕大多數僅僅是KWindow虛方法表的原封不動的克隆，只有20項屬于它自己，只有這20項真正有意義，方法表中980項被浪費掉了。它們唯一的意義在于占據一些位置，使得“指針加偏移”的計算能夠繼續準確地尋址。你以為事情已經很糟糕了？不，事實上還可以更糟糕！
假設你需要一個標準按鈕，它的外觀、顏色、文字和其他行為都與KPushButton完全一樣，僅僅是相應CLICK事件的操作不同，你需要怎么辦？顯然是從KPushButton中派生自己的KMyPush-ButtonOK類，然后改寫其中的1 個方法（可能是叫做OnClick的）。那么在這個新的類中，虛方法表是多長呢？是1項嗎？不是。是20項嗎？也不是。實際上，是1000項！其中只有1項（OnClick）體現了它存在的意義，其他999項（在32位機器上占據3996個字節）幾乎完全被浪費掉了！一個中等規模的應用程序中安排幾十個界面，數百個自定制控件，則僅在虛方法表上浪費的存儲空間即達到數百KB甚至1MB以上。也許這個數字在今天用GB 大筐裝主存的時代實在是小兒科，但是其背后所體現的思路之丑陋卻是任何一個有點良心的開發者（尤其是C++開發者）所不能容忍的。
也正是因為這個原因，從OWL 到VCL，.. 從MFC到Qt，以至于近幾年出現的GUI和游戲開發框架，所有涉及大量事件行為的C++ GUI Framework沒有一家使用標準的C++多態技術來構造窗口類層次，而是各自為戰，發明出五花八門的技術來繞過這個暗礁。其中比較經典的解決方案有三，分別以VCL 的動態方法、MFC的全局事件查找表和Qt 的Signal/Slot為代表。而其背后的思想是一致的，用Grady Booch的一句話來總結，就是：“當你發現系統中需要大量相似的小型類的時候，應當用大量相似的小型對象解決之。”2 也就是說，將一些本來會導致需要派生新類來解決的問題，用實例化新的對象來解決。這種思路幾乎必然導致類似C#中delegate那樣的機制成為必需品。可惜的是，標準C++ 不支持delegate。雖然C++社群里有很多人做了各種努力，應用了諸如template、functor等高級技巧，但是在效果上距離真正的delegate還有差距。因此，為了保持解決方案的簡單，Borland C++Builder擴展了__closure關鍵字，MFC發明出一大堆怪模怪樣的宏，Qt搞了一個moc前處理器，八仙過海，各顯神通。
讓我們小結一下，面向對象多態性有兩種不同的應用場景，而C++的標準多態技術只適合其中一種，對于另一種并不適合，必須以其他機制實現。
解決思路和建議
或許有讀者讀到這里，會對C++產生很大的懷疑。需要說明的是，C++選擇的多態性實現技術是完全符合C++哲學的。而且，C++允許你以各種可能的辦法來解決這個問題。時至今日，依靠各種成熟的GUI框架，大多數情況下我們可以自動繞過暗礁。
問題的嚴重性在于，由于C++教育上的問題，很多開發者對于C++原生多態技術在上述第二種應用場合中的局限性認識不足，因此當他們面臨類似的問題時，會不自覺地踏入陷阱中。在此我愿提醒C++開發者，當你面對的系統中含有標準的事件處理特征，而且事件數量較大時，請慎重考慮你的類層次結構設計。可以考慮模仿MFC或者Qt的解決方法，但在我看來，一個更加直接而且簡單的方法是，模擬本文第1節中描述的、基于字符串比較的方法查找表，用一個單一的消息分發對象來向各個對象分發消息。由于這個消息分發對象會經常需要調整變化，將它單獨放在一個DLL 甚至COM組件中，在運行時加載到進程內。這種方案不是最精巧的，但是在大多數情況下有效，并且實現起來比較簡單。限于篇幅，這里不詳細描述。
事實上，我本人認為，C++語言應當從編譯器上解決這個問題。基本思路為，當基類虛方法數量大而派生類改寫的方法數量小的時候（這個信息可以從編譯過程中得到），改變派生類對象的虛方法查找機制，改按位置查找為按被調用函數實際信息查找。這樣一來，派生類中的虛方法表可不必與基類保持結構上的一致，從而避免了空間上的浪費。這種思路跟Delphi/Object Pascal語言中dynamic關鍵字有相似之處。本文不再贅述。
【編輯推薦】
