C++ 中的生成式垃圾收集器

• 下载源代码文件 - 2 Kb
• 下载演示项目 - 8 Kb

引言

编写这段代码的灵感来源于一篇题为《基于对象生命周期的实时垃圾收集器》的论文，作者是 H. Liberman 和 C. Hewitt。在论文中，作者描述了一个堆存储框架，该框架使得对短期对象的存储比对长期对象的存储更经济。尽管该算法是为 LISP 和类似系统提出的，但相同的概念也被应用于 C++。论文可以在以下网址找到： http://lieber.www.media.mit.edu/people/lieber/Lieberary/GC/Realtime/Realtime.html

动态内存管理通常是指在程序执行的不同过程中向操作系统请求内存。所有动态内存请求都通过一个称为堆的内存区域来满足。在 C++ 中，这通过 new 操作符来实现。该操作符通过调用 malloc 来实现，malloc 在堆上分配内存后，会返回一个指向该对象的指针。然而，这种动态获取内存的灵活性是有代价的：即程序员有责任使用 delete 操作符将动态分配的内存返回到空闲池中。delete 操作符又会调用 free，后者会回收堆上分配的内存。调用 delete 后，对象被销毁，其析构函数被调用。进一步访问指针数据可能导致不可预测的结果。

"垃圾收集"（Garbage Collection）是一个自动化的过程，用于查找程序不再可访问的先前分配的内存，然后将其回收以供将来使用。垃圾收集器通过多种方式实现这一点，其中一种方法是遍历堆上的所有指针并查找弱指针（允许对象内存被回收的指针）。简单来说，使用垃圾收集器可以减轻程序员每次调用 new 时都担心调用 delete 的负担。自动垃圾收集器可以将大型软件的开发周期缩短约 30%，并进一步减少内存泄漏，从而实现更稳定的系统。

一些系统还使用引用计数来实现垃圾收集，但它们也存在一些令人不安的缺点。

1. 无法回收循环结构，即即使是垃圾，循环结构也可能具有非零计数。
2. 经常导致内存碎片化。
3. 成本高昂，因为每次分配/释放都需要进行加/减运算。

由于上述问题，使用引用计数作为内存管理问题的首要解决方案是不可行的，尤其是当程序代码量开始增加时。尽管如此，公共领域可用的垃圾收集器实现非常少。其中一个是由 Silicon Graphics 提供的。这是为 gcc 编译器设计的一个通用的、可进行垃圾收集的存储分配器。所使用的算法在以下文献中有所描述：

1. Boehm, H., and M. Weiser, "Garbage Collection in an Uncooperative Environment", Software Practice & Experience, September 1988
2. Boehm, H., A. Demers, and S. Shenker, "Mostly Parallel Garbage Collection", Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design and Implementation, SIGPLAN Notices 26, 6 (June 1991), pp. 157-164.

设计方法

该垃圾收集器维护的堆由几个代组成。用户通过包装指针类 Pointer<T> 创建指针。一旦发出内存分配请求，垃圾收集器就会返回一个指向对象的指针（在自己的堆空间中创建），并记录其地址（请记住指针本身是在栈上创建的）在一个 vector<void**> 中。同样，对象的大小也会被记录下来，用于将来的分代复制。一旦包装指针超出作用域，或者进行指针赋值，就会运行垃圾收集算法，以验证所有指针的完整性。垃圾收集算法包括将所有可访问的对象移出当前代，将它们迁移到另一代，然后遍历堆以解决指向最近重新定位对象的*所有*指针。最后，当前代内存将被回收。如果当前代中有任何不可达数据，也会一并回收。

垃圾收集器功能由一个名为 GC 的类实现。它拥有所有静态成员函数。在程序执行的任何时候，都可以通过调用 GC::Collect() 来强制启动垃圾收集过程。可以通过调用 GC::GetMaxGeneration() 来查询代数上限。如果您想知道垃圾收集器管理的内存上分配的总字节数，可以调用 GC::GetTotalBytesAllocated()。

class GC
{
private: 
//Array of pointers to pointers that are made on the stack 
	static std::vector< void**	> _PointersOnStack; 
//  Holds the size of objects that are made on the stack 
	static std::vector<unsigned int > _SizeOfObjects;  
//Holds all the generations 
	static std::vector< Generation* >  _Generations;
// Holds total bytes allocated on the heap
	static int BytesAllocated;

public:
// Invokes the GC for all generations
	static void Collect();
// Invokes the GC only upto and including the generation specified
	static void Collect( Generation*& pGeneration );
// Call this to allocate memory from the garbage collector
	static void* operator new( size_t, void** pStackPtr );
// Gets maximum number of generations that have been made
	static int GetMaxGeneration();
// Gets the total memory (bytes) that has been allocated on the heap
	static int GetTotalBytesAllocated() { return BytesAllocated; }
// Returns the total number of generations in the GC
	static int GetGenerationCount() { return _Generations.size(); }	
// Sets the total bytes that have been allocated by the garbage collector
	static void SetTotalBytesAllocated( int Value ) { BytesAllocated = Value; }
};

在垃圾收集过程中迭代的指针必须指向 Pointer<T> 类型的对象。该类实现了智能指针的功能。它重载了赋值运算符和自动转换运算符等多个运算符。每当 Pointer 对象超出作用域或进行赋值时，就会调用垃圾收集过程。

template <class T>
class Pointer 
{
private:
// Invoked on assignment and destruction
	void Destroy()
	{
		p = NULL;
		GC::Collect();		
	}
public:
// Wrapped pointer
	T* p;
// Constructor
	Pointer( T* p_ =  NULL ) : p( p_ )	{} 
// Destructor 
	~Pointer() 
		{ GC::SetTotalBytesAllocated( GC::GetTotalBytesAllocated()
		                                               - sizeof( *p )
		);p->~T(); // Explicitely call the destructor
		Destroy();
	}
// Assignment operator 1
	Pointer& operator = ( Pointer<T> & p_ ) { return operator = ( ( T* ) p_); }
// Assignment operator 2
	Pointer& operator = ( T* p_ ) 
	{     
		Destroy();
		p =  
		p_; return *this;
	} 
// Automatic type conversion to
	T* operator T*() { return p;} 
// Dereferencing
	operator T& operator*() { return *p; } 
// Pointer indirection    
	operator T*operator->() { return p; }    
// For automatic type conversion during new call
	operator void**() { return ( void** ) & p; }
};

堆的各个代由一个名为 Generation 的类实现。每一代都封装了一个连续内存区域的表，因此，通过使新创建的对象彼此靠近，可以减少缺页中断，并且对象也会驻留在处理器缓存中。有很多代，并且代号最高的代包含最近创建的对象。每一代都有一定的容量，当堆上的对象超出该容量时，会自动创建一个新代。将一代标记为“已废弃”并收集因弱引用而丢失的内存的过程称为扫描。

class 
Generation {  
private:
// The generation number int
	_GenerationNumber;
// Pointers to the objects in the generation 
	std::vector<void* >  _Pointers;
// Points to the top of memory available in the generation
	void* _pTopOfMemory;
// The generation allocates memory from this location	
	void* _pNextObjPtr;
// Returns maximum size available for one generation
	static int MaxSize;
// Table of memory inside generation
	BYTE MemoryTable[MaxSize];
public:
// Gets the remaining memory of the Generation
	int GetRemainingMemory() const;
// Returns maximum memory that can be allocated for one generation
	int GetTotalMemory() const { return MaxSize; }
// Allocates memory for an object and returns its void*
	void* Allocate( size_t Size );
// Gets the generation number
    int GetGenerationNumber() const { return _GenerationNumber; }
// Performs bitbybit copying 
	static void* CopyBitByBit( const void* pSourceLocation, size_t Size,
	                                      Generation* pTargetGeneration );
// delete operator	
	void operator delete( void* v ) { free( v ); }	
public:
	Generation( int GenNumber = 0 );
};

如何使用

使用内置的"::operator new" 分配的对象是不可收集的。只有使用重载的 new 操作符（其第二个参数是指针的地址）分配的对象才是可收集的。为了方便编程，我还编写了 Pointer 到 void** 的自动转换函数。

void* operator new( const size_t sz, void** pVoid )
{
	return GC::operator new( sz , pVoid );
}

例如，以下代码演示了上述垃圾收集器在对象创建和使用方面的差异：

int* pInt = new int; // Traditional approach to create pointers - memory leaks !!!	
Pointer<int> pInt = new(pInt) int; // My approach - no memory leaks

运行演示程序，并在 WinNT/2k 的任务管理器中查看内存分配。您会观察到有无垃圾收集器时系统性能的显著差异。为了证明垃圾收集的质量，我还重载了全局的 new 和 delete 操作符，以增加和减少内存分配计数器。该计数器是检测程序内存泄漏的宝贵指标。

之前，我曾在使用 GC 堆上分配的指针调用虚函数时遇到许多问题，但现在这些问题都已解决。目前尚未实现数组对象的内存分配，但将在不久的将来实现。我非常欢迎任何关于改进垃圾收集器设计和功能的建议。

修订历史

2002 年 6 月 26 日 - 调整了代码的大小和格式，以防止滚动