Распределяет ли Iterator :: collect тот же объем памяти, что и String :: with_capacity? - PullRequest
Новая
       20

Распределяет ли Iterator :: collect тот же объем памяти, что и String :: with_capacity?

4 голосов
/ 29 октября 2019

В 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 (этому фрагменту нужна юникод-сегментация ящик) 

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", но у него нет источникакод перемежается, поэтому я в растерянности.

1 Ответ

6 голосов
/ 29 октября 2019

Ваш исходный код в порядке, и я не рекомендую изменять его.

Оригинальная версия выделяется один раз: внутри String::with_capacity.

Вторая версия выделяет как минимум дважды: во-первых, он создает Vec<&str> и увеличивает его на push, используя &str s. Затем он подсчитывает общий размер всех &str s и создает новый 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. Хуже, &str s может быть пустым, поэтому 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> для String: 

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

У меня есть смутное ощущение, что extend приятнее, но оба из них - совершенно идиоматические способы написаниятот же код. Вам не следует переписывать его, чтобы использовать collect, если только вы не чувствуете, что оно лучше выражает намерение и , вам не нужны дополнительные выделения.

Related

...