Expression Template

如果在 C++ 里面评选称得上是“魔法”的技术，Expression Template (ET，酷吧？) 当之无愧要成为其中一员。

如果要求两个数组的内积，该怎么做？

int a[4] = {1,100,0,-1};
int b[4] = {2,2,2,2};

手写循环就不说了，STL 算法是这样：

inner_product(a, a + 4, b, 0);

不错，但是有个问题。STL 算法本质上还是个循环，在大规模的运算中，循环带来的效率损失有点过高了，我们希望能有一个表达式，它的效率能跟下面这个一样高，但是又具有通用性，让我们只需要像 STL 算法那样写出来就可以运算。

a[0]*b[0] + a[1]*b[1] + a[2]*b[2] + a[3]*b[3]

论及效率，上面这个表达式大概是无人能出其右，但是它实在太不通用了，如果能这样该多好：

inner_product<4>(a, b)

怎样兼顾上面两种方法的效率和表达能力呢？ET 来帮忙了。

如果希望计算能尽量在编译期间完成，该怎么办？有了 TM (Template Metaprogramming) 的基础，我们知道毫无疑问要玩递归

template <int dim, class T>
struct inner_product
{
T operator()(T* a, T* b)
{
return inner_product<dim - 1, T>()(a + 1, b + 1) +
inner_product<1, T>()(a, b);
}
};

template <class T>
struct inner_product<1, T>
{
T operator()(T* a, T* b)
{ return (*a) * (*b); }
};

现在我们可以这么干了：

inner_product<4, int>()(a, b);

还不错吧？已经差不多了，如果加上一个 helper function， 目标就完全达到了：

template <int dim, class T>
T dot_product(T a[dim], T b[dim])
{
return inner_product<dim, T>()(a, b);
}

//...

dot_product<4>(a, b);

那么它跟普通的 STL 算法有什么区别呢？效率，当然是效率。在编译器看到

inner_product<dim - 1, T>()(a + 1, b + 1) + inner_product<1, T>()(a, b);

的时候，它会发现加号的后面一半可以直接写成 (*a) * (*b) ，而前面一半则需要实例化另外一个模板，也就是说：

inner_product<dim - 1, T>()(a + 1, b + 1) ==>
inner_product<dim - 2, T>()(a + 1 + 1, b + 1 + 1) + (*(a + 1)) * (*(b + 1))

这个过程毫无疑问会递归下去，直到所有的模板都能直接实例化为止，那个时候，表达式就变成了

(*(a + 3)) * (*(b + 3)) + (*(a + 2)) * (*(b + 2)) + (*(a + 1)) * (*(b + 1)) + (*a) * (*b)

而在运行期计算的，实际上就是这个。