Use Arc Instead of Vec

留言

https://www.youtube.com/watch?v=A4cKi7PTJSs

在这个视频中,我想讨论为什么你可能会考虑在Rust代码中使用Arc<[T]>而不是Vec作为合理的默认选择。这可能有点争议,所以让我稍微解释一下。

Arc<[T]>对于不可变数据来说可能是一个很好的选择。如果你构建了一个大的数据序列,之后不再修改,你可以考虑使用Arc<[T]>。它非常适合存储在结构体、数组或集合中的数据,或者是需要到处传递的数据。我不是在讨论那些作为局部变量快速收集的Vec,或者仅用于一些快速临时存储的Vec。我指的是你要长期存储的数据,你可以考虑使用Arc<[T]>,特别是对于实现了Clone trait的数据。

这不应该是一个很大的惊喜,因为Clone某种程度上是Arc的超能力,我们稍后会讨论这一点。如果你经常需要克隆大型不可变数据序列,Arc可以比Vec快得多。如果你不需要克隆,你可以使用比Arc<[T]>更好的Box,我们会在最后讨论这一点。

为什么我推荐这个呢?有三个很大的原因:

  1. 我们已经提到过,Arc有一个极其廉价的常数时间克隆。无论你指向的序列有多大,克隆它所需的时间都是相同的,只涉及增加一个整数和内存复制Arc指针本身,这非常快,而且不涉及任何内存分配,而通常克隆Vec是需要分配内存的。所以这是一个你可以通过简单地切换到Arc<[T]>就能获得的巨大优化。

  2. Arc<[T]>只有16字节,它只需要存储一个指针和一个长度。而Vec需要存储一个指针、一个长度和一个容量,使其为24字节。虽然这只是8字节的差异,看起来不大,但如果你存储大量这样的东西,特别是在结构体或数组中,这额外的内存可能会累积起来,可能会降低缓存局部性,使得遍历这些东量图案件变得更困难。

  3. Arc<[T]>实现了Deref<Target=[T]>,就像Vec一样。所以你可以在Arc<[T]>上做所有与Vec相同的只读操作。你可以询问其长度,可以遍历它,可以索引它。这一点非常重要,因为前两点很酷,但如果Arc<[T]>比Vec难用得多,我不会特意去推荐它们。但事实并非如此,因为它实现了Deref<Target=[T]>,它也实现了许多其他你可能需要的trait,这使得Arc<[T]>在很多情况下可以直接替代Vec。所以前两点是很好的性能提升,第三点意味着使用Arc<[T]>基本上不比使用Vec难,所以你不妨先考虑使用它。

我一直在讨论Arc<[T]>与Vec的对比,实际上我接下来会讨论Arc与String的对比,这是完全相同的二分法,只是稍微更容易讨论和想出例子。但我要说的关于Arc与String的一切都直接适用于Arc<[T]>与Vec。

我还想提到,任何时候使用Arc时,如果你不需要Arc提供的线程安全性,你应该总是先尝试使用Rc。我在这里说Arc是因为这是最通用的建议,但如果你可以使用Rc,你绝对应该尝试,因为它的开销比Arc低。

我还想澄清一点,我说的是Arc,而不是Arc。Arc确实有一些与Arc相同的优点,但它也有一个很大的缺点,那就是你需要双重指针间接才能真正访问你关心的字符数据。我会在最后展示一个可视化的例子,但Arc通常来说比较笨重,内存效率低,而且这种双重间接对性能来说非常不利。所以我不推荐使用它。我说的是Arc。Rust宽指针的强大之处在于我们可以让一个Arc直接指向堆上的动态大小字符缓冲区。

假设我正在开发一个游戏,我的系统中有一个叫做MonsterID的类型,在底层它只是用一些文本来表示,我想使用String类型来管理这些文本。

首先,我可能想在我的MonsterID结构体上派生一堆trait。我想能够克隆这个东西,我想能够打印调试表示,比较它,哈希它。我还想使用serde来做一些序列化和反序列化,可能是从配置文件或者一些保存数据。所以我想在我的MonsterID结构体上加上所有这些派生,并且我希望它们都能工作。使用String时,这些都能工作。

接下来,我想在我的MonsterID结构体上有一个方法,可以将底层表示作为字符串切片获取。也许我想把它记录到控制台,也许我想在某个地方用它做分析。所以我只想以字符串切片的形式访问底层数据,这在使用String时很容易做到。

然后,我想在某个地方有一些配置数据,这将是一个从MonsterID到它们统计数据的哈希映射。你知道,它们的伤害、生命值等等,它将以MonsterID为键。这就是为什么我需要派生Eq和Hash,而使用String作为底层数据类型时,这一切都能正常工作。

接下来,我想把这些东西存储在一个大列表中,包含我曾经生成的所有敌人。注意,我在这里使用的是Vec,因为这将是我在游戏运行时不断添加的东西,我可能会将MonsterID克隆到这里,这个列表可能会变得相当大,它将是一排排的MonsterID。

接下来,我需要一些功能来基于MonsterID创建一个我将在游戏中使用的实际敌人。我可能会将MonsterID克隆到这个函数中,可能会将MonsterID克隆到敌人实例中,这样每个敌人实例都知道它是哪个怪物。

最后,假设我在一个B-tree映射中存储一些统计数据,这个映射从MonsterID到我在游戏过程中摧毁该怪物的次数。我在这里使用B-tree映射只是作为一种不同于哈希映射的数据结构,我们可以使用MonsterID作为B-tree映射中的键,因为它实现了Ord。

这里有一些不同的用例,可能还有更多。这只是一个例子,说明像这样的基本类型如何开始在整个系统中扩散,你可能需要经常克隆它,你可能需要将它存储在所有这些不同的数据结构中,突然间,这些操作的成本开始变得重要,开始累积起来。所以让我们看看当我们使用String时,克隆这个东西的成本和整体内存占用是多少。

下面是String的表示方式:

String中的实际字符串数据表示为堆上的字符缓冲区。String分配足够的内存来存储你的文本,显然,但然后它还分配了一些额外的空间,以便它可以在不需要重新分配的情况下增长。这里我们有”Goblin”和四个额外的字节备用容量,以防字符串需要进一步增长,尽管我们知道它不会,因为Goblin已经是一个完整的怪物名称了。

接下来,String结构本身由三个8字节的字组成:一个指针、一个长度和一个容量。指针直接指向字符串数据,长度指的是G-O-B-L-I-N,所以是6,容量包括末尾的额外四个字节,所以是10。

让我们看看克隆String是什么样子的。首先,我们需要克隆整个字符缓冲区,所以首先我们需要分配更多的内存,然后我们需要复制所有的字符,这是一个线性时间操作,换句话说,字符串越长,它需要的时间就越长。然后我们需要在栈上创建一个新的String结构,并将它指向新的字符缓冲区。注意,这次我们删除了额外的容量,因为String的克隆不会过度分配,它会给你一个确切大小的缓冲区。所以我们现在只有这个6的额外备用容量,这对我们现在并不真正有帮助,因为它与长度相同。

如果我们想再做一次克隆,我们必须做完全相同的事情。我们需要分配一个新的缓冲区,再次复制所有的字符,然后在栈上创建一个新的String结构,指向它。再次,我们有这个额外的容量字段,对我们来说并不真正有用。

希望你能看到,这个分配新内存的过程(顺便说一下,这是非常昂贵的)有点麻烦,而且String结构本身对于简单的目的来说有点大而且过于笨重,比如只是为了谈论goblins。

现在让我们看看同样的情况,但使用Arc而不是String。

使用Arc,我们从一些看起来不同的堆数据开始。首先,我们有这两个8字节的字,一个是强引用计数,下一个是弱引用计数,然后是我们的实际字符串数据。这已经看起来更大更奇怪了,但别担心,情况会变好的。

我们栈上的Arc只是一个指针和一个长度,它们只有16字节,因为它们没有String那个额外的容量字段。所以它只是指向我们这里的引用计数。

让我们看看克隆时会发生什么。

我们所需要做的就是复制栈上的那个结构,并增加我们的引用计数,所以现在是2。你注意到我们没有做任何类型的内存分配,我们没有对我们的字符串数据进行深度复制,我们只是在两个地方引用相同的字符串数据。

所以我们可以非常便宜地制作这个的克隆,而且字符串数据在多个Arc之间共享的事实也增加了它在我们查找时在缓存中的机会,因为任何时候我使用这四个Arc中的任何一个来读取它,它都会被加载到缓存中。相比之下,String指向的内存只有在我最近使用那个特定的String查找过时才会在缓存中。

所以你可以看到,这整个东西就轻量得多。这些Arc本身更小,所以在相同的内存量中可以容纳更多。坦率地说,这对于我们在程序中传递的不可变字符串来说,是一种更聪明的资源使用方式。

此外,我们在堆上为此付出的这两个额外字,是分摊到我们拥有的每一个Arc上的。所以它们是某种程度上被摊销的,而我们必须为栈上使用的每一个String付出一个额外的字。这两个在堆上的额外字,是的,2比1多,但它们在每个Arc实例之间共享,所以最终比每个String必须携带的那个额外字要少得多。

让我们看看如果我们直接将Arc插入到我们的MonsterID中而不是String会是什么样子,感觉如何。

首先,我们所有的派生都能像以前一样工作。你可以克隆一个Arc,你可以打印它的调试表示,你可以比较它,你可以哈希它,你也可以序列化和反序列化它,尽管你确实需要激活一个serde特性才能这样做,只是因为如果你想这样做,有一些小字需要你阅读,但这很简单直接。所以所有这些仍然像以前一样工作。

那么我们的as_str访问器呢?这个函数根本不需要改变,因为Arc实现了Deref<Target=str>,就像String一样。我们可以简单地引用它并返回,这就变成了对字符串切片的引用。所以这个函数不需要任何改变,它完全正常工作。

接下来,我们的MonsterID到敌人统计的哈希映射呢?我们的MonsterID结构体仍然实现了Eq和Hash,因为Arc实现了这些trait,所以这里也不需要任何改变。事实上,我会说在这里使用Arc更合适,因为String给你了很多修改底层字符串的API,但你不能修改哈希映射的键,因为你可能会破坏数据结构的不变性。所以使用Arc这样的不可变类型来表示你的键比使用String更合适。

继续,我的MonsterID的Vec现在将更加缓存效率,因为我从每个MonsterID中削减了整整一个字,现在它的大小只有之前的三分之二。

我的用于基于MonsterID创建实际敌人实例的函数现在可能更高效了,因为我想象这涉及某种MonsterID的克隆,而现在我们使用Arc,克隆变得更加高效。

最后,我们的B树映射与哈希映射类似,使用不可变数据作为键类型更合适,因为无论如何你都不允许修改B树映射中的键。这个B树映射现在也会更高效,因为它存储的数据更小,而且不需要为那些不需要可变性的情况付出可变性的代价。

所以Arc在所有这些例子中都胜出了。它更高效,而且可以直接替代String。那为什么不直接使用它呢?

这里有一个我一直在暗示但现在要明确说出来的要点:Vec和String是用来修改一堆东西的缓冲区的。它们用于推入、弹出、扩展和截断。如果你不需要这些功能,就不要使用它们,因为它们有一些与之相关的额外成本。

你注意到Vec和String上所有有趣的方法都需要一个可变的self参数。它们都是关于修改缓冲区,改变它的形状。如果你不需要这些功能,那就不要使用Vec和String。如果你只需要查看一些数据,比如问它的长度,看它是否为空,对它进行索引,遍历它,分割它,在其中搜索,所有这些功能都是由str和[T]直接提供的,你可以通过Arc很容易地访问这两者。所以如果这就是你所需要的,你就不需要String和Vec的全部功能,而且通过不为String和Vec付费,你可以获得很多性能提升。

这就是为什么你可能想要使用Arc<[T]>而不是Vec,或者使用Arc而不是String的原因。

现在我想展示一下Arc,因为我提到过它不好,这就是原因:

Arc开始时与String相同,有一个带有一些备用容量的缓冲区。但然后我们还需要将String本身放入一个Arc中。你看,我们在前面有那两个额外的字用于引用计数,然后是String的内容。然后Arc会指向那个String,克隆它会克隆对String的引用,但你看,如果我们想要访问实际写着”Goblin”的文本,我们需要跳到String,然后从String跳到Goblin。这整个过程就有点笨拙和尴尬,这就是为什么Arc不是一个好主意,当我们可以用Arc做得更好时。

最后,我提到如果你不需要克隆,你可以通过使用Box做得比Arc更好,这基本上是你能得到的最好的结果,假设你不需要克隆。这不会有任何额外的备用容量,它只是在堆上分配一些东西,指向它,并知道它有多大。

你不可能比这做得更好了。但当你克隆时,你是在对那个堆数据进行深度克隆,所以那将是一个内存分配和一个线性时间的复制。但如果你不支持克隆,在内存效率方面,你不可能做得比这更好了。所以如果这是你的用例,可以考虑Box。

就这些了,这就是全部内容。让我知道你的想法。谢谢收听,下次再见。

文章目录