Тайная жизнь коров

Перевод | Автор оригинала: Pascal Hertleif

Многие на RustFest Paris упоминали коров - что может быть удивительно, если вы никогда не видели std::заимствовать::Cow!

Cow в этом контексте означает «Клонировать при записи» и представляет собой тип, который позволяет повторно использовать данные, если они не были изменены. Почему-то эти бычьи сверхспособности стандартной библиотеки Rust, кажется, хорошо хранятся в секрете, хотя они и не новы. В этом посте мы углубимся в этот очень полезный тип указателя, объяснив, почему в языках системного программирования вам нужен такой тонкий контроль, подробно объясним Cows и сравните их с другими способами организации ваших данных.

Организация данных

Вот к чему все сводится: люди хотят иметь хороший и точный способ организации своих данных. И они хотят, чтобы их язык программирования поддерживал их. Вот почему многие новые языки включают в себя набор структур данных, оптимизированных для различных случаев использования, и именно поэтому разработчики программного обеспечения так часто имеют дело с документацией по API. Чтобы гарантировать, что ваш код имеет ожидаемые характеристики производительности, важно знать, какой фрагмент данных представлен в каком виде.

В языках системного программирования это в некоторых отношениях даже более важно. Ты хочешь знать:

1. где именно находятся ваши данные,
2. что он эффективно хранится,
3. что он удаляется, как только вы перестанете его использовать,
4. И что вы не копируете это без нужды.

Обеспечение всех этих свойств - отличный способ писать быстрые программы. Давайте посмотрим, как это сделать в Rust.

Где находятся наши данные

Совершенно ясно, где находятся ваши данные. По умолчанию примитивные типы и структуры, содержащие примитивные типы, размещаются в стеке без какого-либо выделения динамической памяти. Если вы хотите хранить данные размера, известного только во время выполнения (например, текстовое содержимое файла), вам необходимо использовать тип, который динамически выделяет память (в куче), например String или Vec. Вы можете явно выделить тип данных в куче, заключив его в Box.

(Если вы не знакомы с понятием «стек и куча», вы можете найти хорошее объяснение в этой главе официальной книги Rust.)

Создание новой (непустой) строки означает выделение памяти, что является довольно затратной операцией. Такой язык, как Rust, дает вам довольно много возможностей пропустить некоторые выделения, и это может значительно ускорить критические для производительности части вашего кода. (Спойлер: Корова - один из таких вариантов.)

Структурирование данных

Если вы знаете, что вы будете делать со своими данными, вы, вероятно, сможете придумать, как их лучше всего хранить. Если вы, например, всегда просматриваете известный список значений, вам подойдет массив (или Vec). Если вам нужно искать значения по известным ключам, и вам не важен порядок их хранения, хеш-карта - это хорошо. Если вам нужен стек для размещения данных из разных потоков, вы можете использовать crossbeam-deque. Это просто для того, чтобы дать вам несколько примеров - есть книги по этой теме, и вы должны их прочитать. Корова сама по себе здесь не поможет, но вы можете использовать ее в своих структурах данных.

Удаление данных

К счастью, в Rust легко убедиться, что наши данные удаляются из памяти как можно скорее (чтобы мы не использовали слишком много памяти и не замедляли работу системы). Rust использует модель владения, при которой ресурсы автоматически удаляются, когда они выходят за пределы области видимости, поэтому нет необходимости периодически запускать сборщик мусора для освобождения памяти. Конечно, вы все равно можете тратить память, выделяя слишком много ее вручную или создавая ссылочные циклы и сбрасывая ее.

Нет ненужного копирования

Один из важных шагов к тому, чтобы быть ответственным гражданином в отношении использования памяти, - это не копировать данные больше, чем необходимо. Если у вас, например, есть функция, которая удаляет пробелы в начале строки, вы можете создать новую строку, содержащую только символы после ведущего пробела. (Помните: новая строка означает новое выделение памяти.) Или вы можете вернуть часть исходной строки, которая начинается после ведущего пробела. Второй вариант требует, чтобы мы сохранили исходные данные, потому что наш новый фрагмент просто ссылается на него внутри. Это означает, что вместо копирования любого количества байтов, которое содержит ваша строка, мы просто записываем два числа: указатель на точку в исходной строке после ведущего пробела и длину оставшейся строки, которая нас интересует. (В Rust принято носить с собой длину.)

Но как насчет более сложной функции? Представим, что мы хотим заменить некоторые символы в строке. Всегда ли нам нужно копировать это с замененными символами? Или можно поступить по-умному и вернуть какой-нибудь указатель на исходную строку, если в замене не было необходимости? Действительно, в Rust это возможно! В этом вся суть Cow.

Что такое корова?

В Rust сокращение «Cow» означает «клонировать при записи» 1. Это перечисление с двумя состояниями: Borrowed и Owned. Это означает, что вы можете использовать его, чтобы абстрагироваться от того, владеете ли вы данными или просто имеете на них ссылку. Это особенно полезно, когда вы хотите вернуть тип из функции, которую может или не нужно выделять.

Стандартный пример

Давайте посмотрим на пример. Допустим, у вас есть путь и вы хотите преобразовать его в строку. К сожалению, не все пути файловой системы допустимы для UTF-8 (строки Rust гарантированно имеют кодировку UTF-8). В Rust есть удобная функция для получения строки независимо: Path::to_string_lossy. Когда путь уже является допустимым UTF-8, он вернет ссылку на исходные данные, в противном случае он создаст новую строку, в которой недопустимые символы заменены символом �.

use std::borrow::Cow;
use std::path::Path;

let path = Path::new("foo.txt");
match path.to_string_lossy() {
    Cow::Borrowed(_str_ref) => println!("path was valid UTF-8"),
    Cow::Owned(_new_string) => println!("path was not valid UTF-8"),
}

Мускулистое определение

Имея это в виду, давайте посмотрим на фактическое определение коровы:

enum Cow<'a, B: ToOwned + ?Sized + 'a> {
    /// Borrowed data.
    Borrowed(&'a B),
    /// Owned data.
    Owned(<B as ToOwned>::Owned),
}

Как видите, требуется некоторое убеждение, чтобы Rust принял этот тип таким образом, чтобы мы могли с ним работать. Давайте пройдемся по порядку.

• 'a - время жизни, в течение которого нам нужно, чтобы наши данные были действительными. Для случая Owned это не очень интересно (чтобы Cow владела данными - это действительно до тех пор, пока Cow не выйдет из области видимости), но в случае, если Cow содержит заимствованные данные, это время жизни является ограничением, установленным данными, на которые мы ссылаемся. У нас не может быть коровы, которая ссылается на уже освобожденную память, и rustc сообщит нам, когда это возможно, упомянув, что корова переживает свое 'a.

• ToOwned - это трэйта, которая определяет метод преобразования заимствованных данных в собственные данные (скорее всего, путем клонирования и предоставления нам права собственности на новое распределение). Тип, который мы получаем от этого метода, является ассоциированным типом для трэйта, и его имя принадлежит (да, то же имя, что и вариант Cow, извините). Это позволяет нам ссылаться на него в Owned (<B as ToOwned>::Owned).

• Чтобы сделать это немного более конкретным, предположим, что у нас есть Cow, которая хранит &str (в случае Borrowed). Реализация ToOwned для str имеет тип Owned = String, поэтому <&str as ToOwned>::Owned == String.

-? Размер забавный. По умолчанию Rust ожидает, что все типы будут иметь известный размер, что выражается неявным ограничением для свойства маркера Sized. Вы можете явно отказаться от этого, добавив «ограничение» на? Sized.

Дело в том, что не все возможные типы имеют известный размер. Например, [u8] - это массив байтов где-то в памяти, но мы не знаем его длины. В коде приложения вы не увидите подобный тип напрямую, вы увидите его за ссылками. И обратите внимание: в Rust сама ссылка может содержать длину. (Смотрите, что я писал выше о срезах!)

Но как это снова относится к Корове? Видите ли, буква B в определении Cow находится за ссылкой: когда-то видна непосредственно в варианте Borrowed, а второй тип скрыт в ToOwned::Owned (который имеет тип Borrow ). Поскольку корова должна иметь возможность содержать &[u8], ее определение должно работать для &'a B, где B = [u8]. Это, в свою очередь, означает, что нужно сказать: «Нам не требуется, чтобы это было Sized, мы все равно знаем, что это за ссылкой» - именно это и делает синтаксис? Sized.

Хорошо, пока все хорошо! Однако позвольте мне указать на одну вещь: если вы хотите сохранить входную строку &'в корове (например, используя Cow::Borrowed (&' input str)), каков конкретный тип коровы? (Общий - Cow <'a, T>.)

Правильно! Корова <'input, str>! Определение типа для заимствованного варианта содержит &'a T, поэтому наш общий тип - это тип, на который мы ссылаемся. Это также означает, что ToOwned нужно реализовывать не для ссылок, а для конкретных типов, таких как str и Path.

Позвольте мне отметить кое-что об этом времени жизни, которое корова несет с собой очень быстро: если вы хотите заменить тип полосы в struct Foo {bar: String} на Cow, вам нужно будет указать время жизни ссылки, которую может include: struct Foo <'a> {bar: Cow <' a, str>}. Это означает, что каждый раз, когда вы теперь используете Foo, это время жизни будет отслеживаться, и каждый раз, когда вы берете или возвращаете Foo, вам может потребоваться просто аннотировать его.

Один из простых способов обойти это - использовать static: вы можете опустить аннотацию времени жизни в своей структуре, но ваша Cow может содержать только ссылки на статическую память. Это может показаться менее полезным, чем универсальное время жизни - потому что это так, - но в случае функций и типов, которые содержат или возвращают новые данные или статические значения по умолчанию, известные во время компиляции, этого может быть достаточно.

Коровы в дикой природе

Знать коров в теории - это прекрасно, но примеры, которые мы видели до сих пор, дают вам лишь небольшой взгляд на то, когда их можно использовать на практике. К сожалению, как оказалось, не многие API-интерфейсы Rust открывают доступ к Cows. Может быть, потому что они рассматриваются как вещь, которую вы можете представить, когда у вас есть узкое место в производительности, или, может быть, это потому, что люди не хотят добавлять аннотации времени жизни к своим структурам (и они не хотят или не могут использовать Cow < 'статический, T>).

Смешанные статические и динамические строки

Один очень интересный вариант использования Cows - это работа с функциями, которые либо возвращают статические строки (то есть строки, которые вы буквально пишете в исходном коде), либо динамические строки, которые собираются во время выполнения. В книге Джима Бланди и Джейсона Орендорфа Programming Rust есть такой пример:

use std::borrow::Cow;

fn describe(error: &Error) -> Cow<'static, str> {
    match *error {
        Error::NotFound => "Error: Not found".into(),
        Error::Custom(e) => format!("Error: {}", e).into(),
    }
}

Небольшое отступление: видите, как мы используем трэйту Into, чтобы сделать построение коров сверхкоротким? Into является противоположностью From и реализован для всех типов, реализующих From. Итак, компилятор знает, что нам нужен Cow <'static, str>, и дал ему String или &' static str. К счастью для нас, impl <'a> From<&' a str> для Cow <'a, str> и impl <' a> From для Cow <'a, str> находятся в стандартной библиотеке, поэтому rustc можно найти и позвонить!

Почему это очень крутой пример? Пользователь Reddit 0x7CFE сказал об этом так:

• Самым важным является то, что, поскольку Cow <'static, str> derefs2 до &str, он может действовать как замена везде, где ожидается &str. Итак, если бы последний вариант ошибки был добавлен к уже существующей базе кода, все было бы просто работать без какого-либо серьезного рефакторинга.

• В других языках, таких как C++, вам, вероятно, придется решить, [либо] возвращать всю версию распределения, такую как std::string, или избавиться от деталей и страдать от плохой эргономики, где вам нужно будет использовать такой [a] метод . Хуже того, запись об ошибке с дополнительными деталями может быть очень редкой, и тем не менее вам нужно будет выделить все, чтобы просто вставить все это.

• Rust предоставляет решение с нулевой стоимостью для случаев, когда не требуются дополнительные детали. Это блестящий пример действия принципа «плати только за то, что используешь».

Контрольные показатели

Одним из примеров повышения производительности программы с помощью Cow является эта часть микротеста Regex Redux. Уловка состоит в том, чтобы сначала сохранить ссылку на данные и заменить ее собственными данными во время итераций цикла.

Серде

Отличным примером того, как вы можете использовать суперсилы Cows в своих собственных структурах для обращения к входным данным вместо их копирования, является атрибут Serde #[serde (заимствовать)]. Если у вас есть структура вроде

#[derive(Debug, Deserialize)]
struct Foo<'input> {
    bar: Cow<'input, str>,
}

Serde по умолчанию заполнит эту полосу Cow принадлежащей ей строкой (игровая площадка). Однако если вы напишете это как

#[derive(Debug, Deserialize)]
struct Foo<'input> {
    #[serde(borrow)]
    bar: Cow<'input, str>,
}

Серде попытается создать заимствованную версию Коровы (детская площадка).

Однако это будет работать только в том случае, если входную строку не нужно настраивать. Так, например, когда вы десериализуете строку JSON, которая имеет экранированные кавычки в it3, Serde должен будет выделить новую строку для хранения неэкранированного представления и, таким образом, даст вам Cow::Owned (игровая площадка).

Спасибо Роберту Балики, Алексу Китченс и Мэтту Брубеку за просмотр этого поста! А также спасибо Брэду Гибсону за то, что он спросил о более подробном объяснении проблемы «большого размера», решение которой заняло у меня менее двух лет!

1. Да, правильно: клонировать при записи, а не копировать при записи. Это потому, что в Rust трейт Copy гарантированно будет простой операцией memcpy, в то время как Clone также может выполнять настраиваемую логику (например, рекурсивно клонировать HashMap <String, String>.

2. Благодаря реализации трейта Deref вы можете использовать ссылку на Cow <'static, str> вместо &str. Это означает, что Cow <'static, str> можно увидеть как ссылку на строку без необходимости ее преобразовывать.

3. "" Экранированные строки содержат обратную косую трэйту \ ", - сказал он.

Спасибо за чтение.