rust - Iterator::collect 是否分配与 String::with_capacity 相同的内存量？

Question

在 C++ 中，当连接一堆字符串（其中每个元素的大小大致已知）时，通常会预先分配内存以避免多次重新分配和移动：

std::vector<std::string> words;
constexpr size_t APPROX_SIZE = 20;

std::string phrase;
phrase.reserve((words.size() + 5) * APPROX_SIZE);  // <-- avoid multiple allocations
for (const auto &w : words)
  phrase.append(w);

同样，我在 Rust 中做了这个（这个块需要unicode-segmentation crate）

fn reverse(input: &str) -> String {
    let mut result = String::with_capacity(input.len());
    for gc in input.graphemes(true /*extended*/).rev() {
        result.push_str(gc)
    }
    result
}

有人告诉我，惯用的做法是一个单一的表达方式

fn reverse(input: &str) -> String {
  input
      .graphemes(true /*extended*/)
      .rev()
      .collect::<Vec<&str>>()
      .concat()
}

虽然我真的很喜欢它并想使用它，但从内存分配的角度来看，前者分配的块会比后者少吗？

我用它反汇编了它，cargo rustc --release -- --emit asm -C "llvm-args=-x86-asm-syntax=intel"但它没有穿插源代码，所以我很茫然。

标签： rustdynamic-memory-allocation

Answer 1

您的原始代码很好，我不建议更改它。

原始版本分配一次： inside String::with_capacity。

第二个版本至少分配两次：首先，它创建 a并通过ing s来Vec<&str>增长它。然后，它计算所有s 的总大小并创建一个具有正确大小的新的。（此代码在 中的方法中。）这很糟糕，原因有以下几个：push&str&strStringjoin_generic_copystr.rs

1. 显然，它不必要地分配。
2. 字素簇可以任意大，因此中间体Vec不能提前有效地调整大小——它只是从大小 1 开始并从那里增长。
3. 对于典型的字符串，它分配的空间比存储最终结果实际需要的空间多得多，因为&str通常大小为 16 字节，而 UTF-8 字形簇通常远小于此。
4. 它浪费时间迭代中间体Vec以获得最终尺寸，您可以从原始尺寸中获取它&str。

最重要的是，我什至不认为这个版本是惯用collect的，因为它是一个临时版本Vec，以便对其进行迭代，而不是collect像您在早期版本的答案中那样仅仅使用原始迭代器。此版本修复了问题 #3 并使 #4 无关紧要，但不能令人满意地解决 #2：

input.graphemes(true).rev().collect()

collect使用FromIteratorfor String，它将尝试使用size_hint实现Iteratorfor的下限Graphemes。但是，正如我之前提到的，扩展的字形簇可以任意长，因此下限不能大于 1。更糟糕的是，&strs 可能为空，因此FromIterator<&str>forString不知道结果的大小（以字节为单位） . 此代码只是创建一个空并重复String调用它。push_str

需要明确的是，这还不错！String有一个增长策略来保证分摊的 O(1) 插入，所以如果你有大部分不需要经常重新分配的小字符串，或者你不相信分配成本是一个瓶颈，collect::<String>()那么在这里使用可能是合理的，如果你会发现它更具可读性和更容易推理。

让我们回到您的原始代码。

let mut result = String::with_capacity(input.len());
for gc in input.graphemes(true).rev() {
    result.push_str(gc);
}

这是惯用的。collect也是惯用的，但collect基本上都是上面的，初始容量不太准确。由于collect没有做你想做的事，所以自己编写代码并不习惯。

还有一个更简洁的迭代器版本，它仍然只进行一次分配。使用extend方法，它是Extend<&str>for的一部分String：

fn reverse(input: &str) -> String {
    let mut result = String::with_capacity(input.len());
    result.extend(input.graphemes(true).rev());
    result
}

我有一种extend更好的模糊感觉，但这两种方式都是编写相同代码的完全惯用方式。你不应该重写它来使用collect，除非你觉得它更好地表达了意图并且你不关心额外的分配。

有关的

• 压扁和收集切片的效率