【Zig 日报】Zig 中的 Newtype 索引模式

[jiacai2050]

Newtype Index Pattern In Zig 一文探讨在注重效率的代码中，使用索引（indexes）而非指针（pointers）的优势、面临的挑战以及相应的解决方案。

核心论点

在追求高性能的代码中，使用索引是一种惯用且更优的做法。

索引的三大优势

1. 节省内存并提高性能

• 内存节省是性能的关键： 在64位架构上，一个32位索引比指针节省4字节。这种内存节省尤为重要，因为现代计算的瓶颈通常是内存和CPU之间的数据传输带宽，而非计算本身。
• 高效利用缓存： 数据结构的紧凑性（密度）提高了CPU缓存的利用率，显著减少了内存访问延迟。
• 普遍的性能提升： 内存节省带来的性能改善是普遍的，它均匀地提高了所有数据结构的紧凑性，即使在分析器中难以察觉，也应作为默认选择。
• 间接节省： 使用索引存储数组，可以通过存储范围而非物化索引列表的方式，实现微妙的内存节省。

2. 更自然地建模递归和循环结构

• 避免指针问题： 指针在处理循环结构时，需要引入可变性和空值检查，使代码复杂。同时，递归的指针链容易导致栈溢出（Stack Overflow），即使在生产环境中也需要复杂的变通方案（例如，Rust编译器处理宏展开错误追踪的案例）。
• 索引的扁平化： 索引将数据保持在扁平的数组中，避免了递归深度带来的风险。

3. 简化序列化和数据传输

• 天然可重定位性： 索引是自然可重定位的，它们不依赖于内存中的绝对地址，极大地简化了数据的跨空间（网络传输）和跨时间（保存到磁盘）的通信。
• 支持批量序列化： 由于数据集中存储在少数几个数组中，可以进行批量序列化（如直接使用memcpy），避免了逐个写入项目带来的开销。

解决类型安全问题（Newtype 模式）

• 挑战： 简单地使用原始整数（如u32）作为索引，最大的问题是将错误的索引用于错误的数组，导致类型不安全。
• 解决方案： 标准做法是为原始索引引入一个新类型包裹器（newtype wrapper），以确保类型安全。
• Zig语言中的实现： 作者推荐了在Zig中利用其非穷举枚举（non-exhaustive enum）特性来实现强类型索引：通过定义 const ItemIndex = enum(u32) { _ };，可以在保持索引为u32效率的同时，创建出一个独特的类型，防止索引被误用。

N叉树的实现示例

作者展示了一个在Zig中如何使用这种模式实现带有父指针的N叉树的例子，并指出几点实践经验：

pub const Tree = struct {
   nodes: []const Node.Data,
   pub const Node = enum(u32) {
       root = 0,
       invalid = std.math.maxInt(u32),
       _,
       pub const Data = struct {
           parent: Node, // .invalid means no parent.
           children: struct {
               index: u32,
               count: u32,
           },
           comptime {
               assert(@sizeOf(Data) == 12);
           }
       };
   };
   fn get(
       tree: *const Tree,
       node: Node,
   ) Node.Data {
       return tree.nodes[@intFromEnum(node)];
   }
   pub fn parent(
       tree: *const Tree,
       node: Node,
   ) ?Node {
       const result = tree.get(node).parent;
       return if (result == .invalid) null else result;
   }
   pub fn children(
       tree: *const Tree,
       node: Node,
   ) []const Node {
       const range = tree.get(node).children;
       return tree.nodes[range.index..][0..range.count];
   }
};

1. 应先定义集合名词（如Tree），而非单个元素（Node）。
2. 索引类型命名通常不带Index后缀（如直接使用Node）。
3. 可以使用嵌套类型（Node.Data）来组织数据。
4. 在索引类型中定义符号常量（如.root，.invalid）来表示特殊状态，例如用.invalid表示空父节点，以避免使用占用空间的?Node类型。
5. 建议在编译时断言（comptime assert）结构体的大小，作为对内存布局的注释和说明。

加入我们

Zig 中文社区是一个开放的组织，我们致力于推广 Zig 在中文群体中的使用，有多种方式可以参与进来：

1. 供稿，分享自己使用 Zig 的心得
2. 改进 ZigCC 组织下的开源项目
3. 加入微信群、Telegram 群组