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

в 15:47, , рубрики: Rust, аллокатор, выделение памяти, память, Программирование, строки

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

КДПВ Это последняя статья из цикла про работу со строками и памятью в 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, чтобы самим увидеть логику изменения размера вектора.

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

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

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

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

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

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

Автор: kstep

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js