用C++实现对内存的管理

今天，对绝大多数程序来说，通用的内存分配方法--此处指代分配算符（Allocator：即malloc或new），已达到了理想的速度及满足了低碎片率的要求，然而，在内存分配领域，一丁点的信息都值得探讨很久，某些特定程序关于分配模式的信息，将有助于实现专门的分配算符，可显著地提高大多数高性能要求程序的性能底线。有时，当通用内存分配算符平均耗费几百个时钟周期时，一个良好的自定义内存分配算符可能只需要不到半打的周期。

　　这就是为什么大多数高性能、高要求的应用程序（如GCC、Apache、Microsoft SQL Server），都有着它们自己的内存分配算符。也许，把这些专门的内存分配算符归纳起来，放进一个库中，是个不错的想法，但是，你的程序可能有不同的分配模式，其需要另外的内存分配算符，那怎么办呢？

　　等等，还有呢，如果我们设计了一种特殊用途的内存分配算符，就可以不断发展下去，由此可从中筛选出一些，来组成一个通用目的的内存分配算符，如果此通用分配算符优于现有的通用分配算符，那么此项设计就是有效及实用的。

　　下面的示例使用了Emery小组的库--HeapLayers（），为了定义可配置的分配算符，其中使用了mixins（在C++社区中，也被称为Coplien递归模式）：通过参数化的基来定义类，每一层中只定义两个成员函数，malloc和free：

template
struct Allocator : public T {
　void * malloc(size_t sz);
　void free(void* p);
　//系统相关的值
　enum { Alignment = sizeof(double) };
　//可选接口e
　size_t getSize(const void* p);
};

　　在每一层的实现中，都有可能向它的基类请求内存，一般来说，一个不依赖于外界的内存分配算符，都会处在层次的顶层--直接向前请求系统的new和delete操作符、malloc和free函数。在HeapLayers的术语中，没有顶层堆，以下是示例：

struct MallocHeap {
　void * malloc(size_t sz) {
　　return std::malloc(sz);
　}
　void free(void* p) {
　　return std::free(p);
　}
};

　　为获取内存，顶层堆也能通过系统调用来实现，如Unix的sbrk或mmap。getSize函数的情况就比较特殊，不是每个人都需要它，定义它只是一个可选项。但如果定义了它，你所需做的只是插入一个内存块大小的层，并提供getSize函数，见例1：

　　例1：

template
class SizeHeap {
　union freeObject {
　　size_t sz;
　　double _dummy; //对齐所需
　};
public:
　void * malloc(const size_t sz) {
　　//添加必要的空间
　　freeObject * ptr = (freeObject *)SuperHeap::malloc(sz + sizeof(freeObject));
　　//请求的大小
　　ptr->sz = sz;
　　return ptr + 1;
　}
　void free(void * ptr) {
　　SuperHeap::free((freeObject *) ptr - 1);
　}
　static size_t getSize (const void * ptr) {
　　return ((freeObject *)ptr - 1)->sz;
　}
};

　　SizeHeap是怎样实现一个实用的层，并挂钩于它基类的malloc与free函数的最好示例，它在完成一些额外的工作之后，把修改好的结果返回给使用者。SizeHeap为存储内存块大小，分配了额外的内存，再加上适当的小心调整（指union），尽可能地避免了内存数据对齐问题。不难想像，我们可构建一个debug堆，其通过特定模式在内存块之前或之后填充了一些字节，通过检查是否模式已被保留，来确认内存的溢出。事实上，这正是HeapLayers的DebugHeap层所做的，非常的简洁。

　　让我们再来看看，以上还不是最理想的状态，某些系统已经提供了计算已分配内存块大小的原语（此处指操作符，即前述的分配算符），在这些系统上，SizeHeap实际上只会浪费空间。在这种情况下（如Microsoft Visual C++），你将不需要SizeHeap与MallocHeap的衔接，因为MallcoHeap将会实现getSize：

struct MallocHeap {
　... 与上相同 ...
　size_t getSize(void* p) {
　　return _msize(p);
　}
};

　　但似乎还有一些不足之处。想一想，我们是在统计时钟周期，如果一个系统的malloc声明了内存的块大小将存储在实际块之前的一个字中，那将会怎样呢？在这种情况下，SizeHeap还是会浪费空间，因为它仍会在紧接着系统已植入的块后存储一个字。此处所需的，只是一个用SizeHeap的方法实现了getSize的层，但未挂钩malloc与free。这就是为什么HeapLayers把前面的SizeHeap分成了两个，见例2：

　　例2：

template
struct UseSizeHeap : public Super {
　static size_t getSize(const void * ptr) {
　　return ((freeObject *) ptr - 1)->sz;
　}
protected:
　union freeObject {
　　size_t sz;
　　double _dummy; //对齐所需
　};
};

template
class SizeHeap: public UseSizeHeap{
　typedef typename
　UseSizeHeap::freeObject
　freeObject;
public:
　void * malloc(const size_t sz) {
　　//添加必要的空间
　　freeObject * ptr = (freeObject *)SuperHeap::malloc(sz + sizeof(freeObject));
　　//存储请求的大小
　　ptr->sz = sz;
　　return (void *) (ptr + 1);
　}
　void free(void * ptr) {
　　SuperHeap::free((freeObject *)ptr - 1);
　}
};

[NextPage]

　现在，SizeHeap就会正确地添加UseSizeHeap层，并利用它的getSize实现了，而UseSizeHeap也能通过其他配置来使用--这是一个非常优雅的设计。

　　一个实用的示例：FreelistHeap

　　到目前为止，我们还处于一个准备的阶段，只有架构，还不知怎样利用这些层来编写一个高效专用的内存分配算符，也许一个比较合适的开发步骤可如下所示：

　　·收集有关程序为每种内存块大小进行分配次数的信息。

　　·为最经常请求的大小（在此称为S），维持一个私有、逐一链接的列表。
　
　　·对S的内存分配尽可能地从列表中返回内存，或者从默认分配算符中返回（在分层架构中，从上级层中）。

　　·对S大小内存块的释放，把内存块放回至列表中。

　　·一个精心设计的分配策略，应可对范围大小从S1至S2，使用相同的释放列表，并消耗同等的内存。而所需链接列表的操作开销为O(1)，实际上只有几条指令。另外，指向下一条目的指针，能存储在实际的块中（块中存储了无用的数据--总为一个释放了的块），因此，对每个块就不需要额外的内存了。正因为大多数应用程序分配内存的大小都是不同的，所以，对任何分配算符的实现来说，释放列表就必不可少了。

　　下面让我们来实现一个层，由其对已知静态范围大小从S1至S2，实现了一个释放列表，见例3：

　　例3：

template
struct FLHeap {
　~FLHeap() {
　　while (myFreeList) {
　　　freeObject* next = myFreeList->next;
　　　Super::free(myFreeList);
　　　myFreeList = next;
　　}
　}
　void * malloc(const size_t s) {
　　if (s < S1 || s > S2)) {
　　　return Super::malloc(s);
　　}
　　if (!myFreeList) {
　　　return Super::malloc(S2);
　　}
　　void * ptr = myFreeList;
　　myFreeList = myFreeList->next;
　　return ptr;
　}
　void free(void * p) {
　　const size_t s = getSize(p);
　　if (s < S1 || s > S2) {
　　　return Super::free(p);
　　}
　　freeObject p =reinterpret_cast(ptr);
　　p->next = myFreeList;
　　myFreeList = p;
　}
private:
　// 嵌入在释放的对象中的链接列表指针
　class freeObject {
　　public:
　　　freeObject * next;
　};
　//释放的对象链接列表头
　freeObject * myFreeList;
};

　　现在，你像如下所示可定义一个自定义的堆：

typedef FLHeap<
SizeHeap,
24,
32>
SmartoHeapo;

　　SmartoHeapo在分配的大小在24至32之间时，速度相当快，对其它大小来说，也基本上一样。