为 lua 配一个合适的内存分配器
以前版本的 lua 缺省是调用的 crt 的内存分配函数来管理内存的。但是修改也很方便,内部留下了宏专门用来替换。现在的 5.1 版更为方便,可以直接把外部的内存分配器塞到虚拟机里去。
有过 C/C++ 项目经验的人都知道,一个合适的内存分配器可以极大的提高整个项目的运行效率。所以 sgi 的 stl 实现中,还特别利用 free list 技术实现了一个小内存管理器以提高效率。事实证明,对于大多数程序而言,效果是很明显的。VC 自带的 stl 版本没有专门为用户提供一个优秀的内存分配器,便成了许多人诟病的对象。
其实以我自己的观点,VC 的 stl (我用的 VC6 ,没有考察更新版本的情况)还是非常优秀的,一点都不比 sgi 的版本差。至于 allocator 这种东西,成熟的项目应该根据自己的情况来实现。即使提供给我一个足够优秀的也不能保证在我的项目中表现最佳,那么还不如不提供。基础而通用的东西,减无可减的设计才符合我的审美观。sgi 版 stl 里的 allocator 就是可以被减掉的。
好了,不扯远了。今天想谈的是,如何为 lua 定制一个合适的内存分配器。
lua 是基于 C 的哲学设计出来的东西,而不像 python ,看起来是 C 写的,但是处处充满了 C++ 的味道。在 C 里,内存管理函数可不仅仅 malloc 和 free 两个。还有一个更重要的 api 是 realloc 。lua 就是用 realloc 来实现可变长度的数组的。( Lua 定义的 realloc 和 C 标准稍有不同,参见 Lua 参考手册 中 lua_Alloc 的定义)
这种再分配方式在 C++ 风格的程序中已经几乎废弃,但是在 C 程序中屡见不鲜。这是因为 C 结构通常设计的很简单,简单的值 copy 就已经够用了。realloc 可以保证新分配出来的内存完全复制了旧内存的数据,在分配器合理设计下,甚至不需要移动内存就可以原地扩展出空间来。这样,一个可变长的数组的实现(Lua 里大量用到)就可以做的非常高效。(可能比 C++ 的 std::vector 要高效的多。)
设计一个合理的 realloc 却比较困难,我们需要对项目进行具体分析。好在 lua VM 的行为并不复杂,其元操作就那么几个。对其做内存管理上的优化就变的简单起来。
云风这里提供一个初步的思路给大家参考:
通常我们会用 free list 的机制加速小内存的分配。对 free list 不太清楚的朋友,可以找本侯杰的《STL 源码剖析》 一读。针对小内存分配的请求,通常我们会让 free list 系统返回最合适的 free node 。这样对于 C++ 的大部分应用来说,是最经济的。
但是于 lua ,效果可能相反。lua 的很多东西,比如 table ,就依赖一个可增长的 vector 的实现。在增长的初期,增长的频率还是很高的。刚好合适的尺寸,反而会导致每次 realloc 时做多余的 memcpy 。
其实我们只用做一个小小的修改。每次新的分配请求的时候,返回一个最大的节点即可。那么预先分配好的 free list 池满之前,小内存的增长要求总可以就地得到满足。
下一步,在预分配的内存池满了以后,我们只需要执行一个回收过程。把每个节点扫描一遍,把有冗余空间的节点一分为二。收集来的零碎足可以满足又一批小内存的请求。
由于 Lua 基于 gc 工作,我们也可以在 lua 自己 gc 时做这样的操作。便又可以将打碎的小内存块合并起来了。
ps. 增加一个自定义的 gc 环节并不困难。只需要注册一个 userdata 到 lua state 里,并不做任何引用。 然后给这个 userdata 加一个 gc 元方法即可。
Comments
Posted by: jason | (9) February 2, 2009 04:50 PM
Posted by: jason | (8) February 2, 2009 04:15 PM
Posted by: Cloud | (7) January 23, 2008 07:29 PM
Posted by: 真木 | (6) January 23, 2008 04:57 PM
Posted by: Cloud | (5) July 2, 2007 07:37 PM
Posted by: ro4tub | (4) July 2, 2007 05:41 PM
Posted by: wang | (3) May 24, 2007 08:32 PM
Posted by: dreamsun | (2) December 12, 2006 08:47 PM
Posted by: dreamsun | (1) December 12, 2006 08:46 PM