奇技淫巧C++之懒惰计算

考虑这样一个表达式语句：

String result = str_you + “said: ” + str_he + “ said: @#$% ” + str_i + “said: over!”;

　　对于这样一个语句，程序如何求值呢？假设str_you是一个典型std::string类型，这个语句需要做5 次operator+运算，多个string临时对象,还极有可能的，多次的内存分配操作。

　　如果你的team leader对你说了类似话，兄弟，他是对你的代码性能不满呢。当然，聪明如你，一定会在上司找到你之前就发现了这里是个性能瓶颈，并且告诉他你正着手解决它呢。

　　办法是多种多样的，最正确的办法当然首先是看看设计上是否存在缺陷，并且可以修复以改善性能问题。假设，任何部分都很正确（我知道这不可能，一定有被你称为菜鸟的同事干了蠢事，不是吗？），责任只好落到你的肩上。打算怎么办？

　　我不知道你会怎么做，也许你会换一个更快的string,或者简单调整一下语句:

string result; result.reserve(1000); result += str_you; result += “said: ”; result += str_he; result += “ said: @#$% ”; result += str_i; result += “said: over!”;

　　如果只有一两个性能热点，我打赌，我会这样先尝试一下。我认为这是一个很好的开始，我们已经认识到导致瓶颈的原因并且试图消除它。你也可以这么做。 写这篇文章，当然意味着还有别的方法，而且和懒惰计算有关。因为我们不能修改basic_string::的operator+,因此，先把表达式变形:

Acce() + str_you + “said: ” + str_he + “ said: @#$% ” + str_i + “said: over!”;

　　因为operator+从左向右结合，可以采用我们加速过的运算过程。先看最简单的情况,和string相加。

template<typename Left, typename Right> struct Accelerate{ 　operator string () const; 　Left& left; 　Right& right; }; template<typename Left, typename Right> inline Accelerate< Accelerate< Left >, Right> operator+(Accelerate< Left >& lsh, const Right& rsh) { 　return Accelerate< Accelerate< Left >, Right>(lsh, rsh); }

　　显然，Accelerate是轻量级的，现在考虑怎么实现operator string () const呢？我的计划是，首先计算出字符串的总长度，然后开一个足够大的空间来复制字符串，避免反复分配内存:

operator string () const{ 　string str; 　str.reserve(length(left) + length(right)); 　append(str, left); 　append(str, right); 　return str; };

　　第一步，看看怎么实现length:

struct Empty{}; template<typename T> inline size_t length(const T& t){ 　return t.size(); } template<typename Left, typename Right> inline size_t length(const Accelerate<Left, Right>& t){ 　return length(t.left) + length(t.right); } template<> inline size_t length(const Accelerate<Empty, Empty>& t){ 　return 0; }

　　第二步，看看怎么实现append:

Template<typename Left, typename Right> inline append(string& str, const Accelerate& t ){ 　append(str, t.left); 　append(str,t.right); } Template< > inline append(string&, const Accelerate<Empty, Empty>& ){} inline append(string& str, const string& rsh){ 　copy(rsh.begin(), rsh.end(), back_inserter(str)); }

　　现在，我们整个计算的框架算是完成了，不过可真够复杂的。注意观察，实际上，Accelerate利用多重继承，把表达式转换成一个二叉树，叶结点就是实际的字符串。对于Acce有如下定义:

typedef Accelerate<Empty, Empty> Acce;

　　上面的过程针对string,实际上可以推广到其他的字符串形式，我们只需要重载特定的函数：length,append:

size_t length(const char* str) { 　return strlen(str); } Template<int SIZE> size_t length(const char[SIZE] str) { 　return SIZE – 1; //注意，形如length(”text”)这样的代码，重载决议将使用这个重载版本。 }

　　至于append,也是类似的手法：

inline void append(string& str, const char* src){ 　while(*src != ‘\0’) str.push_back(*src++); }

　　性能分析：

string str; str.reserve(length(left) + length(right));

　　这里，采用str是没有必要的，在性能关键的场合，这里完全可以用内存块取代，可以改善性能。另外,length的计算，对于string和char [SIZE]这两种形式，都是常数时间，后一种更是可以在编译期优化掉，无需计算。但是，对于char*这种形势，strlen导致一次线性扫描。在 append的过程中，再一次线性扫描同一个数据来源，这是可以继续优化的地方。但是在这里继续剖析的话，就弱化了我们懒惰计算的主旨了。在这里，只是展 示懒惰计算的威力。实际上，懒惰计算在ORM环境下也是常常用到的，当然也包括数据库操作，和从文件加载对象这样的操作。 为 了获得某个数据，必须进行事先的若干处理才能获得，假设事先处理的相对成本比较高，那么就可以考虑懒惰计算，在真正需要获得数据的时候，才实施计算，另外 可以在实施计算时，可以有更多的信息，从而实施各种优化手段。例如，ORM操作中，并不及时载入对象，当对象真正需要时，批量载入多个Lazy的对象，从 而优化IO也是一例。

查看本文来源