The Lone Lisp Heap：孤独的单件 Lisp 堆

背景

这篇文章源自 Hacker News 社区，作者详细回顾了自己开发名为 Lone 的 Lisp 解释器的历程。Lone 是一个用“独立 C 语言”（freestanding C）编写的 Lisp 解释器。

所谓“独立 C 语言”，是指不依赖标准 C 库（如 libc）的 C 语言子集。在这种环境下，没有动态内存分配函数（如 malloc），也没有操作系统提供的底层支持。这意味着开发者必须从零开始构建一切，包括内存管理、数据结构乃至语言本身。

作者坦言，Lone 并非经过预先精心设计的产物，而是在开发过程中实时构建的。语言本身更像是其实现过程的副产品，随着作者对系统理解的加深而不断演化。起初，作者作为一个新手，被那些看似简单却近乎天真的想法所吸引，代码风格也反映了这种初学者的特质。

核心内容

1. 从零开始的内存分配器

在缺乏 malloc 的独立 C 环境中，作者必须自己编写内存分配器。最初的实现极其简陋：

• 基本结构：分配器通过链表管理内存块。每个块包含位置、大小以及“空闲/占用”的状态标记。
• 分配逻辑：采用“首次适应”（First Fit）算法。当代码请求内存时，分配器遍历链表，返回第一个大小足够的块。
• 分裂机制：如果请求的内存小于块的大小，分配器会将块分裂为两部分：一部分是恰好满足请求大小的已分配块，另一部分是剩余的空闲块。
• 合并机制：在释放内存时，如果相邻的块也是空闲的，分配器会将它们合并（Coalescing），以减少碎片。

然而，这个初始分配器性能极差：

• 线性扫描：每次分配都需要遍历链表，时间复杂度为 O(n)。
• 内存浪费：由于返回的是大块内存，对于小对象请求（如 64 字节请求返回 16 KiB 块），造成了巨大的空间浪费。
• 碎片问题：小块的空闲内存容易在链表头部堆积，导致严重的内存碎片化，甚至引发可避免的“内存不足”错误。
• 元数据开销：每个块前缀都带有描述符，导致 30%-50% 的元数据开销，且这些头部结构容易成为安全漏洞的目标。

尽管存在上述缺陷，这个简陋的分配器支撑了 Lone 长达三年。对于作者而言，当时的首要目标是能够创建对象以进行语言开发，而非追求极致性能。

2. 垃圾回收与指针扫描的挑战

随着语言功能的完善，另一个问题浮现：垃圾回收（Garbage Collection）。

Lone 采用保守式垃圾回收（Conservative GC）。为了确定栈上的值是否为指向 Lisp 对象的指针，GC 需要维护所有 Lisp 值指针的列表，并扫描栈空间进行比对。

• 暴力扫描的困境：如果简单地遍历栈上的每个字（word）并与所有 Lisp 指针进行比对，会导致二次方（Quadratic）的时间复杂度，性能灾难。
• 数据结构的需求：作者意识到需要一种更聪明的数据结构来加速指针查找，避免“二次方耻辱榜”中的低效算法。

3. 第一代堆：数组链表

受早期 Ruby 开发经验的启发，作者引入了“数组的链表”这一概念，构建了 Lone 的第一个专用堆。

• 批量分配：对象不再单独分配，而是以“块”（Chunk）为单位批量购买。每个块是一个紧密排列的 Lisp 对象数组，中间没有间隙。
• 范围检查：GC 只需检查指针是否落在某个块的地址范围内，即可判断其有效性，极大地简化了扫描逻辑。
• 复活而非分配：从机制上看，分配器并非真正“分配”新对象，而是从已分配但标记为“死亡”的块中“复活”对象。GC 将块中的槽位标记为死，当需要新对象时，直接复用这些槽位。
• 数组的优势：尽管链表在理论上显得优雅，但数组更符合处理器的缓存机制，且被计算机科学验证为解决此类问题的良方。作者感叹数组的朴素力量。

4. 指针的暴政与链表的妥协

虽然数组块提供了良好的局部性和 GC 效率，但带来了新的问题：插入性能。

• 数组的局限性：在大的单体数组块中间插入新值需要调整数组大小，成本高昂。
• 链表的引入：为了解决插入问题，作者引入了链表。新的值被放入链表节点中，如果需要更多存储，只需分配新块并链接；如果整个块死亡，则断开链接并释放。
• 混合架构：这种设计结合了链表的插入优势（O(1) 插入）和数组的存储优势（紧凑布局）。作者戏称这似乎是“峰值性能”的模样，但随即对这种架构的深层原因提出了质疑：“但为什么会这样……”（文章在此处戛然而止，暗示作者开始反思这种混合架构是否真的最优，或者是否存在更本质的问题）。

关键要点

• Freestanding C 的限制：在独立 C 环境中，开发者必须手动实现内存管理，没有 malloc 和 libc 可用。
• 初始分配器的缺陷：作者最初实现的“首次适应”分配器虽然功能完整，但存在线性扫描慢、内存碎片严重、元数据开销大等严重性能问题。
• 保守式 GC 的需求：Lone 使用保守式垃圾回收，要求高效地识别栈上的指针，这促使了专用数据结构的开发。
• 数组链表堆的设计：为了解决 GC 扫描效率问题，作者设计了基于“数组块链表”的堆。对象在块内紧密排列，GC 通过范围检查判断指针有效性。
• 性能权衡：数组提供了良好的缓存局部性和 GC 效率，但插入性能差；链表解决了插入问题，但引入了额外的指针开销。最终方案是两者的结合。
• 迭代式开发：Lone 语言并非预先设计，而是随着对系统理解的加深和实际需求的出现，通过不断重构底层数据结构（从简单内存块到数组链表）而演化出来的。

意义与影响

这篇文章不仅是一个个人项目的技术笔记，更深刻地揭示了系统编程中的权衡艺术和自底向上构建语言的复杂性。

1. 对“简单”的重新定义：作者从追求“近乎天真的简单”开始，最终构建出一个包含复杂内存管理和垃圾回收机制的系统。这展示了在底层系统中，简单的表象下往往隐藏着巨大的工程复杂度。
2. 内存管理的演进路径：文章清晰地展示了一个内存分配器从“原始手动管理”到“专用垃圾回收堆”的演进过程。这种从通用分配器到领域专用内存管理器（Domain-Specific Memory Manager）的转变，是许多高性能解释器和虚拟机（如 JVM、V8）的核心设计哲学。
3. 数据结构选择的启示：作者对数组与链表选择的反思，强调了处理器架构（缓存友好性）对软件性能的巨大影响。在微观层面，数据的物理布局（Layout）往往比算法的时间复杂度更决定实际运行效率。
4. 独立 C 语言的实践价值：在嵌入式系统、操作系统内核或高性能运行时环境中，摆脱标准库依赖并手动管理资源是一种重要的技能。Lone 的案例为理解底层内存模型提供了生动的实践视角。

尽管文章在结尾处留下了关于“指针暴政”的未解之问，但它完整地呈现了一个开发者如何通过与底层硬件和内存模型的直接对话，逐步构建出一个能运行的 Lisp 解释器的全过程。