Arc

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

Впрочем, наш список пока не является потокобезопасным. Чтобы сделать его таковым, мы должны решить проблему атомарного подсчёта ссылок. В противном случае два потока могут попытаться увеличить счётчик ссылок, а удастся это только одному. Тогда список будет освобождён чуть раньше, чем нужно!

Чтобы получить потокобезопасность, мы должны использовать Arc. Arc полностью идентичен Rc за тем исключением, что счётчик ссылок модифицируется атомарно. Это влечёт небольшие накладные расходы, и если оно вам не надо, вы всегда можете использовать Rc. Всё, что нам надо с делать с нашим списком, это заменить каждое упоминание Rc на std::sync::Arc. И это всё. Мы потокобезопасны. Сделано!

Правда, возникает один интересный вопрос: откуда мы знаем, что тип потокобезопасен? Можем ли мы ошибаться?

Нет! В Rust потокобезопасность сломать нельзя!

Причина в том, что Rust моделирует потокобезопасность с помощью двух типажей: Send и Sync.

Тип относится к Send (отправляемый), если его можно безопасно передать в другой поток. Тип относится к Sync (синхронный), если его можно безопасно разделить между потоками. Есть правило: если T реализует Sync, то &T реализует Send. Безопасность в данном случае означает, что мы не можем устроить гонку данных (data races). Не путайте её с более общий случаем — состоянием гонки (race conditions).

Это типажи-маркеры или, говоря простым языком, они не предоставляют ни одного метода. Тип просто либо является Send, либо не является. Можно сказать, что это свойство типа, которое могут требовать другие API. Если тип не помечен как Send, компилятор проверяет, что его нельзя передавать в другой поток! Идеально!

Send и Sync автоматически реализуются для типов, состоящих только из полей Send и Sync. Похожим образом, типаж Copy может быть реализован только для типов, состоящих из Copy-типов. Но для Send и Sync компилятор идёт ещё дальше и реализует всё за вас.

Почти все типы — одновременно и Send, и Sync. Большинство типов относятся к Send, потому что они полностью владеют своими данными. Большинство типов относятся к Sync, потому что единственный способ разделить данные между потоками — воспользоваться разделяемой ссылкой, которая, как мы знаем, неизменяемая!

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

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

Какое отношение всё это имеет к Rc и Arc, спросите вы? Ну, они оба внутренне изменчивы из-за счётчика ссылок. Хуже того, этот счётчик разделяется между всеми экземплярами! Rc просто использует ячейку и это значит, что он не является потокобезопасным. Arc использует атомарный тип и это значит, что он является потокобезопасным. Естественно, вы не можете магически превратить тип в потокобезопасный, просто поместив его в Arc. Arc может только наследовать потокобезопасность, как и любой другой тип.

Я очень-очень-очень не хочу углубляться в тонкости атомарных моделей памяти или не-унаследованных реализаций Send. Излишне говорить, что по мере погружения в тему потокобезопасности Rust, всё становится сложнее. Для обычных программистов всё это просто работает и вам на самом деле не надо об этом думать.