关于c++:翻译c类中空成员的优化

文章来自于 The “Empty Member” C++ Optimization。是我在看 c ++ std::string 代码时遇到的一个链接，其中解释了为什么_Alloc_hider 会采纳 inhert from Alloc 的起因。
文章应该是 97 年的，所以外面的指针长度还是 4 byte。

c++ 类中“空成员”的优化

C++ 规范库中有很多有用的模板，包含享誉盛名的 SGI STL。这些模板的实现很高效，也不失灵便。在日常的编程中，能够把这些模板当作范例来进行学习，也可启发咱们如何进行兼顾灵活性与效率的程序设计。

“空成员”的优化，就是这样的一个榜样：一个没有类成员的 class，就不应该占用内存空间。什么状况下须要一个没有类成员的 class 呢？这样的 class 个别会领有一系列的 typedef 或者成员函数，而程序的调用方能够用本人定义的相似的 class 来实现一些非凡的性能（自定义的 class 可不肯定没有类成员）。这个默认提供的 class 应该能够满足绝大多数的需要。这种状况下，优化这个空成员的 class 是个很有性价比的事件。

因为语言的限度（之后会解释），空成员的 class 通常会占据肯定的内存空间。如果是个别状况也就算了，然而在 stl 里，不进行优化的话，还是会劝退很多潜在的使用者的。

空成员“收缩”

以 STL 举例。每个 STL 的容器都有一个 allocator 的参数，当容器须要内存的时候，它会向 allocator 去申请。如果用户想要本人定制化内存申请过程，那么就能够在结构容器时提供本人的 allocator。大多数状况下，容器用的是 STL 默认的 allocator，这个默认的 allocator 间接调用 new 来实现调配。这是个空类，相似于上面这个定义

  template <class T>
    class allocator {   // an empty class
      . . .
      static T* allocate(size_t n)
        {return (T*) ::operator new(n * sizeof T); }
      . . .
    };

举个 list 的例子，class list 保留了一个公有的 allocator 成员，这个成员在构造函数里进行赋值

  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<>::alloc_ 通常占据 4 byte，只管这个 Alloc 是个空类。这通常来说不太会是个问题。但万一 list 本身是一个微小的数据结构的一个节点（比方 vector<list>)，当 vector 很大的时候，这种额定的空间耗费是不可漠视的。微小的内存占用意味着更慢的执行速度。就算在当下，绝对于 cpu 本身的频率来说，内存拜访曾经十分慢了。

空对象

那么改怎么解决这个问题？解决问题之前，首先须要搞清楚为什么这里会有这一层开销。C++ 的语言定义是这么说的：

A class with an empty sequence of members and base class objects is an empty class. Complete objects and member subobjects of an empty class type shall have nonzero size.
空类：没有数据成员，并且没有基类。这个基类实例化进去的残缺对象的大小不应该为 0.

解释以下这个规定的原因：

  struct Bar { };
  struct Foo {struct Bar a[2];
    struct Bar b;
  };
  Foo f;

那么 f.b 和f.a[]别离是什么？如果 sizeof(Bar) 是 0，那么这 2 个地址就是一样的。如果你用地址来作为对象的标识，那么 f.b 和f.a[0]就是同一个对象了。C++ 规范委员会通过禁止空类的对象大小为 0 来解决这个问题。

但为什么还须要占据 4 byte 的大小呢？尽管大部分的编译器认为sizeof(Bar) == 1，但 4 byte 是对象对齐的需要。比方：

  struct Baz {
    Bar b;
    int* p;
  };

构造体 Baz 在大多数的体系结构上大小是 8 byte，编译器本人在 Baz::b 前面增加了补齐，是为了让 Baz::p 不会横跨一个字(word)。

  struct Baz
  +-----------------------------------+
  | +-------+-------+-------+-------+ |
  | | Bar b | XXXXX | XXXXX | XXXXX | |
  | +-------+-------+-------+-------+ |
  | +-------------------------------+ |
  | | int* p                        | |
  | +-------------------------------+ |
  +-----------------------------------+

那该如何躲避调这个额定的开销呢？C++ 规范也在 Footnote 里提了一嘴：

A base class subobject of an empty class type may have zero size.
空类作为基类时，其大小能够为 0

也就是说，如果是这个构造体

  struct Baz2 : Bar {int* p;};

编译器就会认为 Bar 的大小为 0，这样 sizeof(Baz2)就是 4。

  struct Baz2
  +-----------------------------------+
  | +-------------------------------+ |
  | | int* p                        | |
  | +-------------------------------+ |
  +-----------------------------------+

编译器并未要求实现成这个样子，然而你能够认为大部分规范的编译器就是这样实现的。

打消收缩

当初你晓得了打消这个开销的原理了，问题是接下来怎么做？最直观的，list<> 间接继承 Allocator，如下：

  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()，而非allco_.allocate() 实现内存申请。
不过，用户提供的 Alloc 是容许领有虚函数的，这可能会和子类 list<> 里的某些办法有抵触。（list<>::init和Alloc::init())。

另一种可行的形式是，将 Alloc 打包到 list<> 的成员变量上(比方指向第一个 list node 的指针)，这样 Allocator 的接口不会裸露进去。

  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) {. . .}
      . . .
    };

采纳这种办法实现的话，申请内存就用head.allocate()。没有额定的开销，list<> 用起来也和以前一样。不过就像其余做的好的优化一样，实现上总是有点俊俏，但总归不会影响到接口了。

对立一点的解决方案

当然还有晋升的空间了。看看上面这个 template

  template <class Base, class Member>
    struct BaseOpt : Base {
      Member m;
      BaseOpt(Base const& b, Member const& mem) 
        : Base(b), m(mem) {}};

用这个模板，那么 list 的接口就能够变成这样：

  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) {. . .}
      . . .
    };

这个实现相比与最开始的版本，看起来也没那么不堪了。其余的 STL 容器，也能够借助 BaseOpt 来简化代码。只不过，成员函数申请内存的时候就会奇怪一些了，这个咱们当初还临时不思考了。

当初能够在 BaseOpt 定义的中央加上很好的文档来形容这个优化技术了。

也能够在 BaseOpt 里增加一些成员，然而并不倡议这样做。这可能会造成和 Base 里名称抵触（就像咱们在第一次尝试打消收缩的代码里一样）。

收尾

这项技术能够在当下通用的编译器里应用。就算编译器没有实现空基类优化，也没有额定的开销。