酱坛子

专注C++技术 在这里写下自己的学习心得 感悟 和大家讨论 共同进步(欢迎批评!!!)

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  65 Posts :: 16 Stories :: 236 Comments :: 0 Trackbacks

公告

王一伟 湖南商学院毕业 电子信息工程专业

常用链接

留言簿(19)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 352906
  • 排名 - 53

最新随笔

最新评论

阅读排行榜

评论排行榜

被误解的C++——优化variant实现

 
所属分类:C/C++ C++ 语言
-----------------------------------------

优化variant实现
上一次,我大概制作了一个variant类型,并设法赋予这个类型同C++内置类型几乎一样的行为。但是,具体实现起来,倒是有点望而生畏。想想看,如果我的variant需要包容5种类型,那么单单一个操作符,就需要5×5+1=26个操作符重载(那单独一个是variant类型操作数的重载)。所有二元操作符都是如此。
通过蛮力来实现variant,尽管可能,但着实愚蠢。我们必须寻找更简单有效的实现途径,避免为了一个“屁眼大的”variant(请原谅我说粗话)写上几万行代码,而且这些代码就像一窝小猪仔那样相像。好在C++为我们提供了充足的现代武器,使我们拥有足够的火力摆平这些问题。
让我们先从操作数都是variant的二元操作符入手:
variant  operator+( const variant& v1, const variant& v2) {…}

简单起见,先考察operator+的实现,然后扩展到其他操作符。
由于操作数是variant类型,那么它们可能代表不同的类型。我们必须知道操作数的实际类型,才能对其实施相应的+操作。最传统的办法就是使用switch:
variant operator+(const variant& v1, const variant& v2) {
switch(v1.get_type_code())
{
case vt_double:
switch(v2.get_type_code())
{
case vt_double:
…;
break;

}
case vt_int:
switch(v2.get_type_code())
{
case vt_double:
…;
break;

}

}
}
好家伙,又是一个组合爆炸。一步步来,我们先来处理这堆讨人嫌的switch…case…。一般而言,对于一个函数(操作符)内的的大量分派操作,可以使用包含函数指针的数组或者容器替代。如果标记值(这里的vt_...)是连续的,可以直接使用数组;如果标记值不连续,可以使用关联容器。这里vt_...是连续的,所以用数组比较方便:
typedef variant (*add_op_t)(const variant& v1, const variant& v2);
add_op_t tbl_type_ops[3][3];//函数指针表,假设variant对应三种类型
variant add_op_double_double(const variant& v1, const variant& v2){…}
variant add_op_double_int(const variant& v1, const variant& v2){…}

variant add_op_int_double(const variant& v1, const variant& v2){…}

tbl_type_ops [vt_double][vt_double]=add_op_double_double;
tbl_type_ops [vt_double][vt_int]=add_op_double_int;

variant operator+(const variant& v1, const variant& v2) {
returntbl_type_ops [v1.get_type_code()][v2.get_type_code](v1, v2);
}
operator+的代码是简单了,但是它的代码实际上转嫁到每个专用操作函数add_op_...上去了。并没有简化多少。下一步,我们来处理这些add_op_...:
template<typename VT1, typename VT2>
variant add_op(const variant& v1, const variant&v2) {
throwexception(string(“cannot add type ”)+typeid(VT1).typename()
+”to”+typeid(VT2).typename());
}//主函数模板,对应不兼容类型的操作。抛出异常。
template<>
variant<double, double> add_op(const variant& v1, const variant&v2) {
returnvariant(v1.dbval+v2.dbval);
}//针对double+double的操作

tbl_type_ops [vt_double][vt_double]=add_op<double, double>;
tbl_type_ops [vt_double][vt_int]=add_op<double,int>;

利用函数模板,及其特化,消化掉一部分的冗余代码。利用主函数模板实现所有不能互操作的类型操作,而可操作的类型则使用特化的模板实现。当然,冗余代码还是存在,这部分我们一会儿再处理。先来看看tbl_type_ops的填充。这部分代码也存在组合爆炸。为消除这个问题,我请出了模板元编程(TMP)。当然,我没有那么好的本事去直接倒腾TMP,我“借用”了boost::mpl::vector来实现这步优化:
//使用mpl::vector存放variant包容的类型
typedef boost::mpl::vector<double, int, string>op_types;
const int n_types=boost::mpl::size<op_types>::value;
//操作函数指针表
typedef variant (*add_op_t)(const variant& v1, const variant& v2);
add_op_t tbl_type_ops[n_types][n_types];
//填充函数指针表单个元素
template<int m, int n>
inline void set_tbl_type() {
typedefmpl::deref<mpl::advance<mpl::begin<op_types>::type, 
mpl::int_<m> >::type>::typetype_1;
typedefmpl::deref<mpl::advance<mpl::begin<op_types>::type, 
mpl::int_<n> >::type>::typetype_2;

tbl_type_ops [m][n]=add_op<type_1, type_2>;
}
//填充函数指针表单元的函数对象类
template<int m, int n>
struct fill_tbl_types_n
{
void operator()() {
set_tbl_type<m-1, n-1>();//填充函数指针单元
fill_tbl_types_n<m, n-1>()();//递归
}
};
template<int m>
struct fill_tbl_types_n<m, 0>//特化,递归结束
{
void operator()() {}
};
//填充函数指针表行的函数对象类
template<int m, int n>
struct fill_tbl_types_m
{
void operator()() {
fill_tbl_types_n<m, n>()();//创建并调用fill_tbl_types_n函数对象
fill_tbl_types_m<m-1, n>()();//递归
}
};
template<int n>
struct fill_tbl_types_m<0, n>//特化,递归结束
{
void operator()() {}
};
void fill_tbl_op() {
fill_tbl_types_m<n_types, n_types>()();
}
这里运用函数对象类模板的特化,构造了函数指针表的填充自动函数。在需要时,只需调用fill_tbl_op()函数即可。该函数中创建fill_tbl_types_m<n_types, n_types>函数对象,然后调用。这个函数对象的operator()首先创建并调用fill_tbl_types_n<m, n>函数对象。后者先调用set_tbl_type<m-1, n-1>模板函数,执行填充tbl_type_op数组的[m-1, n-1]单元格。然后递归调用fill_tbl_types_n<m, n-1>函数对象。直到n-1==0,编译器便会选择特化版本的fill_tbl_types_n<m, 0>函数对象。该特化的operator()操作符重载是空的,因此递归结束。这样完成一行的填充。然后,fill_tbl_types_m<m, n>则递归调用fill_tbl_types_m<m-1, n>函数对象,填充下一行。直到调用fill_tbl_types_m<0, n>特化版本,结束递归。
现在需要仔细看一下set_tbl_type<>函数模板。该模板上来就是两个typedef。这两个typedef创建了两个类型别名,分别用m和n做索引,从boost::mpl::vector<double, int, string>中取出相应的类型:
typedefmpl::deref<mpl::advance<mpl::begin<op_types>::type, 
mpl::int_<m> >::type>::typetype_1;

头晕是吧。我的头还有点晕呢。这就是模板元编程,不停地鼓捣类型。具体的操作可以参考boost文档或《The Template Meta-programming》一书,我这里就不多说了,反正就是从一个存放类型的vector中取出所需的类型。
这样获得的两个类型用来实例化add_op<>()模板函数,并且填充到tbl_type_ops[m][n]元素中。
这样,利用TMP和GP两种强大的机制,消除了tbl_type_ops填充的组合爆炸问题。如果我们需要向variant中加入新的类型,那么只需在mpl::vector<double, int, string>中直接加入类型即可:
typedef mpl::vector<double, int, string, bool, datetime>op_types;
OK,下面回过头,来处理add_op<>中存在的组合爆炸。对于每一对可以直接或间接相加的类型,都需要做一个add_op<>的特化版本。这当然不够好。我们可以进一步抽象add_op,然后加以优化。我把整个add_op<>模板改写成如下代码:
template<typename VT1, typename VT2>
variant add_op(const variant& v1, const variant& v2) {
typedeftype_ret<VT1, VT2>::typeRetT;
returnvariant(v1.operator RetT()+v2.operator RetT());
}
这里,我首先利用type_ret模板(模板元函数)获得两个操作数相加后应有的返回类型。这个模板一会说明。然后,调用variant上的类型转换操作符,将两个操作数转换成返回类型。最后相加,并创建返回variant对象。代码非常简单,没法再简单了。
再来看看type_ret<>:
template<typename T1, typename T2>
struct type_ret
{
typedefT1type;
};
template<>
struct type_ret<int, double>
{
typedefdoubletype;
};
template<>
struct type_ret<string, double>
{
typedefdoubletype;
};
…//其他类型对的返回类型
type_ret<>是典型的模板元函数,没有任何实际代码,只有编译时计算的typedef。主模板将第一个类型参数typedef出一个别名。其后的模板特化对于一些特殊的情况做出定义,如int和double相加返回第二个操作数类型double(即所谓的类型提升)。
我们现在已经优化了variant+varint的代码。现在来看看如何优化variant类型和其他类型的加法:
template<typename T>
variant operator+(const variant& v1, const T& v2) {
returnv1+variant(v2);
}
template<typename T>
variant operator+(const T& v1, const variant& v2) {
returnvariant(v1)+v2;
}
这非常简单,直接利用了variant+variant,将其它类型的操作数转换成variant类型,然后相加。


----------------------------------------------------------------------

好,加法完成了。但还有其他操作符。每个操作符都做那么一个函数指针表,也不见得高明到哪里去。现在需要整合优化这些操作符。这里,我想到了两种方法:一种是将函数指针表和填充操作整个地封装在一个模板中,模板参数采用int op形式。每一种操作符对应一个整数(或枚举值),并利用某种手段(如singleton)唯一生成一组全局的函数表,以此处理每一种操作。另一种方法是为函数指针表加一个维度(二维扩展到三维),新的维度对应不同的操作符。前一种方法灵活性强些,而且有利于性能优化;而后一种方法实现简单。这里我使用后一种方法:
enum
{
vt_op_add=0,
vt_op_add_assign=1,
vt_op_equal=2,
vt_op_not_equal=3

};
const int vt_op_num=10;

template<typename T, int op>
struct var_op;

template<typename T>
struct var_op<T, vt_op_add>
{
T operator()(const T& v1, const T& v2) {
returnv1+v1;
}
}

template<typename T>
struct var_op<T, vt_op_equal>
{
bool operator()(const T& v1, const T& v2) {
returnv1==v1;
}
}

template<typename VT1, typename VT2, int op>
variant variant_op(const variant& v1, const variant& v2) {
typedeftype_ret<VT1, VT2>::typeRetT;
returnvariant(var_op<RetT,op>()(v1.operator RetT()+v2.operator RetT()));
}
我使用了一个函数对象模板var_op<>抽象各种算法(二元)。针对每一种运算符特化。抽象的variant_op函数模板实例化var_op<>,然后调用。获得相应的操作。
观察variant_op的模板参数,会发现已经包含了一个操作的基本要素。(眼下这个形式正好符合逆波兰表达式)。
接下来,只需将函数指针数组,及其填充算法加以扩展,便可大功告成:
add_op_t tbl_type_ops[n_types][n_types][vt_op_num];
//填充函数指针表单个元素
template<int m, int n, int op>
inline void set_tbl_type() {
typedefmpl::deref<mpl::advance<mpl::begin<op_types>::type, 
mpl::int_<m> >::type>::typetype_1;
typedefmpl::deref<mpl::advance<mpl::begin<op_types>::type, 
mpl::int_<n> >::type>::typetype_2;

tbl_type_ops [m][n][op]=add_op<type_1, type_2, op>;
}

template<int m, int n, int op>
struct fill_tbl_types_op
{
void operator()() {
set_tbl_type<m-1, n-1, op-1>();
fill_tbl_types_op<m, n, op-1>()();//递归
}
};
template<int m, int n>
struct fill_tbl_types_op<m, n, 0>//特化,递归结束
{
void operator()(){}
}

template<int m, int n, int op>
struct fill_tbl_types_n
{
void operator()() {
fill_tbl_types_op<m, n, op>();
fill_tbl_types_n<m, n-1, op>()();//递归
}
};
template<int m, int op>
struct fill_tbl_types_n<m, 0, op>//特化,递归结束
{
void operator()() {}
};

template<int m, int n, int op>
struct fill_tbl_types_m
{
void operator()() {
fill_tbl_types_n<m, n, op>()();
fill_tbl_types_m<m-1, n, op>()();//递归
}
};
template<int n, int op>
struct fill_tbl_types_m<0, n, op>//特化,递归结束
{
void operator()() {}
};

void fill_tbl_op() {
fill_tbl_types_m<n_types, n_types, vt_op_num>()();
}

template<typename RetT, int op>
struct var_oper
{
RetT operator()(const variant& v1, const variant& v2) {
returntbl_type_ops [v1.get_type_code()][v2.get_type_code]
[op](v1, v2).operator RetT();
}
template<int op>
struct var_oper<variant, op>
{
variant operator()(const variant& v1, const variant& v2) {
returntbl_type_ops [v1.get_type_code()][v2.get_type_code]
[op](v1, v2);
}
于是操作符的实现,成了以下形式:
variant operator+(const variant& v1, const variant& v2) {
returnvar_oper<variant, vt_op_add>(v1, v2);
}
bool operator==(const variant& v1, const variant& v2) {
returnvar_oper<bool, vt_op_equal>(v1, v2);
}

如果还觉得复杂,那么可以进一步使用宏做一些包装。
好了,variant的优化基本上完成了。当然还会有一些方面值得我们去进一步地优化,比如可以利用boost的type traits和标准库的limit优化type_ret模板的实现和类型转换操作的实现等等。这里不再赘述。
需要说明的是,整个优化仅仅针对代码,并未考虑性能问题。在优化的过程中,某些手法的使用实际上降低的性能。比如函数指针表存在间接调用,不如直接使用inline函数来的高效。而且,函数指针表要求所有指向的函数必须以相同的类型返回。为了兼容+、-等操作,我使用了值返回。但对于+=等操作符完全可以利用引用返回,以提升性能。如果要解决这种问题,需要用前面提到的模板封装函数指针表的方案,为每一个操作符创建一个函数指针表加以解决。
另一个性能问题主要是在variant与其它类型的操作中,其它类型转换成variant类型然后再计算。比起直接使用目标类型计算慢不少。这个问题也可以利用GP和TMP消除,但代码会复杂不少。
理论上,利用inline和编译器优化,可以消除大部分性能问题。但不是所有的,函数指针表的间接调用,是无论如何也优化不掉的。
此外,我在实现函数指针表的构造算法时,没有使用函数模板,而是使用了函数对象模板(重载operator()的模板)。这是因为函数模板目前不能局部特化,而这里是必须的。另一方面,由于使用了递归,函数模板无法做到inline(),而使用函数对象模板则不会有此限制。表达式fill_tbl_types_m()();最终(优化)编译后的结果会是这样(伪码):
tbl_type_ops [2][2][0]=add_op<string, string, 0>;
tbl_type_ops [2][1][0]=add_op<string, int, 0>;

tbl_type_ops [1][2][0]=add_op<int, string, 0>;

递归和函数对象的调用没有了,完全inline化了。inline函数有时却无法做到这一点。而fill_tbl_types_op等模板实际上起到了代码生成器的作用。这也是GP的一个鲜为人知的功能。如果你有一大堆代码需要编写,而这些代码有很强的规律性和重复性,那么请优先考虑使用模板来为你生成代码,又快又好。
该总结了。如果审视一些代码,会发现只要存在重复和规律性,我们总能利用一些技术和方法加以优化,减少代码量,简化代码结构,减少潜在错误,最终提高开发效率。这里,我使用了C++的泛型编程和模板元编程技术,大幅优化了variant类型中的大量冗余代码。并且为variant类型构建了一个灵活,而又易于扩充的结构。此类技术有很广的应用,不仅仅局限在variant这种底层构件中。相关的一个应用就是构造抽象类工厂,在《Modren C++ Design》一书中,有很完整的案例。
此外,这类技术对于调和运行时多态(OOP)和编译时多态(GP)的矛盾有很大的作用。variant只有在运行时方能确定其具体的类型,而C++的模板只能提供编译时的GP。我利用函数指针数组(当然在更复杂的应用中,可以利用OOP的动多态机制),实现运行时分派操作。而利用GP和TMP大幅简化函数指针数组、操作实现函数,以及操作符的构造。这些技术和方法可以在大多数需要运行时多态,但又存在大量重复或雷同代码的地方得以应用。

posted on 2007-10-09 22:35 @王一伟 阅读(3187) 评论(0)  编辑 收藏 引用

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