云风的 BLOG: 一个 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永远也无法被回收——你太犀利了！！

Posted by: Leo | (18) July 28, 2014 06:14 PM

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

Posted by: xu | (17) December 13, 2013 04:56 PM

很强大的东西，偷学了

Posted by: 云笔记 | (16) December 5, 2013 02:59 PM

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

Posted by: Bot.su | (15) December 5, 2013 11:29 AM

@mjohh 谢谢, 已改. btw, 下次可以直接提 pull-request

Posted by: Cloud | (14) December 3, 2013 11:22 AM

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永远也无法被回收。

Posted by: mjohh | (13) December 2, 2013 02:14 PM

支持并且期待着。

Posted by: 业务云笔记 | (12) December 2, 2013 01:29 PM

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

Posted by: proluo | (11) December 1, 2013 12:41 AM

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

Posted by: Hal | (10) November 30, 2013 10:51 PM

@Hal bpa.c:158 对 length 是为了处理任何 slice (即使不需要移动) 都计入开销. 实际上处理一个 slice 是必须读 ref 和 size 的, 也就是 sizeof(struct slice) 多线程的问题不想在这里深追究, 要根据实际情况要使用上的约束,才好做优化.

Posted by: Cloud | (9) November 29, 2013 05:26 PM

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

Posted by: Hal | (8) November 29, 2013 03:14 PM

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

Posted by: Anonymous | (7) November 29, 2013 12:33 AM

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

Posted by: Anonymous | (6) November 28, 2013 11:11 PM

支持啊尽快出书吧！！

Posted by: 好笔头 | (5) November 28, 2013 11:26 AM

求出书时间？

Posted by: Anonymous | (4) November 28, 2013 09:19 AM

所以这个是可以直接使用你制定的某个内存块这样你可以很轻松的把用到的内存dump到文件上或者transfer到远程我感觉这个概念很不错云游戏也许用得着

Posted by: geek42 | (3) November 27, 2013 06:41 PM

我是人类