Lone Lisp 单一堆架构：从指针暴政到统一内存管理的工程重构

动态语言的内存管理长期处于两难境地：通用分配器灵活但碎片化严重，专用分配器高效却难以扩展。Lone Lisp 的实现者 Matheus Moreira 在三年实践中完成了从多堆链表到单一统一堆的架构跃迁，这一过程揭示了指针语义对内存布局的深层约束，以及索引化表示带来的架构自由度。

多堆设计的隐性成本

Lone Lisp 最初采用典型的「链表 + 数组」混合结构：维护一个 chunk 链表，每个 chunk 内含固定长度的 value 数组。这种设计在垃圾回收场景下表现良好 ——GC 只需检查指针是否落入某个 chunk 的地址范围即可判定是否为堆对象。然而，这种架构很快暴露根本性缺陷。

指针的「暴政」在于其不可变性。当 chunk 需要扩容时，传统指针语义要求重新分配数组并复制数据，这将使所有指向原数组的指针失效。对于 Lisp 这种一切皆引用的语言，这意味着全局性的指针更新，或根本性的架构限制。Moreira 将这一现象称为「指针的 NIMBY 效应」—— 指针拒绝迁移，迫使整个世界围绕它们重构。

此外，链表结构本身带来显著的开销。每个 chunk 的元数据、指针维护、以及跨 chunk 的碎片化，使得内存利用率难以优化。GC 虽然能通过地址范围快速判定指针归属，但分配新 value 时仍需遍历链表寻找空闲槽位，复杂度随堆规模线性增长。

索引化：解耦 value 与内存位置

破局之道在于彻底解耦 value 标识与内存地址。Lone Lisp 将 value 从指针改为索引值，堆结构退化为一个巨大的扁平数组。value 不再直接指向内存，而是表示为数组下标，实际指针在访问时动态计算：

struct lone_lisp_heap_value *value_of(struct lone_lisp *l, struct lone_lisp_value v) {
    size_t index = extract_index(v);
    return &l->heap.values[index];
}

这一改动彻底消除了 resize 的语义障碍。数组可以任意移动、扩展或收缩，所有已存在的 value 依然有效 —— 它们只是索引，而非物理地址。这种「位置无关性」为后续的内存优化打开了空间。

重构后的堆结构简化为单一数组，配合 Linux 的 mremap 系统调用，可以实现零拷贝的堆扩展。mremap 允许内核直接重组页表，将虚拟地址映射到新的物理页，无需复制现有数据。Moreira 的实现中，堆容量按倍数增长，扩展操作仅涉及页表更新，耗时与堆大小无关。

工程实现的关键参数

单一堆架构的落地需要精确的参数设计。Lone Lisp 将 value 结构对齐到 64 字节，这恰好匹配主流处理器的 cache line 大小，确保单个 value 不会跨页边界，同时也优化了缓存友好性。

内存管理从字节级别提升到页级别。堆初始容量配置为固定数量的 value 槽位，通过 mmap 匿名映射申请。当容量耗尽时，mremap 以原子方式扩展映射区域。这种设计将复杂的分配策略简化为单一的数组索引管理，大幅降低了实现复杂度。

然而，单一堆并非银弹。Lone Lisp 的分配器仍需线性扫描查找死亡的 value 进行复用，分配操作的复杂度保持 O (n)。这与传统的空闲链表或 segregated free list 相比，在分配密集型场景下可能成为瓶颈。此外，所有 value 类型共享同一数组，可能导致缓存污染 —— 频繁访问的 cons cell 与较少访问的大型结构体交错存储，破坏空间局部性。

架构选择的适用边界

单一堆架构最适合以下场景：对象生命周期差异不大、GC 频率较高、对堆动态扩展有强需求。对于对象类型差异极大的系统，或分配模式高度可预测的场景，传统的多堆 / 分代策略可能更优。

可落地的实施要点包括：

• value 大小对齐到 cache line（通常为 64 字节）
• 初始容量设置需权衡启动开销与扩展频率
• 考虑在 value 头部嵌入世代标记，为未来分代 GC 预留扩展点
• 监控堆扩展频率，频繁扩展可能暗示初始容量配置过小

Lone Lisp 的演进表明，内存架构的选择本质上是语义层与性能层的权衡。索引化表示牺牲了指针的直接访问效率，换取了内存布局的完全自由度。这种 trade-off 在需要频繁 resize 或实现复杂 GC 算法的场景中，往往能带来长期的维护收益。

资料来源

• Matheus Moreira, "The lone lisp heap", 2025
• Linux Programmer's Manual, mremap(2)

systems