Does Iterator::collect allocate the same amount of memory as String::with_capacity?

Question

In C++ when joining a bunch of strings (where each element's size is known roughly), it's common to pre-allocate memory to avoid multiple re-allocations and moves:

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);

Similarly, I did this in Rust (this chunk needs the 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
}

I was told that the idiomatic way of doing it is a single expression

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

While I really like it and want to use it, from a memory allocation point of view, would the former allocate less chunks than the latter?

I disassembled this with cargo rustc --release -- --emit asm -C "llvm-args=-x86-asm-syntax=intel" but it doesn't have source code interspersed, so I'm at a loss.

Answer 1

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

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

第二个版本分配了至少两次：首先，它创建一个Vec<&str>并push通过将&strs 增长到它。然后，它计算所有&strs 的总大小，并创建一个String具有正确大小的新大小。（此代码位于中的join_generic_copy方法中str.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用途FromIterator为String，这将尝试使用下界的size_hint从Iterator执行Graphemes。然而，正如我前面提到的，扩展字形集群可以任意长，所以下界不能有任何大于1。更糟的是，&strS可以是空的，所以FromIterator<&str>对于String不知道任何有关结果以字节为单位的大小。这段代码只是创建一个空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除非您觉得它可以更好地表达意图，并且您不关心额外的分配，否则不应将其重写为use 。

有关

• 平整和收集切片的效率