4 效率 | .27t_lBZ4oZgg

条例16：谨记80-20原则
条款17：考虑使用lazy evaluation（缓式评估）
条款18：分期摊还预期的计算成本
条款19：了解临时对象的来源
条款20：协助完成“返回值优化（RVO）“
条款21：利用重载技术（overload）避免隐式类型转换（implicit type conversions）
条款22：考虑以操作符符合形式（op==）取代其独身形式（op）
条款23：考虑使用其他程序库
条款24：了解virtual functions、multiple inheritance、virtual base classes、runtime type identification的成本

条例16：谨记80-20原则

80-20原则说：一个程序80%的资源用于20%的代码身上。因此根据观察或实验来识别出造成你心痛那20%代码，辨别之道就是使用某个程序分析器（program profiler）。

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

lazy evaluation（缓式评估）就是以某种方式撰写你的classes，使它们延缓运算，直到那些运算结果刻不容缓地迫切需要为止。其运算结果一直不需要，运算也就一直不执行。lazy evaluation有以下4种常见用途：
- Reference Counting（引用计数）。可避免非必要的对象赋值。lazy做法可以省下许多工作，string s1和string s2是两个字符串对象，我们让s2以s1为初值，而当s2的值需要修改时，才求取其值。那么我们可以在s2在需要被修改前，使用s1和s2的共享数据，直到需要被修改时才创建s2副本。
- 区分读和写。对于一个类的operator[]调用动作，可能为了写或读，而运用lazy evaluatino和proxy classes，可以延缓决定究竟是读是写。
- lazy fetching（缓式取出）。可避免非必要的数据库读取动作。产生一个对象时，只产生相应的“外壳”，不从磁盘读取任何数据，直至被需要时，才求取。这个可以使用smart pointer或者mutable修饰在const member functions里头判断并决定是否求取赋值。
- lazy expression evaluation（表达式缓评估）。可避免非必要的数值计算动作。

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

与lazy evaluation不同的是，超急评估（over-eager evaluation）超前进度地做“要求以外”的更多工作。举个例子，有个class template用来表现大型数据收集中心：
1
2
3
4
5
6
7
8
9
template<class NumbercalType>
class DataCollection
{
public:
NumercalType min() const;
NumercalType max() const;
NumercalType avg() const;
...
};
这个函数的实现方法有三种：
- eager evaluation：被调用时返回结果。
- lazy evaluation：函数的返回值需要被派上用场时，决定适当值。
- over-eager evaluation：随实记录程序执行过程中数据集的最小值、最大值和平均值。一旦被调用，立刻返回正确值无需再计算。这种方式通过频繁的调用摊还成本。
Caching时“分期摊还预期计算成本”的一种做法。Prefetching（预先取出）则是另一个种做法。可以想象它是大批购买物品后的折扣。因为磁盘控制器从磁盘读取数据时，读的是整个数据块或sectors。经验显示，如果某处数据被需要，通常其邻近的数据也被需要。这就是有名的locality of reference现象。系统设计者以此现象设计出磁盘缓存（disk caches）、指令与数据的内存缓存（memory caches）以及指令预先取出（instruction prefetches）。

加入要实现一个动态数组的template：

template<class T>
class DynArray { ... };
DynArray<double> a;
a[22] = 3.5;
a[32] = 0;

它怎么扩张自己？做内存动态分配行为：

template<clas 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
}

增加数组大小会调用new，但new会调用operator new，而operator new通常代价昂贵，因为它们会调用底层操作系统，而系统调用比进程内的函数调用速度慢，所以尽量不要系统调用。这时就可以使用over-eager evaluation（超急评估）策略，通过增加额外的数组大小来降低不久的下次可能再扩张时的成本。

条款19：了解临时对象的来源

程序员交谈的时候往往把一个短暂需要的变量称为临时变量，但在C++中它并不是临时对象，只是函数中的一个局部对象。C++真正的临时对象是不可见的。只要产生一个non-heap object而没有为它命名，就是临时对象。这种匿名对象发生于两种情况：一是隐式类型转换（implicit type conversions）；二是函数返回对象。

第一种考虑为了让函数调用成功而产生的临时对象，发生在传递某对象给一个函数，而其类与它即将绑定上去的参数类型不同：

// 返回ch在str中出现的个数
size_t countChar(const string &str, char ch);
char buffer[MAX_STRING_LEN];
char c;
// 读入一个char和一个string，利用setw避免读入string时缓冲区满溢的情况
std::cin >> c >> setw(MAX_STRING_LEN) >> buffer;
cout << "There are " << countChar(buffer, c)
    << " occurrences of the character " << c
    << " in " << buffer << endl;

编译器擦除了类型不吻合的状态：以buffer作为自变量，调用string constructor，countChar的str参数绑定于此string临时对象上。当countChar返回，此临时对象自动销毁。只有当对象以by value或当对象传给一个reference-to-const参数时转换才会发生。

第二种会产生临时对象的情况是当函数返回一个对象时。例如operator+的返回对象。

条款20：协助完成“返回值优化（RVO）“

函数如果返回对象，对于效率狂来说是个严重的溃败，因为以by-value方式返回对象，背后隐藏的constructor和destructor都将无法消除。而如果以by-pointer方式返回对象，对于其删除指针的操作通常会遗忘而导致资源泄露（resource leaks）。甚至以by-reference返回对象，那也是一个错误的行为，它返回的reference指向一个不再存活的对象。

我们可以用某种特殊写法来撰写函数，使它在返回对象时能够让编译器消除临时变量的成本。这个伎俩就是：返回所谓的constructor arguments以取代对象：

// 返回对象：最有效率的做法。
inline const Rational operator*(const Rational &lhs, const Rational &rhs)
{
    return Rational(lhs.numerator() * rhs.numerator(), lhs.denominator() * rhs.denominator());
}

它返回了一个表达式，该表达式调用了一个Rational constructor，这是一个临时对象，而函数复制此临时对象。
C++允许编译器将临时对下个你优化。编译器消除operator*内的临时对象及被operaotr*返回的临时对象。它可以让return表达式所定义的对象构造于所绑定的命名对象的内存内。如果编译器这么做，调用operator*的临时对象的总成本为0。甚至还可以声明为inline，以消除调用operator*所花费的额外开销。这种特殊的优化行为甚至有个专属名称：return value optimization。

条款21：利用重载技术（overload）避免隐式类型转换（implicit type conversions）

对于解决可能操作符运算隐式的内置类型转换为用户定制类型产生的临时变量，有个办法是为该操作符重载一个内置参数的版本。

条款22：考虑以操作符符合形式（op==）取代其独身形式（op）

大部分程序员希望，如果他们能x = x + y;这么写，那么他们也能够x += y这么写。如果x和y属于定制类型，就不保证如此，到目前为止C++并不考虑在operator+，operator=和operator+=之间设立任何互动关系。除非自己实现。确保操作符的复合形式（operator+=）和独身形式（operator+）之间的自然关系能够存在，一个好办法就是以前者为基础实现后者：

template<class T>
const T operator+(const T &lhs, const T &rhs)
{ return T(lhs) += rhs; }

Rational a, b, c, d, result;
// 会用到3个临时变量
result = a + b + c + d;
// 不需要临时变量，效率比上面的好
// 如果同时供应两种选择，便于客户较易理解的操作符独身版之余，同时保留了更有效率的符合版本
result = a;
result += b;
result += c;
result += d;

T(lhs)是个调用动作，调用T的copy constructor，它会产生一个临时变量，然后临时变量被用来调用operator+=：

template<class T>
const T operator+(const T &lhs, const T &rhs)
{
    T result(lhs);          // 将lhs复制发给result
    return result += rhs;   // 将rhs加到result上然后返回
}

这个template几乎等同于上一个，但是有个重要差异。第二个template内含了一个命名对象，这意味着返回值优化（return value optimization）无法施展于此operator+。

条款23：考虑使用其他程序库

理想的程序库应该小、快速、威力强大、富弹性、有扩展性、直观、可广泛使用、有良好支持，使用时没有束缚，而且没有臭虫。然而这时不存在的。如果针对大小和速度做优化，通常不具移植性，如果有丰富性能，就不容易直观，没有臭虫的程序库只能在乌托邦中寻找。

检验一个极为简单的性能评估软件，它只测试基本的IO机能。这个程序从标准输入读取30,000个浮点数，然后以固定格式将它们写到标准输出设备。程序用iostream还是stdio取决于预处理器符号STDIO：

#ifdef STDIO
#include <stdio.h>
#else 
#include <iostream>
#include <iomanip>
#endif

const int VALUES = 30000;

int main(int argc, char **argv)
{
    double d;
    for (int n = 1; n <= VALUES; ++n)
    {
#ifdef STDIO
        scanf("%lf", &d);
        printf("%10.5f", d);
#else
        std::cin >> d;
        std::cout << std::setw(10)
                  << std::setprecision(5)
                  << std::setiosflags(std::ios::showpoint)
                  << std::setiosflags(std::ios::fixed)
                  << d;
#endif
        if (n % 5 == 0)
        {
#ifndef STDIO
            printf("\n");
#else 
            std::cout << '\n';
#endif
        }
    }
    return 0;
}

iostreams也可以产生固定格式的I/O，虽然不易写。但是operator<<不但类型安全而且可扩充，而printf两者皆否。stdio版有时候比iostream只是块一点点（20%），有时候很多（200%）。

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

了解编译器以什么样的方法来实现它们是件重要的事情。其中最重要的就是虚函数。当一个虚函数被调用，执行的代码对应于调用者对象的类型。对象的pointer或reference，其类型是无形的，编译器是用virtual tables和virtual table pointers，通常被简写为vtbls和vptrs。

vtbl通常是由函数指针架构而成的数组（有些是用链表）。程序中每个class凡声明（或继承）虚函数者，都有自己的一个vtbl，而其中的条目（entires）就是该class的各个虚函数实现体的指针。这就是虚函数的第一个成本：必须为每个拥有虚函数的class耗费一个vtbl空间，空间大小视虚函数的个数（包括继承而来的）而定。

凡声明由虚函数的class，其对象都含有一个隐藏的data member，用来指向该class的vtbl。这个隐藏的data member——所谓的vptr——被编译器加入对象内某个只有编译器才知道的位置。这是虚函数的第二个成本：必须在每个拥有虚函数的对象内付出一个额外指针的代价。

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

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

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

编译器必须产生代码，完成以下动作：

根据对象的vptr找出其vbl。因为编译器知道去哪里找vptr。成本只有一个偏移调整（offset adjustment，以便获得vptr）和一个指针间接动作（以便获得vtbl）。
找出被调用函数（f1）在vtbl内的对应指针。成本只是一个差移（offset）。

调用步骤2所得指针所指向的函数。

// 想象一下每个对象都有隐藏的data member称为vtpr，而函数发
的vtbl索引是i
// 那么先前语句
pC1->f1();
// 产生的代码将是：
(*pC1->vptr[i])(pC1);
// 调用pC1->vptr所指的vtbl中的第i条目所指函数。
// 然后pC1被传给该函数的this指针所用

这几乎和一个非虚函数的效率相当。它调用虚函数的成本基本和通过一个函数指针来调用函数相同。虚函数本身不构成性能上的瓶颈。
虚函数真正的运行期成本发生在和inlining互动的时候。虚函数不应该inlined。因为inline意味着在编译期，将调用端的调用动作被调用函数的函数本体所取代，而virtual则意味着等待，直到运行期间才知道哪个函数被调用。这就是虚函数的第三个成本：事实上等同于放弃了inlining。（如果虚函数通过对象被调用，是可以inlined的，但大部分虚函数调用动作是通过对象的指针或references完成的，这行为无法被inlined，所以虚函数等于无法被inlined。）
在多重继承的情况下，情况变得有些复杂，一个对象可能包含多个vptr（每个base class各对应一个），这使得空间负担更大，运行期的调用成本也有增长。
多重继承往往导致virtual base classes（虚拟基类）的需求。virtual base classes可导致另一种成本，当利用指针或references指向某个virtual base class成分时，对象内可能出现多个这样的指针：

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

运行时期类型辨识（runtime type identification, RTTI）让我们在运行期获得objects和classes的相关信息，它们被存放在类型为type_info的对象内。可以利用typeid操作符取得某个class相应的type_info对象。只有当某种类型拥有至少一个虚函数，才保证我们能检验该类型对象的动态类型。它是个根据class的vtbl来实现的。RTTI的空间成本就只需在每个class vtbl内增加一个条目，再加上每个class所需的一份type_info对象空间。

性质	对象大小增加	Class数据量增加	Inlining几率降低
虚函数 Virtual Functions	是	是	是
多重继承 Multiple Inheritance	是	是	否
虚拟基类 Virtual Base Classes	往往如此	有时候	否
运行时期类型标识 RTTI	否	是	否