От переводчика
Это последняя статья из цикла про работу со строками и памятью в Rust от Herman Radtke, которую я перевожу. Мне она показалась наиболее полезной, и изначально я хотел начать перевод с неё, но потом мне показалось, что остальные статьи в серии тоже нужны, для создания контекста и введения в более простые, но очень важные, моменты языка, без которых эта статья теряет свою полезность.
Мы узнали как создать функцию, которая принимает String или &str (англ.) в качестве аргумента. Теперь я хочу показать вам как создать функцию, которая возвращает
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. Тип 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
пробелов нет, то он просто возвращается как есть. Мы добавляем немного сложности во время выполнения, чтобы оптимизировать работу с памятью. Обратите внимание, что у нашего типа 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 (англ.) для преобразования &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 строку с потерей невалидных сочетаний байт, и функция, которая переводит концы строк из CRLF в LF. Для обеих этих функций есть случай, при котором можно вернуть &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 объяснил, что оно может быть не настолько медленным, как я думал). Rust не только должен попросить ядро выделить новую память, он ещё должен скопировать содержимое вектора из старой области памяти в новую. Взгляните на исходный код Vec::push, чтобы самим увидеть логику изменения размера вектора.
- Любой приличный аллокатор просит память у ОС большими кусками, а затем выдаёт её пользователям.
- Любой приличный многопоточный аллокатор памяти так же поддерживает кеши для каждого потока, так что вам не надо всё время синхронизировать к нему доступ.
- Очень часто можно увеличить выделенную память на месте, и в таких случаях копирования данных не будет. Может вы и выделили только 100 байт, но если следующая тысяча байт окажется свободной, аллокатор просто выдаст их вам.
- Даже в случае копирования, используется побайтовое копирование с помощью
memcpy
, с полностью предсказуемым способом доступа к памяти. Так что это, пожалуй, наиболее эффективный способ перемещения данных из памяти в память. Системная библиотека libc обычно включает в себяmemcpy
с оптимизациями для вашей конкретной микроархитектуры. - Вы также можете «перемещать» большие выделенные куски памяти с помощью перенастройки MMU, то есть вам понадобится скопировать только одну страницу данных. Однако, обычно изменение страничных таблиц имеет большую фиксированную стоимость, так что способ подходит для очень больших векторов. Я не уверен, что
jemalloc
в Rust делает такие оптимизации.
Изменение размера std::vector
в C++ может оказаться очень медленным из-за того, что нужно вызывать конструкторы перемещения индивидуально для каждого элемента, а они могут выкинуть исключение.
В общем, мы хотим выделять новую память только тогда, когда она нужна, и ровно столько, сколько нужно. Для коротких строк, как например remove_spaces("Herman Radtke")
, накладные расходы на перевыделение памяти не играют большой роли. Но что если я захочу удалить все пробелы во всех JavaScript файлах на моём сайте? Накладные расходы на перевыделение памяти для буфера будут намного больше. При помещении данных в вектор (String
или любой другой), очень полезно указывать размер памяти, которая потребуется, при создании вектора. В лучшем случае вы заранее знаете нужную длину, так что ёмкость вектора может быть установлена точно. Комментарии к коду Vec
предупреждают примерно о том же.
Что ещё почитать?
String
или&str
в функциях Rust (оригинал)- Создание функции на Rust, которая принимает
String
или&str
(оригинал)
Автор: kstep