什么是Empty Base Optimization？

什么是Empty Base Optimization？

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

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

#include
usingnamespacestd;

classBase
{};

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

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

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

sizeof(Base)1
addrobj10xbfdc9033
addrobj20xbfdc9032

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

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

classTestCls
{
Basem_obj;
intm_num;
};

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

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

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

classTestCls:publicBase
{
intm_num;
};

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

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

那么如果這個子類除了基類之外，沒有別的成員呢？如下面：

classTestCls:publicBase
{};

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

上面的代碼輸出仍然是1，因為如果這個類本身除了空基類之外沒別的成員， 說明這個類本身也是一個空類，所以最開始說的情況就適用于這里。編譯器就給空類給了1的size。

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

STL中的string

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

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

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

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

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

cpp-btree中的ebo

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

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

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

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_;
};

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

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

一個例外

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

有點繞，我們看看下面的代碼就明白了：

#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;
}

運行一下上面的代碼，你會看到，TestCls的size是8，并且obj的地址和obj.m_obj的地址并不一樣。這說明了ebo并沒有進行。