堆分配

堆分配的代价不高。具体细节取决于使用的分配器，但每次分配和deallocation通常都需要获取一个全局锁，做一些非平凡的数据结构操作。并可能执行一个系统调用。小分配不一定比大分配便宜。值得了解哪些Rust数据结构和操作会导致分配，因为避免它们可以大大提高性能。

Rust Container Cheat Sheet有常见的Rust类型的可视化，是下面章节的绝佳配套。

Profiling

如果通用profile解析器显示 “malloc”、“free“和相关函数为热函数，那么很可能值得尝试降低分配率或使用其他分配器。

DHAT是降低分配率时可以使用的一个优秀的剖析器。它能精确地识别热分配点及其分配率。确切的结果会有所不同，但使用rustc的经验表明，每执行一百万条指令减少10条分配率可以有可衡量的性能改进（例如~1%）。

下面是DHAT的一些输出示例。

AP 1.1/25 (2 children) {
  Total:     54,533,440 bytes (4.02%, 2,714.28/Minstr) in 458,839 blocks (7.72%, 22.84/Minstr), avg size 118.85 bytes, avg lifetime 1,127,259,403.64 instrs (5.61% of program duration)
  At t-gmax: 0 bytes (0%) in 0 blocks (0%), avg size 0 bytes
  At t-end:  0 bytes (0%) in 0 blocks (0%), avg size 0 bytes
  Reads:     15,993,012 bytes (0.29%, 796.02/Minstr), 0.29/byte
  Writes:    20,974,752 bytes (1.03%, 1,043.97/Minstr), 0.38/byte
  Allocated at {
    #1: 0x95CACC9: alloc (alloc.rs:72)
    #2: 0x95CACC9: alloc (alloc.rs:148)
    #3: 0x95CACC9: reserve_internal<syntax::tokenstream::TokenStream,alloc::alloc::Global> (raw_vec.rs:669)
    #4: 0x95CACC9: reserve<syntax::tokenstream::TokenStream,alloc::alloc::Global> (raw_vec.rs:492)
    #5: 0x95CACC9: reserve<syntax::tokenstream::TokenStream> (vec.rs:460)
    #6: 0x95CACC9: push<syntax::tokenstream::TokenStream> (vec.rs:989)
    #7: 0x95CACC9: parse_token_trees_until_close_delim (tokentrees.rs:27)
    #8: 0x95CACC9: syntax::parse::lexer::tokentrees::<impl syntax::parse::lexer::StringReader<'a>>::parse_token_tree (tokentrees.rs:81)
  }
}

在这个例子中，描述所有的内容已经超出了本书的范围，但应该清楚的是，DHAT给出了大量关于分配的信息，比如它们发生的地点和频率，它们的规模有多大，它们的寿命有多长，以及它们被访问的频率。

Box

Box是最简单的堆分配类型。Box<T>值是一个在堆上分配的T值。

有时值得将结构体或枚举字段中的一个或多个字段装箱，以使类型更小。(更多信息请参见 Type Sizes 一章)。

除此之外，Box是直接的，并没有提供太多优化的空间。

Rc/Arc

[Rc]/[Arc]类似于Box，但堆上的值有两个引用计数。它们允许值共享，这可以是减少内存使用的有效方法。

[Rc]：https://doc.rust-lang.org/std/rc/struct.Rc.html [Arc]：https://doc.rust-lang.org/std/sync/struct.Arc.html

但是，如果用于很少共享的值，它们可以通过堆分配本来可能不会被堆分配的值来提高分配率。 Example.

与Box不同的是，在Rc/Arc值上调用clone并不涉及分配。相反，它只是增加一个引用计数。

Vec

[Vec]是一种堆分配类型，在优化分配数量和/或尽量减少浪费的空间方面有很大的空间。要做到这一点，需要了解其元素的存储方式。

[Vec]：https://doc.rust-lang.org/std/vec/struct.Vec.html

一个 “Vec “包含三个词：一个长度、一个容量和一个指针。如果容量是非零，元素大小是非零，指针将指向堆分配的内存；否则，它将不指向分配的内存。

即使 “Vec “本身不是堆分配的，元素（如果存在且大小非零）也会是堆分配的。如果存在非零大小的元素，那么存放这些元素的内存可能会比必要的大，为未来的元素提供空间。存在的元素数就是长度，不需要重新分配就可以容纳的元素数就是容量。

当向量需要增长到超过其当前容量时，元素将被复制到一个更大的堆分配中，旧的堆分配将被释放。

Vec growth

用普通方法创建一个新的、空的Vec。 (vec![] 或 Vec::new 或 Vec::default）的长度和容量为零，不需要进行堆分配。如果你反复将单个元素推到Vec的末端，它将周期性地重新分配。增长策略没有被指定，但在写这篇文章的时候，它使用了一个准双倍策略，结果是以下容量。0, 4, 8, 16, 32, 64, 等等. (它直接从0跳到4，而不是通过1和2，因为这在实践中避免了许多分配。) 随着向量的增长，重新分配的频率将以指数形式减少，但可能浪费的多余容量将以指数形式增加。

这种增长策略对于可增长的数据结构来说是典型的，在一般情况下是合理的，但如果你事先知道一个向量的可能长度，你可以做的往往更好。如果你有一个热向量分配站点（例如一个热的 Vec::push调用），值得使用eprintln!来打印该站点的向量长度，然后做一些后处理（例如使用counts）来确定长度分布。例如，你可能有很多短向量，也可能有较少的超长向量，优化分配站点的最佳方式也会相应变化。

Short Vecs

如果你有很多短向量，你可以使用smallveccrate中的SmallVec类型。SmallVec<[T;N]>是Vec的替代物，它可以在SmallVec本身中存储N个元素，如果元素数量超过这个数量，就会切换到堆分配。(还需要注意的是，vec![]字元必须用smallvec![]字元代替。) Example 1, Example 2.

SmallVec如果使用得当，可以可靠地降低分配率，但使用它并不能保证提高性能。对于正常的操作，它比Vec稍慢，因为它必须总是检查元素是否被堆分配。另外，如果N很高或者T很大，那么SmallVec<[T; N]>本身就会比Vec<T>大，复制SmallVec值的速度会比较慢。和以往一样，需要通过基准测试来确认优化是否有效。

如果你有很多短向量，并且你精确地知道它们的最大长度，[arrayvec]箱子中的ArrayVec比SmallVec更好。它不需要回落到堆分配，这使得它更快一些。 Example.

Longer Vecs

如果你知道一个向量的最小或精确大小，你可以用Vec::with_capacity、Vec::reserve或Vec::reserve_exact来保留一个特定的容量。例如，如果你知道一个向量将成长为至少有20个元素，这些函数可以使用一次分配立即提供一个至少有20个容量的向量，而一次推送一个项目将导致四次分配（对于4、8、16和32的容量）。 Example.

如果你知道一个向量的最大长度，上述函数也可以让你不分配多余的不必要的空间。同样，Vec::shrink_to_fit也可以用来尽量减少浪费的空间，但要注意它可能会引起重新分配。

String

一个String包含堆分配的字节。String的表示和操作与Vec<u8>非常相似。许多与增长和容量有关的Vec方法与String有对应关系，如String::with_capacity。

来自smallstr箱子的SmallString类型与SmallVec类型类似。

请注意，format!宏产生一个String，这意味着它进行了分配。如果你能通过使用字符串文字来避免format!的调用，就能避免这种分配。 Example.

Hash tables

HashSet和HashMap是哈希表。在分配方面，它们的表示和操作与Vec的表示和操作相似：它们有一个单一的连续的堆分配，存放键和值，随着表的增长，必要时重新分配。许多与增长和容量有关的Vec方法都有与HashSet/HashMap对应的方法，如HashSet::with_capacity。

Cow

有时候你有一些借来的数据，比如&str，大部分是只读的，但偶尔需要修改。每次都克隆数据会很浪费。相反，你可以通过Cow类型使用 “write-on-clone “语义，它既可以表示借来的数据，也可以表示拥有的数据。

通常情况下，当从一个借来的值x开始时，你用Cow::Borrowed(x)把它包在一个Cow中。因为Cow实现了Deref，所以你可以直接在它所包含的数据上调用非修改的方法。如果需要修改，Cow::to_mut将获得一个对所拥有的值的可修改引用，必要时进行克隆。

Cow的工作可能会很麻烦，但它往往是值得的。 Example 1, Example 2, Example 3, Example 4.

clone

在一个包含堆分配内存的值上调用[clone]通常会涉及额外的分配。例如，在一个非空的Vec上调用clone，需要对元素进行新的分配（但请注意，新Vec的容量可能与原Vec的容量不同）。例外的情况是Rc/Arc，clone的调用只是增加引用数。

clone_from是clone的替代方法。a.clone_from(&b)相当于a = b.clone()，但可以避免不必要的分配。例如，如果你想在一个现有的Vec之上克隆一个Vec，现有Vec的堆分配将尽可能地被重复使用，如下例所示。

#![allow(unused)]
fn main() {
let mut v1: Vec<u32> = Vec::with_capacity(99);
let v2: Vec<u32> = vec![1, 2, 3];
v1.clone_from(&v2); // v1's allocation is reused
assert_eq!(v1.capacity(), 99);
}

虽然clone通常会造成分配，但在很多情况下使用它是一件很合理的事情，往往可以使代码更简单。使用剖析数据来查看哪些clone调用是热门的，值得花力气去避免。

有时，由于(a)程序员的错误，或(b)代码中的变化，使以前必要的clone调用变得不必要，Rust代码最终会包含不必要的clone调用。如果你看到一个似乎没有必要的热clone调用，有时可以简单地删除它。 Example 1, Example 2, Example 3.

to_owned

ToOwned::to_owned]是为许多常见类型实现的。它从借来的数据中创建拥有的数据，通常是通过克隆的方式，因此经常会引起堆分配。例如，它可以用来从一个&str创建一个String。

有时，可以通过在结构中存储对借入数据的引用而不是自有副本来避免to_owned调用。这需要在结构体上做终身注解，使代码复杂化，只有在分析和基准测试表明值得时才可以这样做。 Example.

Cow

有时代码处理的是借用和拥有数据的混合。想象一下一个包含错误消息的向量，其中一些是静态字符串字面量，另一些是用 format! 构造的。显而易见的表示是 Vec<String>，如下例所示。

#![allow(unused)]
fn main() {
let mut errors: Vec<String> = vec![];
errors.push("something went wrong".to_string());
errors.push(format!("something went wrong on line {}", 100));
}

这需要一个 to_string 调用来将静态字符串字面量提升为 String，这会产生一次分配。

相反，您可以使用 Cow 类型，它可以保存借用或拥有的数据。借用值 x 被包装在 Cow::Borrowed(x) 中，拥有值 y 被包装在 Cow::Owned(y) 中。Cow 还为各种字符串、切片和路径类型实现了 From<T> trait，因此通常也可以使用 into。 （或者 Cow::from，这更长一些，但会产生更易读的代码，因为它使类型更清晰。）以下示例将所有这些内容整合在一起。

#![allow(unused)]
fn main() {
use std::borrow::Cow;
let mut errors: Vec<Cow<'static, str>> = vec![];
errors.push(Cow::Borrowed("something went wrong"));
errors.push(Cow::Owned(format!("something went wrong on line {}", 100)));
errors.push(Cow::from("something else went wrong"));
errors.push(format!("something else went wrong on line {}", 101).into());
}

现在，errors 包含了借用和拥有数据的混合，而无需进行任何额外的分配。这个示例涉及 &str/String，但其他配对，如 &[T]/Vec<T> 和 &Path/PathBuf 也是可能的。

Example 1, Example 2.

以上所有内容适用于数据是不可变的情况。但是，Cow 也允许将借用数据提升为拥有数据，如果需要对其进行修改。Cow::to_mut 将获得一个可变引用到一个拥有值，必要时进行克隆。这就是所谓的“写时复制”，也是 Cow 名称的由来。

Reusing Collections

有时你需要分阶段建立一个集合，如Vec。通常情况下，通过修改一个Vec比建立多个Vec然后将它们组合起来更好。

例如，如果你有一个函数 “do_stuff”，产生一个 “Vec”，可能会被多次调用。

#![allow(unused)]
fn main() {
fn do_stuff(x: u32, y: u32) -> Vec<u32> {
    vec![x, y]
}
}

It might be better to instead modify a passed-in Vec:

#![allow(unused)]
fn main() {
fn do_stuff(x: u32, y: u32, vec: &mut Vec<u32>) {
    vec.push(x);
    vec.push(y);
}
}

有时，值得保留一个可以重复使用的 “主力“集合。例如，如果一个循环的每次迭代都需要一个Vec，你可以在循环外声明Vec，在循环体中使用它，然后在循环体结束时调用clear（清空Vec而不影响它的容量）。这避免了分配，但代价是掩盖了一个事实，即每次迭代对Vec的使用与其他迭代无关。 Example 1, Example 2.

同样，有时值得在一个结构中保留一个 “主力 “集合，以便在一个或多个被重复调用的方法中重用。

从文件中逐行读取

BufRead::lines 使得逐行读取文件变得很容易：

#![allow(unused)]
fn main() {
fn blah() -> Result<(), std::io::Error> {
fn process(_: &str) {}
use std::io::{self, BufRead};
let mut lock = io::stdin().lock();
for line in lock.lines() {
    process(&line?);
}
Ok(())
}
}

但它生成的迭代器返回的是 io::Result<String>，这意味着它为文件中的每一行分配内存。

另一种方法是在循环中使用一个工作用的 String，通过 BufRead::read_line：

#![allow(unused)]
fn main() {
fn blah() -> Result<(), std::io::Error> {
fn process(_: &str) {}
use std::io::{self, BufRead};
let mut lock = io::stdin().lock();
let mut line = String::new();
while lock.read_line(&mut line)? != 0 {
    process(&line);
    line.clear();
}
Ok(())
}
}

这样可以将分配的次数降至最多几次，甚至可能只有一次。（确切的次数取决于需要多少次重新分配 line，这取决于文件中行长度的分布情况。）

这种方法只适用于循环体能够操作 &str 而不是 String 的情况。

Example.

使用不同的分配器

除了更改代码外，还可以通过使用不同的分配器来改善堆分配性能。请参阅 Alternative Allocators 部分获取详细信息。

避免回归

为了确保代码执行时的分配次数和/或大小不会意外增加，您可以使用 dhat-rs 的 堆使用测试 功能编写测试，检查特定代码段分配了预期量的堆内存。