choosing-your-guarantees.md

% Выбор гарантий

Одна из важных черт языка Rust — это то, что он позволяет нам управлять накладными расходами и гарантиями программы.

В стандартной библиотеке Rust есть различные «обёрточные типы», которые реализуют множество компромиссов между накладными расходами, эргономикой, и гарантиями. Многие позволяют выбирать между проверками во время компиляции и проверками во время исполнения. Эта глава подробно объяснит несколько избранных абстракций.

Перед тем, как продолжить, крайне рекомендуем познакомиться с владением и заимствованием в Rust.

Основные типы указателей

Box<T>

Box<T> — «владеющий» указатель, или, по-другому, «упаковка». Хотя он и может выдавать ссылки на содержащиеся в нём данные, он — единственный владелец этих данных. В частности, когда происходит что-то вроде этого:

let x = Box::new(1);
let y = x;
// x больше не доступен

Здесь упаковка была перемещена в y. Поскольку x больше не владеет ею, с этого момента компилятор не позволит использовать x. Упаковка также может быть перемещена из функции — для этого функция возвращает её как свой результат.

Когда упаковка, которая не была перемещена, выходит из области видимости, выполняются деструкторы. Эти деструкторы освобождают содержащиеся данные.

Мы абстрагируемся от динамического выделения памяти, и это абстракция без накладных расходов. Это идеальный способ выделить память в куче и безопасно передавать указатель на эту память. Заметьте, что вы можете создавать ссылки на упаковку по обычным правилам заимствования, которые проверяются во время компиляции.

&T и &mut T

Это неизменяемые и изменяемые ссылки, соответственно. Они реализуют шаблон «read-write lock», т.е. вы можете создать или одну изменяемую ссылку на данные, или любое число неизменяемых, но не оба вида ссылок одновременно. Эта гарантия проверяется во время компиляции, и ничего не стоит во время исполнения. В большинстве случаев эти два типа указателей покрывают все нужды по передаче дешёвых ссылок между частями кода.

При копировании эти указатели сохраняют связанное с ними время жизни — они всё равно не могут прожить дольше, чем исходное значение, на которое они ссылаются.

*const T и *mut T

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

Они полезны при создании безопасных низкоуровневых абстракций вроде Vec<T>, но их следует избегать в безопасном коде.

Rc<T>

Это первая рассматриваемая обёртка, использование которой влечёт за собой накладные расходы во время исполнения.

Rc<T> — это указатель со счётчиком ссылок. Другими словами, он позволяет создавать несколько «владеющих» указателей на одни и те же данные, и эти данные будут уничтожены, когда все указатели выйдут из области видимости.

Собственно, внутри у него счётчик ссылок (reference count, или сокращённо refcount), который увеличивается каждый раз, когда происходит клонирование Rc, и уменьшается когда Rc выходит из области видимости. Основная ответственность Rc<T> — удостовериться в том, что для разделяемых данных вызываются деструкторы.

Хранимые данные при этом неизменяемы, и если создаётся цикл ссылок, данные утекут. Если нам нужно отсутствие утечек в присутствие циклов, нужно использовать сборщик мусора.

Гарантии

Здесь главная гарантия в том, что данные не будут уничтожены, пока все ссылки на них не исчезнут.

Счётчик ссылок нужно использовать, когда мы хотим динамически выделить какие-то данные и предоставить ссылки на эти данные только для чтения, и при этом неясно, какая часть программы последней закончит использование ссылки. Это подходящая альтернатива &T, когда невозможно статически доказать правильность &T, или когда это создаёт слишком большие неудобства в написании кода, на который разработчик не хочет тратить своё время.

Этот указатель не является потокобезопасным, и Rust не позволяет передавать его или делиться им с другими потоками. Это позволяет избежать накладных расходов от использования атомарных операций там, где они не нужны.

Есть похожий умный указатель, Weak<T>. Это невладеющий, но и не заимствуемый, умный указатель. Он тоже похож на &T, но не ограничен временем жизни — Weak<T> можно не отпускать. Однако, возможна ситуация, когда попытка доступа к хранимым в нём данным провалится и вернёт None, поскольку Weak<T> может пережить владеющие Rc. Его удобно использовать в случае циклических структур данных и некоторых других.

Накладные расходы

Что касается памяти, Rc<T> — это одно выделение, однако оно будет включать два лишних слова (т.е. два значения типа usize) по сравнению с обычным Box<T>. Это верно и для «сильных», и для «слабых» счётчиков ссылок.

Расходы на Rc<T> заключаются в увеличении и уменьшении счётчика ссылок каждый раз, когда Rc<T> клонируется или выходит из области видимости, соответственно. Отметим, что клонирование не выполняет глубокое копирование, а просто увеличивает счётчик и возвращает копию Rc<T>.

Типы-ячейки (cell types)

Типы Cell предоставляют «внутреннюю» изменяемость. Другими словами, они содержат данные, которые можно изменять даже если тип не может быть получен в изменяемом виде (например, когда он за указателем & или за Rc<T>).

Документация модуля cell довольно хорошо объясняет эти вещи.

Эти типы обычно используют в полях структур, но они не ограничены таким использованием.

Cell<T>

Cell<T> — это тип, который обеспечивает внутреннюю изменяемость без накладных расходов, но только для типов, реализующих типаж Copy. Поскольку компилятор знает, что все данные, вложенные в Cell<T>, находятся на стеке, их можно просто заменять без страха утечки ресурсов.

Нарушить инварианты с помощью этой обёртки всё равно можно, поэтому будьте осторожны при её использовании. Если поле обёрнуто в Cell, это индикатор того, что эти данные изменяемы и поле может не сохранить своё значение с момента чтения до момента его использования.

use std::cell::Cell;

let x = Cell::new(1);
let y = &x;
let z = &x;
x.set(2);
y.set(3);
z.set(4);
println!("{}", x.get());

Заметьте, что здесь мы смогли изменить значение через различные ссылки без права изменения.

В плане затрат во время исполнения, такой код аналогичен нижеследующему:

let mut x = 1;
let y = &mut x;
let z = &mut x;
x = 2;
*y = 3;
*z = 4;
println!("{}", x);

но имеет преимущество в том, что он действительно компилируется.

Гарантии

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

Это применяется при изменении примитивов и других типов, реализующих Copy, когда нет лёгкого способа сделать это в соответствии с статическими правилами & и &mut.

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

Накладные расходы

Накладные расходы при использовании Cell<T> отсутствуют, однако если вы оборачиваете в него большие структуры, есть смысл вместо этого обернуть отдельные поля, поскольку иначе каждая запись будет производить полное копирование структуры.

RefCell<T>

RefCell<T> также предоставляет внутреннюю изменяемость, но не ограничен только типами, реализующими Copy.

Однако, у этого решения есть накладные расходы. RefCell<T> реализует шаблон «read-write lock» во время исполнения, а не во время компиляции, как &T/ &mut T. Он похож на однопоточный мьютекс. У него есть функции borrow() и borrow_mut(), которые изменяют внутренний счётчик ссылок и возвращают умный указатель, который может быть разыменован без права изменения или с ним, соответственно. Счётчик ссылок восстанавливается, когда умные указатели выходят из области видимости. С этой системой мы можем динамически гарантировать, что во время заимствования с правом изменения никаких других ссылок на значение больше нет. Если программист пытается позаимствовать значение в этот момент, поток запаникует.

use std::cell::RefCell;

let x = RefCell::new(vec![1,2,3,4]);
{
    println!("{:?}", *x.borrow())
}

{
    let mut my_ref = x.borrow_mut();
    my_ref.push(1);
}

Как и Cell, это в основном применяется в ситуациях, когда сложно или невозможно удовлетворить статическую проверку заимствования. В целом мы знаем, что такие изменения не будут происходить вложенным образом, но это стоит дополнительно проверить.

Для больших, сложных программ, есть смысл положить некоторые вещи в RefCell, чтобы упростить работу с ними. Например, многие словари в структуре ctxtctxt в компиляторе Rust обёрнуты в этот тип. Они изменяются только однажды — во время создания, но не во время инициализации, или несколько раз в явно отдельных местах. Однако, поскольку эта структура повсеместно используется везде, жонглирование изменяемыми и неизменяемыми указателями было бы очень сложным (или невозможным), и наверняка создало бы мешанину указателей &, которую сложно было бы расширять. С другой стороны, RefCell предоставляет дешёвый (но не бесплатный) способ обращаться к таким данным. В будущем, если кто-то добавит код, который пытается изменить ячейку, пока она заимствована, это вызовет панику, источник которой можно отследить. И такая паника обычно происходит детерминированно.

Похожим образом, в DOM Servo много изменения данных, большая часть которого происходит внутри типа DOM, но часть выходит за его границы и изменяет произвольные вещи. Использование RefCell и Cell для ограждения этих изменений позволяет нам избежать необходимости беспокоиться об изменяемости везде, и одновременно обозначает места, где изменение действительно происходит.

Заметьте, что стоит избегать использования RefCell, если возможно достаточно простое решение с помощью указателей &.

Гарантии

RefCell ослабляет статические ограничения, предотвращающие совпадение изменяемых указателей, и заменяет их на динамические ограничения. Сами гарантии при этом не изменяются.

Накладные расходы

RefCell не выделяет память, но содержит дополнительный индикатор «состояния заимствования» (размером в одно слово) вместе с данными.

Во время исполнения каждое заимствование вызывает изменение и проверку счётчика ссылок.

Синхронизированные типы

Многие из вышеперечисленных типов не могут быть использованы потокобезопасным образом. В частности, Rc<T> и RefCell<T>, оба из которых используют не-атомарные счётчики ссылок, не могут быть использованы так. (Атомарные счётчики ссылок — это такие, которые могут быть увеличены из нескольких потоков, не вызывая при этом гонку данных.) Благодаря этому они привносят меньше накладных расходов, но нам также потребуются и потокобезопасные варианты этих типов. Они существуют — это Arc<T> и Mutex<T>/RWLock<T>.

Заметьте, что не-потокобезопасные типы не могут быть переданы между потоками, и это проверяется во время компиляции.

В модуле sync много полезных обёрточных типов для многопоточного программирования, но мы затронем только главные из них.

Arc<T>

Arc<T> — это вариант Rc<T>, который использует атомарный счётчик ссылок (поэтому «Arc»). Его можно свободно передавать между потоками.

shared_ptr из C++ похож на Arc, но в случае C++ вложенные данные всегда изменяемы. Чтобы получить семантику, похожую на семантику C++, нужно использовать Arc<Mutex<T>>, Arc<RwLock<T>>, или Arc<UnsafeCell<T>>¹. (UnsafeCell<T> — это тип-ячейка, который может содержать любые данные и не имеет накладных расходов, но доступ к его содержимому производится только внутри небезопасных блоков.) Последний стоит использовать только тогда, когда мы уверены в том, что наша работа не вызовет нарушения безопасности памяти. Учитывайте, что запись в структуру не атомарна, а многие функции вроде vec.push() могут выделять память заново в процессе работы, и тем самым вызывать небезопасное поведение.

Гарантии

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

Накладные расходы

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

Mutex<T> and RwLock<T>

Mutex<T> и RwLock<T> предоставляют механизм взаимоисключения с помощью охранных значений RAII. Охранные значения — это объекты, имеющие некоторое состояние, как замок, пока не выполнится их деструктор. В обоих случаях, мьютекс непрозрачен, пока на нём не вызовут lock(), после чего поток остановится до момента, когда мьютекс может быть закрыт, после чего возвращается охранное значение. Оно может быть использовано для доступа к вложенным данным с правом изменения, а мьютекс будет снова открыт, когда охранное значение выйдет из области видимости.

{
    let guard = mutex.lock();
    // охранное значение разыменовывается в изменяемое значение
    // вложенного в мьютекс типа
    *guard += 1;
} // мьютекс открывается когда выполняется деструктор

RwLock имеет преимущество — он эффективно работает в случае множественных чтений. Ведь читать из общих данных всегда безопасно, пока в эти данные никто не хочет писать; и RwLock позволяет читающим получить «право чтения». Право чтения может быть получено многими потоками одновременно, и за читающими следит счётчик ссылок. Тот же, кто хочет записать данные, должен получить «право записи», а оно может быть получено только когда все читающие вышли из области видимости.

Гарантии

Оба этих типа предоставляют безопасное изменение данных из разных потоков, но не защищают от взаимной блокировки (deadlock). Некоторая дополнительная безопасность протокола работы с данными может быть получена с помощью системы типов.

Накладные расходы

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

Сочетание

Распространённая жалоба на код на Rust — это сложность чтения типов вроде Rc<RefCell<Vec<T>>> (или ещё более сложных сочетаний похожих типов). Не всегда понятно, что делает такая комбинация, или почему автор решил использовать именно такой тип. Не ясно и то, в каких случаях сам программист должен использовать похожие сочетания типов.

Обычно, вам понадобятся такие типы, когда вы хотите сочетать гарантии разных типов, но не хотите переплачивать за то, что вам не нужно.

Например, одно из таких сочетаний — это Rc<RefCell<T>>. Сам по себе Rc<T> не может быть разыменован с правом изменения; поскольку Rc<T> позволяет делиться данными и одновременная попытка изменения данных может привести к небезопасному поведению, мы кладём внутрь RefCell<T>, чтобы получить динамическую проверку одновременных попыток изменения. Теперь у нас есть разделяемые изменяемые данные, но одновременный доступ к ним предоставляется только на чтение, а запись всегда исключительна.

Далее мы можем развить эту мысль и получить Rc<RefCell<Vec<T>>> или Rc<Vec<RefCell<T>>>. Это — изменяемые, разделяемые между потоками вектора, но они не одинаковы.

В первом типе RefCell<T> оборачивает Vec<T>, поэтому изменяем весь Vec<T> целиком. В то же время, это значит, что в каждый момент времени может быть только одна ссылка на Vec<T> с правом изменения. Поэтому код не может одновременно работать с разными элементами вектора, обращаясь к ним через разные Rc. Однако, мы сможем добавлять и удалять элементы вектора в произвольные моменты времени. Этот тип похож на &mut Vec<T>, с тем различием, что проверка заимствования делается во время исполнения.

Во втором типе заимствуются отдельные элементы, а вектор в целом неизменяем. Поэтому мы можем получить ссылки на отдельные элементы, но не можем добавлять или удалять элементы. Это похоже на &mut [T]², но, опять-таки, проверка заимствования производится во время исполнения.

В многопоточных программах возникает похожая ситуация с Arc<Mutex<T>>, который обеспечивает разделяемое владение и одновременное изменение.

Когда вы читаете такой код, рассматривайте гарантии и накладные расходы каждого вложенного типа шаг за шагом.

Когда вы выбираете сложный тип, поступайте наоборот: решите, какие гарантии вам нужны, и в каком «слое» сочетания они понадобятся. Например, если у вас стоит выбор между Vec<RefCell<T>> и RefCell<Vec<T>>, найдите компромисс путём рассуждений, как мы делали выше по тексту, и выберите нужный вам тип.

Footnotes

1. На самом деле, Arc<UnsafeCell<T>> не скомпилируется, поскольку UnsafeCell<T> не реализует Send или Sync, но мы можем обернуть его в тип и реализовать для него Send/Sync вручную, чтобы получить Arc<Wrapper<T>>, где Wrapper — это struct Wrapper<T>(UnsafeCell<T>). ↩

2. &[T] и &mut [T] — это срезы; они состоят из указателя и длины, и могут ссылаться на часть вектора или массива. &mut [T] также позволяет изменять свои элементы, но его длину изменить нельзя. ↩