C++内存打点厘革(2)：最袖珍的垃圾接纳器
当前位置：以往代写 > C/C++ 教程 >C++内存打点厘革(2)：最袖珍的垃圾接纳器

C++内存打点厘革(2)：最袖珍的垃圾接纳器

2019-06-13

C++内存打点厘革(2)：最袖珍的垃圾接纳器

C++内存打点厘革(2)：最袖珍的垃圾接纳器

副标题#e#

概述

C/C++最被人诟病的，大概是没有一个内存垃圾接纳器（确切是说没有一个尺度的垃圾接纳器）。本文接头的内容要点是，在C/C++中实现一个最袖珍的、成果受限的垃圾接纳器。这个垃圾接纳器区别于其他垃圾接纳器的主要特征是：

1. 袖珍但具实用性。整个垃圾接纳器代码行数100行阁下（不含空缺行），相当小巧。相对而言，它的成果也受到必然的限制。可是它在许多要害的场所恰恰很是有用。该垃圾接纳器以实用作为首要方针，已经成为我和身边一些同事编程的重要东西。

2. 高机能。区别于其他垃圾接纳器的是这个袖珍的垃圾接纳器非但不会导致机能的下降，反而提高了措施的时间机能（分派的速度加速）和空间机能（所占内存空间比正常的malloc/new少）。而这也是实用的重要指标。

本文算法并不巨大。技能上的对象，许多点明白就没有什么了，也许重要的意义是在于其创始性。其实，boost[1]提供的pool组件也在试图提供雷同成果的自动内存接纳本领。可是实现相对巨大且低效（基于经典的mempool技能[2]）。

此刻，你也许急着想看看，这个垃圾接纳器长什么样了。闲话少叙，那就让我们就开始一步步把答案揭开吧。

思路

领略该垃圾接纳器的要害点在于，是在于领略它的方针：为一个巨大的局部进程（算法）提供自动内存接纳的本领。

所谓局部进程（算法），是指那些算法巨大性较高，但在措施运行期所占的时间又较量短暂的进程[3]。譬喻：搜索引擎的搜索进程、读盘/存盘进程、显示（绘制）进程等等。凡是这些进程大概需要申请许多内存，并且内存分派操纵的进口点许多（就是挪用new的处所许多），假如每挪用一次new就要思量应该在什么处所delete就徒然挥霍我们名贵的脑力，使得我们无法把全力精神会合在算法自己的设计上。也许就是在这种景象下，C/C++措施员出格羡慕那些具备垃圾接纳器的语言。相对而言，假如算法巨大性不高的话，我们的措施员完全有本领节制好new/delete的匹配干系。而且，这种“一切皆在我掌控之中”的感受给了我们安详感[4]和满意感。

因此，这个垃圾接纳器的重心并不是要提供一个理论上成果完备的内存自动接纳机制。它只是针对巨大性较高的局部进程（算法），为他们提供最实效的内存打点手段。从局部进程的一开始，你就尽管去申请、利用内存，比及整个算法完成之后，这个进程申请的大部门内存（需要作为算法功效保存的破例），无论它是在算法的谁人步调申请的，均在这个竣事点上由垃圾接纳器自动销毁。我们画个示意图：

C++内存解决变化(2)：最袖珍的垃圾采取器

图 1


#p#副标题#e#

规格

我们将该垃圾接纳器定名为AutoFreeAlloc。它的接口很简朴，仅涉及两个观念：Alloc、Clear。

typedef void (*FnDestructor)(void* pThis);

class AutoFreeAlloc
{
public:
~AutoFreeAlloc(); // 析构函数。自动挪用Clear释放内存
void* Alloc(size_t cb); // 雷同于malloc(cb)
void* Alloc(size_t cb, FnDestructor fn); // 申请内存并指定析构函数
void Clear(); // 析构并释放所有分派的工具
};

为了利便，提供帮助的New操纵（上一篇中已经简朴先容实现了），概略如下：

template <class Type, class AllocType>
Type* New(AllocType& alloc); // 雷同于new Type

template <class Type, class ArgType1, class AllocType>
Type* New(ArgType1 arg1, AllocType& alloc); // 雷同于new Type(arg1)

template <class Type, class AllocType>
Type* NewArray(size_t count, AllocType& alloc);// 雷同于new Type[count]

利用样例：

AutoFreeAlloc alloc;

int* intArray = (int*)alloc.Alloc(sizeof(int)*count);
int* intArray2 = NewArray<int>(count, alloc);

* obj = New<MyClass>(alloc);
MyClass* objWithArg = New<MyClass>(arg1, alloc);
MyClass* objArray = NewArray<MyClass>(count, alloc);

// …
// 此刻，不能再会见intArray, obj, objWithArg, objArray等数据了。

内存打点机制

class AutoFreeAlloc
{
public:
enum { BlockSize = 2048 };
private:
struct _MemBlock
{
_MemBlock* pPrev;
char buffer[BlockSize];
};
enum { HeaderSize = sizeof(_MemBlock) - BlockSize };

char* m_begin;
char* m_end;
};

AutoFreeAlloc类与内存打点相关的变量只有两个：m_begin、m_end。单从变量界说来看，根基上很丢脸大白。可是有了下面这张示意图就容易领略多了：

C++内存解决变化(2)：最袖珍的垃圾采取器

图 2

#p#副标题#e#

#p#分页标题#e#

整个AutoFreeAlloc申请的内存，通过_MemBlock组成链表。只要得到了链表的头，就可以遍历整个内存链，释放所有申请的内存了。而链表的头(图中标为_ChainHeader)，可以通过m_begin计较获得：

_MemBlock* AutoFreeAlloc::_ChainHeader() const
{
return (_MemBlock*)(m_begin - HeaderSize);
}

为了使得_ChainHeader初始值为null，结构函数我们这样写：

AutoFreeAlloc::AutoFreeAlloc()
{
m_begin = m_end = (char*)HeaderSize;
}

★ 下面我们思量内存分派进程。Alloc进程主要会有三种环境，详细代码为：

void* AutoFreeAlloc::Alloc(size_t cb)
{
if (m_end – m_begin < cb)
{
if (cb >= BlockSize)
{
_MemBlock* pHeader = _ChainHeader();
_MemBlock* pNew = (_MemBlock*)m_alloc.allocate(HeaderSize + cb);
if (pHeader)
{
pNew->pPrev = pHeader->pPrev;
pHeader->pPrev = pNew;
}
else
{
m_end = m_begin = pNew->buffer;
pNew->pPrev = NULL;
}
return pNew->buffer; }
else
{
_MemBlock* pNew = (_MemBlock*)malloc(sizeof(_MemBlock));
pNew->pPrev = _ChainHeader();
m_begin = pNew->buffer;
m_end = m_begin + BlockSize;
}
}
return m_end -= cb;
}

1. 最简朴的环境，是当前_MemBlock尚有足够的自由内存(free memory)，即：

m_end – m_begin >= cb

此时，只需要将m_end前移cb字节就可以了。我们画个示意图如下：

C++内存解决变化(2)：最袖珍的垃圾采取器

图 3

#p#副标题#e#

2. 在当前的_MemBlock的自由内存（free memory）不敷的环境下，我们就需要申请一个新的_MemBlock以供利用[5]。申请新的_MemBlock，我们又会碰着两种环境：

a) 申请的字节数（即cb）小于一个_MemBlock所可以或许提供的内存（即BlockSize）。

这种环境下，我们只需要将该_MemBlock作为新的当前_MemBlock挂到链表中，剩下的事情就和景象1完全雷同。示意图如下：

C++内存解决变化(2)：最袖珍的垃圾采取器

图 4

b) 而在内存申请的字节数（即cb）大于或便是一个Block的字节数时，我们需要申请可利用内存高出正常长度（BlockSize）的_MemBlock。这个新生成的_MemBlock全部内存被用户申请。故此，我们只需要修改_ChainHeader的pPrev指针，改为指向这一块新申请的_MemBlock即可。m_begin、m_end保持稳定（当前的_MemBlock照旧当前的_MemBlock）。如图：

C++内存解决变化(2)：最袖珍的垃圾采取器

图 5

★ 下面我们思量内存释放（Clear）进程。这个进程就是遍历_MemBlock释放所有的_MemBlock的进程，很是简朴。代码如下：

void AutoFreeAlloc::Clear()
{
_MemBlock* pHeader = _ChainHeader();
while (pHeader)
{
_MemBlock* pTemp = pHeader->pPrev;
free(pHeader);
pHeader = pTemp;
}
m_begin = m_end = (char*)HeaderSize;
}

#p#副标题#e#

自动析构进程

我们知道，C++以及其他面向工具语言为工具引入告终构、析构进程。这是一个了不得的发现。因为只有这样，才气够担保工具从一开始发生以来（刚new出来），到工具销毁这整个进程，它的数据都处于完备状态，是自洽的。

我们知道，C++以及其他面向工具语言为工具引入告终构、析构进程。这是一个了不得的发现。因为只有这样，才气够担保工具从一开始发生以来（刚new出来），到工具销毁这整个进程，它的数据都处于完备状态，是自洽的。

由于垃圾接纳器认真工具的接纳，它自然不止需要存眷工具申请的内存的释放，同时也需要担保，在工具销毁之前它的析构进程被挪用。上文我们为了存眷内存打点进程，把自动析构进程需要的代码均去除了。为了支持自动析构，AutoFreeAlloc类增加了以下成员：

class AutoFreeAlloc
{
struct _DestroyNode
{
_DestroyNode* pPrev;
FnDestructor fnDestroy;
};
_DestroyNode* m_destroyChain;
};

假如一个类存在析构，则它需要在Alloc内存的同时指定析构函数。代码如下：

void* AutoFreeAlloc::Alloc(size_t cb, FnDestructor fn)
{
_DestroyNode* pNode = (_DestroyNode*)Alloc(sizeof(_DestroyNode) + cb);
pNode->fnDestroy = fn;
pNode->pPrev = m_destroyChain;
m_destroyChain = pNode;
return pNode + 1;
}

只要通过该Alloc函数申请的内存，我们在Clear中就可以挪用相应的析构。虽然，Clear函数需要增补自动析构相关的代码：

#p#分页标题#e#

void AutoFreeAlloc::Clear()
{
while (m_destroyChain)
{
m_destroyChain->fnDestroy(m_destroyChain + 1);
m_destroyChain = m_destroyChain->pPrev;
}
// 以下是原先正常的内存释放进程…
}

时间机能阐明

C++内存解决变化(2)：最袖珍的垃圾采取器void* AutoFreeAlloc::Alloc(size_t cb);

OOP技能带来一个内存上的问题是，工具粒度越来越细了，工具根基上都是小工具。这就对内存打点的机能提出了很高的要求。

假如我们以工具巨细平均为32字节计较的话，每2048/32 = 64操纵中，只有一次操纵满意m_end – m_begin < cb的条件。也就是说，在凡是环境（63/64 = 98.4%的概率）下，Alloc操纵只需要一个减法操纵就完成内存分派。

我说这是世界上最快速的内存分派算法，也许你对此仍然抱有猜疑立场。可是可以必定的一点是，要打破它的机能极限我以为已经很难很难了。

C++内存解决变化(2)：最袖珍的垃圾采取器void AutoFreeAlloc::Clear();

一般内存打点器凡是一次内存分派操纵就需挪用相应的一次Free操纵。可是AutoFreeAlloc不针对每一个Alloc举办释放，而是针对每一个_MemBlock。仍假设工具平均巨细为32字节的话，也就是相当于把64次Alloc操纵归并，为其提供一次相应的Free进程。

★ 结论：AutoFreeAlloc在时间上的机能，约莫比普通的malloc/free的快64倍。

#p#副标题#e#

空间机能阐明

我们知道，一般内存打点器为了将用户申请的内存块打点起来，除了用户需要的cb字节内存外，凡是特别还提供一个内存块的头布局，通过这个头布局将内存串通成为一个链表。一般来讲，这个头布局至少有两项（大概还不止），示意如下：

struct MemHeader
{
MemHeader* pPrev;
size_t cb;
};

仍然假设平均Alloc一次的内存为32字节。则一次malloc分派进程，就会挥霍8/32 = 25%的内存。而且由于大量的小工具存在，整个内存中的碎片（指那些自由但无法被利用的内存）将出格严重。

而AutoFreeAlloc的Alloc没有如何特别开销。整个AutoFreeAlloc，只有在将_MemBlock串为链表的有一个特另外pPrev指针，加上_MemBlock是malloc出来的，有特另外8字节开销。总计挥霍(4+8)/2048 = 0.6%的内存，险些可以忽略不计。

跋文

AutoFreeAlloc于2004-5-21开拓，只有100行的代码量。可是，这个组件得到了空前的乐成，它的应用范畴慢慢扩大，高出了我最初实现这个组件时的估量。

我徐徐沉着下来，思量这个中蕴涵的原理。我慢慢了解到了，它的乐成之处，不是它在时间、空间机能的高效，而是在于它辅佐C++措施员办理了最大的困难——内存打点。固然，这个办理方案并不是完整的。

AutoFreeAlloc是一个切入点，从它身上，让我大白了C++的new/delete的不公道；STL引入的allocator是一个切入点，从它身上，让我大白了内存打点有很强的区域性，在差异的区域（局部进程）中对allocator的需求却又不尽沟通。

我们前文也提到了一个例子：一个文档打开，编辑，直到文档被最终封锁，这个完成算不算局部进程呢？在AutoFreeAlloc办理的问题域来看，显然我们无法认为它是一个局部进程。可是，从其他allocator角度来讲，是否就有大概把它作为一个局部进程了呢？

正是思量到AutoFreeAlloc的缺陷，我们需要一个成果更强的垃圾接纳器。这就是我们下一次需要接头的组件了。

最后，仍然需要明晰的一点时。我们很难也不需要实现一个象Java、C#那样的垃圾接纳器。提供一个具备特定的内存打点本领的allocator才是正道。

[1] 请参考boost官方网站http://www.boost.org/。

[2] mempool技能是一个很成熟的内存打点技能，被sgi-stl、boost等C++库实现者回收。

[3] 真正是否要把一个进程界说为局部进程，完全取决于设计者自己。譬喻，一个文档打开，编辑，直到文档被最终封锁，这个完成算不算局部进程呢？在大部门环境下我们认为它不是一个局部进程，可是下回我们将专门接头是否有大概，以及应该如何将它作为一个局部进程。

[4] 那些提供了垃圾接纳器的语言的利用者，显然也有应用了垃圾接纳器的烦恼。譬喻C#在挪用非管束代码（如挪用Win32 api）时，这些问题变得突出，一个疏忽就留下潜在隐患。这与C/C++措施员遗憾语言没有垃圾接纳器的感受雷同。

#p#分页标题#e#

[5] 当前的_MemBlock的自由内存很大概照旧有的，可是不敷cb字节。此时我们说这里有内存碎片（memory piece）：这些碎片尽量没有人利用，可是我们把它弃而不消。

附加说明：

本文所描写的AutoFreeAlloc组件，完整代码可在WINX库(http://sourceforge.net/projects/winx)中找到。你也可以通过以下链接在线欣赏：

AutoFreeAlloc完整源代码：http://winx.cvs.sourceforge.net/winx/stdext/include/stdext/memory/AutoFreeAlloc.h?view=markup

别的， 这篇文章写的时间较早，其规格固然与此刻的AutoFreeAlloc一样，但成员函数名改了：

Alloc -> allocate

Clear -> clear

之所以这样，是因为AutoFreeAlloc被纳入stdext库（这个库可独立于winx界面库，是winx界面库的基本）。stdext库的定名气势气魄只管与STL的定名习惯一致。

    关键字：

在线提交作业