在将 Clojure 代码编译到 Lua 运行时环境时，持久化数据结构的实现是一个核心挑战。Clojure 依赖 Persistent HAMT（Hash Array Mapped Trie）和位分区 trie 来实现高效的不可变向量与映射，而 Lua 本身只提供可变的表结构。本文基于 ClojureFnl 项目的最新实践，分析将这类数据结构移植到 Fennel 时需要考虑的内存布局、分支因子权衡以及结构共享的实现机制。

为什么需要真正的持久化结构

在早期尝试中，社区通常使用简单的「写时复制」方案配合 Lua 元表来实现不可变数据结构。这种方法在理论上是可行的 —— 只要内部表也是不可变的，修改外层映射时只需复制被更改的路径上的节点。但实际运行时会发现性能问题极为严重。以 itable 库为例，每次关联操作都可能触发大量深拷贝，在处理包含数万条记录的映射时，性能会下降数百倍。

ClojureFnl 项目的作者意识到，若要真正支撑 Clojure 代码在 Fennel 上的运行，必须实现与 Clojure 相同级别的持久化语义。这意味着不仅要有不可变的外观，还要有与原生 Lua 表相当的效率（尽管必然存在一定差距）。

持久化哈希映射的 HAMT 实现

HAMT 的核心思想是将键的哈希值按位分段，每段作为 trie 的一个层级索引。假设分支因子为 16，则每 4 位哈希值对应一层节点选择。插入新键时，只需要在从根到叶子的路径上创建新节点，其余分支保持不变，从而实现结构共享。

在 Fennel 实现中，分支因子的选择需要权衡树的深度与单次更新的复制成本。Clojure 使用 32 作为分支因子，但对 Lua 运行时来说，32 意味着每层需要处理更大的稀疏数组，导致单次变更的复制开销增加。实验表明，16 是一个更合理的折中：包含 5 万条记录的映射深度约为 4 层，相比 32 分支的 3 层只增加一次指针跳转，但每次变更需要复制的数组显著缩小。

这种实现的查找和更新复杂度均为 O（log₁₆ N），对于实际使用场景可视为常数时间。以下是核心操作的实现要点：使用 assoc 进行键值关联时，沿哈希路径向下遍历并在必要位置创建新节点；dissoc 删除操作则通过将目标节点置为特殊标记来实现；transient 模式允许在批量操作期间使用可变结构，最后通过 persistent 转换回不可变形式。

持久化向量的实现原理类似，但使用基于索引的位分区而非哈希。分支因子设为 32，因为向量数组的密度通常高于哈希映射的桶，更高的分支因子能减少树深度。查找时通过右移 5 位（对应 32 分支）来计算每层的节点索引，这与 Clojure 的实现完全一致。

更新操作会沿着从根到叶子的路径创建新数组节点，其他分支的节点保持不变，从而实现结构共享。conj 操作在向量尾部添加元素时，如果当前叶子节点未满则直接扩展，否则创建新的根节点并提升现有叶子。pop 操作则通过替换根节点的尾部引用来实现高效的尾部删除。

在排序映射和集合的场景下，项目采用了 Okasaki 插入算法和 Germane & Might 删除算法实现持久化红黑树。Clojure 本身也使用这种结构来支持有序关联容器，尽管其性能通常逊于 HAMT，但在需要按键顺序遍历的场景下不可或缺。

哈希碰撞与盐值处理

将 Clojure 的持久化语义移植到 Lua 时，一个微妙但重要的问题是哈希碰撞处理。Clojure 使用对象标识作为哈希盐值来避免可变对象的相等性歧义，但在 Lua 中实现这一点需要额外注意。

具体来说，使用 djb2 算法进行哈希计算时存在一个问题：普通的 Lua 表和持久化映射如果内容相同，会产生相同的哈希值。例如 (hash-map :foo 1 :bar 2) 和 {:foo 1 :bar 2} 这两个不同的对象会哈希到同一个值，导致它们被放入同一个桶中。解决方案是为持久化集合添加一个基于其原型地址的盐值，这样即使是内容相同的对象也会因为内存地址不同而拥有不同的哈希值，从而正确区分键的身份。

这种方法的代价是引入了额外的哈希计算开销，但对于确保持久化数据结构的语义正确性来说是必要的。

性能测试结果显示，与原生 Lua 表相比，持久化数据结构存在显著的 slowdown。在 5 万元素的测试中，PUC Lua 上的插入操作约慢 80 倍，删除操作可能慢 200 倍以上。不过使用 transient 形式可以进行优化，将插入性能提升到约 40 倍的 slowdown。LuaJIT 环境下情况有所改善，插入操作约慢 50 倍，查询操作约慢 50 倍。

这些性能差距主要源于两方面：每次操作都需要遍历从根到叶的完整路径，导致大量 Lua 表访问；其次是不可避免的内存分配压力，每次变更都会产生新节点。Transient 形式通过允许可变操作来缓解这一问题，但仍需在操作完成后转换为持久化形式。

工程实践与编译器集成

在 ClojureFnl 项目中，这些持久化数据结构被直接嵌入到编译结果中。编译 Clojure 代码时，映射字面量 {:foo 1 :bar 2} 会生成对 PersistentHashMap.new 的调用，序列操作则路由到相应的向量或列表实现。这要求编译器能够识别哪些数据结构需要持久化语义，哪些可以用原生 Lua 表替代。

实际的工程建议是：小规模映射（键数量少于等于 8）可以直接使用 Lua 表，因为线性查找的开销低于 HAMT 的树遍历；但在 Clojure 语义要求严格不可变的场景下，必须使用完整的持久化实现。此外，批量构造时应利用 transient 形式来降低中间操作的分配开销。

资料来源：本文技术细节主要参考 ClojureFnl 项目作者 Andrey Orst 的博客文章《Clojure on Fennel part one: Persistent Data Structures》（2026 年 4 月 7 日），该文详细记录了 immutable.fnl 库的设计与性能基准测试数据。