为 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
呃，又看了一下，原来lua里把realloc当free用。
Posted by: jason | (9) February 2, 2009 04:50 PM
lua的内存分配只能自定义lua_Alloc，却不能自定义free，所以lua_Alloc不管怎么实现，一定是要基于malloc的。
不能算真正可以装配的内存分配器。
Posted by: jason | (8) February 2, 2009 04:15 PM
realloc 的含义必须是保证数据也能被复制过去，所以一定要 memcpy。
这个可以在 lua 手册中查到。
Posted by: Cloud![[TypeKey Profile Page]](https://blog.codingnow.com/nav-commenters.gif)
| (7)
January 23, 2008 07:29 PM
其他的我还不明白，
有一点就是说，如果一个宿主系统没有 realloc 功能函数
就要自己写一个类似的，malloc之后memcpy一下，对吧？
直接用 malloc会有问题...难怪，搞了我半个月了...
Posted by: 真木 | (6) January 23, 2008 04:57 PM
to ro4tub, 你不自己定义出内存管理器，最新的 lua 根本不会让你构建出虚拟机啊 :q
"Adding custom memory allocation to Lua or Python is more complex.It requires changes to their internal code."
过时的消息吧？lua 的标准 api `lua_newstate` 强制要求你提供一个内存分配器给它用。而为兼容之前的 `lua_open` 已经不被提倡使用了。（它会为你配置一个缺省的内存分配器。）
这篇文章是给出一个“合适”的内存分配器的建议，而不是“如何”定制。
关于如何定制的问题，lua 手册已经写的很清楚了：
写一个 `lua_Alloc` 就 ok 了。
ps. 其实在早期的版本中，更改 lua 的内存分配器也不是难事，改改 luaconf.h 重新编译就够了。更早的版本，也只需要动源文件中的一个宏定义。
Posted by: Cloud![[TypeKey Profile Page]](https://blog.codingnow.com/nav-commenters.gif)
| (5)
July 2, 2007 07:37 PM
说实话，看完了这篇文章，仍是不知道如何给lua vm定制内存管理器。可能使我的悟性比较差。
我记得在game programming gems6上一篇文章中比较lua/python/gamemonkey/anglescript时，提到"Adding custom memory allocation to Lua or Python is more complex.It requires changes to their internal code."
Posted by: ro4tub | (4) July 2, 2007 05:41 PM
草 你 吗 你写的什么 几 毛 玩意
Posted by: wang | (3) May 24, 2007 08:32 PM
但是看见过一本讲如何做写游戏脚本语言的600多页的书就是基于lua的.等手头的书弄完就借来一阅,学无止境!
Posted by: dreamsun | (2) December 12, 2006 08:47 PM
还没有看lua脚本语言,大体还不知道怎么回事呢.后面要学习的,云风已经用的很熟练了,哎呀!差距啊!
Posted by: dreamsun | (1) December 12, 2006 08:46 PM