- PVSM.RU - https://www.pvsm.ru -

Создание функции на Rust, которая возвращает String или &str

От переводчика

КДПВ [1] Это последняя статья из цикла про работу со строками и памятью в Rust от Herman Radtke, которую я перевожу. Мне она показалась наиболее полезной, и изначально я хотел начать перевод с неё, но потом мне показалось, что остальные статьи в серии тоже нужны, для создания контекста и введения в более простые, но очень важные, моменты языка, без которых эта статья теряет свою полезность.


Мы узнали как создать функцию, которая принимает String или &str [2] (англ. [3]) в качестве аргумента. Теперь я хочу показать вам как создать функцию, которая возвращает String или &str. Ещё я хочу обсудить, почему нам это может понадобиться.

Для начала давайте напишем функцию, которая удаляет все пробелы из заданной строки. Наша функция может выглядеть примерно так:

fn remove_spaces(input: &str) -> String {
   let mut buf = String::with_capacity(input.len());

   for c in input.chars() {
      if c != ' ' {
         buf.push(c);
      }
   }

   buf
}

Эта функция выделяет память для строкового буфера, проходит по всем символам в строке input и добавляет все не пробельные символы в буфер buf. Теперь вопрос: что если на входе нет ни одного пробела? Тогда значение input будет точно таким же, как и buf. В таком случае было бы более эффективно вообще не создавать buf. Вместо этого мы бы хотели просто вернуть заданный input обратно пользователю функции. Тип input&str, но наша функция возвращает String. Мы бы могли изменить тип input на String:

fn remove_spaces(input: String) -> String { ... }

Но тут возникают две проблемы. Во-первых, если input станет String, пользователю функции придётся перемещать право владения input в нашу функцию, так что он не сможет работать с этими же данными в будущем. Нам следует брать владение input только если оно нам действительно нужно. Во-вторых, на входе уже может быть &str, и тогда мы заставляем пользователя преобразовывать строку в String, сводя на нет нашу попытку избежать выделения памяти для buf.

Клонирование при записи

На самом деле мы хотим иметь возможность возвращать нашу входную строку (&str) если в ней нет пробелов, и новую строку (String) если пробелы есть и нам понадобилось их удалить. Здесь и приходит на помощь тип копирования-при-записи (clone-on-write) Cow [4]. Тип Cow позволяет нам абстрагироваться от того, владеем ли мы переменной (Owned) или мы её только позаимствовали (Borrowed). В нашем примере &str — ссылка на существующую строку, так что это будут заимствованные данные. Если в строке есть пробелы, нам нужно выделить память для новой строки String. Переменная buf владеет этой строкой. В обычном случае мы бы переместили владение buf, вернув её пользователю. При использовании Cow мы хотим переместить владение buf в тип Cow, а затем вернуть уже его.

use std::borrow::Cow;

fn remove_spaces<'a>(input: &'a str) -> Cow<'a, str> {
    if input.contains(' ') {
        let mut buf = String::with_capacity(input.len());

        for c in input.chars() {
            if c != ' ' {
                buf.push(c);
            }
        }

        return Cow::Owned(buf);
    }

    return Cow::Borrowed(input);
}

Наша функция проверяет, содержит ли исходный аргумент input хотя бы один пробел, и только затем выделяет память под новый буфер. Если в input пробелов нет, то он просто возвращается как есть. Мы добавляем немного сложности во время выполнения [5], чтобы оптимизировать работу с памятью. Обратите внимание, что у нашего типа Cow то же самое время жизни, что и у &str. Как мы уже говорили ранее, компилятору нужно отслеживать использование ссылки &str, чтобы знать, когда можно безопасно освободить память (или вызвать метод-деструктор, если тип реализует Drop).

Красота Cow в том, что он реализует типаж Deref, так что вы можете вызывать для него не изменяющие данные методы, даже не зная, выделен ли для результата новый буфер. Например:

let s = remove_spaces("Herman Radtke");
println!("Длина строки: {}", s.len());

Если мне нужно изменить s, то я могу преобразовать её во владеющую переменную с помощью метода into_owned(). Если Cow содержит заимствованные данные (выбран вариант Borrowed), то произойдёт выделение памяти. Такой подход позволяет нам клонировать (то есть выделять память) лениво, только когда нам действительно нужно записать (или изменить) в переменную.

Пример с изменяемым Cow::Borrowed:

let s = remove_spaces("Herman"); // s завёрнута в Cow::Borrowed
let len = s.len(); // функция с доступом только для чтения вызывается через Deref
let owned: String = s.into_owned(); // выделяется память для новой строки String

Пример с изменяемым Cow::Owned:

let s = remove_spaces("Herman Radtke"); // s завёрнута в Cow::Owned
let len = s.len(); // функция с доступом только для чтения вызывается через Deref
let owned: String = s.into_owned(); // выделения памяти не происходит, у нас уже есть строка String

Идея Cow в следующем:

  • Отложить выделение памяти на как можно долгий срок. В лучшем случае мы никогда не выделим новую память.
  • Дать возможность пользователю нашей функции remove_spaces не волноваться о выделении памяти. Использование Cow будет одинаковым в любом случае (будет ли новая память выделена, или нет).

Использование типажа Into

Раньше мы говорили об использовании типажа Into [2] (англ. [3]) для преобразования &str в String. Точно так же мы можем использовать его для конвертации &str или String в нужный вариант Cow. Вызов .into() заставит компилятор выбрать верный вариант конвертации автоматически. Использование .into() нисколько не замедлит наш код, это просто способ избавиться от явного указания варианта Cow::Owned или Cow::Borrowed.

fn remove_spaces<'a>(input: &'a str) -> Cow<'a, str> {
    if input.contains(' ') {
        let mut buf = String::with_capacity(input.len());
        let v: Vec<char> = input.chars().collect();

        for c in v {
            if c != ' ' {
                buf.push(c);
            }
        }

        return buf.into();
    }
    return input.into();
}

Ну и напоследок мы можем немного упростить наш пример с использованием итераторов:

fn remove_spaces<'a>(input: &'a str) -> Cow<'a, str> {
    if input.contains(' ') {
        input
        .chars()
        .filter(|&x| x != ' ')
        .collect::<std::string::String>()
        .into()
    } else {
        input.into()
    }
}

Реальное использование Cow

Мой пример с удалением пробелов кажется немного надуманным, но в реальном коде такая стратегия тоже находит применение. В ядре Rust есть функция, которая преобразует байты в UTF-8 строку с потерей невалидных сочетаний байт [6], и функция, которая переводит концы строк из CRLF в LF [7]. Для обеих этих функций есть случай, при котором можно вернуть &str в оптимальном случае, и менее оптимальный случай, требующий выделения памяти под String. Другие примеры, которые мне приходят в голову: кодирование строки в валидный XML/HTML или корректное экранирование спецсимволов в SQL запросе. Во многих случаях входные данные уже правильно закодированы или экранированы, и тогда лучше просто вернуть входную строку обратно как есть. Если же данные нужно менять, то нам придётся выделить память для строкового буфера и вернуть уже его.

Зачем использовать String::with_capacity()?

Пока мы говорим об эффективном управлении памятью, обратите внимание, что я использовал String::with_capacity() вместо String::new() при создании строкового буфера. Вы можете использовать и String::new() вместо String::with_capacity(), но гораздо эффективнее выделять память для буфера сразу всю требуемую память, вместо того, чтобы перевыделять её по мере того, как мы добавляем в буфер новые символы.

String — на самом деле вектор Vec из кодовых позиций (code points) UTF-8. При вызове String::new() Rust создаёт вектор нулевой длины. Когда мы помещаем в строковый буфер символ a, например с помощью input.push('a'), Rust должен увеличить ёмкость вектора. Для этого он выделит 2 байта памяти. При дальнейшем помещении символов в буфер, когда мы превышаем выделенный объём памяти, Rust удваивает размер строки, перевыделяя память. Он продолжит увеличивать ёмкость вектора каждый раз при её превышении. Последовательность выделяемой ёмкости такая: 0, 2, 4, 8, 16, 32, …, 2^n, где n — количество раз, когда Rust обнаружил превышение выделенного объёма памяти. Перевыделение памяти очень медленное (поправка: kmc_v3 объяснил [8], что оно может быть не настолько медленным, как я думал). Rust не только должен попросить ядро выделить новую память, он ещё должен скопировать содержимое вектора из старой области памяти в новую. Взгляните на исходный код Vec::push [9], чтобы самим увидеть логику изменения размера вектора.

Уточнение о перевыделении памяти от kmc_v3

Всё может быть не так уж плохо, потому что:

  • Любой приличный аллокатор просит память у ОС большими кусками, а затем выдаёт её пользователям.
  • Любой приличный многопоточный аллокатор памяти так же поддерживает кеши для каждого потока, так что вам не надо всё время синхронизировать к нему доступ.
  • Очень часто можно увеличить выделенную память на месте, и в таких случаях копирования данных не будет. Может вы и выделили только 100 байт, но если следующая тысяча байт окажется свободной, аллокатор просто выдаст их вам.
  • Даже в случае копирования, используется побайтовое копирование с помощью memcpy [10], с полностью предсказуемым способом доступа к памяти. Так что это, пожалуй, наиболее эффективный способ перемещения данных из памяти в память. Системная библиотека libc обычно включает в себя memcpy с оптимизациями для вашей конкретной микроархитектуры.
  • Вы также можете «перемещать» большие выделенные куски памяти с помощью перенастройки MMU [11], то есть вам понадобится скопировать только одну страницу данных. Однако, обычно изменение страничных таблиц имеет большую фиксированную стоимость, так что способ подходит для очень больших векторов. Я не уверен, что jemalloc в Rust делает такие оптимизации.

Изменение размера std::vector в C++ может оказаться очень медленным из-за того, что нужно вызывать конструкторы перемещения индивидуально для каждого элемента, а они могут выкинуть исключение.

В общем, мы хотим выделять новую память только тогда, когда она нужна, и ровно столько, сколько нужно. Для коротких строк, как например remove_spaces("Herman Radtke"), накладные расходы на перевыделение памяти не играют большой роли. Но что если я захочу удалить все пробелы во всех JavaScript файлах на моём сайте? Накладные расходы на перевыделение памяти для буфера будут намного больше. При помещении данных в вектор (String или любой другой), очень полезно указывать размер памяти, которая потребуется, при создании вектора. В лучшем случае вы заранее знаете нужную длину, так что ёмкость вектора может быть установлена точно. Комментарии к коду [12] Vec предупреждают примерно о том же.

Что ещё почитать?

Автор: kstep

Источник [1]


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/programmirovanie/108061

Ссылки в тексте:

[1] Image: http://habrahabr.ru/post/274565/

[2] создать функцию, которая принимает String или &str: http://habrahabr.ru/post/274455/

[3] англ.: http://hermanradtke.com/2015/05/06/creating-a-rust-function-that-accepts-string-or-str.html

[4] Cow: https://doc.rust-lang.org/stable/std/borrow/enum.Cow.html

[5] сложности во время выполнения: https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2#.D0.90.D0.BD.D0.B0.D0.BB.D0.B8.D0.B7_.D1.82.D1.80.D1.83.D0.B4.D0.BE.D1.91.D0.BC.D0.BA.D0.BE.D1.81.D1.82.D0.B8_.D0.B0.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC.D0.BE.D0.B2

[6] преобразует байты в UTF-8 строку с потерей невалидных сочетаний байт: https://github.com/rust-lang/rust/blob/720735b9430f7ff61761f54587b82dab45317938/src/libcollections/string.rs#L153

[7] переводит концы строк из CRLF в LF: https://github.com/rust-lang/rust/blob/c23a9d42ea082830593a73d25821842baf9ccf33/src/libsyntax/parse/lexer/mod.rs#L271

[8] объяснил: http://www.reddit.com/r/rust/comments/37q8sr/creating_a_rust_function_that_returns_a_str_or/croylbu

[9] Vec::push: https://github.com/rust-lang/rust/blob/720735b9430f7ff61761f54587b82dab45317938/src/libcollections/vec.rs#L628

[10] memcpy: https://www.opennet.ru/man.shtml?topic=memcpy&category=3&russian=0

[11] MMU: https://ru.wikipedia.org/wiki/%D0%91%D0%BB%D0%BE%D0%BA_%D1%83%D0%BF%D1%80%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BF%D0%B0%D0%BC%D1%8F%D1%82%D1%8C%D1%8E

[12] Комментарии к коду: https://github.com/rust-lang/rust/blob/720735b9430f7ff61761f54587b82dab45317938/src/libcollections/vec.rs#L147-152

[13] String или &str в функциях Rust: http://habrahabr.ru/post/274485/

[14] оригинал: http://hermanradtke.com/2015/05/03/string-vs-str-in-rust-functions.html