Инженер-программист
0,2
рейтинг
5 января в 18:47

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

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


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

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


Перевод: Herman J. Radtke III
Константин @kstep
карма
46,0
рейтинг 0,2
Инженер-программист
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (11)

  • +1
    Поначалу это всё выглядит как магия, но после пары месяцев использования становится реально удобно, компилятор как лучший друг — не дает выстрелить себе в ногу на каждом шагу.
    • 0
      а вы где-то на коммерческих проектах применяете или может опенсорс или чисто для себя как хобби?
      • +1
        Я разрабатываю свою ОС — Airely. Вот последнее видео: https://youtu.be/HtdqmUuhIL4
      • 0
        Для меня это больше хобби, в основном мои проекты выросли из необходимости что-то с чем-то синтегрировать и автоматизировать для себя, поэтому в основном это обёртки вокруг разных API: mpd, pocket, vkrs,…
        Из чуть более известного — systemd-crontab-generator, a.k.a. systemd-cron-next.
  • –1
    Можете что-нибудь посоветовать по написанию идиоматичных wrapper'ов над ffi binding'ами? Например, какие-нибудь хорошо написанные высокоуровневые обёртки над сишными библиотеками, на код которых стоит посмотреть в этом разрезе.

    Из того, что сходу нашёл — это ffi guide, секция в The Book о ffi и некоторое количество статей. Параллельно читаю The Rustonomicon.

    Сами биндинги думал генерировать с помощью rust-bindgen, дабы не писать руками тонну кода, но местами оно выглядит странно. Например, генерирует префиксы в именах структур, в том числе, внешних по отношению к конкретному header'у (например Struct_stat, который на самом деле libc::stat и т. п.). Или даёт странные сигнатуры для callback'ов (unsafe extern "C" fn, что в случае rust 1.5.0 требует передавать unsafe функцию в качестве callback'а, т. к. обычная к unsafe не приводится.

    Если интересен контекст — хочу обернуть libsmbclient, как единственно живую и стабильную реализацию smb.
    • 0
      Посмотрите в сторону rust-sdl2, rust-sdl2_ttf, или на rust-lua53 — там совсем другой подход (скачиваются исходники Lua с официального сайта, собираются в либу и оборачиваются растом).
      • 0
        SDL bindings, по отзывам, одни из самых лучших.
        • 0
          Соглашусь. Там, правда, есть хитрость одна — скачать дев-либы с оффсайта и закинуть их в директорию самого раста, но, я считаю, это самое простое, что может быть при работе с чем-то не родным.
          А с родными зависимостями как раз меня подкупил Cargo — такой системы сборки нет ни у кого, насколько я знаю. Сам качает, сам компиляет, сам линкует — просто сказка.
          • –1
            Во многих языках это норма (ruby, python, js/node). При установке соответствующего пакета собираются нативные зависимости. Линкуются там, правда, только прослойки для интерпретатора, но идеологически довольно похоже.
            • 0
              Я больше сравнивал с C/C++, столько систем сборок, что ужас. И ни одна из них не сравнится с Cargo.
          • 0
            Особенно радует поддержка кастомных билд скриптов на расте, что позволяет делать такие вещи, как при сборке lua53 (скачивание исходников языка в сборке проекта) или моего systemd-cron-next (генерация systemd юнитов из handlebars-шаблонов).

            Понятно, что для скриптовых языков это всё не новость (pip, npm, rake...), но от компилируемого языка такой прелести лично я джва года давно ждал.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.