垃圾回收系列

原文: http://terrylee.me/blog/post/2010/09/25/garbage-collection-and-performance-part1.aspx

垃圾回收系列（1）：没有GC，世界将会怎样

最近在公司内部做了一次关于垃圾回收的讲座，我打算用几篇文章把讲座的内容整理出来，供大家参考。在开始之前，我们有必要稍微复习一下内存分配的主要方式，大多数主流语言都支持三种内存分配方式：

1. 静态分配：静态变量和全局变量的分配形式
2. 自动分配：在栈中为局部变量分配内存的方法
3. 动态分配：在堆中动态分配内存空间以存储数据的方式

如何管理堆对象的生命周期，正是我们要探讨的话题。从面向对象的角度来看，每个对象的生命周期应该由自己管理，也就是说，作为一个对象，它知道自己什么时候被创建，什么时候被销毁。然而事实上却不是这样，因为对象之间有相互引用关系，所以对象往往不知道自己什么时候可以宣告死亡，如果对象释放太早，会造成“悬空引用”问题；如果释放的太晚或者不释放，又会造成内存泄露问题。

在C/C++中提供了显式的内存管理方案，可以用malloc/new来显式分配一段内存，而当这段内存不再需要的时候，使用free/delete把它返回给系统，看下面这段代码：

int main()
{
    string *ptr = new string;

// do something

delete ptr;
}

这个过程非常的自然清晰，不是吗？在使用之前用new分配一段内存，使用完毕后再用delete销毁。可惜的是，现实世界中的代码不都是这么简单，开发人员会由于各种各样的原因，而忘记释放内存，或者释放内存不正确，从而导致内存泄露。下面是一个典型的内存泄露示例：

void service(int n, char** names)
{
for(int i=0; i< n; i++)
    {
char* buf = (char*) malloc(strlen(names[i]));

        strncpy(buf,names[i], strlen(names[i]));
    }    
}

显然这里释放内存的工作应该由开发人员完成，但开发人员却忘记了调用free()。

void service()
{
    Node* x = new Node("mid-autumn");
    Node* ptr = x;
delete x;
    cout << ptr->data << endl;     
}

这段代码的问题在于不正确的调用了delete，提前释放了x的内存而导致最后一句ptr->data出错。麻烦的事情远不止这些，继续看下面这段代码：

int main()
{
    string *ptr = new string[100];

// do something

delete ptr;
}

这段代码中看起来很美，使用new来为100个string对象分配内存，最后也使用了delete来销毁，但不幸的是这段代码仍然不正确，这里为100个string对象分配的对象，最后可能有99个string未必删除，原因在于没有使用相同形式的new和delete，正确的应该为：

int main()
{
    string *ptr = new string[100];

// do something

delete [] ptr;
}

注意到最后那个[]了吗？简单的说，在调用new时使用了[]，在调用delete时也要使用[]。但这条规则又不像我们说的这么简单，有了typedef，在调用new时可能没有使用[]，但是在调用delete时却要使用[]，如下面这段代码：

typedef string address[4];

int main()
{
    string *ptr = new address;

// do something

delete [] ptr;
}

噩梦还没有到此结束，如果我们有两个类型Array和NamedArray，其中NamedArray公有继承于Array，如下面的代码所示：

template<class T>
class Array
 {
public:
        Array(int lowBound, int highBound);
        ~Array();
private:
        vector<T> data;
        size_t size;
int lBound, int hBound;
};

template<class T>
class NamedArray : public Array<T> 
{
public:
        NamedArray(int lowBound, int highBound, const string& name);
private:
        string* aName;   
};

开发人员在使用上面两个类型时，写了这样一段代码：

int main()
{
   NamedArray<int> *pna = new NamedArray<int>(10,20,"Users");
   Array<int> *pa;
   pa = pna;

// do something

delete pa;
}

看出问题所在了吗？最后一行调用delete并不能释放aname所占用的内存，原因在于Array类型的析构函数~Array()并没有被声明为virtual！所以父类的析构函数并没有表现出多态的特性。

通过上面的几个例子，想必大家已经体会到了显式管理内存的困难，于是在C++里出现了智能指针的概念，来减少开发人员手工管理内存出错的可能性，最常见的如STL中的std::auto_ptr，本质上它也是个普通的指针，只不过std::auto_ptr会在析构的时候调用 delete 操作符来自动释放所包含的对象。

int main()
{
   auto_ptr<int> ptr(new int(42));

   cout << *ptr << endl;

// 不再需要delete了
}

在大名鼎鼎的Boost C++库中更是包含了很多的智能指针，可用于各种情况，如作用域指针boost::scoped_ptr，共享指针boost::shared_ptr等等，如下代码所示：

#include <boost/shared_ptr.hpp> 
#include <vector> 

int main() 
{ 
  std::vector<boost::shared_ptr<int> > v; 
  v.push_back(boost::shared_ptr<int>(new int(1))); 
  v.push_back(boost::shared_ptr<int>(new int(2))); 
} 

对象生命周期管理，除了使用显式管理方案之后，还有一种机制就是隐式管理，即垃圾回收（Garbage Collection，简称为GC），最早出现于世界第二元老语言Lisp中，Jean E. Sammet曾经说过，Lisp语言最长久的贡献之一是一个非语言特征，即代表了系统自动处理内存的方法的术语极其技术——垃圾回收（GC，Garbage Collection）。而现在很多平台和语言都支持垃圾回收机制，如JVM、CLR、Python等。在下一篇文章中将会介绍几种经典的垃圾回收算法。

垃圾回收系列（2）：几种经典的垃圾回收算法

本文是关于垃圾回收讲座的第二篇，第一篇为《垃圾回收系列（1）：没有GC，世界将会怎样》。本文主要关注垃圾回收算法。垃圾回收机制，最早出现于世界上第二元老语言Lisp，Jean E. Sammet曾经说过，Lisp语言最长久的共享之一是一个非语言特征，即代表了系统自动处理内存的方法的术语极其技术——垃圾收集（GC，Garbage Collection）。接下来我们介绍几种经典的垃圾回收算法，这些算法尽管出现于60、70年代，但是现在的CLR、JVM等上面的垃圾回收器，仍然使用了它们。

引用计数算法

引用计数（Reference Counting）算法是每个对象计算指向它的指针的数量，当有一个指针指向自己时计数值加1；当删除一个指向自己的指针时，计数值减1，如果计数值减为0，说明已经不存在指向该对象的指针了，所以它可以被安全的销毁了。可以很直观的用下面的图表示：

引用计数算法的优点在于内存管理的开销分布于整个应用程序运行期间，非常的“平滑”，无需挂起应用程序的运行来做垃圾回收；而它的另外一个优势在于空间上的引用局部性比较好，当某个对象的引用计数值变为0时，系统无需访问位于堆中其他页面的单元，而后面我们将要看到的几种垃圾回收算法在回收前都回遍历所有的存活单元，这可能会引起换页（Paging）操作；最后引用计数算法提供了一种类似于栈分配的方式，废弃即回收，后面我们将要看到的几种垃圾回收算法在对象废弃后，都会存活一段时间，才会被回收。

引用计数算法有着诸多的优点，但它的缺点也是很明显的。首先能看到的一点是时间上的开销，每次在对象创建或者释放时，都要计算引用计数值，这会引起一些额外的开销；第二是空间上的开销，由于每个对象要保持自己被引用的数量，必须付出额外的空间来存放引用计数值；引用计数算法最大的缺点就在于它无法处理环形引用，如下图所示：

此处蓝色的这两个对象既不可达也无法回收，因为彼此之间互相引用，它们各自的计数值都不为0，这种情况对引用计数算法来说是无能为力的，而其他的垃圾回收算法却能很好的处理环形引用。

引用计数算法最著名的运用，莫过于微软的COM技术，大名鼎鼎的IUnknown接口：

interface IUnknown
{
virtual HRESULT _stdcall QueryInterface
        (const IID& iid, void* * ppv) = 0;
virtual ULONG _stdcall AddRef() = 0;
virtual ULONG _stdcall Release() = 0;
}

其中的AddRef和Release就是用来让组件自己管理其生命周期，而客户程序只关心接口，而无须再去关心组件的生命周期，一个简单的使用示例如下：

int main()
{
    IUnknown* pi = CreateInstance();

    IX* pix = NULL;
    HRESULT hr = pi->QueryInterface(IID_IX, (void*)&pix);
if(SUCCEEDED(hr))
    {
        pix->DoSomething();
        pix->Release();
    }

    pi->Release();
}

上面的客户程序在CreateInstance中已经调用过AddRef，所以无需再次调用，而在使用完接口后调用Release，这样组件自己维护的计数值将会改变。下面代码给出一个简单的实现AddRef和Release示例：

ULONG _stdcall AddRef()
{
return ++ m_cRef;
}

ULONG _stdcall Release()
{
if(--m_cRef == 0)
    {
delete this;
return 0;
    }
return m_cRef;
}

在编程语言Python中，使用也是引用计数算法，当对象的引用计数值为0时，将会调用__del__函数，至于为什么Python要选用引用计数算法，据我看过的一篇文章里面说，由于Python作为脚本语言，经常要与C/C++这些语言交互，而使用引用计数算法可以避免改变对象在内存中的位置，而Python为了解决环形引用问题，也引入gc模块，所以本质上Python的GC的方案是混合引用计数和跟踪（后面要讲的三个算法）两种垃圾回收机制。

标记-清除算法

标记-清除（Mark-Sweep）算法依赖于对所有存活对象进行一次全局遍历来确定哪些对象可以回收，遍历的过程从根出发，找到所有可达对象，除此之外，其它不可达的对象就是垃圾对象，可被回收。整个过程分为两个阶段：标记阶段找到所有存活对象；清除阶段清除所有垃圾对象。

标记阶段：

清除阶段：

相比较引用计数算法，标记-清除算法可以非常自然的处理环形引用问题，另外在创建对象和销毁对象时时少了操作引用计数值的开销。它的缺点在于标记-清除算法是一种“停止-启动”算法，在垃圾回收器运行过程中，应用程序必须暂时停止，所以对于标记-清除算法的研究如何减少它的停顿时间，而分代式垃圾收集器就是为了减少它的停顿时间，后面会说到。另外，标记-清除算法在标记阶段需要遍历所有的存活对象，会造成一定的开销，在清除阶段，清除垃圾对象后会造成大量的内存碎片。

标记-缩并算法

标记-缩并算法是为了解决内存碎片问题而产生的一种算法。 它的整个过程可以描述为：标记所有的存活对象；通过重新调整存活对象位置来缩并对象图；更新指向被移动了位置的对象的指针。

标记阶段：

清除阶段：

缩并阶段：

标记-压缩算法最大的难点在于如何选择所使用的压缩算法，如果压缩算法选择不好，将会导致极大的程序性能问题，如导致Cache命中率低等。一般来说，根据压缩后对象的位置不同，压缩算法可以分为以下三种：

1. 任意：移动对象时不考虑它们原来的次序，也不考虑它们之间是否有互相引用的关系。
2. 线性：尽可能的将原来的对象和它所指向的对象放在相邻位置上，这样可以达到更好的空间局部性。
3. 滑动：将对象“滑动”到堆的一端，把存活对象之间的*单元“挤出去”，从而维持了分配时的原始次序。

节点拷贝算法

节点拷贝算法是把整个堆分成两个半区（From，To）， GC的过程其实就是把存活对象从一个半区From拷贝到另外一个半区To的过程，而在下一次回收时，两个半区再互换角色。在移动结束后，再更新对象的指针引用，GC开始前的情形：

GC结束后的情形：

节点拷贝算法由于在拷贝过程中，就可以进行内存整理，所以不会再有内存碎片的问题，同时也不需要再专门做一次内存压缩。，而它最大的缺点在于需要双倍的空间。

总结

本文总共介绍了四种经典的垃圾回收算法，其中后三种经常称之为跟踪垃圾回收，因为引用计数算法能够平滑的进行垃圾回收，而不会出现“停止”现象，经常出现于一些实时系统中，但它无法解决环形问题；而基于跟踪的垃圾回收机制，在每一次垃圾回收过程中，要遍历或者复制所有的存活对象，这是一个非常耗时的工作，一种好的解决方案就是对堆上的对象进行分区，对不同区域的对象使用不同的垃圾回收算法，分代式垃圾回收器正是其中一种，CLR和JVM中都采用了分代式垃圾回收机制，但它们在处理上又有些不同，后面的文章再详细介绍这两种垃圾回收器的区别。

垃圾回收系列（3）：CLR与JVM垃圾回收器的比较

本文为垃圾回收讲座的第三篇，在前面两篇（一、二）文章里介绍了手工管理内存带来的一些问题，以及一些经典的GC算法。本文我们主要关注微软的CLR与JVM垃圾回收器方面的比较。我们知道CLR和JVM都采用了分代式垃圾回收器，而分代式垃圾回收器则基于以下几点假设：

1. 对象越新，其生存期就越短
2. 对象越老，其生存期就越长
3. 对堆的一部分执行GC比对整个堆执行GC要快

CLR和JVM尽管都采用了分代式垃圾回收器，但是它们在很多处理方面都有些不同：分代机制，大对象堆，回收模式，回收算法，寻找存活对象效率等。

分代机制

在CLR中，对象按年龄可以分为三代：第0代、第1代、第2代，如下图所示：

 

在这三代之间，对象代的提升过程，大家可以参考《CLR via C#》，里面有比较详细的介绍。

JVM中对于对象的分代式新生代和旧生代：

回收模式

在CLR4.0之前，提供三种不同的垃圾回收模式：工作站并发GC、工作站非并发GC以及服务器GC，如下图所示：

工作站非并发GC模式，没有专门的GC线程，而是由工作线程负责回收，在回收过程中，需要暂时挂起应用程序，回收结束后应用程序继续运行，所以在回收过程中会有应用程序暂停现象：

工作站并发GC模式，为了解决在执行垃圾回收时引起的应用程序暂停问题，会有一个专门的GC线程负责垃圾回收，大多数时间垃圾回收都可以应用程序并发执行，但是仅仅是针对Full GC，而对于第0代、第1代对象，仍然会使用非并发模式执行，并发垃圾回收本质上牺牲了更多的CPU时间和内存来换取应用程序暂停时间的减小：

服务器GC模式运行在多CPU服务器上，如果在单CPU机器上配置了使用服务器GC，不会起任何作用，垃圾回收仍然会使用工作站非并发模式执行。服务器GC模式为每个CPU分配一个专用的垃圾回收线程和一个托管堆，并且该垃圾回收线程具有较高的优先级，在执行垃圾回收期间，应用程序工作线程会暂时挂起：

CLR 4.0中提供了后台垃圾回收机制，用于取代并发GC。

JVM（以Hotspot为例）中使用的垃圾回收更为复杂，针对新生代、旧生代在工作站和服务器上，分别使用不同的垃圾回收模式，如下图所示：

在Client端默认的方式为串行GC，而在服务端，对于新生代和旧生代默认的方式分别为：并行回收GC和并行GC：

下图体现了默认串行GC与并行GC之前的区别，并行GC会把堆分成多个区，分区进行标记和回收，但这两种方式都会引起应用程序的暂停：

下图体现了默认的标记缩并回收与并发GC，在并发GC中，标记的总共分为三个阶段，分别为：Initial Mark、Concurrent Marking和Remark，只有在Initial Mark和Remark阶段才会引起应用程序暂停，而在Concurrent Marking和清除阶段都是与应用程序并发执行，并不会引起暂停：

回收算法

在CLR中有专门的大对象堆（LOH），超过85000字节的对象将会分配在LOH上面，只有在进行第2代对象垃圾回收时才会同时对LOH进行回收，即一次Full GC。第0代、第1代、第2代对象所在的堆称之为小对象堆（SOH）。

在CLR中，对于小对象堆SOH，采用的回收算法为标记-缩并算法，由于移动大对象比较耗费时间，所以在LOH上，CLR采用了标记-清除算法，即只做对象的清除并不对大对象堆进行压缩。

在JVM中，对于新生代对象采用节点复制算法进行回收，这也是为什么我们在上面的图中，新生代对象堆分为S0和S1的原因，有时也称之为为From和To；对于旧生代对象根据不同的回收模式，采用不同的回收算法：

串行GC：标记-缩并算法（滑动缩并）
并行GC：标记-缩并算法
并发GC：标记-清除算法

提高查找存活对象的效率

现在考虑这样一个问题，只对第0代（或者新生代）对象做回收，在查找存活对象过程中（不关是标记-缩并还是节点复制算法），从根集合开始，如果发现有一个根对象指向了第1代、第2代（或者旧生代），为了提高效率，垃圾回收器将会立即终止这条线上的查找：

这样带来的一个问题是:如果在第0代（或者新生代）分配的对象X，没有根对象指向它，但有一个第1代或者第2代（旧生代）的对象，指向了该新创建的对象：

此时虽然没有根对象可以到达新创建的对象X，但由于有其他代的对象指向它，所以它仍然不能当做垃圾回收，为了解决这个问题，人们提出了各种解决方案，常见的有：

1. 记忆集
2. 硬件标记
3. 虚拟页面标记
4. 字标记
5. 卡标记

由于硬件标记需要特定的硬件平台来支持，所以不具有可移植性，现在更多的垃圾回收器都使用了软件解决方案，在CLR和JVM上都使用了卡标记技术，即把托管堆分成一个一个的卡片，这个卡片代表一个抽象的概念（卡片的大小可以等于一个字，也可以等于一个虚拟页面）。如果有卡片上的对象发生了变化，则在Card Table中做一个标记，在查找存活对象时，除了要查找根对象之外，还有查找Card Table中标记的对象所引用的对象：

在CLR和JVM上所使用的卡片大小也不相同，CLR为128字节一个卡片，而JVM上为512字节一个卡片。在更新卡片过程中，它们都是按字节（Byte）进行更新而不是按位（Bit）进行更新。

垃圾回收系列（4）：GC性能调优及总结

本文为垃圾回收讲座第四篇，也是最后一篇。前三篇（一、二、三）分别介绍了手工管理内存带来的一些问题，一些经典的GC算法以及CLR与JVM在垃圾回收方面的比较。本文将会简单介绍垃圾回收性能调优的话题，以及给大家推荐一些垃圾回收的资料和开源项目。

GC性能调优

无论对于哪方面的调优，数据库调优、网络调优还是垃圾回收调优，其遵循的过程都是一样的：首先要评估现状，当前的状况是什么样的，收集相关的数据；再次设定一个目标，即我们调优要达到什么目的，而不是盲目的进行调整；然后做一些调优方面的尝试，并对调优的结果进行验证，看看尝试调优的结果如何，最后再进行一些细微调整。调优的过程不是一蹴而就的，而是我们可能要在反复去做这几个步骤，如下图所示：

在评估现状阶段，主要是收集现阶段的运行数据，典型的数据如：

a. 垃圾回收（新、Full GC）频率
b. 垃圾回收（新、Full GC）花费时间
c. 旧生代（第2代、大对象堆）对象数量

幸运的是，不管是在CLR上面还是JVM上，都有大量的工具能够帮助我们完成数据的收集：

CLR：CLR Profiler、VSTS、Windows Performance Monitor、Windbg + SOS
JVM：GC日志、GC Portal、JConsole、JVisualVM/VisualGC、JMap

如下图所示使用JConsole监控应用程序内存使用情况，以及GC时间等，完整的JConsole使用方法可以参考这里。

下图为使用CLR Profiler查看托管堆上各代对象情况：

GC性能调优的第二阶段是确定调优的目标：如降低垃圾回收（新、Full GC）频率；减少垃圾回收（新、Full GC）时间；减少由于垃圾回收造成应用程序暂停时间等等。接下来根据制定的目标进行一些优化，Full GC频率太高，是因为有大量的新对象被提升，造成2代（旧生代）空间占满，从而导致Full GC太频繁，那我们就需要考虑降低Full GC的频率，如是不是由于Finalize()方法导致；扩容2代（旧生代）大小（JVM）；修改程序（缓存的东西太多）等。

上面只是简单介绍了GC性能调优的几个步骤，并没有特别具体介绍在CLR和JVM如何调优（说实话，在CLR上面，什么都不用去做，因为没得选择）。总之，在做GC性能调优时，牢记墨菲定律：
a. 任何事都没有表面看起来那么简单
b. 所有的事都会比你预计的时间长
c. 会出错的事总会出错
d. 如果你担心某种情况发生，那么它就更有可能发生

GC资料推荐

迄今为止，唯一一本介绍垃圾收集的书籍《Garbage Collection》，书中的内容相当全面，从垃圾回收算法到各种垃圾回收器，都有介绍，可惜中文版已经绝版：

全书共12章。第1章首先介绍计算机存储器管理的演化和自动内存回收的需求，并引入了本书所使用的术语和记法。第2章介绍了3种“经典”的垃圾收集技术：引用计数（reference counting）、标记－清扫（mark-sweep）和节点复制算法（copying）。 随后的4章更详细地讨论了上述这些垃圾收集方式和标记－缩并（mark-compact）收集。第7章和第8章分别介绍了在现代垃圾收集实现中具有重要地位的分代式（generational）垃圾收集和渐进式（incremental）垃圾收集。第9章和第10章扩展了垃圾收集的领域，讨论了如何让垃圾收集能够在无法得到来自语言编译器的支持的环境（分别是C和C++）中运行。第11章讨论了一个相对较新的研究领域 -- 垃圾收集和硬件数据cache的相互作用。第12章简要地考察了用于分布式系统的垃圾收集。

另外，研究垃圾回收还可以从开源项目中获益：

libgc：开源的C/C++垃圾回收器实现，详细信息可以到这里了解。另外，在Sun网站上有一篇文章作了详细的介绍。
sscli：CLI的开源实现，只可惜从.NET 2.0之后就再也没有更新过，也是目前唯一可以了解CLR垃圾回收细节的源代码。
manualgc：网易云风写的C垃圾回收器，代码只有短短的几百行，里面有些数据结构的设计相当精妙，大家可以学习一下。