More Effective C++之效率Efficiency_上

    本章以两个角度对“效率”主题发动攻击。第一个角度和程序语言无关，其相关讨论适用于任何程序语言。针对书中所列的观念，C++有一个极佳的实现媒介：由于它对封装（encapsulation）的强力支持，我们有可能将低效的class实现品以相同接口但拥有较佳算法和数据结构的新产品取代。
    第二个角度和C++本省有强烈关系。高性能算法和数据结构虽然很棒，但是草率的实现过程会严重降低其影响力。最阴鸷险恶的错误就是“产生和销毁过多的对象”，这不但容易形成，而且不容易被辨识出来。多余对象的构造动作和析构动作相识程序性能的大出血，每次一有非必要的对象被产生和被销毁，便流失宝贵的CPU时间。这个问题在C++程序中是如此普遍，本书特别为它贡献了4个各自独立的条款，分别描述非必要的对象究竟来自何处，以及如何消除它们而不损害程序的正确性。
程序变大和变慢，并不知因为产生太多的对象，高性能道路上的其他坑坑洞洞还包括程序库的选用及语言特性的实施。以下各条款中，也会讨论这些题目。
    读过本章内容后，我们将对改善性能的数个原则有所熟悉，我们将确切知道如何组织非必要的对象在程序中蔓延，对于编译器如何产生可执行文件，也会有更敏锐的了解。

条款16：谨记80-20法则

    80-20法则告诉我们：一个程序80%的资源用于20%的代码身上。是的80%的执行时间花在大约20%的代码身上，80%的内存被大约20%的代码使用，80%的磁盘访问动作由20%的代码执行，80%的维护力气花在20%的代码上面。这个法则在数不尽的机器平台，操作系统，以及应用程序上不断得获得验证。80-20法则不只是一个动人的口号而已，它是性能议题上的一个准则，有广大的应用价值和坚实的实证基础。
    当我们考虑80-20法则时，有一点很重要：不要拘泥于字面上的数字。有些人喜欢更严厉的90-10法则，也有人喜欢同样有着实验证据而稍微宽松的数据，不论正确数字为何，基本的重点在于：软件的整体性能几乎总是由构成要素（代码）的一小部分决定。
    当程序员努力提升软件性能的时候，80-20法则即可以简化我们的生活，也可以是我们的生活更复杂。从某个角度看，80-20法则暗示，大部分时候，我们所产出的代码，其性能坦白说是平凡的，因为80%的时间中，其效率不会影响系统整体性能。或许这不至于对我们的自尊心造成太大的打击，但应该多少会降低我们的压力。从另一个角度看，这个法则暗示，如果我们的软件有性能上的问题，我们将面临悲惨的前景，因为我们不只需要找出造成问题的那一小段瓶颈所在，还必须找出办法大幅提升其性能。这些工作之中，最麻烦的还是找出瓶颈所在。有两个本质不同的方法可以逼近它；
    大部分人采用的瓶颈查找法是“猜”。用经验猜，用直觉猜，或是根据谣言，或更糟的根据代代相传流于形式的宣称：因为网络的延迟啦，因为内存分配器没有做适当的调整啦，因为编译器没有足够的优化啦，或是因为某个愚蠢的经理拒绝我们在关键的内部循环中使用inline assembly啦……如此的见解与判断往往夹带着一些叫人不得不领情的嘲讽，而嘲讽者和其预判却又往往都是错误的。
    大部分程序员对于程序的性能特质，都有错误的直觉，因为程序的性能特质倾向高度的非直觉性。结果，无数的努力灌注在一些绝对无法提升整体性能的程序段落上头，形成严重的精力浪费。举个例子，我们当然可以采用某些特选的算法和数据结构加入程序之中，将运算量最小化，但如果这个程序受制于I/O（所谓I/O-bound）,那么前述种种努力对性能就一点帮助也没有。我们可以选用威力强化的I/O程序库来取代编译器所附的版本，如果程序受制于CPU(所谓CPU-bound)，这对性能也发挥不了什么作用。
    那么，如果我们面对一个迟缓的程序或是一个内存用量过大啊的程序，我们该怎么办？80-20法则告诉我们，如果我们只是东一块西一块地改善程序，病急乱投医，头痛医头脚痛医脚，不会有太大帮助。“程序的性能特质倾向高度的非直觉性”这个事实意味着，企图猜出性能瓶颈之所在，比头痛医头脚痛医脚更是不如。那么，什么是可行之道？
    可行之道就是完全根据观察或实验来识别出造成我们心痛的那20%代码。而辨识之道就是借助某个程序分析器（program profiler）。然而并不是任何分析器都足堪大任，它必须可以直接测量我们所在意的资源。例如，假设我们的程序太慢，我们需要一个分析器告诉程序的不同区段各花费多少时间，于是便可以专注在特别耗时的地方加以改善，这不但可以巨幅提高局部效率，对整体效率也会有极大帮助。
    那种告诉你每个语句需要多少执行时间，或是每个函数被调用多少次的分析器（profile），其实功能有限。从性能观点来看，我们不必在乎一个语句被执行多少次或一个函数被调用多少次。毕竟，程序用户或程序库客户之中，会抱怨“执行太多语句”或是“调用了太多函数”的人是很罕见的。如果我们的软件够快，没有人会在乎执行太多语句；如果我们的软件过慢，也没有人会因为只执行了很少的语句就接受这个软件。他们所在乎的只是：他们讨厌等待，如果程序让他们等待，他们就会讨厌提供程序的人。
    当然啦，知道语句被执行或函数别调用的频繁度，有时候可以让我们对软件的行为有更深刻的了解。举个例子，如果我们为某个class产生一百个对象，而该class的constructor却被调用了数千次，那当然值得注意。此外，语句的执行次数和函数的调用次数可以间接协助我们了解无法直接测量的软件行为。如果无法直接测量动态内存的使用，那么，知道内存分配函数和释放函数（如new，new[]和delete，delete[] 见 条款8 ）被调用的频率，至少也可以带来一些联想。
    当然，即使是最好的分析器（profile）也受制于它所使用的数据。如果我们已无法重现的（unrepresentative）数据喂给既定程序，然后分析其行为，那么万一分析器引导去调整属于80%那一部分代码——它们对于整体性能通常没有什么责任——我们就没有立场加以抱怨。记住，分析器只能告诉我们程序在某次（某组）特定执行过程中的行为，因此如果我们以无法重现的数据来运行程序，然后分析之，我们便是在分析无法重现的行为。那可能会导致我们对一些不常被使用的程序行为做优化努力，这对常用部分的整体冲击可能反而是负面的。
    防范这种病态结果的最佳办法就是尽可能多地以最多的数据来分析我们的软件。此外，我们必须确保每一组数据对于软件的所有客户（或至少最重要的客户）而言都是可重制的（representative）。可重置数据通常不难取得，因为许多客户会很乐意让我们使用他们的数据做软件分析之用。毕竟，我们将因此调整软件以符合他们的需求，而那对双方都好。
学习心得
    本主题告诫我们影响程序的性能会是占比比较少的20%的代码，同时如何找到并优化这20%的代码，是不能随意靠猜，或者简单的分析就能达成的；需要基于大量数据的测试及分析才能获取到的；所以在性能优化过程中，需要建立在充分的事实性能测试数据及逻辑分析后才进行优化。

条款17：考虑使用lazy evaluation（缓式评估）

    从效率的观点看，最好的运算是从未被执行的运算。那当然好，但如果我们不需要做某些事，当初又何必把相应的代码放进程序呢？如果我们确实需要做某些事，我们又怎么能够避免相应代码的执行？
    关键在于所谓的拖延战术。在计算机中有一个高贵的名称：lazy evaluation（缓式评估）。一旦我们采用lazy evaluation，就是以某种方式撰写的classes，使它们延缓运算，直到那些刻不容缓地被迫切需要为止。如果其运算结果一直不需要，运算也就一直不执行。
    我们列举几个场景。

Reference Counting（引用计数）

    考虑这样的代码：

class String { ... };						// 一个字符串类
String s1 = "Hello";
String s2 = s1;								// 调用String的copy constructor

    String copy constructor的一个常见做法是，一旦s2以s1为初值，便导致s1和s2各自有一份“Hello”副本。如此的copy constructor会导致相当大的成本代价，因为它必须为s1的内容做一份副本，交给s2，而那通常会伴随着用new operator(见条款8)分配heap内存，并调用strcpy将s1的数据复制到s2所分配的内存内。这是所谓的eager evaluation（急式评估）：只因String的copy constructor被调用，就为s1做一个副本并放进s2内。其实此时s2尚未真正需要实际内容，因为s2尚未被使用。
    缓式（lazy）做法可省下许多工作。我们让s2分享s1的值，而不再给予s2一个“s1内容副本”。唯一需要做的就是一些簿记工作，是我们得以知道谁共享了些什么东西。这种做法节省了“调用new”及“复制任何东西”的高昂成本。“s1和s2共享同一个数据结构”这个事实对客户而言是透明的，对以下语句当然也不会有影响，因为以下语句只读取数据，并不写入数据：

cout << s1;									// 读出s1的值
cout << s1 + s2;							// 读s1和s2的值

    事实上，数据共享所引起的唯一危机是在其中某个字符串被修改时所发生的。此时应该（我们期望）只有一个（而非两个）字符串被修改。下面的语句中：

s2.convertToUpperCase();

    应该只有s2的内容被改变，s1并没有改变。
    为了处理这样的语句，我们必须令String的convertToUpperCase函数为s2的内容做一个副本，并在修改它之前先让该副本成为s2的私有数据。在convertToUpperCase函数内，我们再不能够做任何拖延了：我们必须将s2（被共享）的内容做一个副本，给s2私人使用。另一方面，如果s2从未被更改，我们就不需要为内容做一个私有副本，该内容可以继续被共享。如果我们够幸运，s2从未被修改，那么我们就不需要求取其值。
    这种“数据共享”的行动细节（及相应代码）在条款29¹有详细叙述，其观念便是lazy evaluation：在我们真正需要之前，不必着急为某物做一个副本。取而代之的是，以拖延战术应付之——主要能够，就使用其他副本。在某些领域，我们常有可能永远不需要提供那样一个副本。

区分读和写

    继刚刚所举的reference-counting字符串实例之后，更进一步，我们看看lazy evaluation带给我们的第二种应用。考虑以下代码：

String s = "Hmoer's Iliad";					// 假设s是个reference-counted字符串
...
cout << s[3];								// 调用operator[] 以读取数据s[3]。
s[3] = 'x';									// 调用operator[] 将数据写入s[3]。

    第一个operator[]调用动作用来读取字符串的某一部分，第二个调用则执行一个写入动作。我们希望能够区分两者，因为对一个reference-counted字符串做读取动作，代价十分低廉，但是对这样一个字符串做写入动作，可能需要先为该字符串做一个副本。
    这是我们处于一个困难的实现位置上。为了达成我们所想要的，我们必须在operator[]内做不同的事情（视它用于读取功能或写入功能而定）。我们如何能够判断operator[]是在读或写的环境下被调用呢？答案很残忍：我们无能为力。然而如果运用lazy evaluation和条款30¹所描述的proxy classes。我们可以延缓决定“究竟是读还是写”，直到能够确定其答案为止。

Lazy Fetching(缓式取出）

    Lazy evaluation的第三个例子：想想我们的程序使用大型对象，其中内含许多字段。如果对象必须在程序每次执行时保持与前次执行的一致性与连贯性，所以它们必须存储于一个数据库中。每个对象有一个独一无二的识别码，可用来从数据库中取回对象：

class LargeObject {											// 大型的、可持久的（persistent）对象。
public:LargeObject(ObjectID id);								// 从磁盘中回存对象const string& field1() const;							// 字段1的值int field2() const;										// 字段2的值double field3() const;									// ...const string& field4() const;		const string& field5() const;				...
};

    现在考虑从磁盘中回复一个LargeObject对象所需的成本：

void restoreAndProcessObject(ObjectID id) {LargeObject object(id);									// 回复对象。
}

    由于LargeObject的体积很大，欲取出此类对象的所有数据，数据库相关操作程序可能成本极高，特别是如果这些数据必须从远程数据库跨越网络而来。某些情况下，读取所有数据其实是不必要的。举个例子，考虑下面这种应用：

void restoreAndProcessObject(ObjectID id) {LargeObject object(id);	if (object.field2() == 0 ) {cout << "Object " << id << ":null field2.\n";}
}

    此处只用到field2，所以设立其他字段所花费的任何努力都是一种浪费。
    此问题的缓式（lazy）做法是，我们在产生一个LargeObject对象时，只产生该对象的“外壳”，不从磁盘读取任何字段数据。当对象内的某个字段被需要了，程序才从数据库中取回对应的数据。下面的做法可实现出这种所谓的“demand-paged”式的对象初始化行为。

class LargeObject {												
public:LargeObject(ObjectID id);								const string& field1() const;						int field2() const;										double field3() const;						const string& field4() const;		const string& field5() const;				...
private：ObjectID oid;mutable string *field1Value;							// 稍后讨论“mutable”。mutable int * field2Value;mutalbe double * field3Value;mutalbe string *field4Value;...
};
LargeObject::LargeObjectt(ObejctID id) 
: oid(id), field1Value(0), field2Value(0), field3Value(0), ...  {
}
const string& LargeObject::field1() const {if (field1Value == 0 ) {read the data for field 1 from the database andmake filed1Value point to it;}return *field1Value;
}

    对象内的每个字段都是指针，指向必要的数据，而LargeObject constructor负责将每个指针初始化为null。如此的null指针象征字段数据尚未由数据库读入。LargeObject的每一个member function在访问字段指针所指的数据之前，都必须检查字段指针的状态。如果指针是null，表示对应的数据必须先从数据库读入，然后才能操作该数据。
    实现lazy fetching时，我们必须面对一个问题：null指针可能会在任何memeber functions(包括const member functions，如field1)内被赋值，以指向真正的数据。然而当我们企图在const member functions内修改data memebers，编译器不会同意。所以我们必须用某种方法告诉编译器说：“放轻松我知道我正在干什么”。说这句话的最好方法就是将指针声明为mutable，意思是这样的字段可以在任何memeber function内被修改，甚至是在const member functions内。这就是为什么上述LargeObject的所有字段都被声明为mutable的缘故。
    再次看看LargeObject内的指针。让我们面对这个事实：将所有这些指针初始化为null，然后再使用之前测试它。这样不仅沉闷、令人生厌，而且容易出错。幸运的是，如此单调乏味的苦工可由smart pointers（见条款28¹）自动完成。如果我们在LargeObject内使用smart pointers，就不再需要为这些指针声明mutable。啊，其实只是延后使用而已，因为当你忙完这些，坐下来准备实现smart pointer class时，还是需要用到mutable。不妨把它视为另一种“拖延战术”。

Lazy Expression Evaluation（表达式缓评估）

    lazy evaluation的最后一个例子来自数值应用。考虑以下代码：

template<class T>
class Matrix { ... }									// 同质（homogeneous）矩阵Matrix<int> m1(1000, 1000);								// 一个1000*1000的矩阵
Matrix<int> m2(1000, 1000);								// 同上。
...
Matrix<int> m3 = m1 + m2;								// 将m1加上m2

    operator+通常采用eager evaluation(急式评估)。此例会计算并返回m1和m2的总和。这是一个大规模运算（1000000个加法），此外还有大量内存分配成本。
    Lazy evaluation策略于是说话了：“动作太多，我不打算这么做”。它设立一个数据结构于m3中，表示m3的值是m1和m2的总和。如此的数据结构可能只是由两个指针和一个enum构成，前者指向m1和m2，后者用来指示运算动作时“加法”。很明显，设立这样的数据结构可比“对m1和m2进行加法”快多了。耗用的内存也少得多。
    假设之后，在m3被使用之前，程序执行了以下动作：

Matrix<int> m4(10000, 1000);
...
m3 = m4 * m1;

    现在我们可以忘记m3是m1和m2的总和了（于是省下了计算成本）。从现在开始我们可以记录：m3是m4和m1的乘积。不用说，我们不会立刻执行这个乘法。何必操心呢？我们一向慢慢来（lazy）。
    这个例子看起来有点做作，因为没有一位程序员会在程序员中计算两个矩阵的和却不使用它。但其实这例子并非真的那么做作。虽然没有任何程序员会故意计算一个不需要的值，但是在维护过程中，程序员更改执行路线，使原本有用的计算变得不再必要，是常有的事。欲降低这种即兴式演出所带来的影响，请在使用对象的前一刻才将对象定义出来。然而，即使如此循循善诱，目前所讨论的问题仍然不定时地就会出现。
    尽管如此，如果这是lazy evaluation取得功名的唯一机会，那么实在不值得我们如此大费周章。更常见的一种情况是，我们只需要大型运算中的部分运算结果。例如，假设我们将m3初始化为m1和m2的总和之后，这样使用m3：

cout << m3[4];											// 输出m3的第四行；

    很显然我们不再能够采用拖延战术——我们必须计算m3第四行的值。但是也不要过度热心，因为没有理由在此刻计算m3第四行以外的任何值。那些值可以保留未计算状态，直到真正被需要为止。如果幸运，也许根本不必计算它们。
    我们成为幸运儿的几率有多少？矩阵运算的经验告诉我们，很大。事实上正因为lazy evaluation才撑起APL²的神奇。APL开发于20世纪60年代，允许用户以交谈的方式使用此软件执行矩阵运算。虽然当时它所处的执行平台，其运算能力比起今天高档微波炉烤箱内的芯片恐怕尚有不足，但APL表面上能够快速处理加法、乘法，甚至除法。其所运用的伎俩就是lazy evaluation。这个伎俩通常极具效力，因为APL的用户通常之所以对矩阵做加法、乘法或除法，并不是因为他们需要整个矩阵结果，而是只需要其中一小部分。APL采用lazy evaluation来延缓计算。这允许用户在一个“底部机器尚未成熟到足以实现出eager evaluation（急式评估）”的环境中，以交谈的方式执行“运算密集”工作，今天，虽然机器更快了，但数据量也更大了，用户也更没有耐性了，所以当许多当代的矩阵程序库仍然继续借重lazy evaluation。

cout << m3;												// 输出m3的所有内容

    钓钩拉起来了，我们必须计算m3的完整内容。同样道理，如果m3所依赖的矩阵之中有一个被修改了，我们也必须立刻行动：

m3 = m1 + m2;											// 记录：m3是m1和m2的总和
m1 = m4;												// 现在：m3应该是m2和“m1旧值”的总和

    在这里我们必须做点事情，确保对m1的复制动作不会改变m3.在Matrix的assignment操作符，我们可能会在改变m1之前先计算m3的值，或者我们可能将m1的旧值复制一份，然后再令m3依赖该值。我们必须另外做些事情以保证m3有其该有的值，不因m1的改变而改变。其他可能修改矩阵值的函数，也必须以类似的方式处理。
    由于必须存储数值间的依赖关系，而且必须维护一些数据结构以存储数值、依赖关系，或是两者的组合，此外还必须将赋值（assignment）、复制（copying）、加法（addition）等操作符加以重载，所以lazy evaluation在数值运算领域中有许多工作要做。不过辛苦有代价，它通常能够在程序执行时节省大量的时间和空间，在许多应用领域中，此收益足以让程序员为lazy evaluation卖命。

摘要

    上述4个例子显示，lazy evaluation在许多领域中都可能有用途：可避免非必要的对象复制，可区别operator[]的读取和写动作，可避免非必要的数据库读取动作，可避免非必要的数值计算动作。尽管如此，lazy evaluation并非永远是好主意。就像我们搁下打扫房间的工作一样，如果父母一定回来检查的话，我们究竟还是得打扫，占不到丁点便宜。是的，如果计算式必要的，lazy evaluation并不会为程序节省任何工作或任何时间。事实上如果计算绝对必要，lazy evaluation甚至可能使程序更缓慢，并增加内存用量，因为程序除了必须做原本希望避免的所有工作之外，还必须处理那些为了lazy evaluation而设计的数据结构。只有当“软件被要求执行某些计算，而那些计算其实可以避免”的情况下，lazy evaluation才有用处。
    lazy evaluation并非C++的专属技能。这项技术可以用任何一种程序语言完成，有数种语言——尤其是APL、某些Lisp版本，以及几乎所有数据流（dataflow）语言——已接受这个观念成为语言的一个基础部分。但主流程序语言仍然采用eager evaluation，而C++是主流语言之一。不过，C++特别适合作为“由用户完成的lazy evaluation”的载体，因为它支持封装性质（encapsulation），使我们有可能把lazy evaluation加入某个calss内而不必让其客户知道详情。
    再次看看上述例子中的程序片段，我们可以验证，那些class接口对于是否使用eager evaluation或lazy evaluation并没有露出半点蛛丝马迹。这意味着我们可以先实现一个class，使用直接而易懂的eager evaluation策略，但是分析报告指出“这个class乃性能瓶颈之所在”后，以另一个实行lazy evaluation的class取代原先的class。我们的客户唯一可能见到的改变（在重新编译或重新链接之后）就是性能有了改善。这是客户喜爱的一种软件加强法，一种让我们竟然可以对懒惰（lazy）感到骄傲的方法。
学习心得
    本条款告诉我们，我们通常认为的eager evaluation（急式策略），或者我们通常赞颂的立刻执行，可能会导致程序运行“缓慢”。因为有很多急式（立即）运算的结果，可能程序不一定全部用得到，甚至有可能不会被用到；此种现象在矩阵运算中极其常见，所以才有了lazy evaluation（缓式评估）的策略。本条款给了我们一个实践策略，实现程序功能时首先不考虑lazy evaluation；只有当某个class确实成为性能瓶颈时，才开始进行分析，看看是否有可能通过lazy evaluation代替原来的eager evaluation，是否达到节省部分运算的目的，从而提升程序性能。

条款18：分期摊还预期的计算成本

    在条款17中，赞扬了拖延战术（laziness）——也就是尽可能延后执行——的价值，也解释了拖延战术如何改善程序性能。本条款将站在一个不同的位置，在这里拖延战术无着力点。现在改善软件性能的方法是：令它超前进度地做“要求以外”的更多工作。此条款背后的哲学课称为超急评估（over-eager evaluation）：在被要求之前就先把事情做下去。
    举个例子，考虑一个class template，用来表现数值数据的大型收集中心：

template <class NumbericalType>
calss DataCollection {
public:DataCollection min() const;DataCollection max() const;DataCollection avg() const;...
};

    假设min，max，avg3个函数分别返回该数据群当时的最小值、最大值和平均值。这些函数的实现法有3种。第一种是使用eager evaluation，于是我们在min，max或avg被调用时才检查所有数据，然后返回检查结果；第二种是使用lazy evaluation，于是我们令这些函数返回某些数据结构，用来在“这些函数的返回值真正需要被派上用场”时，决定其适当的数值；第三种是使用over-eager evaluation，也就是随时记录程序执行过程中数据集的最小值、最大值和平均值，一旦min、max或avg被调用，我们便立刻返回正确的值，无需再计算。如果min，max和avg常被调用，我们便立刻返回正确的值，无需再计算。如果min、max和avg常被调用，我们便能够分期（逐次）摊还“随时极速数据群之最小、最大、平均值”的城北，而每次调用所需付出的（摊还后的）成本，将比eager evaluation或lazy evaluation低。
    Over-eager evaluation背后的观念是，如果我们预期程序常常会用来某个计算，我们可以降低每次计算的平均成本，办法就是设计一份数据结构以便能够极有效率地处理需求。
    其中最简单的一个做法就是将“已经计算好而有可能再被需要”的数值保留下来（所谓caching）。例如，假设我们写一个程序用来提供职员信息，而我们预期职员的房间号在此程序中常常会被使用。更深层次假设，职员相关信息存储在一个数据库中。由于大部分应用程序并不需要职员的房间号码，所以这个数据库并没有特别针对此字段做优化。为避免这个有着特殊应用到程序重复不断地寻找职员房间号码而造成数据库的不当压力，我们一个写一个firstCubicleNumber函数，会将所查到房间号码记录下来。后继再有房间号码的查询需求时，如果该号码已取出，就借用告诉缓存（cache）完成任务，不必再去查询数据库。
    下面是findCubicleNumber的一种实现方法，其中使用Standard Template Library（–见条款35¹）提供的map object作为局部缓存：

int findCubicleNumber(const string& employeeName) {// 定义一个static map以持有（employee name， cubicle number）数据对// 这个map用来局部缓存（local cache）。typedef map<string, int> CubicleMap;static CubicMap cubes;// 尝试在cache中针对employeeName找出一笔记录。如果确有一包，// STL iterator “it”便会指向该笔被找到的记录CubicleMap::iterator it = cubes.find(employeeName);// 如果找不到任何吻合记录，“it”的值将会是cubes.end()// (这是STL的标准行为)。如果是这种情况，那么就// 针对此房间号码查询数据库，然后把它加进cache之中。if (it == cubes.end()) {int cubicle = the result of looking up employeeName's cubicle number in the database;cubes[emplyeeName] = cubicle;						// 将(employeeName, cubicle)"数据对"加入cache之中return cubicle;}else {// "it"指向正确的cache记录，那是一笔(employee name, cibicle number)pair。return (*it).second;}
}

    该策略就是使用一个局部缓存（local cache），将相对昂贵的“数据库查询动作”以相对廉价的“内存内数据结构查找动作”取代之。倘若我们假设房间号码频繁被需要，而且这是正确的假设，那么findCubicleNumber内使用cache，应该可以降低“返回一个职员的房间号码”的平均成本。
    Caching是“分期摊还预期计算之成本”的一种做法，Prefetching（预先取出）则是另一种做法。我们可以把prefetching想象是购买大量物品时的一个折扣。例如，磁盘控制器，当它们从磁盘读取数据时，读的是整个数据库或sectors——即使程序只需要其中少量数据。那是因为一次读一大块数据比分成两三次每次读小块数据，速度上快很多。此外，经验显示，如果某处的数据被需要，通常其邻近的数据也会被需要，这便是有名的locality of reference现象（译注：意指被取用的数据有“位置集中”的倾向）。系统设计者依此现象而设计出磁盘缓存（disk caches）、指令与数据的内存缓存（memory cachees），以及“指令预先取出（instructiion prefetches）”
    想象一下，假设我们希望实现一个“动态数组”的template，也就是说数组大小一开始为1，然后自动扩张，使所有非负索引值皆有效：

template<class T> 
class DynArray { ...  };
DynArray a;								// 此时，只有a[0]是合法的数组元素
a[22] = 3.5;							// a被自动扩张，此刻有效索引值是0-22
a[32] = 0;								// a再度扩张，此刻a[0]-a[32]都有效

    DynArray object如何才能在必要的时候扩张自己？最直接易懂的策略就是为新加入的索引值做内存动态分配行为，像这样：

template <class T>
T& DynArray<T>::operator[](int index) {if (index < 0) {throw an exception;				// 负索引值无效}if (index > the current maximum index value) {call new to allocate enough additional memory so that index is valid;}return the indexth element of the array;
}

    此做法是在每次需要增加数组大小时就调用new，但是new会调用operator new，而operator new通常代价昂贵，因为它们通常会调用底层操作系统，而“系统调用”往往比“进程（process)内的函数调用”速度慢。所以我们应该尽可能不要采用系统调用。
    此处我们可以使用over-eager evaluation（超急评估）策略，理由是：如果我们此刻必须增加数组大小以接纳索引i，“locality of reference法则”建议我们未来或许还需要增加大小，以接纳比i稍大的索引。为避免第二次（预期中）扩张所需要的内存分配成本，我们把DynArray的大小调整到比它目前所需的大小（使索引i有效）再大一些，而我们希望未来的扩张落入我们此刻所增加的弹性范围内。例如，DynArray::operator[]可撰写为如下：

template <class T>
T& DynArray<T>::operator[](int index) {if (index < 0) {throw an exception;				// 负索引值无效}if (index > the current maximum index value) {int diff = index - the current maximum index value;call new to allocate enough additional memory so that index + diff is valid;}return the indexth element of the array;
}

    此函数在每次数组需要扩张时，分配两倍内存。回头看看先前的使用方式，我们可以注意到，DynArray只需要分配一次内存就好——虽然其逻辑大小扩张了两次；

class DynArray { ...  };
DynArray a;								// 此时，只有a[0]是合法的数组元素
a[22] = 3.5;							// a被自动扩张，使能容纳索引为44，a的逻辑大小为23
a[32] = 0;								// a的逻辑大小改变，以允许a[32]存在，但是没有再调用new

    如果a有必要在扩张，而新的索引值不超过44，那么二度扩张不费吹灰之力。
    这个条款可由一个旋律贯穿之：较佳的速度往往导致较大的内存成本。是的，随时记录最小值、最大值、平均值总是需要额外的空间，但可以节省时间。Cacheing会消耗较多的内存，但可以降低那些“已被缓存（caching）的结果”的重新生成时间。整个故事和计算机科学的历史一样古老：空间可以换时间。（但并非总是如此。较大的对象意味着比较不容易塞入虚内存分页（virtual memory page）或缓存分析（cache page）中。少数情况下，对象变大会降低软件的性能，因为我们的换页（paging）活动会增加，我们的缓存命中率（cache hit rate）会降低，或者两者皆发生。如果我们引起这类问题，如果找出症结所在？答案是利用分析器（profiler）。
    本条款所提出的忠告——也就是我们可以通过over-eager evaluation和caching和prefetching等做法分期摊还预期运算成本——和在条款17所提供的lazy evaluation并不矛盾。当我们必须支持某些运算而其结果并不总是需要的时候，lazy evaluation可以改善程序效率。当我们必须支持某些运算而其结果几乎总是被需要，或是其结果常常被多次需要的时候，over-eager evaluation可以改善程序效率。两者都比直截了当的eager evaluation难实现，但是两者都能为适当的程序带来巨大的性能提升。

学习心得
    本条款的主要思想是使用over-eager evaluation（超急评估），此条款与条款17形成呼应，互有适应的场景；该条款适用于经常会被调用，但是可以通过缓存结果的方式进行提前计算进行空间换时间；还有就是对于资源的申请，可以预见性的提前申请（比如内存预申请更大的空间），作为over-eager evaluation的一种形式。

学习文档³;

---

1. 1: 待补充 ↩︎ ↩︎ ↩︎ ↩︎

2. 2: A Programming Language, https://aplwiki.com
       很公平的是，拖延战术有时无法成功。如果m3被这样使用： ↩︎

3. 3: More Effective C++: 35个改善编程与设计的有效方法/（美）梅耶(Meyers’s.)著;侯捷译.北京：电子工业出版社，2011.1 ↩︎