什么是Empty Base Optimization？-电子发烧友网

什么是Empty Base Optimization？

说到C++中的Empty Base Optimization(简称ebo)可能大家还是比较陌生，但是C++中每天都在用的std::string中就用到了ebo。

那么到底什么是ebo呢？其实ebo就是当一个类的对象理想内存占用可以为0的时候，把这个类的对象作为另一个类的成员时，把其内存占用变为0的一种优化方法。说起来可能有点绕，还是用一个例子来说明一下吧，看下面的代码：

#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。这是因为如果一个类的内存占用为0，那么连续的分配对象有可能会有同一个内存地址，这个是不合理的。所以编译器为了避免这种情况，让空的类也会占有1 byte的大小。

那么如果我要用Base作为另一个类的成员变量呢，比如下面这样：

classTestCls
{
Basem_obj;
intm_num;
};

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

知道上面的输出会是多少吗？5？在32位的机器上面是8，因为编译器为了存取的方便，会在m_obj的后面产生3 byte的padding，以和机器字对齐。总之答案不会是4。

但是在内存非常紧张的情况下，还真的会想要让TestCls的size是4。有办法吗？这里就可以用到今天介绍的ebo了，看下面的代码：

classTestCls:publicBase
{
intm_num;
};

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

这次能猜到输出是多少吗？没错，就是我们想要的4！当我们把空的类作为基类的时候，编译器就会把这个基类的size去掉，做了优化，从而使得整个对象占有真正需要的size。

那么如果这个子类除了基类之外，没有别的成员呢？如下面：

classTestCls:publicBase
{};

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

上面的代码输出仍然是1，因为如果这个类本身除了空基类之外没别的成员，说明这个类本身也是一个空类，所以最开始说的情况就适用于这里。编译器就给空类给了1的size。

上面说的就是Empty Base Optimization了。那么现实中哪里使用到了这个技巧呢？除了最开始提到的std::string之外，Google的cpp-btree也用到了这个技巧。下面我们来看看这两个现实中的例子。

STL中的string

C++每天都用的string中就用到了ebo。我们来看看string是如何定义成员的(省略函数定义，以下代码源自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继承于模板参数类_Alloc(并且还是私有继承)，还有一个自己的成员_M_p。_M_p是用来存放实际数据的，而_Alloc呢？熟悉STL的人可能还记得STL里面有一个allocator。这个allocator一般的实现都是没有任何的数据成员，只有static函数的。所以这个类是一个空类。默认的string就是将这个allocator当作模板参数传递到_Alloc。所以_Alloc大多数情况下都是空类，而string经常会在程序中用到，还很经常会大量的使用，比如在容器中，这个时候就需要考虑内存占用了。所以在这里就是用了ebo的优化。

可能会有人会问，string里面实际上只有char*，但是不是说string还记录了size，还用到了copy on write技术的吗？那怎么只有一个char*呢？这个和string的实现中的内存布局相关，其中Copy on write是g++的stl中实现的策略，想要了解g++的string的内存布局，可以看看陈硕的这篇文章。

cpp-btree中的ebo

cpp-btree是Google出的一个基于B树的模板容器类库。如果有不熟悉B树的童鞋，可以移步这里看一看这个数据结构的动画演示。

B树是一种平衡树结构，一般常用于数据库的磁盘文件数据结构(不过一般会用其变体B+树)。而cpp-btree则是全内存的，和std::map类似的一种容器实现，其对于大量元素(>100w)的存取效率要高于std::map的红黑树实现，并且还节省内存。

关于cpp-btree的广告就卖到这里，我们看看他哪里使用了ebo。在cpp-btree里面提供了btree_set和btree_map两个容器类，而他们的公共实现都在btree这个类里面。btree这个类实现了主要的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，而在默认的btree_map实现中，这个allocator就是std::allocator。所以一般情况下，Base也是一个空类。

这里btree也利用了ebo节省了内存占用。

一个例外

在编译器判断是否做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;
}