基于垃圾回收的资源管理

基于垃圾回收的资源管理

游戏中有大量的资源数据，这部分数据通常数以百兆，甚至上G。如何在运行时管理好这些数据，也是游戏软件相对其他许多软件的一大难题。

管理这些资源分为加载和Cache两个方面。对于资源数量比较少的游戏，我们可以采用只加载不释放的方式，即使资源总量大于物理内存数，OS 在虚拟内存的管理方面也自然有它的优势。至于加载的时机，为了追求用户玩的时候的流畅体验，我们可以在一开始就进行 loading。当然也可以为了减少 loading 时间，去做动态加载。动态加载的问题比较复杂，可能涉及多线程，以及预读操作。这篇 blog 不展开谈。前段时间写过一篇动态加载资源可以参考。

如果总的资源数很大的时候，我们就需要 cache 管理。因为在 32 位 OS 下，虚拟地址空间是有限的。这里主要谈 cache 的管理。

最近我实现的一套方案是基于 gc 的。首先需要一套内存分配器，首先向 OS 索取整块的大块内存（例如一次 8M），然后使用这个自己的内存分配器在这大块内存上再管理。这个内存分配器可以实现的相对简单。因为我们将使用 gc ，不再需要 free 函数。只需要分开管理好大块内存和小块内存，提供足够的效率就可以了。

当申请的内存堆不够用时，可以有两种策略对待。其一是向 OS 索取新的内存块，其二就是 gc 。这两个策略应当根据实际情况结合使用。

gc 使用根扫描并标记的算法。用户逻辑层维护一个或几个资源的根。gc 发生时根开始做标记工作。如果正确的进行这一步，我的方法是，所有从受 gc 管理的堆中分配出来的内存，它们的 cookie 上都记录有一个 mark 函数地址。这个函数用于标记这个内存块中可能出现的相关块。mark 函数只需要每个不同的类定义一个，并在 new 出对象时注册到 cookie 上。这些对象的 new 自然是被重载过的，用于从受 gc 管理的内存堆中分配内存块出来。至于 POD 类型，注册一个空函数指针就够了。

为了实行 cache 的管理，每个被分配出来的内存块还应该设置一个 id 。我们可以通过 id 来检索出内存块地址。这样，在通过 cache 读取资源的时候，每个资源都分配一个 id ，存放在受管理的内存堆中。这些资源都不需要主动释放。一旦发生 gc ，正在使用的资源将在根扫描流程被标记。其它的资源会被回收掉。同时， id 映射表也应该在 gc 完毕后被正确的设置。

当然资源本身的关联关系错综复杂的时候，这种方法在算法简洁度上要优于引用计数的算法。而且资源占用的物理内存往往因为更加连续而得到更大的利用率。cache 的容量也更加容易控制。

我的带 gc 的内存分配器的接口大约是这样定义的（以下由实际的代码经过修改）：

struct i_gc_allocator
{
    virtual void* malloc(
          size_t size,
          unsigned id,
          void (*mark_func)(void *, void (*)(void *))
    ) = 0;
    virtual size_t gc() = 0;
    virtual void expand() = 0;
    virtual mark(void *root) = 0;
    virtual void* find(unsigned id) = 0;
};

这里只提供了 malloc 来分配内存。并且可以在分配内存的同时给内存块赋予 id。以后可以通过 find 来找回内存。当我们频繁加载资源的时候，这可以用来保证每份资源都唯一的被加载一次。 expand 用来向 OS 申请新的内存块。 mark 函数可以从一个 root 内存块开始标记。而 gc 就用于回收内存堆。它有一个返回值，表示 gc 完成后内存中还有多少残留数据。这可以用来作为是否要调用 expand 的一个参考。这个接口用于比较底层的控制，真正使用时还需要进一步的封装。

对于一般的 POD 类型，只用简单的调用 malloc(size,id,0) 就可以了。复杂的类型可以按如下实现：

class gcdata {
    void *data;
    static void mark(void *addr,void (*m)(void *)) {
        gcdata *self=(gcdata*)addr;
        m(self->data);
    }
public:
    gcdata(i_gc_allocator *gc) {
        data=gc->malloc(100,0,0);
    }
    void* operator new(size_t s,unsigned id,i_gc_allocator *gc) {
        return gc->malloc(s,id,mark);
    }
    void operator delete(void *p,unsigned,i_gc_allocator *gc) {}
};

我们这里给出了一个想受到 gc 管理的资源类型的例子：gcdata 。这个对象中有一个成员变量 data 指向一块另外分配出来的长度为 100 字节的内存。这里的 mark 函数就用于标记对象中gcdata 这个自行申请的内存块 data。它使对象被扫描时，data 可以一起被扫描到。

gcdata *obj=new (id,allocator) gcdata(allocator);

当我们通过 allocator 构造出这个对象时，对象占用的内存就会受到管理。

allocator->mark(obj);
allocator->gc();

在 gc 前调用 mark 将保证 obj 对象不会被回收掉。

这个 gc 模块并不去整理内存，分配出来的内存不会再移动了，这可以简化很多设计。

云风 提交于 March 8, 2006 09:51 PM|固定链接

COMMENTS

应该加上个mark内存移动管理,否则还是有可能产生大量的小碎片的,影响到内存的分配.其实java虚拟机的实现代码就是这样管理的,我自己没做过不好说,仅仅建议一下

Posted by: hpking | (13)January 14, 2008 10:33 AM

多线程的问题不在这里讨论范围之内。以上代码只是示意。

ps. 扫描的过程是很快的。

Posted by: Cloud| (12)March 24, 2006 05:56 PM

你在扫描的时候不加锁的吗？

Posted by: 当代最伟大的预言师 | (11)March 24, 2006 05:32 PM

既然你读了我的书，那么你这个问题在书上 208,209 页有详细分析。

另外，最好不要在 blog 上发主题无关的回复，我有专门的留言本的 :)

Posted by: Cloud| (10)March 21, 2006 11:03 PM

云风，看了您的书感受非常深。最近想学习用vc内嵌汇编使用mmx指令优化内存存取，但遇到一个非常辣手的问题，希望您能够帮我看看。

#include"windows.h"
#include<iostream>
using namespace std;

void fn16(unsigned char *mem1,unsigned char *mem2,unsigned long dwSize)
{

_asm
{
pushf
mov ecx,dwSize
mov esi,mem1
mov edi,mem2
///mmx优化部分//////////////////////////////////////////////
again2:
cmp ecx,16 //是否比16字节大
jl notbeggerthan16
movq mm0,[esi]
movq mm1,[esi+8]
movq [edi],mm0
movq [edi+8],mm1
add esi,16
add edi,16
sub ecx,16
jmp again2

notbeggerthan16:
cmp ecx,8
jl notbeggerthan8
movq mm0,[esi]
movq [edi],mm0
add esi,8
add edi,8
sub ecx,8
jmp notbeggerthan16
////////////非mmx优化部分/////////////////////////////////////////
notbeggerthan8:
start8:
cmp ecx,0
jz end
mov ax,[esi] //假设内存大小是16的倍数
add esi,2
mov [edi],ax
add edi,2
sub ecx,2
jmp start8
end:
emms
popf
}//end _asmsm

}

void main()
{
SYSTEMTIME st;
GetSystemTime(&st);
unsigned long timeBegin0=st.wSecond;
unsigned long timeBegin=st.wMilliseconds;
unsigned char *mem1=new unsigned char[2048*2000];
unsigned char *mem2=new unsigned char[2048*2000];

for (int i=0;i<=100;i++)
{
fn16(mem1,mem2,2048*2000);
}

GetSystemTime(&st);
unsigned long timeEnd0=st.wSecond;
unsigned long timeEnd=st.wMilliseconds;

unsigned long pass=(timeEnd0-timeBegin0)*1000+timeEnd-timeBegin;
cout<<pass;
}

以上程序负责把mem1中dwSize个字节的数据传入mem2。实验后发现：
当所传字节数在2048*500左右的时候，使用mmx后明显快近一倍的速度。而当dwSize>2048*2000的时候 却没有什么区别。不知道为何。

我对比的方法是：把“////优化部分///”和“//非优化部分///”之间的部分注释掉即为非优化的程序。通过看循环100次的时间差来判断快慢。

Posted by: 姚洁 | (9)March 21, 2006 03:12 PM

云风,windows vista今年又可能开始卖了.程序员应该如何面对新的挑战呢?又要如何做好准备呢?
你能写篇文章谈谈你的观点吗?

Posted by: 天生爱玩 | (8)March 9, 2006 09:42 PM

"并不去整理内存，分配出来的内存不会再移动了"

没看懂挖。
8M一块，是不是等8M里面没有正在使用的内存块的时候释放这个8M，否则整个8M都留下？
申请内存的时候先去已有的这些个8M里分配，不行的话就expand？

Posted by: huangyi | (7)March 9, 2006 07:15 PM

明白你的意思了。
按照这个思路到了内存空间不足的时候就是整体清除再来过了吧

Posted by:Zenberg| (6)March 9, 2006 04:27 PM

gc 不整理内存，所以只是扫描一下。速度跟内存块的个数有关，而不会移动大块内存，所以不会有停顿感。

Posted by: Cloud| (5)March 9, 2006 03:24 PM

怎么解决在gc时候的停顿呢？

Posted by: 当代最伟大的预言师 | (4)March 9, 2006 01:53 PM

内存块全部是一个接一个放在整块内存中的。根扫描就是用来标记被使用块，除掉被使用块，剩下全部是可以被释放的。

内存碎片是内存管理程序都会产生的，如何避免是内存管理模块的工作。这种 gc 会延缓内存释放的操作，可以进一步缓解内存碎片的产生。

Posted by: Cloud| (3)March 9, 2006 10:45 AM

不整理内存，随着分配和释放的不断进行，会很快产生很多内存碎片，导致缓存块虽有足够空间却无法满足分配对象的请求，这时就把整块内存都释放？

Posted by: liaoliao | (2)March 9, 2006 09:11 AM

没看明白你说的回收动作是如何进行的，如果说gc时候正使用的资源被标记其他的被gc，那么你一定还有判断资源有没有被使用的方式，是否仍类似于引用计数？
效率上不去说，理解上没有引用计数容易理解...^_^