« 云风:一个编程的自由人(图灵访谈) | 返回首页 | Skynet 的服务监控及远程调用 »

一个 Bump Pointer Allocator

最近抽时间在读 Milo Yip 翻译的《游戏引擎架构》。书还没有出版,我应邀给这个译本写序,所以先拿到了电子版,正在加紧读一遍。全书接近 800 页,我已经读了 600 页左右,希望这个周末可以抽时间读完。

这本书是由顽皮狗的主程之一 Jason Gregory 写的,内容很精彩,Milo Yip 翻译的也相当不错。有很多章节我读的很有共鸣,想先挑一点来写写。

由于作者的主要技术背景是 Console game 开发,而 Console 目前内存非常有限,且没有虚拟内存,对内存的管理和使用就非常苛刻。很多 PC 平台上几乎被忽视的问题到了 Console 平台上就需要仔细考虑了。我很有共鸣是因为 10 多年前在开发大话西游时,要求在 64M 内存上跑起来,同样写了好多内存管理相关的代码。

比如栈式内存管理,就是在堆上模拟一个栈,只管分配,然后记住一个标记点一起释放。

又比如双端分配器,自己管理一大块内存,根据需求不同从两端向中间分配,这个还可以配合上面的分配器一起工作。

把对象的生命期绑定在渲染帧上,在一帧渲染完后把当帧的临时内存全部释放;或者做的更复杂一点,做一个乒乓开关,临时内存可以保留到下一帧结束。呵呵,这些以前都写过。

04 年的时候在网易公司内部做个一个比赛,就是在一块固定大小的内存内实现自己的内存管理器。用我们从梦幻西游,以及大话西游的客户端中实际采集来的数据做比赛评分,分别按允许速度和碎片率打分。我自己虽然没有参赛,但当时也写过一份程序拿到了最高分 :) 当时比赛的前三名现在都是网易项目(或离职后是新公司的主程)的主程。


现在关注的问题不太一样了,在 PC 平台上开发,一般就直接把 jemalloc 等成熟库拿来用,不太关注这部分的优化了。只在最近做 iOS 开发才重新和阿楠讨论过内存受限平台的内存管理问题。我们定制了一个 iOS 上供 Lua 用的特制分配器,用实际项目的数据采集结果做特定优化,效果还不错。


书中提到顽皮狗的引擎在做资源管理时,一律使用 handle 而不是直接内存地址指针来索引对象。这样,所有被内存管理器管理的内存块都是可以被移动的。因为使用的是 handle 来做相互引用,就不存在指针重定位问题。

引擎可以利用空闲时间,慢慢做内存整理工作。把释放掉的内存块空间压实,做到内存碎片率为零。Cache 利用率也相当高。

如果所有的引擎模块都是自己维护,那么这么做相当棒,据说顽皮狗的引擎可以保证这一点。即使用了第三方库,谨慎选择这些库,通过定制分配器也可以适配的不错。

我以前想过这个做法,但没有实际试验过。书读到这里,突然有了点兴趣。Talk is cheap, show me the code . 花了点时间,我写了段简单的代码实现了这么一个 Bump Pointer Allocator

这个库可以管理你指定的内存块,切割内存使用。所有内存块都用 id 索引,id 不会复用(在 32bit 用完前),所以你可以方便的知道一个 id 已经无效,这相当于支持了弱引用。从 id 映射到地址的操作是 O(1) 的,非常廉价,在显式执行整理操作前,内存不会移动。

内存分配也是 O(1) 的,只在少数情况下会退化成 O(n) 。释放操作只是减引用,也是 O(1) 的。内存整理工作可以定帧调用,虽然它需要 stop the world ,但可以保证在固定时间做完至少一步(除非有单个内存块特别大)。

内存块支持引用计数,由于有弱引用支持,所以使用者可以比较容易的回避循环引用的问题。

它还有许多改进空间:例如支持多线程;支持某些块禁止移动,方便外部保有指针。

如果谁有兴趣可以加以改进。

Comments

@mjohh

产生一个sz==0的slice,导致该slice之后的slice永远也无法被回收——你太犀利了!!

位图式的内存管理,核心是collct;之前只看过链表式的,链表上只记录当前块大小(和下一个指针),不存在“夯实”比较简单。

很强大的东西,偷学了

最近要在做及时对战类游戏,通讯频繁,一局游戏大概半小时左右。内存线程日志等其他技术都有现成的,就通讯不是很理想,求推荐一款免费开源通讯引擎。

@mjohh

谢谢, 已改.

btw, 下次可以直接提 pull-request

collect函数有一个bug:当第1到第n个slice的ref count都>0, 且n*sizeof(struct slice) > COLLECT_STEP_LENGTH, collec 一个step将进入if (length > COLLECT_STEP_LENGTH) {...}分支,产生一个sz==0的slice,导致该slice之后的slice永远也无法被回收。

支持并且期待着。

哎,04年,还记得那年第一次玩梦幻西游,跟着想着将来毕业一定要去网易写程序,现在毕业了,从技术上,比当年和主程你接近了,当时实际上,比当年还远

额,我应该这样说,对那些移动的了slice你有加了一次头部167: length += sz * ALIGN_SIZE; 这个sz包括了头部。有点吹毛求疵了,强迫症,囧

@Hal

bpa.c:158 对 length 是为了处理任何 slice (即使不需要移动) 都计入开销.

实际上处理一个 slice 是必须读 ref 和 size 的, 也就是 sizeof(struct slice)

多线程的问题不想在这里深追究, 要根据实际情况要使用上的约束,才好做优化.

看了下代码,多线程支持会不会很影响效率呢?看了下,几乎大部分函数操作都要上锁。是不是可以考虑每一个线程有一个bpa_heap呢?然后这之后要做的事情就要和很多成熟库一样(TCMalloc,Jemalloc)了。另外bpa.c:158 length += sizeof(struct slice) ;这句是不是不必要的呀。

感觉和windows的堆管理HeapCreate、HeapAlloc、HeapCompact相似。

感觉和windows的堆管理函数
HeapCreate,HeapAlloc啥的比较相似

支持啊尽快出书吧!!

求出书时间?

所以这个是可以直接使用你制定的某个内存块 这样你可以很轻松的把用到的内存dump到文件上 或者transfer到远程

我感觉这个概念很不错 云游戏也许用得着

我是人类

书大概什么时候出版?一定要买一本来看看.

Post a comment

非这个主题相关的留言请到:留言本