所屬分類(lèi)：C/C++ C++ 語(yǔ)言
-----------------------------------------

優(yōu)化variant實(shí)現(xiàn)
上一次，我大概制作了一個(gè)variant類(lèi)型，并設(shè)法賦予這個(gè)類(lèi)型同C++內(nèi)置類(lèi)型幾乎一樣的行為。但是，具體實(shí)現(xiàn)起來(lái)，倒是有點(diǎn)望而生畏。想想看，如果我的variant需要包容5種類(lèi)型，那么單單一個(gè)操作符，就需要5×5+1=26個(gè)操作符重載（那單獨(dú)一個(gè)是variant類(lèi)型操作數(shù)的重載）。所有二元操作符都是如此。
通過(guò)蠻力來(lái)實(shí)現(xiàn)variant，盡管可能，但著實(shí)愚蠢。我們必須尋找更簡(jiǎn)單有效的實(shí)現(xiàn)途徑，避免為了一個(gè)“屁眼大的”variant（請(qǐng)?jiān)徫艺f(shuō)粗話(huà)）寫(xiě)上幾萬(wàn)行代碼，而且這些代碼就像一窩小豬仔那樣相像。好在C++為我們提供了充足的現(xiàn)代武器，使我們擁有足夠的火力擺平這些問(wèn)題。
讓我們先從操作數(shù)都是variant的二元操作符入手：
variant  operator+( const variant& v1, const variant& v2) {…}
…
簡(jiǎn)單起見(jiàn)，先考察operator+的實(shí)現(xiàn)，然后擴(kuò)展到其他操作符。
由于操作數(shù)是variant類(lèi)型，那么它們可能代表不同的類(lèi)型。我們必須知道操作數(shù)的實(shí)際類(lèi)型，才能對(duì)其實(shí)施相應(yīng)的+操作。最傳統(tǒng)的辦法就是使用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;
…
}
…
}
}
好家伙，又是一個(gè)組合爆炸。一步步來(lái)，我們先來(lái)處理這堆討人嫌的switch…case…。一般而言，對(duì)于一個(gè)函數(shù)（操作符）內(nèi)的的大量分派操作，可以使用包含函數(shù)指針的數(shù)組或者容器替代。如果標(biāo)記值（這里的vt_...）是連續(xù)的，可以直接使用數(shù)組；如果標(biāo)記值不連續(xù)，可以使用關(guān)聯(lián)容器。這里vt_...是連續(xù)的，所以用數(shù)組比較方便：
typedef variant (*add_op_t)(const variant& v1, const variant& v2);
add_op_t tbl_type_ops[3][3];//函數(shù)指針表，假設(shè)variant對(duì)應(yīng)三種類(lèi)型
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+的代碼是簡(jiǎn)單了，但是它的代碼實(shí)際上轉(zhuǎn)嫁到每個(gè)專(zhuān)用操作函數(shù)add_op_...上去了。并沒(méi)有簡(jiǎn)化多少。下一步，我們來(lái)處理這些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());
}//主函數(shù)模板，對(duì)應(yīng)不兼容類(lèi)型的操作。拋出異常。
template<>
variant<double, double> add_op(const variant& v1, const variant&v2) {
returnvariant(v1.dbval+v2.dbval);
}//針對(duì)double+double的操作
…
tbl_type_ops [vt_double][vt_double]=add_op<double, double>;
tbl_type_ops [vt_double][vt_int]=add_op<double,int>;
…
利用函數(shù)模板，及其特化，消化掉一部分的冗余代碼。利用主函數(shù)模板實(shí)現(xiàn)所有不能互操作的類(lèi)型操作，而可操作的類(lèi)型則使用特化的模板實(shí)現(xiàn)。當(dāng)然，冗余代碼還是存在，這部分我們一會(huì)兒再處理。先來(lái)看看tbl_type_ops的填充。這部分代碼也存在組合爆炸。為消除這個(gè)問(wèn)題，我請(qǐng)出了模板元編程（TMP）。當(dāng)然，我沒(méi)有那么好的本事去直接倒騰TMP，我“借用”了boost::mpl::vector來(lái)實(shí)現(xiàn)這步優(yōu)化：
//使用mpl::vector存放variant包容的類(lèi)型
typedef boost::mpl::vector<double, int, string>op_types;
const int n_types=boost::mpl::size<op_types>::value;
//操作函數(shù)指針表
typedef variant (*add_op_t)(const variant& v1, const variant& v2);
add_op_t tbl_type_ops[n_types][n_types];
//填充函數(shù)指針表單個(gè)元素
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>;
}
//填充函數(shù)指針表單元的函數(shù)對(duì)象類(lèi)
template<int m, int n>
struct fill_tbl_types_n
{
void operator()() {
set_tbl_type<m-1, n-1>();//填充函數(shù)指針單元
fill_tbl_types_n<m, n-1>()();//遞歸
}
};
template<int m>
struct fill_tbl_types_n<m, 0>//特化，遞歸結(jié)束
{
void operator()() {}
};
//填充函數(shù)指針表行的函數(shù)對(duì)象類(lèi)
template<int m, int n>
struct fill_tbl_types_m
{
void operator()() {
fill_tbl_types_n<m, n>()();//創(chuàng)建并調(diào)用fill_tbl_types_n函數(shù)對(duì)象
fill_tbl_types_m<m-1, n>()();//遞歸
}
};
template<int n>
struct fill_tbl_types_m<0, n>//特化，遞歸結(jié)束
{
void operator()() {}
};
void fill_tbl_op() {
fill_tbl_types_m<n_types, n_types>()();
}
這里運(yùn)用函數(shù)對(duì)象類(lèi)模板的特化，構(gòu)造了函數(shù)指針表的填充自動(dòng)函數(shù)。在需要時(shí)，只需調(diào)用fill_tbl_op()函數(shù)即可。該函數(shù)中創(chuàng)建fill_tbl_types_m<n_types, n_types>函數(shù)對(duì)象，然后調(diào)用。這個(gè)函數(shù)對(duì)象的operator()首先創(chuàng)建并調(diào)用fill_tbl_types_n<m, n>函數(shù)對(duì)象。后者先調(diào)用set_tbl_type<m-1, n-1>模板函數(shù)，執(zhí)行填充tbl_type_op數(shù)組的[m-1, n-1]單元格。然后遞歸調(diào)用fill_tbl_types_n<m, n-1>函數(shù)對(duì)象。直到n-1==0，編譯器便會(huì)選擇特化版本的fill_tbl_types_n<m, 0>函數(shù)對(duì)象。該特化的operator()操作符重載是空的，因此遞歸結(jié)束。這樣完成一行的填充。然后，fill_tbl_types_m<m, n>則遞歸調(diào)用fill_tbl_types_m<m-1, n>函數(shù)對(duì)象，填充下一行。直到調(diào)用fill_tbl_types_m<0, n>特化版本，結(jié)束遞歸。
現(xiàn)在需要仔細(xì)看一下set_tbl_type<>函數(shù)模板。該模板上來(lái)就是兩個(gè)typedef。這兩個(gè)typedef創(chuàng)建了兩個(gè)類(lèi)型別名，分別用m和n做索引，從boost::mpl::vector<double, int, string>中取出相應(yīng)的類(lèi)型：
typedefmpl::deref<mpl::advance<mpl::begin<op_types>::type, 
mpl::int_<m> >::type>::typetype_1;
…
頭暈是吧。我的頭還有點(diǎn)暈?zāi)亍＿@就是模板元編程，不停地鼓搗類(lèi)型。具體的操作可以參考boost文檔或《The Template Meta-programming》一書(shū)，我這里就不多說(shuō)了，反正就是從一個(gè)存放類(lèi)型的vector中取出所需的類(lèi)型。
這樣獲得的兩個(gè)類(lèi)型用來(lái)實(shí)例化add_op<>()模板函數(shù)，并且填充到tbl_type_ops[m][n]元素中。
這樣，利用TMP和GP兩種強(qiáng)大的機(jī)制，消除了tbl_type_ops填充的組合爆炸問(wèn)題。如果我們需要向variant中加入新的類(lèi)型，那么只需在mpl::vector<double, int, string>中直接加入類(lèi)型即可：
typedef mpl::vector<double, int, string, bool, datetime>op_types;
OK，下面回過(guò)頭，來(lái)處理add_op<>中存在的組合爆炸。對(duì)于每一對(duì)可以直接或間接相加的類(lèi)型，都需要做一個(gè)add_op<>的特化版本。這當(dāng)然不夠好。我們可以進(jìn)一步抽象add_op，然后加以?xún)?yōu)化。我把整個(gè)add_op<>模板改寫(xiě)成如下代碼：
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模板（模板元函數(shù)）獲得兩個(gè)操作數(shù)相加后應(yīng)有的返回類(lèi)型。這個(gè)模板一會(huì)說(shuō)明。然后，調(diào)用variant上的類(lèi)型轉(zhuǎn)換操作符，將兩個(gè)操作數(shù)轉(zhuǎn)換成返回類(lèi)型。最后相加，并創(chuàng)建返回variant對(duì)象。代碼非常簡(jiǎn)單，沒(méi)法再簡(jiǎn)單了。
再來(lái)看看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;
};
…//其他類(lèi)型對(duì)的返回類(lèi)型
type_ret<>是典型的模板元函數(shù)，沒(méi)有任何實(shí)際代碼，只有編譯時(shí)計(jì)算的typedef。主模板將第一個(gè)類(lèi)型參數(shù)typedef出一個(gè)別名。其后的模板特化對(duì)于一些特殊的情況做出定義，如int和double相加返回第二個(gè)操作數(shù)類(lèi)型double（即所謂的類(lèi)型提升）。
我們現(xiàn)在已經(jīng)優(yōu)化了variant+varint的代碼。現(xiàn)在來(lái)看看如何優(yōu)化variant類(lèi)型和其他類(lèi)型的加法：
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;
}
這非常簡(jiǎn)單，直接利用了variant+variant，將其它類(lèi)型的操作數(shù)轉(zhuǎn)換成variant類(lèi)型，然后相加。


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

好，加法完成了。但還有其他操作符。每個(gè)操作符都做那么一個(gè)函數(shù)指針表，也不見(jiàn)得高明到哪里去。現(xiàn)在需要整合優(yōu)化這些操作符。這里，我想到了兩種方法：一種是將函數(shù)指針表和填充操作整個(gè)地封裝在一個(gè)模板中，模板參數(shù)采用int op形式。每一種操作符對(duì)應(yīng)一個(gè)整數(shù)（或枚舉值），并利用某種手段（如singleton）唯一生成一組全局的函數(shù)表，以此處理每一種操作。另一種方法是為函數(shù)指針表加一個(gè)維度（二維擴(kuò)展到三維），新的維度對(duì)應(yīng)不同的操作符。前一種方法靈活性強(qiáng)些，而且有利于性能優(yōu)化；而后一種方法實(shí)現(xiàn)簡(jiǎn)單。這里我使用后一種方法：
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()));
}
我使用了一個(gè)函數(shù)對(duì)象模板var_op<>抽象各種算法（二元）。針對(duì)每一種運(yùn)算符特化。抽象的variant_op函數(shù)模板實(shí)例化var_op<>，然后調(diào)用。獲得相應(yīng)的操作。
觀(guān)察variant_op的模板參數(shù)，會(huì)發(fā)現(xiàn)已經(jīng)包含了一個(gè)操作的基本要素。（眼下這個(gè)形式正好符合逆波蘭表達(dá)式）。
接下來(lái)，只需將函數(shù)指針數(shù)組，及其填充算法加以擴(kuò)展，便可大功告成：
add_op_t tbl_type_ops[n_types][n_types][vt_op_num];
//填充函數(shù)指針表單個(gè)元素
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>//特化，遞歸結(jié)束
{
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>//特化，遞歸結(jié)束
{
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>//特化，遞歸結(jié)束
{
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);
}
于是操作符的實(shí)現(xiàn)，成了以下形式：
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);
}
…
如果還覺(jué)得復(fù)雜，那么可以進(jìn)一步使用宏做一些包裝。
好了，variant的優(yōu)化基本上完成了。當(dāng)然還會(huì)有一些方面值得我們?nèi)ミM(jìn)一步地優(yōu)化，比如可以利用boost的type traits和標(biāo)準(zhǔn)庫(kù)的limit優(yōu)化type_ret模板的實(shí)現(xiàn)和類(lèi)型轉(zhuǎn)換操作的實(shí)現(xiàn)等等。這里不再贅述。
需要說(shuō)明的是，整個(gè)優(yōu)化僅僅針對(duì)代碼，并未考慮性能問(wèn)題。在優(yōu)化的過(guò)程中，某些手法的使用實(shí)際上降低的性能。比如函數(shù)指針表存在間接調(diào)用，不如直接使用inline函數(shù)來(lái)的高效。而且，函數(shù)指針表要求所有指向的函數(shù)必須以相同的類(lèi)型返回。為了兼容+、-等操作，我使用了值返回。但對(duì)于+=等操作符完全可以利用引用返回，以提升性能。如果要解決這種問(wèn)題，需要用前面提到的模板封裝函數(shù)指針表的方案，為每一個(gè)操作符創(chuàng)建一個(gè)函數(shù)指針表加以解決。
另一個(gè)性能問(wèn)題主要是在variant與其它類(lèi)型的操作中，其它類(lèi)型轉(zhuǎn)換成variant類(lèi)型然后再計(jì)算。比起直接使用目標(biāo)類(lèi)型計(jì)算慢不少。這個(gè)問(wèn)題也可以利用GP和TMP消除，但代碼會(huì)復(fù)雜不少。
理論上，利用inline和編譯器優(yōu)化，可以消除大部分性能問(wèn)題。但不是所有的，函數(shù)指針表的間接調(diào)用，是無(wú)論如何也優(yōu)化不掉的。
此外，我在實(shí)現(xiàn)函數(shù)指針表的構(gòu)造算法時(shí)，沒(méi)有使用函數(shù)模板，而是使用了函數(shù)對(duì)象模板（重載operator()的模板）。這是因?yàn)楹瘮?shù)模板目前不能局部特化，而這里是必須的。另一方面，由于使用了遞歸，函數(shù)模板無(wú)法做到inline()，而使用函數(shù)對(duì)象模板則不會(huì)有此限制。表達(dá)式fill_tbl_types_m()();最終（優(yōu)化）編譯后的結(jié)果會(huì)是這樣（偽碼）：
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>;
…
遞歸和函數(shù)對(duì)象的調(diào)用沒(méi)有了，完全inline化了。inline函數(shù)有時(shí)卻無(wú)法做到這一點(diǎn)。而fill_tbl_types_op等模板實(shí)際上起到了代碼生成器的作用。這也是GP的一個(gè)鮮為人知的功能。如果你有一大堆代碼需要編寫(xiě)，而這些代碼有很強(qiáng)的規(guī)律性和重復(fù)性，那么請(qǐng)優(yōu)先考慮使用模板來(lái)為你生成代碼，又快又好。
該總結(jié)了。如果審視一些代碼，會(huì)發(fā)現(xiàn)只要存在重復(fù)和規(guī)律性，我們總能利用一些技術(shù)和方法加以?xún)?yōu)化，減少代碼量，簡(jiǎn)化代碼結(jié)構(gòu)，減少潛在錯(cuò)誤，最終提高開(kāi)發(fā)效率。這里，我使用了C++的泛型編程和模板元編程技術(shù)，大幅優(yōu)化了variant類(lèi)型中的大量冗余代碼。并且為variant類(lèi)型構(gòu)建了一個(gè)靈活，而又易于擴(kuò)充的結(jié)構(gòu)。此類(lèi)技術(shù)有很廣的應(yīng)用，不僅僅局限在variant這種底層構(gòu)件中。相關(guān)的一個(gè)應(yīng)用就是構(gòu)造抽象類(lèi)工廠(chǎng)，在《Modren C++ Design》一書(shū)中，有很完整的案例。
此外，這類(lèi)技術(shù)對(duì)于調(diào)和運(yùn)行時(shí)多態(tài)（OOP）和編譯時(shí)多態(tài)（GP）的矛盾有很大的作用。variant只有在運(yùn)行時(shí)方能確定其具體的類(lèi)型，而C++的模板只能提供編譯時(shí)的GP。我利用函數(shù)指針數(shù)組（當(dāng)然在更復(fù)雜的應(yīng)用中，可以利用OOP的動(dòng)多態(tài)機(jī)制），實(shí)現(xiàn)運(yùn)行時(shí)分派操作。而利用GP和TMP大幅簡(jiǎn)化函數(shù)指針數(shù)組、操作實(shí)現(xiàn)函數(shù)，以及操作符的構(gòu)造。這些技術(shù)和方法可以在大多數(shù)需要運(yùn)行時(shí)多態(tài)，但又存在大量重復(fù)或雷同代碼的地方得以應(yīng)用。