Deltamaster Tech Center

在学习数据结构和算法的时候，我们一般都会通过分析算法复杂度，来对某个问题选择合适的数据结构和算法。

下面就是一个经典问题：

我们需要一个容器，容器中存放的是int数据。容器中的元素是有序的，对容器有一个插入操作，要求是插入后容器中的元素仍然是有序的。我们应该选择list还是vector？

让我们先从算法复杂度的角度来简单看一下这个问题。首先一点是有序，所以找到要插入的位置，对于list的算法复杂度是O(n)，因为平均需要遍历一半的链表长度，对于vector的算法复杂度是log^2(n)，因为可以进行二分查找确定位置。然后是插入，list的插入操作是O(1)，非常理想的常数级操作，而vector的插入操作是O(n)，因为平均要移动一半的元素。综合下来看，list是要更胜一筹，所以应该选择list。但是事实却与这个推测截然相反？

让我们用C++写一段程序来进行验证：

#include <iostream>
#include <vector>
#include <list>
#include <random>

using namespace std;

template <typename T>
typename T::iterator insert(T& c, typename T::value_type elem)
{
    auto i = c.begin();
    for (; i != c.end(); i++) {
        if (elem <= *i) {
            break;
        }
    }
    return c.insert(i, elem);
}

int main(int argc, char** argv)
{
    vector<int> v;
    list<int> l;
    auto engine = default_random_engine();

    if (argc < 3) return 1;

    if (argv[1] && argv[1][0] == 'v') {
        for (int i = 0; i < atoi(argv[2]); i++) {
            insert(v, engine());
        }
    } else {
        for (int i = 0; i < atoi(argv[2]); i++) {
            insert(l, engine());
        }
    }

    return 0;
}

在这里为了说明问题方便起见，在查找阶段我们让vector和list都使用O(n)的方法进行查找。那么对于这段程序（下面表里的算法复杂度是针对每次插入操作而言的）：

这样，我们通过生成一系列随机数的方式来进行测试。让我们看看不同数据规模下的测试结果如何，表格中的时间单位是秒。

为什么list的性能反而差，而且相差如此悬殊？因为我们之前没有站在体系结构的角度看问题。同样是O(n)的操作，对于计算机而言实际执行的效率可能有着天壤之别。

让我们回顾一下前面程序中的insert函数模板，对于两种容器，我们使用了完全相同的线性查找算法。对于计算机而言，list版本的步进操作（i++），需要多进行一次寻址（根据指针找到下一个节点的位置），而更重要的是，找到的下一个节点，很有可能没有命中缓存，因为通过list中的相邻元素在内存中并没有相邻关系；而vector的步进操作，几乎能够保证命中缓存，因为每次访问的，都是内存中相邻的元素。对于插入操作而言，list虽然只有O(1)复杂度，而且确实非常快，但却要每次进行一次很小的内存分配，而又因为list的每个节点都要包含其他指针信息，对于内存空间也是很大的浪费。

我们从这个测试中得到的启示是：

• 性能分析要用实际测试数据说话，主观推测容易以偏概全；
• 对于体系结构的理解非常重要，缓存命中率是影响性能的重要因素；
• 数据规模小的时候，算法复杂度无关紧要；
• 不要过度优化；
• 节约使用内存！

许多程序员，尤其是很多稍有一些经验的C++程序员，会陷入一种为了性能而牺牲接口设计可维护性的误区，最终往往在性能上提升很少，甚至没有提高，程序可维护性也大大降低，这是我们都不希望看到的结果。

下面是一个典型的例子，当然进行了一定的抽象和简化。

void getA(A& x)
{
	// do some initialization to "x"
}

void f()
{
	A a;
	getA(a);
	// use "a"
}

我问，为什么不设计成“A getA()”，让对象a在函数getA中进行构造呢？这样接口就更加容易阅读，一般并不鼓励将参数作为输出参数来使用，这样会降低程序的可读性。

他给出的答案是，这样可以避免对象的拷贝构造，能够提升性能。因为如果在getA中构造了A的对象，那么在返回时要调用一次拷贝构造函数将这个对象拷贝构造到调用处，然后再析构getA中临时产生的对象。

事实果真如此吗？让我们阅读一下C++标准的相关章节。

When certain criteria are met, an implementation is allowed to omit the copy/move construction of a class object, even if the constructor selected for the copy/move operation and/or the destructor for the object have side effects. In such cases, the implementation treats the source and target of the omitted copy/move operation as simply two different ways of referring to the same object, and the destruction of that object occurs at the later of the times when the two objects would have been destroyed without the optimization. This elision of copy/move operations, called copy elision, is permitted in the following circumstances (which may be combined to eliminate multiple copies):

• in a return statement in a function with a class return type, when the expression is the name of a non-volatile automatic object (other than a function or catch-clause parameter) with the same cv-unqualified type as the function return type, the copy/move operation can be omitted by constructing the automatic object directly into the function’s return value

让我们根据上面条款来看看，下面的代码会怎么处理。

A getA()
{
	A x; // logically construct "x" here, but actually not
	// do some initialization to "x"
	return x; // logically copy-construct "x" to "a" here, but actually not
	// logically destruct "x", but actually not
}

void f()
{
	A a = getA(); // actually construct "x" directly here
	// use "a"
}

根据标准说明，函数getA的返回值是类型A，并且与返回类型一样是non-const、non-volatile对象，也是automatic对象（逻辑上被分配到栈上），从对象x到调用处（f函数中的变量a）的拷贝构造可以被省略，对象x将会被直接构造在f函数的变量a处（getA中的x和f中的a将被视为同一个对象）。即使拷贝构造函数中有任何副作用，这个调用也仍然可以被省略，并且这种行为被视为正常的语义，而非优化行为。

在gcc编译器中，即使指定优化级别为0，在上面的例子中也不会有两个A对象被构造；而Visual Studio指定了一定优化级别以后，多余的对象构造也会被省略。

因此，第一种写法能够提升性能的说法并不成立，而且接口设计相当丑陋难读。相反，有时第一种写法甚至会损害性能。

请看下面的代码。

A::A(int x, int y, int z) : x(x), y(y), z(z) {}

A getA()
{
	// get height, width, length from somewhere else
	A x(height, width, length);
	return x;
}

void f()
{
	A a = getA();
	// use "a"
}

这段代码说A有一种接受三个参数的构造函数，而这三个参数在getA中可以通过某些逻辑得到，那么可以直接通过带参数的构造函数对A进行初始化，这个带参数的构造函数直接用高效的冒号语法进行初始化。反观第一种方案，如果获取三个参数的逻辑对于函数f是不可见的，那么我们就必须要首先默认构造A对象，然后再进行赋值操作对A对象进行初始化，非但性能低下，且代码丑陋难以维护。

在C++11中引入了右值引用的概念，即使有编译器决定将x构造在getA内部，再用它来构造对象a，这种情形也适用move constructor，而几乎没有可观的性能损耗。当然，在这种情况下，即使定义了move constructor，gcc也不会调用它。

所以，我们不应该想当然地对代码进行优化，尤其是在要牺牲代码可读性的情况下更加应该慎重：

• 首先应该考察，是否确实存在性能低下（在这个例子中没有）
• 如果性能低下，则需考察这个性能问题是否是系统性能的瓶颈
• 如果是，是否能够借助编译器优化提升性能，或者局部性地改变代码使得编译器更容易优化，或许会影响一定的代码的可读性，但对于接口的可读性没有影响
• 如果仍然无法改善，才有可能考虑牺牲接口的可读性