Hotdry.
归档
compilers

3D几何语言的跨运行表达式缓存：从编译器优化到实时编程体验

深入解析Geoscript语言中独特的跨运行表达式缓存优化技术，探讨如何通过AST结构哈希和持久化缓存大幅提升3D几何编程的迭代速度。

在实时 3D 几何编程领域，每一次代码修改后的等待时间都直接影响着创意流程的流畅度。当开发者调整一个参数、修改一个函数，然后需要等待数秒甚至数十秒才能看到结果时，那种流畅的创作体验就被打断了。这正是 Casey Primozic 在开发 Geoscript 语言和 Geotoy 应用时面临的核心挑战。

Geoscript 是一个专门用于生成和操作 3D 几何的领域特定语言，设计用于类似 Shadertoy 的实时编程环境 Geotoy。与通用编程语言不同，Geoscript 程序具有一个关键特性：它们本质上是纯函数，没有外部输入，每次运行都产生完全相同的输出。这一特性为编译器优化开辟了独特的可能性。

3D 几何语言的优化机会

大多数编程语言需要处理动态输入、用户交互、数据库查询等不确定因素，但 Geoscript 程序完全不同。正如 Primozic 在他的文章中指出的："几乎 Geoscript 程序中的所有内容都是常量，不依赖于任何外部或动态输入。"

这种确定性带来了几个重要的优化机会：

  1. 常量折叠可以扩展到整个程序：由于没有外部依赖，理论上整个程序都可以在编译时求值
  2. 表达式结果可以安全缓存：相同的 AST 节点总是产生相同的结果
  3. 跨运行优化成为可能：程序在不同运行间的相似性可以被利用

Geoscript 最初实现了标准的编译器优化管道，包括常量折叠和公共子表达式消除（CSE）。常量折叠优化了像1 + 1这样的简单表达式，而 CSE 则识别并重用相同的计算子表达式。然而，这些优化虽然有用，但并没有带来革命性的性能提升。

跨运行表达式缓存：核心创新

真正的突破来自于一个简单的洞察：既然 Geoscript 程序是确定性的，那么为什么不在不同运行之间缓存表达式的结果呢？

在实时编程环境中，开发者通常会进行小步迭代：修改一行代码，运行程序，查看结果，然后基于结果决定下一步修改。在这个过程中，程序的大部分内容保持不变。如果能够重用前一次运行中已经计算过的表达式结果，就可以大幅减少重复计算。

实现机制

跨运行表达式缓存的核心实现基于以下几个关键技术：

1. AST 结构哈希

为了识别相同的表达式，Geoscript 实现了树基结构哈希。每个 AST 节点都可以被哈希为一个唯一的u128值。哈希算法需要考虑节点的类型、操作符、子节点哈希等所有结构信息，确保相同的 AST 结构产生相同的哈希值。

// 伪代码示例：AST节点哈希
fn hash_ast(node: &AstNode) -> u128 {
    match node {
        AstNode::Literal(value) => hash_literal(value),
        AstNode::BinaryOp { op, left, right } => {
            combine_hashes(hash_op(op), hash_ast(left), hash_ast(right))
        }
        AstNode::Call { func, args } => {
            let mut h = hash_ident(func);
            for arg in args {
                h = combine_hashes(h, hash_ast(arg));
            }
            h
        }
        // ... 其他节点类型
    }
}

2. 缓存键设计

缓存键不仅仅是 AST 哈希。对于涉及伪随机数生成器（PRNG）的表达式，还需要包含 RNG 状态。这是因为 PRNG 调用既是状态读取器也是状态写入器，需要被建模为(rng_state) -> (value, new_rng_state)的纯函数。

// 伪代码：缓存键生成
fn cache_key(expr: &AstNode, rng_state: Option<RngState>) -> CacheKey {
    let expr_hash = hash_ast(expr);
    match rng_state {
        Some(state) => combine_hashes(expr_hash, hash_rng_state(state)),
        None => expr_hash,
    }
}

3. 缓存持久化

缓存需要在不同运行之间持久化。在 Geotoy 的 Web 环境中，这通常意味着使用浏览器的本地存储或 IndexedDB。缓存条目包含：

  • 缓存键（AST 哈希 + 可选 RNG 状态）
  • 计算结果（序列化的几何数据）
  • 时间戳和元数据

实际效果：从 900ms 到即时反馈

考虑一个实际的 Geotoy 组合示例：

distance_to_circle = |p: vec3, radius: num| {
  sqrt(p.y*p.y + pow(sqrt(p.x*p.x + p.z*p.z) - radius, 2))
}

radius = 8

0..
  -> || randv(-radius*1.1, radius*1.1)
  | filter(|p| distance_to_circle(p, radius) < 2)
  | take(1550)
  | alpha_wrap(alpha=1/100, offset=1/100)
  | smooth(iterations=2)
  | simplify(tolerance=0.01)
  | render

在这个例子中，alpha_wrap函数来自 CGAL 库，用于从点云生成网格。这个操作非常昂贵，在作者的机器上需要约 900ms。

当开发者调整simplify函数的tolerance参数时，传统方法需要重新运行整个管道，包括昂贵的alpha_wrap调用。使用跨运行缓存后，只有simplify调用需要重新执行，其他所有未改变的部分都从缓存中读取。

工程实现细节

缓存失效策略

虽然 Geoscript 程序是确定性的，但缓存仍然需要失效策略：

  1. 语法变化检测：当 AST 结构改变时，相应的缓存条目失效
  2. 版本兼容性：当语言语义或库函数改变时，需要清空整个缓存
  3. 内存管理：设置缓存大小限制和 LRU 淘汰策略

闭包和作用域处理

Geoscript 支持闭包，这增加了缓存的复杂性。闭包可以捕获外部作用域的变量，只有当这些变量本身是常量时，闭包表达式才能被缓存。

radius = 10
sphere_fn = || {
  # 这个闭包可以缓存，因为radius是常量
  icosphere(radius=radius, resolution=4)
}

dynamic_value = rand()
dynamic_fn = || {
  # 这个闭包不能缓存，因为dynamic_value不是常量
  icosphere(radius=dynamic_value, resolution=4)
}

实现需要跟踪变量的常量性，并在 AST 哈希中包含捕获变量的值。

副作用处理

Geoscript 有一些有限的副作用，主要是网格渲染和调试输出。这些副作用表达式不能被缓存，或者需要特殊处理以确保副作用只在适当的时间发生。

与其他系统的比较

构建系统缓存

这种缓存策略与 Nix、Bazel 等构建系统的缓存机制有相似之处。构建系统缓存构建产物（对象文件、软件包），而 Geoscript 缓存程序求值的中间结果。两者都基于确定性计算模型。

Grasshopper 3D

Hacker News 上的评论指出，这种缓存类似于 Grasshopper 3D 可视化编程环境中使用的技术。在 Grasshopper 中，昂贵的计算节点结果被缓存，允许用户平滑地调整下游参数，而无需重新执行整个程序。

Lucid 语言

另一个评论提到了 Lucid 编程语言，该语言在 50 年前尝试了 "缓存整个世界" 的方法。当时由于存储成本高昂，这种方法遇到了困难。今天，存储成本已大幅降低，使得这种策略更加可行。

性能参数与监控要点

缓存命中率指标

实施跨运行缓存后，需要监控几个关键指标：

  1. 缓存命中率：表达式求值中从缓存读取的比例
  2. 缓存大小：内存 / 存储使用情况
  3. 平均节省时间：缓存命中的表达式原本需要的计算时间

优化阈值建议

基于 Geoscript 的经验，以下参数可以作为类似系统的起点：

  • 最小缓存收益：只缓存计算时间超过 5ms 的表达式
  • 最大缓存条目：根据可用内存设置，建议 1000-5000 个条目
  • 哈希冲突概率：使用 128 位哈希，冲突概率极低（~2^-64）

调试和诊断工具

实现应包括：

  • 缓存统计信息输出
  • 缓存未命中的原因分析（语法变化、副作用、非常量依赖等）
  • 手动缓存清除和验证工具

局限性与未来方向

当前限制

  1. 动态输入不适用：如果程序需要处理用户输入或外部数据，这种优化不适用
  2. 内存开销：缓存几何数据可能占用大量内存
  3. 并行化挑战：缓存可能引入线程安全问题

扩展可能性

  1. 增量求值：不仅缓存结果，还记录计算依赖，实现真正的增量求值
  2. 分布式缓存：在协作环境中共享缓存结果
  3. 自适应缓存：基于使用模式动态调整缓存策略

结论

Geoscript 的跨运行表达式缓存优化展示了领域特定语言如何利用其独特特性实现通用语言难以达到的优化。通过将程序视为纯函数，并利用实时编程中的迭代模式，这种技术大幅提升了开发者的体验。

正如 Primozic 所说："这个持久化表达式记忆优化已经成为我对 Geoscript 添加的最有影响力的优化。" 它最初是作为公共子表达式消除的副产品出现的，但最终证明比原始目标更有价值。

对于编译器开发者和领域特定语言设计者来说，这个案例提供了几个重要启示：

  1. 深入理解领域特性是发现独特优化机会的关键
  2. 简单的洞察有时比复杂的算法更有价值
  3. 实际使用模式应该指导优化策略的设计

在实时创意编程工具日益重要的今天，这种能够显著减少迭代等待时间的技术具有广泛的应用前景。无论是 3D 建模、音频处理还是数据可视化，任何涉及昂贵计算和频繁迭代的领域都可以从类似的缓存策略中受益。

资料来源：

  1. Casey Primozic, "A Unique Performance Optimization for a 3D Geometry Language", https://cprimozic.net/notes/posts/persistent-expr-memo-optimization-for-geoscript/
  2. Hacker News 讨论，https://news.ycombinator.com/item?id=46573566
查看归档