什么是Empty Base Optimization？

說(shuō)到C++中的Empty Base Optimization(簡(jiǎn)稱ebo)可能大家還是比較陌生，但是C++中每天都在用的std::string中就用到了ebo。

那么到底什么是ebo呢？其實(shí)ebo就是當(dāng)一個(gè)類的對(duì)象理想內(nèi)存占用可以為0的時(shí)候，把這個(gè)類的對(duì)象作為另一個(gè)類的成員時(shí)，把其內(nèi)存占用變?yōu)?的一種優(yōu)化方法。說(shuō)起來(lái)可能有點(diǎn)繞，還是用一個(gè)例子來(lái)說(shuō)明一下吧，看下面的代碼：

#include
usingnamespacestd;

classBase
{};

intmain()
{
cout<"sizeof(Base)"<sizeof(Base)<"addrobj1"<void*)&obj1<"addrobj2"<void*)&obj2<return0;
}

大家能猜到上面的代碼的輸出嗎？sizeof(Base)會(huì)是0嗎？obj1的地址會(huì)和obj2的一樣嗎？

自己編譯上面的代碼，運(yùn)行一下，會(huì)得到類似下面的輸出(第2、3行會(huì)略有不同)：

sizeof(Base)1
addrobj10xbfdc9033
addrobj20xbfdc9032

看見(jiàn)了吧？就算Base不包含任何的成員，編譯器也會(huì)讓Base占1 byte。這是因?yàn)槿绻粋€(gè)類的內(nèi)存占用為0，那么連續(xù)的分配對(duì)象有可能會(huì)有同一個(gè)內(nèi)存地址，這個(gè)是不合理的。所以編譯器為了避免這種情況，讓空的類也會(huì)占有1 byte的大小。

那么如果我要用Base作為另一個(gè)類的成員變量呢，比如下面這樣：

classTestCls
{
Basem_obj;
intm_num;
};

intmain()
{
cout<"sizeof(TestCls)"<sizeof(TestCls)<return0;
}

知道上面的輸出會(huì)是多少嗎？5？在32位的機(jī)器上面是8，因?yàn)榫幾g器為了存取的方便，會(huì)在m_obj的后面產(chǎn)生3 byte的padding，以和機(jī)器字對(duì)齊。總之答案不會(huì)是4。

但是在內(nèi)存非常緊張的情況下，還真的會(huì)想要讓TestCls的size是4。有辦法嗎？這里就可以用到今天介紹的ebo了，看下面的代碼：

classTestCls:publicBase
{
intm_num;
};

intmain()
{
cout<"sizeof(TestCls)"<sizeof(TestCls)<return0;
}

這次能猜到輸出是多少嗎？沒(méi)錯(cuò)，就是我們想要的4！當(dāng)我們把空的類作為基類的時(shí)候，編譯器就會(huì)把這個(gè)基類的size去掉，做了優(yōu)化， 從而使得整個(gè)對(duì)象占有真正需要的size。

那么如果這個(gè)子類除了基類之外，沒(méi)有別的成員呢？如下面：

classTestCls:publicBase
{};

intmain()
{
cout<"sizeof(TestCls)"<sizeof(TestCls)<return0;
}

上面的代碼輸出仍然是1，因?yàn)槿绻@個(gè)類本身除了空基類之外沒(méi)別的成員， 說(shuō)明這個(gè)類本身也是一個(gè)空類，所以最開(kāi)始說(shuō)的情況就適用于這里。編譯器就給空類給了1的size。

上面說(shuō)的就是Empty Base Optimization了。那么現(xiàn)實(shí)中哪里使用到了這個(gè)技巧呢？除了最開(kāi)始提到的std::string之外，Google的cpp-btree也用到了這個(gè)技巧。下面我們來(lái)看看這兩個(gè)現(xiàn)實(shí)中的例子。

STL中的string

C++每天都用的string中就用到了ebo。我們來(lái)看看string是如何定義成員的(省略函數(shù)定義，以下代碼源自gcc 4.1.2 c++)：

template<typename_CharT,typename_Traits,typename_Alloc>
classbasic_string
{
public:
mutable_Alloc_hider_M_dataplus;
};

注意string實(shí)際上是模板類basic_string的一個(gè)特化類。而basic_string只包含了一個(gè)成員_M_dataplus， 其類型為_Alloc_hider。

我們來(lái)看看_Alloc_hider是怎么定義：

template<typename_CharT,typename_Traits,typename_Alloc>
classbasic_string
{
private:
struct_Alloc_hider:_Alloc//Useebo
{
_CharT*_M_p;//Theactualdata.
};
};

_Alloc_hider繼承于模板參數(shù)類_Alloc(并且還是私有繼承)，還有一個(gè)自己的成員_M_p。_M_p是用來(lái)存放實(shí)際數(shù)據(jù)的，而_Alloc呢？熟悉STL的人可能還記得STL里面有一個(gè)allocator。這個(gè)allocator一般的實(shí)現(xiàn)都是沒(méi)有任何的數(shù)據(jù)成員，只有static函數(shù)的。所以這個(gè)類是一個(gè)空類。默認(rèn)的string就是將這個(gè)allocator當(dāng)作模板參數(shù)傳遞到_Alloc。所以_Alloc大多數(shù)情況下都是空類，而string經(jīng)常會(huì)在程序中用到， 還很經(jīng)常會(huì)大量的使用，比如在容器中，這個(gè)時(shí)候就需要考慮內(nèi)存占用了。所以在這里就是用了ebo的優(yōu)化。

可能會(huì)有人會(huì)問(wèn)，string里面實(shí)際上只有char*，但是不是說(shuō)string還記錄了size， 還用到了copy on write技術(shù)的嗎？那怎么只有一個(gè)char*呢？這個(gè)和string的實(shí)現(xiàn)中的內(nèi)存布局相關(guān)，其中Copy on write是g++的stl中實(shí)現(xiàn)的策略， 想要了解g++的string的內(nèi)存布局，可以看看陳碩的這篇文章。

cpp-btree中的ebo

cpp-btree是Google出的一個(gè)基于B樹(shù)的模板容器類庫(kù)。如果有不熟悉B樹(shù)的童鞋，可以移步這里看一看這個(gè)數(shù)據(jù)結(jié)構(gòu)的動(dòng)畫演示。

B樹(shù)是一種平衡樹(shù)結(jié)構(gòu)，一般常用于數(shù)據(jù)庫(kù)的磁盤文件數(shù)據(jù)結(jié)構(gòu)(不過(guò)一般會(huì)用其變體B+樹(shù))。而cpp-btree則是全內(nèi)存的，和std::map類似的一種容器實(shí)現(xiàn)，其對(duì)于大量元素(>100w)的存取效率要高于std::map的紅黑樹(shù)實(shí)現(xiàn)，并且還節(jié)省內(nèi)存。

關(guān)于cpp-btree的廣告就賣到這里，我們看看他哪里使用了ebo。在cpp-btree里面提供了btree_set和btree_map兩個(gè)容器類， 而他們的公共實(shí)現(xiàn)都在btree這個(gè)類里面。btree這個(gè)類實(shí)現(xiàn)了主要的B樹(shù)的功能，而其成員定義如下：

template<typenameParams>
classbtree:publicParams::key_compare{
private:
typedeftypenameParams::allocator_typeallocator_type;
typedeftypenameallocator_type::templaterebind<char>::other
internal_allocator_type;

template<typenameBase,typenameData>
structempty_base_handle:publicBase{
empty_base_handle(constBase&b,constData&d)
:Base(b),
data(d){
}
Datadata;
};

empty_base_handleroot_;
};

可以看見(jiàn)btree這個(gè)類里面只包含了root_這一個(gè)成員，其類型為empty_base_handle。empty_base_handle是一個(gè)繼承于Base的類，在這里，Base特化成internal_allocator_type。從名字可以看出internal_allocator_type是一個(gè)allocator， 而在默認(rèn)的btree_map實(shí)現(xiàn)中，這個(gè)allocator就是std::allocator。所以一般情況下，Base也是一個(gè)空類。

這里btree也利用了ebo節(jié)省了內(nèi)存占用。

一個(gè)例外

在編譯器判斷是否做ebo的時(shí)候，有這么一個(gè)例外，就是雖然繼承于一個(gè)空類， 但是子類的第一個(gè)非static成員的類型也是這個(gè)空類或者是這個(gè)類的一個(gè)子類。在這種情況下，編譯器是不會(huì)做ebo的。

有點(diǎn)繞，我們看看下面的代碼就明白了：

#include
usingnamespacestd;

classBase
{};

classTestCls:publicBase
{
public:
Basem_obj;//<<<<
intm_num;
};

intmain()
{
cout<"sizeof(Base)"<sizeof(Base)<"sizeof(TestCls)"<sizeof(TestCls)<"addrobj"<void*)&obj<"addrobj.m_obj"<void*)&(obj.m_obj)<"addrobj.m_num"<void*)&(obj.m_num)<return0;
}

運(yùn)行一下上面的代碼，你會(huì)看到，TestCls的size是8，并且obj的地址和obj.m_obj的地址并不一樣。這說(shuō)明了ebo并沒(méi)有進(jìn)行。