Dodrio 是一个使用 Rust 和 WebAssembly 编写的虚拟 DOM 库。它利用了 Wasm 的线性内存和 Rust 的底层控制，通过围绕 Bump Allocation 设计虚拟 DOM 渲染来实现。初步基准测试结果表明它拥有同类最佳的性能。

• 背景
• 从用户的角度来看 Dodrio
• 内部设计
• 初步基准测试
• 未来工作
• 结论

背景

虚拟 DOM 库

虚拟 DOM 库为 Web 的命令式 DOM 提供了一个声明式接口。用户通过生成虚拟 DOM 树结构来描述所需的 DOM 状态，库负责使 Web 页面上的物理 DOM 反映用户生成的虚拟 DOM 树。库使用一些 diffing 算法来减少它们调用的昂贵 DOM 突变方法的数量。此外，它们往往具有缓存功能，以进一步避免不必要地重新渲染未更改的组件并重新 diffing 相同的子树。

Bump Allocation

Bump Allocation 是一种快速但有限的内存分配方法。分配器维护一块内存和一个指向该块内部的指针。要分配一个对象，分配器将指针向上舍入到对象的对其方式，添加对象的尺寸，并进行一个快速测试，以确保指针没有溢出并仍然指向内存块内。分配只需要少量指令。同样，一次性释放所有对象的速度也很快：将指针重置回块的开头。

Bump Allocation 的缺点是，在其他对象仍在使用的情况下，没有通用的方法来释放单个对象并回收其内存区域。

这些权衡使得 Bump Allocation 非常适合阶段式分配。也就是说，一组对象将在同一个程序阶段全部分配、一起使用，最后一起释放。

bump_allocate(size, align):
    aligned_pointer = round_up_to(self.pointer, align)
    new_pointer = aligned_pointer + size
    if no overflow and new_pointer < self.end_of_chunk:
        self.pointer = new_pointer
        return aligned_pointer
    else:
        handle_allocation_failure()

从用户的角度来看 Dodrio

首先，我们应该清楚地了解 Dodrio 是什么和不是什么。Dodrio 只是一个虚拟 DOM 库。它不是一个完整的框架。它不提供状态管理，例如 Redux 存储和操作或双向绑定。它不是构建 Web 应用程序时遇到的所有问题的完整解决方案。

使用 Dodrio 应该对之前使用过 Rust 或虚拟 DOM 库的任何人来说都比较熟悉。为了定义如何将 struct 渲染成 HTML，用户实现 dodrio::Render 特性，该特性接收对 self 的不可变引用，并返回一个虚拟 DOM 树。

Dodrio 使用 Builder 模式 来创建虚拟 DOM 节点。我们打算支持可选的 JSX 样式、内联 HTML 模板语法和编译时过程宏，但我们将其留作 未来工作。

dodrio::Render 特性接口中的 'a 和 'bump 生命期以及 where 'a: 'bump 子句强制执行 self 引用比 Bump Allocation 区域和返回的虚拟 DOM 树存活更久。这意味着，如果 self 包含一个字符串，例如，返回的虚拟 DOM 可以通过引用安全地使用该字符串，而不是将它复制到 Bump Allocation 区域中。Rust 的生命期和借用使我们能够积极地进行节省成本的优化，同时静态地保证它们的安全性。

struct Hello {
    who: String,
}

impl Render for Hello {
    fn render<'a, 'bump>(&'a self, bump: &'bump Bump) -> Node<'bump>
    where
        'a: 'bump,
    {
        span(bump)
            .children([text("Hello, "), text(&self.who), text("!")])
            .finish()
    }
}

事件处理程序被赋予对根 dodrio::Render 组件、用于调度重新渲染的虚拟 DOM 实例句柄以及 DOM 事件本身的引用。

struct Counter {
    count: u32,
}

impl Render for Counter {
    fn render<'a, 'bump>(&'a self, bump: &'bump Bump) -> Node<'bump>
    where
        'a: 'bump,
    {
        let count = bumpalo::format!(in bump, "{}", self.count);
        div(bump)
            .children([
                text(count.into_bump_str()),
                button(bump)
                    .on("click", |root, vdom, _event| {
                        let counter = root.unwrap_mut::<Counter>();
                        counter.count += 1;
                        vdom.schedule_render();
                    })
                    .children([text("+")])
                    .finish(),
            ])
            .finish()
    }
}

此外，Dodrio 还提供了一个概念验证 API，用于在 JavaScript 中定义渲染组件。这反映了 Rust 和 Wasm 生态系统对 JavaScript 的强大集成故事，这使得对 Rust 的增量移植和异构的多语言应用程序成为可能，其中只有性能最敏感的代码路径是用 Rust 编写的。

class Greeting {
  constructor(who) {
    this.who = who;
  }

  render() {
    return {
      tagName: "p",
      attributes: [{ name: "class", value: "greeting" }],
      listeners: [{ on: "click", callback: this.onClick.bind(this) }],
      children: [
        "Hello, ",
        {
          tagName: "strong",
          children: [this.who],
        },
      ],
    };
  }

  async onClick(vdom, event) {
    // Be more excited!
    this.who += "!";

    // Schedule a re-render.
    await vdom.render();

    console.log("re-rendering finished!");
  }
}

#[wasm_bindgen]
extern "C" {
    // Import the JS `Greeting` class.
    #[wasm_bindgen(extends = Object)]
    type Greeting;

    // And the `Greeting` class's constructor.
    #[wasm_bindgen(constructor)]
    fn new(who: &str) -> Greeting;
}

// Construct a JS rendering component from a `Greeting` instance.
let js = JsRender::new(Greeting::new("World"));

最后，Dodrio 公开了安全的公共接口，而且我们在编写 Dodrio 渲染组件时从未感到有必要使用 unsafe。

内部设计

Dodrio 中的虚拟 DOM 树渲染和 diffing 都利用了 Bump Allocation。渲染从组件状态构造基于 Bump Allocation 的虚拟 DOM 树。Diffing 将 DOM 突变批处理到一个基于 Bump Allocation 的“更改列表”中，该列表在 diffing 完成后一次性应用于物理 DOM。这种设计旨在最大化分配吞吐量，而分配吞吐量通常是虚拟 DOM 库的性能瓶颈，并最大限度地减少 Wasm、JavaScript 和本地 DOM 函数之间的来回切换，这应该可以改善时间缓存局部性并避免越界调用。

渲染到双缓冲 Bump Allocation 区域

虚拟 DOM 渲染表现出我们可以利用 Bump Allocation 的阶段

1. 一个虚拟 DOM 树是由 Render 实现构建的，
2. 它与旧的虚拟 DOM 树进行 diffing，
3. 保存到下次渲染新的虚拟 DOM 树时，
4. 当它与新的虚拟 DOM 树进行 diffing 时，
5. 最后，它和它的所有节点都被销毁。

这个过程无限循环。

        ------------------- Time ------------------->
Tree 0: [ render | ------ | diff ]
Tree 1:          [ render | diff | ------ | diff ]
Tree 2:                          [ render | diff | ------ | diff ]
Tree 3:                                          [ render | diff | ------ | diff ]
...

在任何给定时间，只有两个虚拟 DOM 树是活动的。因此，我们可以双缓冲两个 Bump Allocation 区域，它们在包含新或旧虚拟 DOM 树的角色之间来回切换

1. 一个虚拟 DOM 树被渲染到 Bump 区域 A 中，
2. Bump 区域 A 中的新虚拟 DOM 树与 Bump 区域 B 中的旧虚拟 DOM 树进行 diffing，
3. Bump 区域 B 的 Bump 指针被重置，
4. Bump 区域 A 和 B 被交换。

        ------------------- Time ------------------->
Arena A: [ render | ------ | diff | reset | render | diff | -------------- | diff | reset | render | diff ...
Arena B:          [ render | diff | -------------- | diff | reset | render | diff | -------------- | diff ...

Diffing 和更改列表

Dodrio 使用一个简单的、单遍算法来 diff 虚拟 DOM 树。它同步遍历旧树和新树，并在旧树和新树之间存在属性、监听器或子级差异时构建一个包含 DOM 突变操作的更改列表。它目前没有使用任何复杂的算法来最小化更改列表中的操作数量，例如最长公共子序列或耐心 diffing。

更改列表是在 diffing 过程中构建的，应用于物理 DOM，然后被销毁。下次渲染新的虚拟 DOM 树时，该过程将重复。由于在任何时候最多只有一个更改列表是活动的，因此我们对所有更改列表使用单个 Bump Allocation 区域。

更改列表的 DOM 突变操作被编码为 自定义堆栈机的指令。虽然指令的辨别符始终是 32 位整数，但指令的尺寸是可变的，因为一些指令具有立即数，而另一些则没有。机器的堆栈包含物理 DOM 节点（文本节点和元素），立即数对 UTF-8 字符串的指针和长度进行编码。

指令是在 Rust 和 Wasm 侧发出的，然后在 JavaScript 中批量解释并应用于物理 DOM。每个解释特定指令的 JavaScript 函数都接受四个参数

1. 对表示堆栈机的 JavaScript ChangeList 类的引用，
2. 从 Wasm 内存中解码字符串的 Uint8Array 视图，
3. 从 Wasm 内存中解码立即数的 Uint32Array 视图，
4. 以及指令的立即数（如果有）所在的偏移量 i。

它返回 Wasm 内存的 32 位视图中下一个指令的编码位置的新偏移量。

有用于以下方面的指令

• 创建、删除和替换元素和文本节点，
• 添加、删除和更新属性和事件监听器，
• 以及遍历 DOM。

例如，AppendChild 指令没有立即数，但预期堆栈顶部有两个节点。它从堆栈中弹出第一个节点，然后调用 Node.prototype.appendChild，并将弹出的节点作为子节点，并将现在位于堆栈顶部的节点作为父节点。

// Allocate an instruction with zero immediates.
fn op0(&self, discriminant: ChangeDiscriminant) {
    self.bump.alloc(discriminant as u32);
}

/// Immediates: `()`
///
/// Stack: `[... Node Node] -> [... Node]`
pub fn emit_append_child(&self) {
    self.op0(ChangeDiscriminant::AppendChild);
}

function appendChild(changeList, mem8, mem32, i) {
    const child = changeList.stack.pop();
    top(changeList.stack).appendChild(child);
    return i;
}

另一方面，SetText 指令预期堆栈顶部有一个文本节点，并且不修改堆栈。它有一个作为指针和长度立即数编码的字符串。它解码字符串，并调用 Node.prototype.textContent 设置器函数，用解码后的字符串更新文本节点的文本内容。

// Allocate an instruction with two immediates.
fn op2(&self, discriminant: ChangeDiscriminant, a: u32, b: u32) {
    self.bump.alloc([discriminant as u32, a, b]);
}

/// Immediates: `(pointer, length)`
///
/// Stack: `[... TextNode] -> [... TextNode]`
pub fn emit_set_text(&self, text: &str) {
    self.op2(
        ChangeDiscriminant::SetText,
        text.as_ptr() as u32,
        text.len() as u32,
    );
}

function setText(changeList, mem8, mem32, i) {
    const pointer = mem32[i++];
    const length = mem32[i++];
    const str = string(mem8, pointer, length);
    top(changeList.stack).textContent = str;
    return i;
}

初步基准测试

为了了解 Dodrio 相对于其他库的速度，我们将其加入到 Elm 的“闪电般快速的 HTML”基准测试 中，该测试比较了不同库实现的 TodoMVC 的渲染速度。他们声称这种方法是公平的，基准测试结果应该可以推广。他们还主观地评估了优化实现以提高性能的难易程度（例如，在 React 中添加适当的 `shouldComponentUpdate` 提示，以及在 Elm 中添加 `lazy` 包装器）。我们遵循相同的测试方法，并禁用了 Dodrio 默认开启的每帧动画渲染防抖，这与 Elm 实现的测试条件一致。

也就是说，这些基准测试结果存在一些需要注意的地方。React 实现存在阻止其完成基准测试的错误，因此我们没有在下面列出其度量结果。如果您好奇，可以查看原始的 Elm 基准测试结果，了解它与这里测量的其他一些库相比如何。其次，我们尝试将基准测试更新到每个库的最新版本，但很快就陷入了困境，因此 _这个基准测试没有使用每个库的最新版本_。

言归正传，让我们看看基准测试结果。我们在 Linux 上的 Firefox 67 中运行了这些测试。数值越低越好，表示渲染时间越快。

库	优化？	毫秒
Ember 2.6.3	否	3542
Angular 1.5.8	否	2856
Angular 2	否	2743
Elm 0.16	否	4295
Elm 0.17	否	3170
Dodrio 0.1 预览版	否	2181
Angular 1.5.8	是	3175
Angular 2	是	2371
Elm 0.16	是	4229
Elm 0.17	是	2696

**Dodrio 是基准测试中测量的最快库。**但这并不意味着 Dodrio 始终会在所有场景中都最快 - 这无疑是错误的。但这些结果验证了 Dodrio 的设计，并表明它已经具备了同类最佳的性能。此外，还有空间可以使其更快。

• Dodrio 是一款全新的库，还没有像其他测试过的库那样投入多年的开发工作。我们还没有对 Dodrio 进行任何认真的分析或优化工作！

• 基准测试中使用的 Dodrio TodoMVC 实现没有使用像其他实现那样使用 `shouldComponentUpdate` 样式的优化。这些技术仍然可供 Dodrio 用户使用，但您需要更少地使用它们，因为惯用的实现已经足够快了。

未来工作

到目前为止，我们还没有投资于打磨 Dodrio 的人体工程学。我们希望探索添加 类型安全的 HTML 模板，这些模板最终会归结为 Dodrio 虚拟 DOM 树构建器的调用。

此外，我们还可以通过以下几种方式来提高 Dodrio 的性能。

• 我们可以为常见的 DOM 变更操作创建新的指令。 例如，如果我们有直接设置最常见属性的指令（例如 `“id”`、`“class”` 等），我们可以避免从立即值中解码属性名称字符串。

• 我们可以研究更智能的差异算法。 初步分析表明，Dodrio 在应用差异上花费的时间比生成差异或构建虚拟 DOM 树的时间要多得多。有可能改进差异算法可以发出更小的差异，这些差异更容易应用。

• Dodrio 的缓存机制（类似于 React 的 `shouldComponentUpdate`）目前避免了重建虚拟 DOM 子树，但还没有避免重新进行差异比较。 将缓存机制扩展到也避免重新进行差异比较应该相对简单，并且在使用缓存时会带来加速效果。

为了改善人体工程学并进一步提升性能，我们希望在投入更多精力之前，先收集来自实际使用中的反馈意见。

Evan Czaplicki 指出了另一个基准测试——`krausest/js-framework-benchmark`——我们可以用它来进一步评估 Dodrio 的性能。我们期待为 Dodrio 实现这个基准测试，并收集更多测试案例和对性能的见解。

在未来，WebAssembly 主机绑定提案 将使我们能够在 Rust 和 Wasm 中解释更改列表的操作，而无需通过 JavaScript 调用 DOM 方法。

结论

Dodrio 是一款新的虚拟 DOM 库，旨在利用 Wasm 线性内存和 Rust 低级控制的优势，通过广泛使用快速碰撞分配来实现。如果您想了解更多关于 Dodrio 的信息，我们鼓励您查看它的 代码库 和 示例！

感谢 Luke Wagner 和 Alex Crichton 对 Dodrio 设计的贡献，以及他们参与的头脑风暴和橡皮鸭调试会议。我们还与 React、Elm 和 Ember 团队的核心开发者讨论了这些想法中的许多，感谢他们为这些讨论最终带来的 Dodrio 设计背景和理解提供了帮助。最后，感谢 Jason Orendorff、Lin Clark、Till Schneidereit、Alex Crichton、Luke Wagner、Evan Czaplicki 和 Robin Heggelund Hansen 对本文初稿的宝贵反馈。