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算法获得最优的散列函数。
事实上，我们还可以这样理解这种方案的优势，把表中每一项的“方法名”项视为“方法地址”项的描述信息，因此可以认为这种方案中的方法查找表携带自描述信息（或者称为元数据）。基于这种携带自描述信息的数据结构，可以实现丰富多彩的扩展功能，比如在运行时插入新的方法，或者用户层次上的方法调用截获等。因此，我们可以说这一方案的适用面广，强大灵活，但在执行效率上并非最优。
另一种虚方法查找方案则是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对象定义了数百个可供改写的虚方法，并且还允许用户自由扩展新的虚方法。
第二个特点是改写率低，同族对象之间大同小异。通常我们对于绝大多数的窗口消息都是用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关键字有相似之处。本文不再赘述。
原文地址：http://blog.csdn.net/wuliming_sc/article/details/3855906