为 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 元方法即可。


lua 分配器的一些想法及实践

从周末开始, 我一直在忙一个想法。我希望给 skynet 中的 lua 服务定制一个内存分配器。

倒不是为了提升性能。如果可以单独为每个 lua vm 配置一个内存分配器，自己调用 mmap 映射虚拟内存，就可以为独立的服务制作快照了。这样可以随时 fork 出子进程，只保留关心的 vm 的内存快照。主要可以有三个用途：

    可以在快照上做序列化，并把结果返还父进程。通常做序列化有一定的时间代价，如果想定期保存的话，这个代码很可能导致服务暂停。

    可以利用快照监控检查泄露。定期做快照相比较，就能找到累积的对象。我曾经做过这样的工具 。

    可以在镜像上对快照做一些调试工作而不会影响主进程。

为什么为每个虚拟机单独配备分配器是必要的呢？

因为如果对 skynet 整个进程 fork 做出内存快照的话，当所有虚拟机共用一套内存池，很难单独把不感兴趣的内存 unmap 掉。而子进程的内存页是 COW 机制的，一旦子进程工作时间过长，会导致整体内存开销非常大。

因为 lua 本身就可以为虚拟机定制分配器，所以比较容易给出一个实现。事实上我花了半天时间就动手完成了，随后花的更多的精力是从已有项目的线上数据里采集真实的分配器工作流程的 log 用来对新写的分配器做测试。

让已有项目的分配器加上 log ，逐条记录每个 vm 分配器工作时的分配释放操作在临时文件中，再写一个脚本分析这些 log 就可以还原出内存分配器真实的工作流程。大约收集了几百个，从几千条到几千万条不等的 log 后，我就可以做测试了。

测试的过程完全还原线上程序从一开始到退出的每一个内存管理的操作，并在分配后填充入特定的字符串，并在释放的时候逐字节核对并清理。这样的流程跑下来，几乎所有的潜在 bug 都可以发现。（只要测试样本足够多，就至少能保证在现有项目中替换新的分配器不会出问题）

我定制在分配器放在了 github 上 。

从时间性能上，其实是很满意的。由于不需要考虑多线程问题，它几乎一定会比 jemalloc 这样的多线程安全的分配器要快的多。我用了一组 300 万条的真实数据对比过（由于数据比较大，没有上传到 github 上):

$ time ./testalloc skynet

real    0m0.139s
user    0m0.080s
sys     0m0.056s

$ time ./testalloc jemalloc

real    0m0.200s
user    0m0.156s
sys     0m0.040s

$ time ./testalloc malloc

real    0m0.217s
user    0m0.180s
sys     0m0.036s

可以看出 jemalloc 和 glibc 的 malloc 差别不是很大， 但定制的分配器要快的多。

我的分配策略主要分成三个，对于小于 256 字节的内存块，建立若干条 small object list 缓存复用。

对于 27 到 32K 间的内存块，每次分配 32K 的内存页，切割使用。并在回收的时候用一个链表实现的循环双向队列串起来。按回收的大小来绝对从队列的哪一头插入。分配的时候，在队列上最多移动固定数量的节点，找到最近匹配的合适节点使用。

对于大于 32K 的大内存块，则直接调用 mmap 分配。（实际在 lua vm 使用时，这种大内存块的需求非常稀少）

不过最终我对这份实现不太满意，主要是在某些测试样本中表现出了很大的碎片率。

碎片的产生是由算法产生的，因为分配器的策略是，对于小于 32K 的内存块，只会分割使用，而没有合并。如果长期运行，池中的内存会越来越碎，一旦后续有大内存请求，就会向外申请更多的内存。

我曾经想过定期对中等内存的内存页做合并整理。这个方案以前在为客户端写分配器时用过，感觉实用性不是特别高，所以这次也没有尝试。但我想过把中等内存块采用伙伴算法管理，昨天晚上完成了实现，还有少量 bug 需要调试，尚未提交到 github 。不过我对其最终的效果依旧保有怀疑。

先谈一下伙伴算法具体实现的一些问题：

如果使用伙伴算法，内存分配的单位就一定是某个最小单位长度的 2 整数幂倍。假设最小单位是 256 字节的话，能分配的大小就是 256, 512, 1024 ... 32K 这样。我查阅过采集来的数据，恰巧 lua vm 也经常申请 512, 1024, 2048 长度的内存（table 的数据区的长度）。这就有了第一个矛盾：

通常，我们需要为申请的内存多加几个字节的 cookie 保存一些分配器需要的额外信息。lua vm 在调用分配器时，会给出内存块长度，这样长度信息可以不用记录在内存块中，但对于伙伴算法，我们还需要有一个指针指向伙伴堆的管理器的位置。8 字节的 cookit 看起来是不可省的，这就导致了一种尴尬的境地：lua 通常申请 512 这种整的内存块，而加上 8 字节后，就需要用更大一级的块去满足需求。

固然我们可以把单位块的大小设成 520 这种，但按 lua 申请的翻倍策略，浪费也会越来越大。

也不是完全不能去除 cookie 的额外开销。比如，我们可以将整个 32k 的页的首地址对齐。这只需要在 mmap 时先申请 2 倍的空间 64K 。其中一定包含有一个 32K 对齐的地址，然后把不需要的部分 munmap 掉即可。且当一次对齐成功后，再申请时，通常也是对齐的。

对于 buddy 算法申请到的内存，我们只需要把地址对齐到 32K 上，就能找到当前页的头部。把每个页的第一块用于管理整个页就可以了。

一般的 lua vm 需要的 32K 页不会超过 1000 这个数量级（32 M 总开销），而伙伴算法很容易把整个页填满，活动页数量就更少了。所以在分配的时候查找的开销并不算太大。

第二个尴尬是，lua 有时候会以一些并不整的基数翻倍请求内存。这会使得上面的优化策略无效，依旧会有接近 50% 的内部碎片率。

似乎我们在使用 jemalloc 的时候也观察到过一些类似现象：在长期运行的服务器上，系统报告的内存使用情况和自己统计出来的申请内存数量相差一倍左右。

但是，如果有几千个分配器独立工作，分别使用完全独立的内存池，很可能恶化这种情况。因为 lua vm 在工作时，一旦把一块内存的需求翻倍，很可能短期就不会有后续相同的申请。如果很多 vm 共用同一个内存池，回收内存块的利用率就要高的多。