- 浏览: 4169698 次
最新评论
C++内存管理变革(2):最袖珍的垃圾回收器
<iframe align="center" marginwidth="0" marginheight="0" src="http://www.zealware.com/csdnblog.html" frameborder="0" width="728" scrolling="no" height="90"></iframe>
主题推荐
内存管理
变革
c++
内存分配
搜索引擎
猜你在找
<script type="text/javascript">
var searchtitletags = ' C++内存管理变革(2):最袖珍的垃圾回收器' + ',' + '内存管理,变革,c++,内存分配,搜索引擎';
searchService({
index: 'blog',
query: searchtitletags,
from: 10,
size: 10,
appendTo: '#res-relatived',
url: 'recommend',
his: 2,
client: "blog_cf_enhance",
tmpl: '<dd style="background:url(http://static.blog.csdn.net/skin/default/images/blog-dot-red3.gif) no-repeat 0 10px;"><a href="#{ url }" title="#{ title }" strategy="#{ strategy }">#{ title }</a></dd>'
});
</script>
<script type="text/javascript">
new Ad(5, 'ad_bot');
</script>
<script type="text/javascript">
$(function ()
{
$("#ad_frm_0").height("90px");
setTimeout(function(){
$("#ad_frm_2").height("200px");
},1000);
if($("#comment_content").length>0)
{
$("#quick-reply").show();
$("#quick-reply").click(function(){
setEditorFocus();
});
}
var d_top = $('#d-top-a');
document.onscroll = function ()
{
var scrTop = (document.body.scrollTop || document.documentElement.scrollTop);
if (scrTop > 500)
{
d_top.show();
} else
{
d_top.hide();
}
}
$('#d-top-a').click(function ()
{
scrollTo(0, 0);
this.blur();
return false;
});
});
</script><style type="text/css">
.tag_list
{
background: none repeat scroll 0 0 #FFFFFF;
border: 1px solid #D7CBC1;
color: #000000;
font-size: 12px;
line-height: 20px;
list-style: none outside none;
margin: 10px 2% 0 1%;
padding: 1px;
}
.tag_list h5
{
background: none repeat scroll 0 0 #E0DBD3;
color: #47381C;
font-size: 12px;
height: 24px;
line-height: 24px;
padding: 0 5px;
margin: 0;
}
.tag_list h5 a
{
color: #47381C;
}
.classify
{
margin: 10px 0;
padding: 4px 12px 8px;
}
.classify a
{
margin-right: 20px;
white-space: nowrap;
}
</style>
最袖珍的垃圾回收器
许式伟
2005-7-17
关键字: 内存管理 垃圾回收 AutoFreeAlloc
keyword: memory manage, gc, garbage collection, AutoFreeAlloc
概述
C/C++最被人诟病的,可能是没有一个内存垃圾回收器(确切是说没有一个标准的垃圾回收器)。本文讨论的内容要点是,在C/C++中实现一个最袖珍的、功能受限的垃圾回收器。这个垃圾回收器区别于其他垃圾回收器的主要特征是:
1. 袖珍但具实用性。整个垃圾回收器代码行数100行左右(不含空白行),相当小巧。相对而言,它的功能也受到一定的限制。但是它在很多关键的场合恰恰非常有用。该垃圾回收器以实用作为首要目标,已经成为我和身边一些同事编程的重要工具。
2. 高性能。区别于其他垃圾回收器的是这个袖珍的垃圾回收器非但不会导致性能的下降,反而提高了程序的时间性能(分配的速度加快)和空间性能(所占内存空间比正常的malloc/new少)。而这也是实用的重要指标。
本文算法并不复杂。技术上的东西,很多点明了就没有什么了,也许重要的意义是在于其首创性。其实,boost[1]提供的pool组件也在试图提供类似功能的自动内存回收能力。但是实现相对复杂且低效(基于经典的mempool技术[2])。
现在,你也许急着想看看,这个垃圾回收器长什么样了。闲话少叙,那就让我们就开始一步步把谜底揭开吧。
思路
理解该垃圾回收器的关键点在于,是在于理解它的目标:为一个复杂的局部过程(算法)提供自动内存回收的能力。
所谓局部过程(算法),是指那些算法复杂性较高,但在程序运行期所占的时间又比较短暂的过程[3]。例如:搜索引擎的搜索过程、读盘/存盘过程、显示(绘制)过程等等。通常这些过程可能需要申请很多内存,而且内存分配操作的入口点很多(就是调用new的地方很多),如果每调用一次new就要考虑应该在什么地方delete就徒然浪费我们宝贵的脑力,使得我们无法把全力精力集中在算法本身的设计上。也许就是在这种情形下,C/C++程序员特别羡慕那些具备垃圾回收器的语言。相对而言,如果算法复杂性不高的话,我们的程序员完全有能力控制好new/delete的匹配关系。并且,这种“一切皆在我掌控之中”的感觉给了我们安全感[4]和满足感。
因此,这个垃圾回收器的重心并不是要提供一个理论上功能完备的内存自动回收机制。它只是针对复杂性较高的局部过程(算法),为他们提供最实效的内存管理手段。从局部过程的一开始,你就只管去申请、使用内存,等到整个算法完成之后,这个过程申请的大部分内存(需要作为算法结果保留的例外),无论它是在算法的那个步骤申请的,均在这个结束点上由垃圾回收器自动销毁。我们画个示意图:
图 1
规格
我们将该垃圾回收器命名为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 <strong>AllocType</strong>></class>
Type* New(AllocType& alloc); // 类似于new Type
template <class>Type, class <strong>ArgType1</strong>, class <strong>AllocType</strong>></class>
Type* New(ArgType1 arg1, AllocType& alloc); // 类似于new Type(arg1)
template <class>Type, class <strong>AllocType</strong>></class>
Type* NewArray(size_t count, AllocType& alloc);// 类似于new Type[count]
使用样例:
AutoFreeAlloc alloc;
int* intArray = (int*)alloc.Alloc(sizeof(int)*count);
int* intArray2 = NewArrayint>(count, alloc);
MyClass* obj = NewMyClass>(alloc);
MyClass* objWithArg = NewMyClass>(arg1, alloc);
MyClass* objArray = NewArrayMyClass>(count, alloc);
alloc.Clear();
// ...
// 现在,不能再访问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。单从变量定义来看,基本上很难看明白。但是有了下面这张示意图就容易理解多了:
图 2
整个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
<!-- Baidu Button BEGIN -->
<script>window._bd_share_config = { "common": { "bdSnsKey": {}, "bdText": "", "bdMini": "1", "bdMiniList": false, "bdPic": "", "bdStyle": "0", "bdSize": "16" }, "share": {} }; with (document) 0[(getElementsByTagName('head')[0] || body).appendChild(createElement('script')).src = 'http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion=' + ~(-new Date() / 36e5)];</script><!-- Baidu Button END --><!--192.168.100.35--><!-- Baidu Button BEGIN --><script type="text/javascript" id="bdshare_js" data="type=tools&uid=1536434"></script><script type="text/javascript" id="bdshell_js"></script><script type="text/javascript">
document.getElementById("bdshell_js").src = "http://bdimg.share.baidu.com/static/js/shell_v2.js?cdnversion=" + Math.ceil(new Date()/3600000)
</script><!-- Baidu Button END --> {
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;
_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字节就可以了。我们画个示意图如下:
m_end – m_begin >= cb
此时,只需要将m_end前移cb字节就可以了。我们画个示意图如下:
图 3
2. 在当前的_MemBlock的自由内存(free memory)不足的情况下,我们就需要申请一个新的_MemBlock以供使用[5]。申请新的_MemBlock,我们又会遇到两种情况:
a) 申请的字节数(即cb)小于一个_MemBlock所能够提供的内存(即BlockSize)。
这种情况下,我们只需要将该_MemBlock作为新的当前_MemBlock挂到链表中,剩下的工作就和情形1完全类似。示意图如下:
这种情况下,我们只需要将该_MemBlock作为新的当前_MemBlock挂到链表中,剩下的工作就和情形1完全类似。示意图如下:
图 4
b) 而在内存申请的字节数(即cb)大于或等于一个Block的字节数时,我们需要申请可使用内存超过正常长度(BlockSize)的_MemBlock。这个新生成的_MemBlock全部内存被用户申请。故此,我们只需要修改_ChainHeader的pPrev指针,改为指向这一块新申请的_MemBlock即可。m_begin、m_end保持不变(当前的_MemBlock还是当前的_MemBlock)。如图:
图 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;
}
自动析构过程
我们知道,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函数需要补充自动析构相关的代码:
void AutoFreeAlloc::Clear()
{
while (m_destroyChain)
{
m_destroyChain->fnDestroy(m_destroyChain + 1);
m_destroyChain = m_destroyChain->pPrev;
}
// 以下是原先正常的内存释放过程...
}
时间性能分析
void* AutoFreeAlloc::Alloc(size_t cb);
OOP技术带来一个内存上的问题是,对象粒度越来越细了,对象基本上都是小对象。这就对内存管理的性能提出了很高的要求。
如果我们以对象大均为32字节计算的话,每2048/32 = 64操作中,只有一次操作满足m_end – m_begin
我说这是世界上最快速的内存分配算法,也许你对此仍然抱有怀疑态度。但是可以肯定的一点是,要突破它的性能极限我觉得已经很难很难了。
void AutoFreeAlloc::Clear();
一般内存管理器通常一次内存分配操作就需调用相应的一次Free操作。但是AutoFreeAlloc不针对每一个Alloc进行释放,而是针对每一个_MemBlock。仍假设对象平均大小为32字节的话,也就是相当于把64次Alloc操作合并,为其提供一次相应的Free过程。
★ 结论:AutoFreeAlloc在时间上的性能,大约比普通的malloc/free的快64倍。
空间性能分析
我们知道,一般内存管理器为了将用户申请的内存块管理起来,除了用户需要的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++程序员遗憾语言没有垃圾回收器的感觉类似。
附加说明:
本文所描述的AutoFreeAlloc组件,完整代码可在WINX库中找到。你也可以通过以下链接在线浏览:
另外,这篇文章写的时间较早,其规格虽然与现在的AutoFreeAlloc一样,但成员函数名改了:
Alloc -> allocate
Clear -> clear
之所以这样,是因为AutoFreeAlloc被纳入stdext库(这个库可独立于winx界面库,是winx界面库的基础)。stdext库的命名风格尽量与STL的命名习惯一致。
相关文章:《C++内存管理变革》
<script type="text/javascript">
new Ad(4, 'ad_cen');
</script>
<script type="text/javascript">
var fileName = '2239173';
var commentscount = 0;
var islock = false
</script><script type="text/javascript" src="http://static.blog.csdn.net/scripts/comment.js"></script>核心技术类目
全部主题
Hadoop
AWS
移动游戏
Java
Android
iOS
Swift
智能硬件
Docker
OpenStack
VPN
Spark
ERP
IE10
Eclipse
CRM
JavaScript
数据库
Ubuntu
NFC
WAP
jQuery
BI
HTML5
Spring
Apache
.NET
API
HTML
SDK
IIS
Fedora
XML
LBS
Unity
Splashtop
UML
components
Windows Mobile
Rails
QEMU
KDE
Cassandra
CloudStack
FTC
coremail
OPhone
CouchBase
云计算
iOS6
Rackspace
Web App
SpringSide
Maemo
Compuware
大数据
aptech
Perl
Tornado
Ruby
Hibernate
ThinkPHP
HBase
Pure
Solr
Angular
Cloud Foundry
Redis
Scala
Django
Bootstrap
相关推荐
C++高手必过内存管理关,探讨C++内存回收,C++内存泄漏及其检测工具
C内存管理内存管理是C++最令人切齿痛恨的问题,也是C++最有争议的问题,C++高手从中获得了更好的性能,更大的自由,C++菜鸟的收获则是一遍一遍的检查代码和对C++的痛恨,但c,除非放弃C++,转到Java或者.NET,他们的...
本文从内存管理、内存泄漏、内存回收这三个方面来探讨C++内存管理问题。
c++内存管理 c++内存管理 c++内存管理 c++内存管理 c++内存管理
用C++实现的自动垃圾回收器,是单线程版的
在linux下写的单线程与多线程的C++垃圾回收器。是C++编程艺术一书中的垃圾回收的linux版本。
在C++程序中进行垃圾回收的代码,使用标记-回收算法,支持多继承,对象数组的回收。详细的介绍在我的blog http://blog.csdn.net/winux/archive/2007/09/01/1768777.aspx
解决由heap 内存泄露问题。 是“编程艺术"中的改良版本
C_C++ 内存管理算法和实现 Memory Management Algorithms and Implementation in C_C++ C_C++ 内存管理算法和实现 Memory Management Algorithms and Implementation in C_C++ C_C++ 内存管理算法和实现 ...
内存管理是C++最令人切齿痛恨的问题,也是C++最有争议的问题,C++高手从中获得了更好的性能,更大的自由,C++菜鸟的收获则是一遍一遍的检查代码和对C++的痛恨,但内存管理在C++中无处不在,内存泄漏几乎在每个C++...
内存管理是C++最令人切齿痛恨的问题,也是C++最有争议的题,C++高手从中获得了更好的性能,更大的自由,C++菜鸟的收获则是一遍一遍的检查代码和对C++的痛恨,但内存管理在C++中无处不在,内存泄漏几乎在每个C++程序...
内存管理是C++最令人切齿痛恨的问题,也是C++最有争议的问题,C++高手从中获得了更好的性能,更大的自由,C++菜鸟的收获则是一遍一遍的检查代码和对C++的痛恨,但内存管理在C++中无处不在,内存泄漏几乎在每个C++...
相信不少人都在为c++的内存泄露问题而苦恼,此书从内存资源管理和函数等方面教你怎样管理内存。 共48页,分三章,分别讲述内存管理、内容泄漏和垃圾回收。
C++内存管理技术内幕.pdf C++内存管理技术内幕.pdf
侯捷在博览网的C++内存管理课程
C++内存回收机制,说明继承等C++数据结构如何回收
这不是智能指针!这是内存集中管理的GC器,基于RAII。AutoGC简单的C++垃圾回收器,基于c++11标准的多线程。这是源码和lib+示例。
在JAVA 和 C# 中都有垃圾回收功能,程序员在分配一段内存后可以不再理会,而由垃圾回收自动回收,从而使程序员从复杂的内存管理中解脱出来。这是JAVA 和 C#的一大优点。而C++程序员在用 new 分配了一段内存后,还...
本人收集的关于内存方面的经典文档,压缩包里涵盖了目前基本所有的c/c++关于内存的文章,C和C++内存管理资料(包括内存管理-内存泄漏-内存调试-内存检测方法) 还有一个文档介绍电网的调试技巧