发信人: Sarge (Nirvana), 信区: Programming
标 题: C++空成员类优化
发信站: 哈工大紫丁香 (2001年08月17日11:15:47 星期五), 站内信件
这篇文章曾经发表在97年8月的Dr. Dobb Journal上的C++ Issue专栏上
C++空成员类优化
By Nathan C. Myers
翻译：张岩
C++标准库（草案）中充斥着各种有用的模板，其中包括获奖的STL（见DDJ
Mar95）中的一些扩展版本。这些模板提供了非常大的弹性，现在，它们在实际应
用中被最优化来获取最高的性能。和它们在程序中的用处一样，它们作为表达有效
设计的实例，或者作为使你自己的组件富有弹性并同时有效率的灵感的源泉，也是
非常有用的。
提供弹性的一种方式就是使用"空"类--没有数据成员的类。理想情况下，这些类不
应该耗费任何储存空间。它们通常是定义了一些typedef或者成员函数，然后，你
用自己的类（不能确定是否为空类）来替换它们从而满足某种特殊需求。默认的空
成员类是到现在为止最经常用到的，所以，这一情况必须被最优化，这样我们才可
以不需要为所有的特殊需求付出代价。
由于一个不幸的语言定义的细节（稍候作详细的解释），空成员类的实例往往会占
据空间。在其它的类的成员中，这种空间的开销会变成其它方式--小的对象变的足
够大以致无法在某些环境中应用。如果这种开销不能在构造标准库的时候避免的话
，由库的弹性随之而产生的开销会让许多用户望而却步。在标准库中的优化技术也
同样适合你自己的代码。
空成员膨胀
这里有一个例子，在标准C++库中，每一个STL容器类的构造函数都包含，拷贝一
个allocator参数。当容器需要空间的时候，它就向它的allocator成员索取。这样
，有对内存分配有特殊要求的用户（比如共享区间）可以为它定义一个allocator
，并且把它传入一个容器的构造函数，这样容器元素就可以被放置于其中。在普通
条件下，标准的默认allocator被使用，它将申请工作委托给全局的operator new
。它是一个空对象。
这里的简短的代码是一个可能的实现。在Listing 1中，标准的allocator，
allocator<>，只有一个成员函数。
------------------------------------------------------------------------
--------
Listing 1: The Standard Default Allocator
template <class T>
class allocator { // an empty class
. . .
static T* allocate(size_t n)
{ return (T*) ::operator new(n * sizeof T); }
. . .
};
};
------------------------------------------------------------------------
--------
在Listing 2中，广义表的容器模板中维护了一个私有的allocator成员，这是从它
的构造函数参数中拷贝得到的。
------------------------------------------------------------------------
--------
Listing 2: The Standard Container list<>
template <class T, class Alloc = allocator<T> >
class list {
. . .
Alloc alloc_;
struct Node { . . . };
Node* head_;
public:
explicit list(Alloc const& a = Alloc())
: alloc_(a) { . . . }
. . .
};
注：list<>的构造函数被声明为"explicit",这样编译器不会将它用作为一个自动
转型。（这是一个新的语言特性。）
list<>是如何从一个能为T提供空间的allocator中，为一个Node对象分配空间的，
将是下一篇文章的主题。
------------------------------------------------------------------------
--------
成员list<>::alloc_在对象中占据了，通常是四个byte的空间，即使是在Alloc是
一个空成员类allocator<T>的默认情况下。list对象的一些额外空间看起来并不是
很糟糕，直到你想到一个大的vector of lists的时候，或者是在一个hash表中，
你才会考虑到严重性。每一个list中的多余的垃圾都被作了乘法，并且降低了虚拟
内存页面中的list head的数目。浪费的空间使程序变慢。
空对象
这种开销如何才能避免呢？同样，你需要理解开销产生的原因。标准C++语言定义
如是说：
一个有着空的成员序列和基类对象的类称为空类。一个空类的完整的对象和成员
子对象是非零长度。
为什么没有成员数据的对象要占据空间呢？考虑下面的代码：
struct Bar { };
struct Foo {
struct Bar a[2];
struct Bar b;
};
Foo f;
f.b和f.a[]的元素的地址是什么呢？如果sizeof(Bar)是零的话，它们可能就会有
相同的地址。如果你是借助地址来跟踪不同的对象的话，那么f.b和f.a[0]会显现
得像是同一个对象。标准委员会选择了通过禁止零长度可寻址对象来解决这些问题
。
尽管如此，为什么一个空成员会占据如此多的空间（4个byte，在我们的例子中）
？在所有我知道的编译器中，sizeof(Bar)是1。然而，在大多数体系结构下，对象
需要根据它们的类型进行对齐。例如，如果你声明
struct Baz {
Bar b;
int* p;
};
当今大多数体系下，sizeof(Baz)是8，这是因为编译器插入"padding"使成员Baz:
:p不跨越一个word的边界。（见图1a）
------------------------------------------------------------------------
--------
图1a:
struct Baz
+-----------------------------------+
| +-------+-------+-------+-------+ |
| | Bar b | XXXXX | XXXXX | XXXXX | |
| +-------+-------+-------+-------+ |
| +-------------------------------+ |
| | int* p | |
| +-------------------------------+ |
+-----------------------------------+
------------------------------------------------------------------------
--------
图1b:
struct Baz2
+-----------------------------------+
| +-------------------------------+ |
| | int* p | |
| +-------------------------------+ |
+-----------------------------------+
------------------------------------------------------------------------
--------
如何避免这一开销？草案在注脚处暗示：
一个空类的基类的子对象（base class subobject）可以是零长度的。
换句话说，如果你像这样声明Baz2，
struct Baz2:Bar {
int* p;
};
这钟情况，编译器就允许为空基类保存0 byte；因此，sizeof(Baz2)在大多数机
器上只为4。（见图1b）
编译器厂商不是必须来完成这个优化，并且到目前，许多厂商没有这样做。然而，
你可以期待最遵循标准的编译器会这样做，因为标准库中的许多组件（不仅仅是容
器）的效率依赖这一优化。
消除膨胀
你已经找到了消除空间开销所需的原理。怎样执行呢？让我们先考虑你如何来修
正我们例子中的实现，模板的list<>。你可以直接从allocator中继承，如Listing
3中那样，
------------------------------------------------------------------------
--------
Listing 3: A Na?ve Way to Eliminate Bloat
template <class T, class Alloc = allocator<T> >
class list : private Alloc {
. . .
struct Node { . . . };
Node* head_;
public:
explicit list(Alloc const& a = Alloc())
: Alloc(a) { . . . }
. . .
};
------------------------------------------------------------------------
--------
并且，这通常会起作用。list<>中成员函数的代码会用this->allocate()代替原
来的alloc_.allocate()来获得空间。然而，用户提供的Alloc类型允许含有
virtual成员，这将会与派生的list<>成员冲突。（可以设想一个私有成员void
list<>::init()，和一个virtual成员bool Alloc::init()。）
一个好得多的解决方法是用list<>的数据成员将allocator封装，例如指向第一个
节点的指针（如Listing 4所示），这样allocator接口将不会外露。
-----------------------------------------------------------------------
-
--------
Listing 4: A Better Way to Eliminate Bloat
template <class T, class Alloc = allocator<T> >
class list {
. . .
struct Node { . . . };
struct P : public Alloc {
P(Alloc const& a) : Alloc(a), p(0) { }
Node* p;
};
P head_;
public:
explicit list(Alloc const& a = Alloc())
: head_(a) { . . . }
. . .
};
------------------------------------------------------------------------
------------------------------------------------------------------------
--------
现在，list<>的成员通过"head_.allocate()"来获得储存空间。并且通过"head_.
p"来获得第一个元素。这非常完美了，没有任何不必要的开销，list<>的用户感觉
不到有任何不同。和其他任何出色的优化一样，它使实现变的有一点不整洁。但是
这不会影响到接口。
一个封装的解决方案
到现在，还有可以改进的余地。和往常一样，改进引入了模板。在Listing 5中我
们将这种技术封装让它更容易，更简洁地被应用。
------------------------------------------------------------------------
--------
Listing 5: Packaging the Technique
template <class Base, class Member>
struct BaseOpt : Base {
Member m;
BaseOpt(Base const& b, Member const& mem)
: Base(b), m(mem) { }
};
------------------------------------------------------------------------
--------
使用这个模板，我们的list<>声明将像Listing 6种所示，
------------------------------------------------------------------------
--------
Listing 6: The Best Way to Eliminate Bloat
template <class T, class Alloc = allocator<T> >
class list {
. . .
struct Node { . . . };
BaseOpt<Alloc,Node*> head_;
public:
explicit list(Alloc const& a = Alloc())
: head_(a,0) { . . . }
. . .
};
------------------------------------------------------------------------
--------
这一list<>的声明并没有比我们的最初的未优化版本更大、更杂乱。任何其他的
库组件（标准的或非标准的）可以简单地使用BestOpt<>。成员代码只有一点杂乱
；同时已开始很难看清发生了什么，BestOpt<>的声明提供了一个方法来文档化这
个技术和原因。
在BestOpt<>中加入成员是一件十分诱人的事情，但是这不会改善它：她们会如
Listing 3种所展现的那样，出现派生类和基类参数的冲突。
最后
这种技术在任何很好支持模板技术的编译器下都可以被应用。并不是所有的C++编
译器都可以支持空成员基类优化，虽然Sun，HP，Microsoft的编译器都已经这样做
了。但这这种技术即使是在编译器不支持的情况下也不会产生额外的开销。当你手
头有一个能很好支持标准的编译器的时候，它很有可能会做出这种优化，如果你的
代码利用了这种技术，他会自动变得更有效率。
Fergus Henderson在这项技术细化的方面做出了重要的贡献。
--
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.170.170]