I/O OVER

Rust中，常规的vector是一种值

Train Train ·

原文地址 作者：Niko Matsakis

本文不需要Rust基础也能阅读。其中vector指的是大多数很多语言中的List或者动态数组。

我最近一直在思考持久化容器(persistent collections)，特别是它们与Rust的关系，我想写下一些我的观察。1

什么是持久化容器

传统上，持久化容器被看作是一种与众不同的建立容器的方法。传统的容器有类似push的方法，能让vector原地增长：

vec.push(element); // 往 `vec` 增加元素

而持久化容器有类似add的方法，能保留原本的vector不动，而返回一个已经被修改的新vector：

let vec2 = vec.add(element);

此处的关键特性在于vec没有改变，这使得持久化容器非常适合函数式语言（以及适合并行计算）。

持久化容器如何运作

我不会详细介绍任何特定的设计，但是大多数都是基于某种树的。比如说，如果有一个vector类似于[1, 2, 3, 4, 5, 6]，可以想象一下，这些值不是以一大块的方式储存，而是将它们储存在某种树中，值保存在叶子结点里。在下面的示意中，元素被分开放在两个叶子结点，父节点的指针指向这两个节点：

 [*        *] // <-- 这是 vector 的父节点
  |        |
-----    -----
1 2 3    4 5 6

现在想想我们要改变vector中的一个值，比如说我们想把6改成10。这意味着我们必须改变右节点，但可以继续使用左节点。所以我们创建一个新的父节点，这样就能引用新的右节点。

 [*        *]   // <-- 原 vector
  |        |    //     (仍然存在，没有被改变)
-----    -----
1 2 3    4 5 6
-----
  |      4 5 10 // <-- 右节点的新拷贝
  |      ------
  |        |
 [*        *]   // <-- 新的 vector

对于一个平衡的树中，这通常意味着往一个持久化vector中插入元素往往是 \(O(\log n)\) ——我们必须复制和修改一些叶子，然后必须复制和修改所有这条路径的父节点。这比修改传统的vector开销更大，修改传统的vector只是一些CPU指令。

一些意见：

  • 如果这个vector实际上没有别名（多处引用同一段内存），并且你知道它没有别名，那么你常常可以避免这些复制，仅仅是原地修改树。稍后，我会谈到 DVec，一个试验性的Rust持久化容器库做到了这个特性。但在典型的基于GC的语言中很难做到，因为你永远不知道自己在用的是别名。
  • 持久化容器有非常多的其他设计，一些设计偏向于特定的使用模式。比如说，这篇论文提出一中针对于类似Prolog的程序的设计；这个设计内部用了可变性实现 \(O(1)\) 插入，但是在接口上对用户隐藏。当然，这些低开销的插入是有代价的：数据结构的较老的拷贝使用起来开销很大。

持久化容器让容器变成值

某些情况下，持久化容器能让代码更容易被理解。因为他们更像一个「普通的值」，没有自己的「秉性」。来看这个JS代码，用整数：

function foo() {
    let x = 0;
    let y = x;
    y += 1;
    return y - x;
}

此处我们修改 y 的时候，不期望 x 也改变，因为 x 只是一个简单的值。但是如果改成用数组：

function foo() {
    let x = [];
    let y = x;
    y.push(22);
    use(x, y);
}

现在修改y，x也会跟着改变。也许这正是我们想要的，但有时候不是。当vector藏在对象后面的时候，事情会愈发让人摸不清头脑：

function foo() {
    let object = {
        field: []
    };
    ...
    let object2 = {
        field: object.field
    };
    ...
    // 现在 `object.field` 和 `object2.field` 在幕后秘密相连
    ...
}

不要误会，有时候object.field和object2.field是指向同一个vector是非常方便的。但另一些时候这不是你想要的。我常常发现改成持久化容器能让我的代码更清晰、易于理解。

Rust 是特别的

如果曾看过一次我对于Rust的演讲2，就会知道我反复强调Rust设计的一个核心要素：

数据分享和可变：都是好东西，但放在一起就非常可怕。

基本上，这个想法是，当有两个不同的路径访问同样的内存（在上一个例子中的object.field和object2.field），对它进行修改就是非常危险的意图。当在Rust中试图放弃使用GC，情况就尤其如此，因为突然不清楚谁应该管理这块内存了。但哪怕使用GC也是如此，因为一个像object.field.push(...)的修改可能影响比预料中更多的对象，从而导致错误（尤其是但不限于发生在并行线程中的情况）。

那么，如果试图两次访问同一个vector，在Rust中会发生什么？回到刚刚看到的JavaScript例子，但这次使用Rust写。第一个例子是用整数，运作得和JS一样：

let x = 0;
let mut y = x;
y += 1;
return y - x;

但第二个用vector的例子，根本不会通过编译：

let x = vec![];
let mut y = x;
y.push(...);
use(x, y); // ERROR: use of moved value `x`

问题在于，一旦我们用了 y = x，就已经拿走了 x 的所有权，这样它就不能再被使用了。

在Rust中，普通的vector是值

可以引出结论。在Rust中，我们日常使用的「普通的容器」已经像值一样行事：实际任何Rust类型都是如此——只要不使用Cell或者RefCell。换句话说，假设你的代码通过编译，你知道你的vector没有在多个地方被修改：你可以用一个整数来代替它，而它会有相同的行为。这样很好。

这意味着就Rust而言，持久化容器和普通容器相比，不必一定要有「不同的接口」。例如，我创建了一个名为dogged3的持久化vector。Dogged提供了一种称为 DVec 的vector类型，它基于Clojure提供的持久化vector。但如果看看 DVec 提供的方法，会发现这是一种标准的容器（有 push 等等）。

比如说这是一种 DVec 的有效操作：

let mut x = DVec::new();
x.push(something);
x.push(something_else);
for element in &x { ... }

尽管如此，一个DVec还是一个持久化数据结构。在实现上，一个 DVec 被实现为Trie。它包含一个 Arc （引用计数指针）来引用其内部数据。当调用push时，我们会更新Arc 指向新的vector，并把旧数据留在原地。

（顺便说一句，Arc::make_mut是一个非常酷的方法。它检查Arc的引用计数：如果是1，则给你对内容的唯一（可变）访问权限；如果引用计数不是1，那么它将复制Arc（及其内容），并给你这个复制的数据的可变引用。如果你回想起持久化数据结构是如何运作的，就能发现这对于更新一个树是完美的，在容器没有别名的情况下，它可以避免复制操作。）

但持久化容器间是不同的

一个 Vec 和一个 DVec 之间的主要区别不是它们提供的操作，而在于它们的开销。也就是说，在一个标准的Vec上push时，它是一个\(O(1)\)操作。当复制它的时候，就是 \(O(n)\)。对于一个DVec，开销截然不同：push是 \(O(\log ⁡n)\)，但是复制是 \(O(1)\)。

尤其对于一个DVec，clone操作只是增加内部的Arc引用计数，而对于普通vector，clone必须复制所有数据。当然，对一个DVec执行push，会在重建树受影响的部分时复制一部分数据（而Vec一般只需要在数组末尾写入数据）。

众所周知，「大O」记法只描述渐进耗时。DVec我已经遇到的一个问题在于，在性能上它很难与标准的Vec竞争。单纯地整串复制数据经常比更新树以及分配内存要快。我发现只有在极端情况下才有用DVec的理由——比如说做大量复制操作，或者有大量数据。

当然不全关于性能。如果进行大量复制操作，DVec 也应该使用更少的内存，因为大量内部数据可以共享。

结论

在这里我通过持久化容器试图说明，Rust的所有权系统是如何以一种巧妙的方式，将函数式风格和命令式风格融合。也就是说，Rust的标准容器虽然以典型的命令式接口实现，但实际上它们像是「值」一样在运作：将一个vector从一个地方赋值到另一个地方，如果想继续使用原本的那个，则必须clone它，这就使得新的拷贝独立于旧的那个。

这不是新的见解。比如说1990年，Phil Wadler写了一篇题为《线性类型可以改变世界！》的论文，在这之中他得出几乎一摸一样的结论，然而是从相反的起点出发。在论文中他说，依旧能提供一个持久化的接口（例如，vec.add(element)返回新vector的方法），但如果使用线性类型，可以通过一个命令式的数据结构暗地里实现它（例如vec.push(element)），而不让别人知道。

在摆弄DVec的时候，我发现一个持久化vector也提供常规（命令式）接口是很有用的。比如说，我能够非常容易修改ena 合一库（在内部它基于一个vector）让它运作在持久化模式（使用DVec）或者命令式模式（使用Vec）。基本的点子是将具体的vector类型泛型化，如果这些类型提供一样的接口的话这会很简单。

（另外，我乐意看到更多的实验。比如说，如果一个vector开始时是一个常规vector，但是超过某个长度就会变成持久化vector，我认为是非常有用的。）

特别对于Rust，我觉得有其他的原因让人对持久化容器产生兴趣。同时对数据进行分享和修改是一种有风险的模式，但有时候是必要又有用的，而在Rust现在用起来感觉是反人类的。我认为我们应该做一些事情来改善这种情况，我也有一些具体的想法4，但我觉得在这里使用「持久化 vs 命令式容器」的表述是不合理的。换句话说，Rust已经有了持久化容器，它只是在clone操作上特别低效。

  1. 正好，我之前写的SLG求解器似乎特别喜欢用持久化容器 ↩

  2. 如果还没有，那么我觉得这个非常好。 ↩

  3. 在英语中，如果你“dogged”地追求目标，就很坚持不懈（persistent）。 ↩

  4. 具体的想法，必须等到下一篇博客文章。现在是让我女儿去上学的时间了！ ↩