一个简单例子：有很多个html网页，网页的id、title、url、path等信息存在一个数据库表中，网页内容存储在一个磁盘阵列上。现在要把所有网页都读出来，统计其中的html标签、正文等信息，并写入另一个数据库表，怎样的设计最好呢？ 继续阅读 →

C++ 现在最时髦的用法是 template meta programming。booster 们对此非常津津乐道，我本人也是个狂热的booster。到了什么程度？不使用template 就浑身不舒服，不boost一下就感觉对不起C++。但是这种狂热带来的严重后果就是程序编译速度极慢无比，生成的执行程序尺寸超常。

曾经一个 C++ 服务器程序，代码也就10000行左右，编译出来的执行程序竟然20M！编译时间半小时！写的时候感觉不到用了多少template，但是写出来竟然得到这样的结果，不得不让人吃惊！

记得在大学的时候（2000年前后），初学习 template 时，感觉template之间的耦合有点“过于松散”，就像只要有一个螺母，再一个螺栓，就可以往一起套，而不管他们是否一个是塑料，一个是金属，大小粗细是否匹配，螺距是否匹配，所有的这一切，如果只有哪怕一点点不匹配，都会在编译错误中造成一个非常令人费解的超长消息。当初也不知道这一点早已被无数人诟病了，就写了一片文章，自作聪明地提出应该对模板参数有个类似接口声明一样的规格定义（现在C++0x 中的对应物是concept）。当初立即招致骂声一片。现在这一点已经毋庸置疑了，C++0x出世后我们就可以结束这些痛苦了。

但是，前面说的C++的那两个致命缺点，看来短期内很难克服。

编译时间，受制于文件包含这种古老的内存不够用的时代的无奈选择，就像人的阑尾，喉头，视网膜。

程序尺寸，这个缺陷在某些时候也非常致命，举个简单例子，std::sort 使用了多种排序策略，每个sort 的机器码都很大。同时，对每一种数据类型，每一种randiter每一种comparator，都会生成一个sort 的版本，这会造成非常大的代码膨胀。相比之下，C 的 qsort 就没有这种缺陷。如果我们对几十种数据，使用几十个comparator排序，std::sort 的代码尺寸比 qsort 要大几十倍。虽然它在inline方面获得了优势，但是cpucache的失效，甚至是memcache的失效，造成的性能损失要大得多。BS在TCPL中提到的消除代码膨胀的方法，在某些情况下的确有用，但是太繁琐，大约也只有库编写者会使用它。

Java现在也支持泛型，据说不存在代码膨胀问题，但它的泛型只是语法糖，对程序性能好像没有提升。

C++ 怎样平衡代码膨胀和代码性能？是否可以为 template 生成 runtime meta info，用来操纵泛型算法。或甚至使用这些meta info 来在运行时生成真正的机器码。这样甚至可以允许在运行时进行template组装，而不是完全在编译时？这又有些类似于现代虚拟机（如Java HotSpot 虚拟机）的动态优化。

扯太远了，休息下。

 – 共有 n 个内部结点，n 个外部结点
 – winner 只用于初始化时计算败者树，算完后即丢弃
 – winner/loser 的第 0 个单元都不是内部结点，不属于树中的一员
 – winner 的第 0 个单元未用
 – m_tree 的第 0 个单元用于保存最终的赢者, 其它单元保存败者

 – 该初始化需要的 n-1 次比较，总的时间复杂度是 O(n)

 – 严蔚敏&吴伟民 的 LoserTree 初始化复杂度是 O(n*log(n))，并且还需要一个 min_key,
   但是他们的初始化不需要额外的 winner 数组

 – 并且，这个实现比 严蔚敏&吴伟民 的 LoserTree 初始化更强壮

其中引用的一些代码比较长，故未贴出

使用示例：

 

 

 

 

用C++写程序经常需要写一些很小的functor，最常见的例子就是 compare functor，排序的，查找的，自己每定义一个数据结构，就要定义一个 compare functor，甚至多个（对不同字段）。甚至，针对指针的，智能指针的……的compare，这件工作很繁琐，很容易使人厌倦。

举个例子，同一个数据结构有M个字段，这些字段有P种类型，还有有N种不同的访问方式（直接提取、通过指针、通过智能指针、甚至通过反序列化等等），要实现所有这些情况的查找/排序，就需要 M×N 个 compare functor 的定义！

从 boost::multi_index 中学到一点，将 KeyExtractor 和 Comparator 分离，这样，只需要写 P 个Comparator，M+N个KeyExtractor，一般情况下，甚至不需要写Comparator，因为字段类型大多是内建类型，Comparator是默认的。举个例子吧：

using namespace std;

using boost::shared_ptr;

//using boost::intrusive_ptr;

 

struct mydata

{

   int d1, d2, d3, d4, d5;

   string s1, s2, s3;

};

 

struct mydata_get_int

{

   int offset;

 

   mydata_get_int(int offset) : offset(offset) {}

 

   int operator()(const mydata& x) const

   {

      return *(int*)(offset + (unsigned char*)&x);

   }

   // 假定T 就是mydata* 或者智能指针

   template<class T>

   int operator()(const T& x) const

   {

      return *(int*)(offset + (unsigned char*)&(*x));

   }

};

struct mydata_get_str

{

   int offset;

 

   mydata_get_str(int offset) : offset(offset) {}

 

   const string& operator()(const mydata& x) const

   {

      return *(string*)(offset + (unsigned char*)&x);

   }

   // 假定T 就是mydata* 或者智能指针

   template<class T>

   const string& operator()(const T& x) const

   {

      return *(string*)(offset + (unsigned char*)&(*x));

   }

};

 

 

 

class ExtractCompare

{

   KeyExtractor m_extractor;

   KeyCompare   m_comp;

 

public:

   ExtractCompare(const KeyExtractor& ext = KeyExtractor(),

                const KeyCompare& comp = KeyCompare())

      : m_extractor(ext), m_comp(comp) {}

 

   template<class T1, class T2>

   bool operator()(const T1& t1, const T2& t2) const

   {

      return m_comp(m_extractor(t1), m_extractor(t2));

   }

};

原以为足够现代的编译器的优化能力很强，看来我是高估了。GCC 没测过，VC 2008 刚刚被证实了。

    pair<int,int> x(rand(), rand()), y(rand(), rand());

   for (int i = 0; i < 1000; ++i)

   {

      if (x < y)

         x.first += y.second, y.second -= x.second;

   }

 

// pair.< 的定义

template<class _Ty1, class _Ty2> inline

bool operator<(const pair<_Ty1, _Ty2>& _Left,

               const pair<_Ty1, _Ty2>& _Right)

{  // test if _Left < _Right for pairs

   return (_Left.first < _Right.first ||

      !(_Right.first < _Left.first) && _Left.second < _Right.second);

}

主要是看其中的 if (x < y) 会被优化成什么样子。我原估计的是会在 inline 展开之后，将函数的返回值直接映射到true/false分支，没想到让我大失所望：

 

; 93   :  {
; 94   :   if (x < y)

  003d2 8b 45 e4  mov  eax, DWORD PTR _x$[ebp]
  003d5 3b 45 ec  cmp  eax, DWORD PTR _y$[ebp]
  003d8 7c 1c   jl  SHORT $LN71@TestBoolOp
  003da 8b 4d ec  mov  ecx, DWORD PTR _y$[ebp]
  003dd 3b 4d e4  cmp  ecx, DWORD PTR _x$[ebp]
  003e0 7c 08   jl  SHORT $LN70@TestBoolOp
  003e2 8b 55 e8  mov  edx, DWORD PTR _x$[ebp+4]
  003e5 3b 55 f0  cmp  edx, DWORD PTR _y$[ebp+4]
  003e8 7c 0c   jl  SHORT $LN71@TestBoolOp
$LN70@TestBoolOp:
  003ea c7 85 40 ff ff
 ff 00 00 00 00  mov  DWORD PTR tv84[ebp], 0
  003f4 eb 0a   jmp  SHORT $LN68@TestBoolOp
$LN71@TestBoolOp:
  003f6 c7 85 40 ff ff
 ff 01 00 00 00  mov  DWORD PTR tv84[ebp], 1
$LN68@TestBoolOp:
  00400 0f b6 85 40 ff
 ff ff   movzx  eax, BYTE PTR tv84[ebp]
  00407 85 c0   test  eax, eax
  00409 74 12   je  SHORT $LN1@TestBoolOp

; 95   :    x.first += y.second, y.second -= x.second;

  0040b 8b 4d e4  mov  ecx, DWORD PTR _x$[ebp]
  0040e 03 4d f0  add  ecx, DWORD PTR _y$[ebp+4]
  00411 89 4d e4  mov  DWORD PTR _x$[ebp], ecx
  00414 8b 55 f0  mov  edx, DWORD PTR _y$[ebp+4]
  00417 2b 55 e8  sub  edx, DWORD PTR _x$[ebp+4]
  0041a 89 55 f0  mov  DWORD PTR _y$[ebp+4], edx
$LN1@TestBoolOp:

; 96   :  }

  0041d eb a1   jmp  SHORT $LN3@TestBoolOp
$LN2@TestBoolOp:

我原乐观地以为编译器的代码不会出现紫色背景的代码，而红色背景的跳转会直接到黄色处，绿色背景的跳转会跳过黄色。是我对编译器要求太高了吗？可是，这样functor在排序、查找等应用中是随处可见的，要浪费多少CPU 啊！真的是硬件水平高了，软件就可以随意挥霍了吗？

与其这样，类似 std::sort 这样的函数还不如不要 inline Compare Functor，直接使用 qsort 算了，还不用那么多的代码膨胀。感觉这样的代码膨胀带来的效益太少了，好像某权威测试对 std::sort 和 qsort  的对简单数据的排序对比说明它仅比 qsort 快 20%～30%。可是在一个典型应用中它带来的代码膨胀恐怕 2000%～3000%都有吧。

现在用习惯了 C++ 的 Template，不用它就感觉不舒服。但是经常一个小规模的 C++ 程序编译出的执行程序就有2～3M，这还是优化过，去掉所有调试信息的。真不知道如何办好！