天秤座的唐风

总会有一个人需要你的分享~!- 唐风 -

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  13 随笔 :: 0 文章 :: 69 评论 :: 0 Trackbacks

与临时对象的斗争(下)

作者:唐风

原载:www.cnblos.com/liyiwen

上篇里,我们看到了 (N)RVO 和右值引用,下面我们来看看表达式模板。

Expression Template(表达式模板,ET)

如果有“系统地”学习过 C++ 的模板编程,那么你应该已经知道 Expression Template 这个“东西”。在模板圣经《C++ templates》的第 18 章专门用了一整章来讲这个技巧,(是的,我认为它是一种技巧)。足以见得它比较复杂,也很重要。

说起 Expression Template 产生,“临时对象”也是“功臣”之一啊。还是来用例子来说明(你能很容易找到这样类似的例子,呵,我就是参照着别人写的):

class MyVec
{
public:
    MyVec(){
        p = new int[SIZE];
    }
    MyVec(MyVec const& a_left) {
        p = new int[SIZE];
        memcpy(p, a_left.p, SIZE * sizeof(int));
    }
    ~MyVec(){delete [] p;}
    MyVec& operator=(MyVec const& a_left) {
        if (this != &a_left) {
            delete [] p;
            p = new int[SIZE];
            memcpy(p, a_left.p, SIZE * sizeof(int));
        }
        return *this;
    }
    int& operator [](size_t a_idx) { 
        return p[a_idx];
    }
    int operator [](size_t a_idx)const { 
        return p[a_idx];
    }
    MyVec const operator + (MyVec const& a_left) const {
        MyVec temp(*this);
        temp += a_left;
        return temp;
    }
    MyVec& operator += (MyVec const& a_left) { 
        for (size_t i = 0; i < SIZE; ++i) {
            p[i] += a_left.p[i];
        }
        return *this;
    }
private:
    static int const SIZE = 100;
    int* p;
};

int main(int argc, char* argv[])
{
    MyVec a, b, c;
    MyVec d = a + b + c;
    return 0;
}

看,我们写下这么小段代码:

MyVec d = a + b + c;

这是很常用的数学运算吧,而且代码很直观。但这个表达式有一个问题,就是产生了“不必要”的临时对象。因为 a + b 的结果会成为一个存在一个临时对象上 temp 上,然后这个 temp 再加上 c ,最后把结果传给 d 进行初始化。如果这些向量很长,或是表达式再加几节,可以想像这些 temp 会多让人不爽。

而且,如果我们写成这样:

MyVec d = a;
d += b;
d += c;

就可以避免产生多余的临时对象。但这样写,如果是不了解“行情”的人看了MyVec d = a + b + c;之后再看这段,是不是会觉得写这代码的人欠K?

好吧,你会问,上面不是说右值引用可以解决这样问题?是的,但在没有右值引用的“黑暗日子”里,我们就不用过活了?当然要,小学开始数学老师就教我们要一题多解吧,换个思路也有办法,这个办法就是ET。

怎么做的呢?a + b + c 会产生临时变量是因为 C++ 是即时求值的,在看到 a + b,就先算出一个 temp 的Vector对象,然后再向下算。如果能进行延迟求值,看完整个表达式再来计算,那么就可以避免这个temp的产生。

怎么做?

原来的做法中,operator + 直接进行了计算,既然我们不想它“过早”的计算,那么我们就在重新重载一个operator + 运算符,在这个运算中不进行真正的运算,只是生成一个对象,在这个对象中把加法运算符两边的操作数保留下来~然后让它参与到下一步的计算中去。(好吧,这个对象也是临时的,但它的代价非常非常小,我们先不理会它)。于是我们写下面的代码:

class MyVec;

template <typename L>
class ExpPlus {
    L const & lvec;
    MyVec const & rvec;
public:
    ExpPlus(L const& a_l, MyVec const& a_r):
      lvec(a_l), rvec(a_r)
      { }
      int operator [] (size_t a_idx) const;
};

// Point 1
template <typename L>
ExpPlus<L> operator + (L const& a_l, MyVec const & a_r) {
    return ExpPlus<L>(a_l, a_r);
}

class MyVec
{
public:
    MyVec(){
        p = new int[SIZE];
    }

    MyVec(MyVec const& a_r) {
        p = new int[SIZE];
        memcpy(p, a_r.p, SIZE * sizeof(int));
    }

    template <typename Exp>
    MyVec(Exp const& a_r) {
        p = new int[SIZE];
        for (size_t i = 0; i < SIZE; ++i) {
            p[i] += a_r[i];
        }
    }

    ~MyVec(){delete [] p;}

    MyVec& operator = (MyVec const& a_r) {
        if (this != &a_r) {
            delete [] p;
            p = new int[SIZE];
            memcpy(p, a_r.p, SIZE * sizeof(int));
        }
        return *this;
    }

    template <typename Exp>
    MyVec& operator = (Exp const & a_r) {
        delete [] p;
        p = new int[SIZE];
        for (size_t i = 0; i < SIZE; ++i) {
            p[i] += a_r[i];
        }
        return *this;
    }

    int& operator [](size_t a_idx) { 
        return p[a_idx];
    }

    int operator [](size_t a_idx)const { 
        return p[a_idx];
    }
private:
    static int const SIZE = 100;
    int* p;
};

template <typename L>
int ExpPlus<L>::operator [] (size_t a_idx) const {
    return lvec[a_idx] + rvec[a_idx];
}

int main(int argc, char* argv[])
{
    MyVec a, b, c;
    MyVec d = a + b + c;
    return 0;
}

比起之前的代码来说,这段代码有几个重要的修改:首先,我们增加了一个模板类 ExpPlus,用它来代表加法计算的“表达式”,但在进行加法时,它本身并不进行真正的计算。对这个类,定义了下标运算符,这个运算符中才进行了真正的加法计算。然后,对于原来的 MyVec,我们重载它的赋值运算符,让它在赋值的时候通过ExpPlus的下标运算符来获得计算结果(也就是,在赋值操作时才真正的进行了计算!)。

上面这段话,对于不了解ET的人来说,也许一时间还不容易明白,我们一步一步来:

在 d = a + b + c 这个式子中,首先遇到 a + b,这时,模板函数 operator + 会被调用(代码中注释了“Point 1 ”),这时只是生成一个临时的ExpPlus<MyVec>对象(我们叫它 t1 吧),不做计算,只是保留计算的左右操作数(也就是a和b),接着,t1 + c ,再次调用同样的 operator + ,而且也只是生成一个对象(我们叫它 t2 吧),这个对象的类型是 ExpPlus<ExpPlus<MyVec>>,同样,t2 在这里只是保留了两边的操作数(也就是 t1 和 c)。直到整个表达式“做完”,没有任何东西进行了计算,所做的事情实际上只是用 ExpPlus 这个模板类把计算式的信息记录下来了(当然,这些信息就是参与计算的操作数)。

最后,当进行 d = t2 的时候,MyVec 的赋值运算符被调用(用 t2 作参数)。注意,这个调用中的语句 p[i] = t2[i],其中 t2[i] 通过重载的下标运算符,展开成 t1[i] + c[i],同理 t1[i] 又再次展开,成为 a[i]+b[i],最终,p[i] = t2[i] 就变成了:p[i] = a[i] + b[i] + c[i])(当然,里面参杂了内联的效果,这些函数都是非常容易被内联的)。就像变“魔术”一样,我们通过ExpPlus完成了“延迟计算”,并避免了大型的 MyVec 临时对象的产生。

这基本上就是 ET 的“原理”了吧。我们来“专门化”一下 ET 的好处:

  • To create a domain-specific embedded language (DSEL) in C++
  • To support lazy evaluation of C++ expressions (e.g., mathematical expressions), which can be executed much later in the program from the point of their definition.
  • To pass an expression — not the result of the expression — as a parameter to a function.

这样,用 ET 就能兼顾到“直观”和“效率”了。

ET 中 C++ 中的类库里已经有非常多的应用了(包括 boost 中的多个子库,以及 Blitz++ 等高性能数学库)

总结

(N)RVO 是编译器为我们做的优化手段,在能进行优化的情况下,NRVO 的表现是非常好的,因为它才真正的避免了临时对象的产生(rvalue reference 和 expression template 中都可能还存在一些小型临时对象),但 (N)RVO 有很多的限制条件。右值引用(rvalue reference )和 move 语意弥补了 (N)RVO 的不足之处,使得临时对象的开销最小化成为可能,但这也是有局限的,比如,嗯,如果一个类本身不动态地拥有资源……,那 move 就没有意义了。Expression Template 保持了表达式直观和效率两者,很强大,但很显然它太复杂,主要是作为类库的设计者的武器。另外,它也可能使得使用者要理解一些“新”东西,比如,如果我想存储表达式的中间值,那么 <ExpPlus<ExpPlus<...<MyVec>...> 一定会让我很头大(不过有了 C++0x 的 auto 就好多了,呵呵)。

 

全文完!

 

 

posted on 2009-12-03 23:45 唐风 阅读(1708) 评论(14)  编辑 收藏 引用 所属分类: 语言技术

评论

# re: 与临时对象的斗争(下) 2009-12-04 00:22 OwnWaterloo
哦…… 原来这种技术叫expression template……

其实我心里一直这么叫它的:operation proxy……
  回复  更多评论
  

# re: 与临时对象的斗争(下) 2009-12-04 12:35 陈梓瀚(vczh)
不能解决问题嘛,假如我
MyVec a,b,c,d;
d=a+(b+c);
结果还是产生了跟以前一样多的临时对象(好像少了一个?但还是很多,如果列表够长)

这么设计ExpPlus其实是错误的。  回复  更多评论
  

# re: 与临时对象的斗争(下) 2009-12-04 12:36 陈梓瀚(vczh)
@陈梓瀚(vczh)
这个错误也造成了你需要ExpPlus<ExpPlus<...<MyVec>...>>这种囧类型了。你有没有想过让ExpPlus<I>+ExpPlus<I>==ExpPlus<I>?  回复  更多评论
  

# re: 与临时对象的斗争(下) 2009-12-04 18:26 YESHG!
俺来支持下。
二元操作符相当于一个函数,函数返回需要生成临时对象,如果临时对象过大将产生效率问题。ET用可以忽略不计的临时对象代替大的临时对象,将多个二元操作封到了一个函数中,减少了许多过大的临时对象的产生。
假如MyVec的构造函数中不分配那么多空间的话,其实这个开销还好,呵呵。对象过大的话,一般使用指针去更改对象内具体的成员了,而不是整个对象作为参数传过来传过去,当然,这样可能没后者直观……  回复  更多评论
  

# re: 与临时对象的斗争(下) 2009-12-04 18:35 YESHG!
虽然没有产生很多临时的MyVec,但是产生了很多临时的int,函数调用的次数也多了几次,这里就是用int换MyVec的做法。
俺发现俺还是不喜欢用模板啊,看了就晕乎。  回复  更多评论
  

# re: 与临时对象的斗争(下) 2009-12-04 18:41 唐风
@陈梓瀚(vczh)
嗯嗯,好敏锐啊,你说得很对。
d=a+(b+c);
这种在这段程序里是会产生编译错误的……

这个模板类确实非常的不完善,对于一个“可用”的ExpXXX的话,应该要是左右操作数都需要泛化的。为了进一步的重用,可以再泛化操作类型(加减乘)。

这篇文章里我想把重点放在“它可以消除临对象上”,为了能更“简单”地说明ET,所以写的例子很简陋,不过我想大概的做法已经点到了。

完善的做法比较复杂,所以我认为这个库设计都用的武器,写应用层逻辑时也许不太会用到?(调试、维护都不容易啊……)

下面有一篇文章,从头开始一点一点地完善这个ExpXXX,讲解得非常细~,每一个改善是为了什么!(不过是日文的,嘿,YESHG,为你准备的!中文英文的应该也有,不过我没搜到这么细致的,呵呵,不过对《C++templates》里的例子应该也够看了。)
http://homepage1.nifty.com/herumi/prog/prog81.html#MOTIVATION

PS:
至于那个囧类型,我还没看到有什么好的做法。因为要让左右操作数接受不同的表达式(a,a+b,a+b*c等等等等)才可用,所以操作数的“类型”不能固定,ExpPlus<I>+ExpPlus<I>==ExpPlus<I>,感觉行不通。你有什么好做法呢?

  回复  更多评论
  

# re: 与临时对象的斗争(下) 2009-12-04 18:49 唐风
@YESHG!
谢谢老大支持!!

配合内联 RVO,很多情况下这些临时小对象也可以消失,你看看我上面回复中给的链接,MS 有说明……

至于不习惯模板,嘿嘿,吐啊吐啊就习惯了。:)

  回复  更多评论
  

# re: 与临时对象的斗争(下) 2009-12-04 18:51 唐风
@OwnWaterloo

operation proxy……

好形象啊,哈哈
你上篇的回复里就说到了这个呢,不过我是事后才认识到……:P

  回复  更多评论
  

# re: 与临时对象的斗争(下) 2009-12-07 11:36 Wang Feng
ans = a+b+c+d+e+f+....;
如果可以并行的话,这样很有优势
ans = ((a+b)+(c+d))+((e+f)+(g+h));
你这个+=虽然省去了一些临时对象,不过也只好一个一个乖乖地+=了,单个cpu的时候没有事情,多个cpu的时候,大好时间都浪费了。  回复  更多评论
  

# re: 与临时对象的斗争(下) 2009-12-07 19:24 唐风
@Wang Feng
确实如你所言。谢谢你的回复。

说实话,“并行计算”这种高级货,我还真没玩过,嘿嘿。

嗯嗯,真心求教:
这方面有没有比较好的已经成熟的做法(库?)?能不能介绍一下?如果一个表达式比较复杂(比如有加减乘、有括号之类)有什么算法能正确地最优地根据可以并行的“行程”数来分配计算子过程?各子过程的之间的“通信”是怎么做的呢?会像一般“多线程”中的锁机制那样吗(当然,我对锁这东西的理解也限于“理论”范畴内,呵呵)?

PS:
刚才回访了你的 blog,里面大多都是算法方面的东西啊,呵呵。向你学习 :D




  回复  更多评论
  

# re: 与临时对象的斗争(下) 2009-12-08 16:50 陈梓瀚(vczh)
竟然被你发现我的百度宅博  回复  更多评论
  

# re: 与临时对象的斗争(下) 2009-12-08 18:15 唐风
@陈梓瀚(vczh)
好吧,我只能说,是你自己在 cppblog 的链接中列出来的。哈哈哈哈 :P
阁下爱好很广嘛,编译原理狂人(别人这么叫你的) + 漫迷 ……

嗯嗯,凡有回复必回访是我的原则,哈哈,也是想通这这种途径了解对方,多交些朋友



  回复  更多评论
  

# re: 与临时对象的斗争(下) 2013-11-17 00:09 ligand
最后,当进行 d = t2 的时候,MyVec 的赋值运算符被调用(用 t2 作参数)。
======================
这句话是说的。这里调用的不是赋值运算符,而是拷贝构造函数。  回复  更多评论
  

# re: 与临时对象的斗争(下) 2013-11-17 00:12 ligand
表达式模板,看起来很美:通过保存对操作数(operand)的引用,避免了构造庞大的临时对象(如涉及大量的资源、动态内存的获取)。 的确效率提高了。  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理