More Effective C++之效率Efficiency

条款24：了解virtual function、multi inheritance、virtual base classes、runtime type identification的成本

条款24：了解virtual function、multi inheritance、virtual base classes、runtime type identification的成本

C++编译器必须找出一种方法来实现语言中的每一个性质。此等实现细节当然因编译器而异，不同的编译器以不同的方法来实现语言性质。大部分时候我们并不需要关心这件事。然而某些语言特性的实现可能会对对象的大小和其member functions的执行速度带来冲击，所以面对这类特性，了解“编译器可能以什么样的方法来实现它们”是件重要的事情。这类性质中最重要的是虚函数。
当一个虚函数被调用，执行的代码必须对应于“调用者（对象）的动态类型”。对象的pointer或reference，其类型是无形的，编译器如何很有效率地提供这样的行为呢？大部分编译器使用所谓的virtual tables和virtual table pointer——此二者常被简写为vtbls和vptrs。
vtbl通常是一个由“函数指针”组成的数组。某些编译器会以链表（linked list）取代数组，但其基本策略相同。程序中的每一个class凡声明（或集成）虚函数者，都有自己的一个vtbl，而其中条目（entries）就是该class的各个虚函数实现体的指针。例如，假设有一个class定义如下：

class C1 {
public:C1();virtual ~C1();virtual void f1();virtual int f2(char c) const;virtual void f3(const string &s);void f4() const;
};

C1的vtbl看起来像这样：

注意，非虚函数f4并不在表格之中，C1 constructor也一样。非虚函数——包括必定是非虚函数的constructors——会像一般的C函数那样被实现，所以他们的使用并没有什么特殊性能考虑。
如果C2集成C1，然后重新定义某些集成而来的虚函数，并加上新的虚函数：

class C2: public C1 {
public:C2();virtual ~C2();virtual void f1();virtual void f5(char *str);...
};

其vtbl条目（entries）将会指向对应于对象类型的各个适当函数，以及未被C2重新定义的C1虚函数：

这份讨论带出虚函数的第一个成本：我们必须为每个拥有虚函数的class耗费一个vtbl空间，其大小视虚函数的个数（包括继承而来的）而定。每个class应该只有一个vtbl，所以vtbls的总空间通常并不是很大，但如果我们有大量这类classes，或许在每个class中拥有大量虚函数，我们可能会发现，vtbls占用不少内存。
由于程序中每个class的vtbl只需要一份就好，编译器于是必须解决一个棘手的问题：该把它们放在哪里？大部分应用程序和程序库都是有许多目标文件（object files）链接而成的，每个目标文件都是独立生成的。class的vtbl应该放在哪一个目标文件呢？我们可能以为是内含main的那个，但程序库没有main！那么编译器又如何知道它应该产生那些vtbls呢？
显然必须采用另一种策略。对此，编译器厂商倾向于两个阵营。对于提供集合环境（包含编译器和链接器）的厂商而言，一种暴力式做法就是在每一个需要vtbl的目标文件内都产生一个vtbl副本。最后在由链接器剥除重复的副本，使最终的可执行文件或程序库内，只留下每个vtbl的单一实体。
更常见的设计是，以一种勘探式做法，决定哪一个目标文件应该内含某个class的vtbl。做法大意如下：class‘s vtbl被产生于“内含其第一个non-inline，non-pure虚函数定义式”的目标文件中。因此，先前class C1的vtbl应该放在内含C1::~C1定义式的目标文件中（前提是该函数并非inline），而class C2的vtbl应该放在内含C2::~C2的vtbl应该放在内含C2::~C2定义式的目标文件中（前提也是该函数并非inline）。
这种勘探式做法实际上可行，但如果我们脱离前提，将虚函数声明为inline，便会有麻烦。如果class内的所有虚函数都被声明为inline，这种做法便告失败，而大部分以此法为基础的编译器便会在每一个“使用了class’vtbl”的目标文件中产生一个vtbl复制品。在大型系统中，这会导致程序内含成百上千个class‘s vtbl副本。大部分奉行此法的编译器会给出某种手动方法，用以控制vtbl的产生：但最好的解决办法还是避免将虚函数声明为inline。稍后我们会看到，目前编译器通常会忽略函数的inline指示的，这是有一些好理由的。
Virtual tables只是虚函数实现机制的一半而已。如果只有它，不能成气候。一旦有某种方法可以指示出每个对象对应于哪一个vtbl，vtbl才真的有用，而这正是virtual table pointer（vptr）的任务。
凡声明有虚函数的class，其对象都含有一个隐含的data member，用来指向该class的vtbl。这个隐藏的data member——所谓的vptr——被编译器加入对象内某个唯编译器才知道的位置。概念上，我们可以把一个拥有虚函数的对象的内存布局想象如下：

此图显示vptr位于对象尾端，但是不要太过执着：不同的编译器会把它们放在不同的地点。一旦发生继承，对象的vptr往往被data members围绕。多重集成更会加深此图的复杂度。此刻，只需注意到虚函数的第二个成本：我们必须在每一个拥有虚函数的对象内付出“一个额外指针”的代价。
如果对象不大，这份额外开销可能形成值得注意的成本。如果我们的对象（平均而言）内含4bytes的data memebers，那么增加一个vptr会使其大小加倍（其中4bytes¹ 贡献给了vptr）。在一个内存不很充裕的系统中，这意味着我们所能够产生的对象个数减少了。即使在一个内存充裕的系统中，也会发现，软件的性能减低了，因为加大的对象意味着较难塞入一个缓存分页（cache page)或虚内存分页（virtual memory page）之中，也就意味着换页（paging）活动可能会增加。

假设我们有一个程序，其中数个类型为C1和C2对象，根据上述objects、vptrs、vtbls之间的关系，我们可以想象程序中的对象如下：

现在考虑这样的程序片段：

void makeACall(C1 *pC1) {pC1->f1();
}

其中通过pC1调用虚函数f1.如果只看这个判断，无法知道哪一个f1函数（C1::f1或C2::f1）会被调用，因为pC1可能指向一个C1对象，也可能指向一个C2对象。尽管如此编译器仍然必须为makeACall内的“f1函数调用动作”产生可执行代码，而且必须确保正确的函数被调用，不论pC1到底指向谁。编译器必须产生代码，完成以下动作：

根据对象的vptr找出其vtbl。这是一个简单的动作，因为编译器知道到对象的哪里去找出vptr（毕竟那个位置正是编译器决定的），成本只有一个偏移调整（offset adjustment，以便获得vptr）和一个指针间接动作（以便获得vtbl）。
找出被调用函数（本例为f1）在vtbl内的对应指针。这也很简单，因为编译器为每个虚函数制定了一个独一无二的表格索引。本步骤的成本只是一个偏移（offset）以求进入vtbl数组。
调用步骤2所得指针所指向的函数。
如果我们想象每个对象都有一个隐藏的data memeber称为vptr，而函数f1的“vtbl索引”是i，那么先前语句：

pC1->f1();

产生出来的代码将是：

(*pC1->vptr[i])(pC1);								// 调用PC1->vptr所指的vtbl中的第i个条目所指的函数。pC1被传给该函数作为“this”指针之用。

这几乎和一个非虚函数的效率相当，因为在大部分机器上这只需数个指令就可执行。因此，调用一个虚函数的成本，基本上和“通过一个函数指针来调用函数”相同。虚函数本身并不构成性能上的瓶颈。
虚函数真正的运行时期成本发生在和inlining互动的时候。对所有实用目的而言，虚函数不应该inlined。因为“inline”意味着“在编译器，将调用端的调用动作被调用函数的函数本体取代”，而“virtual”则意味着“等待，摘掉运行时期才知道哪个函数被调用”。当编译器面对某个调用动作，却无法知道哪个函数被调用时，我们就可以理解为什么它们没有能力将该函数调用加以inlining了。这便是虚函数的第三个成本：事实上等于放弃了inlining。（如果虚函数通过对象被调用，倒是可以inlined，但大部分虚函数调用动作是通过对象的只恨或reference完成的，此类行为无法被inlined。由于此等调用行为是常态，所以虚函数事实上等于无法被inlined。）
截至目前我们所看到的每件事情，既适用于单一继承也适用于多重继承，但是当多重继承牵扯进来时，事情会变得更复杂。其实没有必要深思其中细节，但是在多重继承情况下，“找出对象内的vptrs”会比较复杂，因为此时一个对象之内会有多个vptrs（每个base class各对应一个）；而且除了我们所讨论的vtbls之外，针对base classes而形成的特殊vtbls也会被产生出来。结果，虚函数对每一个object和每一个class所造成的空间负担又增加了一些，运行时间的调用成本也有轻微的成长。
多重继承往往导致virtual base classes（虚拟基类）的需求。在non-virtual base classes的情况下，如果derived class在其base class有多条继承路径，则此base class的data members会在每一个derived class object体内复制滋生，每一个副本对应“derived class和base class之间的一条继承路线”。如此的复制现象几乎不会是程序员所想要的。让base classes成为virtual，可以消除这样的复制现象。此外virtual base classes亦可能导致另一个成本，因为其实现方法常常利用指针，指向“virtual base class成分”，以消除复制行为，而继承类的对象内可能出现一个（或多个）这样的指针。
举个例子考虑以下情况（常被称之为“恐怖的多重继承菱形图”）

class A { ... };
class B : virtual public A { ... };
class C : virtual public A { ... };
class D: public B, public C { ... };

其中A是个 virtual base class，因为B和C都采用虚拟继承。在某些编译器中，D对象的内存布局可能看起来如下：

把base class data memebers放在对象的尾端似乎有点奇怪，但那的确是常见的手法。当然啦，编译器有权决定如何摆布这些内存，此图的功能只是告诉我们“virtual base classes可能导致对象内的隐藏指针增加”这一概念，除此之外我们不应该对此图再有任何妄想。某些编译器会加入少量较少指针，某些编译器甚至有办法不增加任何指针（此类编译器赋予vptr和vtbl双重任务）。
将此图和稍早显示的“vptrs如何被加入对象内”一图整合起来，我们便明白，如果此处的base class A有任何虚函数，D对象内存布局便应该类似这样：

图中阴影部分便是对象之内由编译器加入的成分。此图可能会误导你，因为阴影面积和其他面积的比例应该由classes内的数据量决定。对小型classes而言，额外开销的相对量会比较大。对数据量多的classes而言，额外开销的相对量就比较无足轻重，虽然基本上它还是令人侧目的。
上图一个诡异之处是，虽然设计4个classes，却只出现3个vptrs。如果编译器喜欢，当然可以产生4个vptrs，但是3个已经足够了（B和D可以共享一个vptr）。大部分编译器会采用这项好处，降低编译器所带来的额外开销。
我们已经看到，虚函数如何使对象更大，并排除inlining，而我们也验证了多重继承和virtual base classes是如何增加对象大小的。让我们进入最后一个主题：运行时期类型辨识(runtime type identification, RTTI)的成本。
RTTI让我们得以在运行时期获得objects和classes的相关信息，所以一定得有某些地方用来存放那些信息才行——是的，它们被存放在类型为type_info的对象内。我们可以利用typeid操作符取得某个class相应的type_info对象。
一个class只需一份RTTI信息就好，但是必须有某种办法让其下属的每个对象都能够取用它。事实上这句话不完全为真。C++规范上说，只有当某种类型拥有至少一个虚函数，才保证我们能够检验这类型对象的动态类型。这使得RTTI相关信息听起来有点像一个vtbl：面对一个class，我们只需一份相关信息，而我们需要某种方法，让任何一个内含虚函数的对象都有能力取得其专属信息。RTTI和vtbl之间的这种平行关系并非偶发，RTTI的设计理念是：根据class的vtbl来实现。
举个例子，vtbl数组之中，索引为0的条目可能内含一个指针，指向“该vtbl所对应的class”的相应的type_info对象。class C1 tbl于是变成这样：

运用这种实现方法，RTTI的空间成本就只需在每一个class vtbl内增加一个条目，再加上每个class所需的一份type_info对象空间，如此而已。就像“vtbls耗用的内存对大部分程序而言不太可能构成威胁”一样，type_info对象的大小也不太可能招惹问题。
以下表格对于虚函数、多重继承、虚拟基类（virtual base classes）和RTTI的主要成本做了一份摘要：

性质	对象大小增加	Class数据量增加	Inlining几率降低
虚函数	是	是	是
多重继承	是	是	否
虚拟基类	往往如此	有时候	否
RTTI	否	是	否

有些人可能会看着这个表格大感惊讶地说：“我要坚守C阵营”。这很公平，我们有选择。但是记住，这里的每一个性质所提供的技能，我们在C语言中毒必须自己动手打造。大部分情况下，相比于编译器所产生的代码，我们自己动手打造的东西可能比较没效率，也比较不够鲁棒性（robustness）。举个例子，以嵌套式（nested）switch语句或层层迭迭的if-then-else来仿真虚函数调用，所产生的代码比条款描述的代码更多，执行起来也比较慢。此外，我们必须靠手动追踪对象类型，意味着我们的对象必须自行携带类型标识，于是对象变得更大。
了解虚函数、多重继承、虚拟基类（Virtual base classes）及RTTI的成本，很是重要。但同等重要的是，我们必须了解到，如果需要这些性质所提供的技能，我们就必须忍受那些成本，毕竟世事难两全。有时候我们的确会有正当的理由回避编译器所产生的服务，例如隐藏的vptrs及“指向virtual base classes”的指针，可能会造成“将C++对象存储于数据库”或“进程（process)边界间搬移C++对象”时的困难难度提高，所以我们可能会希望以某种方式模拟这些性质，使C++对象较易完成其他工作。然后从效率观点而言，自己动手，不太可能做得比编译器所产生的代码更好。

学习心得
本条款介绍了虚函数、多重继承、虚拟基类及RTTI等技术再对象成本增加，class数据量增加及Inlining几率等特性做了简要的描述。其中虚函数中的对象会增一个vptr是C++实现多态的重要基石，同时因为需要运行期才能对虚函数的地址进行确认，所以虚函数通常不能被定义为inline，即便定义为inline也将不会有实际效果。