Ну, привет.

lock xadd. Вот и весь Arc::clone на x86. Одна инструкция. Заглядываешь в дизассемблер и даже немного обидно: столько разговоров про атомарные счётчики ссылок, а внутри обычный атомарный инкремент, который компилятор даже не утруждается оборачивать во что-то крутое.

Вот только эта инструкция вам подыгрывает. На вашем ноуте она бесплатная. А потом тот же код уезжает в прод на пару десятков ядер, и тот же самый инкремент оказывается самым дорогим местом в горячем цикле. Самая подлянка в том, что профайлер на ноуте этого не покажет: чтобы увидеть цену, нужен контеншен, а на одном ядре его нет. Так что вся статья, если честно, про одно. Как научиться смотреть на Arc::clone и видеть не инкремент, а короткий разговор с протоколом кэш-когерентности вашего процессора.

Arc принято звать умным указателем. Мне ближе другая формулировка: это примитив синхронизации, который натянул костюм указателя, чтобы вы его не боялись. Давайте снимем всю эту оболочку и глянем, кто там внутри. По ходу разберёмся, откуда в нём два счётчика, почему clone беспамятный, а drop нет, как живёт Weak, что за толстый указатель прячется в Arc<dyn Trait>, зачем придумали make_mut и где Rc делает Arc по скорости.

Один блок, и в нём всё

Первое, что стоит выкинуть из головы: Arc<T> — это не «данные, а счётчик где-то сбоку». Это один кусок памяти, и в нём лежит вообще всё.

#[repr(C)]
struct ArcInner<T: ?Sized> {
    strong: AtomicUsize,   // сколько живых Arc прямо сейчас
    weak:   AtomicUsize,   // сколько Weak (плюс одна неявная, дойдём)
    data:   T,             // ваши данные. здесь же. не по указателю.
}

Сам Arc поверх этого тонкий, просто указатель на блок:

pub struct Arc<T: ?Sized> {
    ptr: NonNull<ArcInner<T>>,
    phantom: PhantomData<ArcInner<T>>,
}

Главное слово в первом листинге это data: T, а не data: *mut T. Данные лежат встык со счётчиками, в одной аллокации. Наивная реализация (и, кстати, классический shared_ptr в C++) держала бы счётчик отдельно от объекта, а это два захода в аллокатор и два независимых места в памяти. Здесь заход один, и счётчики с данными частенько оказываются в одной кэш-линии.

repr(C) тут не ради красоты. Он прибивает порядок полей гвоздями, и это нужно, чтобы Arc и Weak смотрели на один блок и сходились по смещениям даже тогда, когда T неразмерный, какой-нибудь dyn Trait. К неразмерности ещё вернёмся.

Откуда берётся вторая единица

Счётчика два.

strong это сколько живых Arc. Пока он не ноль, данные живы. Ушёл последний Arc, strong обнулился, у data зовётся деструктор. Пока всё вроде прозрачно.

weak устроен уже с подвохом. Формально это сколько живых Weak, но к этому числу всегда приклеена единица, пока существует хоть один Arc. Все сильные ссылки держат её в складчину, как одну общую слабую на всех.

Подумайте, что должно случиться, когда strong дошёл до нуля. Данные пора дропать, ясно. А освобождать ли память под блок? Нельзя.

На блок ещё могут смотреть Weak, и когда кто-нибудь из них дёрнет upgrade, ему надо прочитать strong и убедиться, что там ноль, то есть «данных больше нет». Освободи мы блок сразу, этот upgrade прочитает труп. Значит, разводим два события по разным счётчикам: данные умирают на strong == 0, память под блок освобождается на weak == 0.

Неявная единица и сшивает эти два момента в одну схему без ветвлений на каждый чих. Жив хоть один Arc, в weak торчит лишняя единица, и блок не освободится при всём желании. Умер последний Arc, и он же эту единицу снимает. Дальше блок доживает ровно до того, как разойдётся последний настоящий Weak.

Из-за этой единицы новички спотыкаются о weak_count, поэтому std её прячет:

let a = Arc::new(5);
let w = Arc::downgrade(&a);

assert_eq!(Arc::strong_count(&a), 1);
assert_eq!(Arc::weak_count(&a), 1);   // внутри-то weak == 2, но неявную +1 вам не показывают

Внутри weak равен двум, неявная плюс одна настоящая, а weak_count вычитает служебную единицу и отдаёт человеческую. У strong вычитать нечего, лишней единицы там нет. Обе цифры под конкурентным доступом стоит читать как «было вот столько секунду назад»: другой поток меняет их когда захочет, в том числе ровно между вашим чтением и вашим решением. Строить на них логику, где важна точность, затея так себе.

Зато из всей этой возни падает в руки самый полезный вывод про Weak: он держит живой не данные, а аллокацию. Поэтому им и режут циклы.

Дерево, где от родителя к детям тянутся сильные Arc, а от детей назад слабые Weak, спокойно соберётся. А два Arc, взявшие друг друга под локоть, утекут навсегда: их strong не упадёт до нуля ни при какой погоде. Если нужна структура, ссылающаяся сама на себя, для этого есть Arc::new_cyclic: он подсовывает вам Weak на ещё не достроенный блок прямо во время инициализации, чтобы вы вшили слабую ссылку на себя и не словили утечку.

Почему clone беспамятный

Вот теперь то, ради чего вообще стоит читать про atomics. Клонирование Arc это инкремент strong, и сделан он самым слабым упорядочиванием, какое бывает, Relaxed. По сути:

impl<T: ?Sized> Clone for Arc<T> {
    fn clone(&self) -> Arc<T> {
        let old = self.inner().strong.fetch_add(1, Relaxed);
        if old > MAX_REFCOUNT {        // MAX_REFCOUNT == isize::MAX
            abort();                    // да, abort, а не panic
        }
        Arc { ptr: self.ptr, phantom: PhantomData }
    }
}

Почему хватает Relaxed? Инкременту не с чем синхронизироваться, ему нечего помнить.

Вы уже держите Arc, значит, данные вам уже видны и давно инициализированы, happens-before к ним установлен раньше, когда исходный Arc создавали и передавали. Клон не публикует новых данных и не вычитывает чужих. Он делает одну-единственную вещь: отмечает, что наблюдателей стало на одного больше. Для этого нужна атомарность, чтобы два одновременных клона не затёрли друг друга, и ничего сверх неё.

Про abort пара слов. Счётчик usize, обычным кодом его за разумное время не переполнить. Но mem::forget(arc.clone()) в цикле теоретически дотянет до края, а перевалив за край, счётчик уйдёт в ноль, и вот вам use-after-free из ниоткуда. Поэтому после инкремента сверяются с порогом isize::MAX и при превышении не паникуют, а валят процесс. Паника тут запрещена, ведь раскрутка стека сама работает с Arc, дропая их по пути, а инвариант в этот момент уже сломан. Та же проверка, между прочим, обязана жить и в инкременте weak внутри downgrade.

Смерть дороже рождения

impl<T: ?Sized> Drop for Arc<T> {
    fn drop(&mut self) {
        if self.inner().strong.fetch_sub(1, Release) != 1 {
            return;                    // мы не последние, молча расходимся
        }
        atomic::fence(Acquire);        // ждём, пока все доедят
        unsafe { self.drop_slow() }    // дропаем data, разбираемся с weak
    }
}

Декремент идёт с Release, а тот единственный поток, который поймал переход счётчика из единицы в ноль, перед тем как тронуть данные, ставит Acquire-фенс. Зачем?

Дроп данных — это эксклюзивный доступ, и случиться он обязан строго после всех чужих касаний этих данных, из всех потоков разом. Пока счётчик не ноль, любой держатель Arc вправе читать данные у себя. Release на каждом декременте плюс Acquire-фенс перед финальным дропом и выстраивают то самое happens-before: все обращения через все когда-либо жившие копии гарантированно закончились до того, как побежал деструктор. Снимите фенс, и деструктор сможет поехать внахлёст с чьим-то последним чтением.

А что именно делает тот последний поток дальше, видно из той же арифметики двух счётчиков:

unsafe fn drop_slow(&mut self) {
    // strong уже ноль: хороним сами данные
    ptr::drop_in_place(&mut (*self.ptr.as_ptr()).data);

    // снимаем ту самую неявную единицу с weak
    if self.inner().weak.fetch_sub(1, Release) == 1 {
        atomic::fence(Acquire);
        // weak тоже ноль: ни одного Weak не осталось, освобождаем блок
        // dealloc(self.ptr ...)
    }
}

Сперва умирают данные, потому что strong обнулился. Потом снимается неявная единица, и только если на этом weak тоже ушёл в ноль (то есть слабых ссылок не осталось), освобождается сам блок. Если же Weak ещё висят, данные уже мертвы, а память живёт дальше, дожидаясь их.

Рождение ссылки: Relaxed, дёшево, беспамятно. Смерть данных: Release на спуске, Acquire на финале, с оглядкой на всех. Завести наблюдателя почти ничего не стоит, а вот хоронить объект надо по протоколу, дождавшись, пока разойдутся все. Клонировать дешевле, чем дропать.

Сколько стоит одна инструкция.

Начнём с того, что на x86 выбор упорядочивания не стоит ничего. Любой fetch_add, хоть Relaxed, хоть SeqCst, это одна и та же lock xadd. Префикс lock сам по себе полный барьер памяти, так что силу SeqCst вы тут получаете в подарок, и подменив её на Relaxed, не выгадаете ни такта. На этой архитектуре Ordering — это записка компилятору и человеку, читающему код, а не процессору. Единственное место, где порядок реально меняет инструкцию — это store под SeqCst, он разворачивается в xchg.

На слабых архитектурах вроде ARM подарка уже нет. Там Relaxed-инкремент это голая атомарка, а Acquire с Release тянут за собой load-acquire, store-release или явные барьеры. Вот где Relaxed на клоне экономит.

Одна lock-инструкция не даётся даром: она утаскивает кэш-линию со счётчиком в эксклюзив вашего ядра. Когда линия уже лежит у вас в L1 и никому больше не сдалась, это пара десятков тактов, неприятно, но терпимо.

А вот когда по одному Arc молотят несколько потоков с разных ядер, линия со счётчиком принимается летать между ними: чтобы инкрементить, ядру нужна эксклюзивная копия, оно тащит линию к себе, отбирая у соседа, через миг сосед отбирает обратно, и так по кругу. Один такой перелёт линии между ядрами в пределах сокета стоит от семидесяти тактов, и это ещё минимум, между разными сокетами счёт идёт на сотни. И это на каждый клон, на каждый дроп.

А теперь вспомните тот посаженный в начале факт про одну кэш-линию. Счётчики лежат в голове блока, данные впритык за ними, и если данные небольшие, они делят линию со счётчиками.

Получается: данные вы не трогаете, они намертво иммутабельны, но бешеный реткаунтинг по соседним байтам всё равно гоняет ту же линию, и читателям данных прилетает. За чужой clone расплачивается тот, кто всего лишь читал значение и был уверен, что у него честный read-only.

Лечится это, если совсем припёрло, разнесением счётчиков и данных по разным линиям (padding или отдельная аллокация под холодную часть), но в обычном Arc такой роскоши нет, layout зашит намертво.

Weak: ссылка, которая умеет ждать

Вокруг Weak припрятано ещё немного механики.

downgrade рождает Weak из Arc, наращивая weak. Но не простым fetch_add, а циклом compare-and-swap. В счётчике weak зарезервировано значение usize::MAX, и пока там лежит MAX, временно запрещено и плодить новые Weak, и апгрейдить старые. Всю эту тему захлопывают get_mut и make_mut, когда им нужно без гонок проверить, что владелец один.

Поэтому downgrade сперва косится, не заперто ли, и если заперто, крутится в спине, пока не откроют.

upgrade идёт встречным курсом и тоже циклом, но уже по strong:

let a = Arc::new(5);
let w = Arc::downgrade(&a);

assert!(w.upgrade().is_some());   // данные живы, на руках настоящий Arc
drop(a);
assert!(w.upgrade().is_none());   // strong доехал до нуля, данных нет, держите None

Внутри upgrade читает strong, видит ноль, отдаёт None (данные уже мертвы), а если не ноль, пробует нарастить strong через compare-exchange. Цикл нужен потому, что между «прочитал» и «нарастил» другой поток может уронить strong в ноль, и наращивать станет нечего. Оттого upgrade и возвращает Option<Arc>, а не Arc: обещать, что данные доживут до вашего апгрейда, никто не подписывался.

Еще Weak::new() не аллоцирует ни байта. Это висячая слабая ссылка, она показывает на адрес-пустышку и на upgrade всегда отвечает None.

И еще: проверка уникальности в get_mut это не наивное strong == 1 && weak == 1. Будь оно так, нашлась бы щель: между двумя сравнениями чужой поток успел бы апгрейднуть Weak и тут же его выронить, обе проверки прошли бы, а на миг существовал второй владелец.

usize::MAX эту щель и заваривает, замораживая апгрейды с даунгрейдами на время проверки.

Толстый указатель для dyn

Раз data лежит встык, всплывает вопрос: а как же Arc<dyn Trait>, ведь размер dyn Trait неизвестен? Через толстый указатель.

trait Animal { fn speak(&self); }
struct Dog;
impl Animal for Dog {
    fn speak(&self) { println!("гав"); }
}

let a: Arc<dyn Animal> = Arc::new(Dog);   // unsize-коэрция из Arc<Dog>
a.speak();

Когда T это dyn Trait, неразмерным становится и сам ArcInner<dyn Trait>, и указатель на него толстеет до двух слов вместо одного. Первое слово показывает на блок, второе несёт указатель на таблицу виртуальных методов этого трейта. То есть Arc<dyn Animal> весит шестнадцать байт на 64 бита, ровно как &dyn Animal или Box<dyn Animal>. Смещение до data внутри блока при этом считается по информации о выравнивании из vtable, поэтому всё сходится даже для данных без статически известного размера.

Превращение Arc<Dog> в Arc<dyn Animal> происходит само собой. Обратно, из Arc<dyn Any> в конкретный тип, спускаются через downcast.Arc::ptr_eq нарочно выкидывает vtable-половину толстого указателя и сравнивает только адреса блоков, чтобы два по-разному типизированных взгляда на один блок считались равными.

make_mut: писать в то, что шарят

Шаренные ссылки в Rust по умолчанию мутировать не дают, и Arc тут не исключение: &mut к данным внутри он просто так не выдаст. Обычная реакция тут потянуться за Mutex или атомиками. Но есть третий ход, про который часто забывают, и это make_mut с семантикой clone-on-write, «копируем при записи».

Arc::make_mut(&mut Arc<T>) отдаёт вам &mut T, разруливая три расклада по-разному:

let mut data = Arc::new(5);
*Arc::make_mut(&mut data) += 1;          // владелец один, пишем на месте, без копий
let mut other = Arc::clone(&data);       // данные не копируются, просто +1 к strong
*Arc::make_mut(&mut data) += 1;          // появился второй Arc, КЛОНИРУЕТ данные в новый блок
*Arc::make_mut(&mut data) += 1;          // снова один, без копий
*Arc::make_mut(&mut other) *= 2;         // тоже один, без копий
assert_eq!(*data, 8);
assert_eq!(*other, 12);

Есть другие сильные Arc на тот же блок, и make_mut копирует данные в новую аллокацию, переключая ваш Arc на неё, чтобы копия стала вашей и только вашей. Пока никто не пишет, все мирно делят один блок, а первый, кто собрался менять общее, отъезжает со своей копией, не задев соседей.

Других Arc нет, но висят Weak? Тогда штука занятная: данные не копируются, а вот живые Weak отвязываются от блока. После этого им уже не апгрейднуться, для них данные будто испарились. То есть make_mut говорит слабым ссылкам «всё, отвернитесь», и спокойно выдаёт мутабельный доступ без единой копии.

А если вы и впрямь один, без чужих Arc и без Weak, make_mut просто отдаёт &mut на месте.

Зачем он, когда есть get_mut? get_mut возвращает Option: Some(&mut T) строго если вы единственный (ни Arc, ни Weak на стороне), иначе None, и выкручивайся как хочешь.

make_mut же в None не умеет: он всегда даёт &mut, при нужде склонировав данные или отвязав слабых.

Когда Rc быстрее

Мы столько носились с атомарностью, что вопрос напрашивается сам: а Rc тогда зачем, если есть Arc? Затем, что Rc не доплачивает за то, что вам не нужно.

Внутри он почти такой же, тот же блок с двумя счётчиками и данными встык, только счётчики не атомарные. Клон Rc это обычный неатомарный инкремент, по сути:

fn clone(&self) -> Rc<T> {
    let n = self.inner().strong.get();
    self.inner().strong.set(n + 1);   // обычный +1, без lock, без барьеров
    Rc { ptr: self.ptr }
}

Ни префикса lock, ни барьера, ни принудительного захвата кэш-линии в эксклюзив. Прочитал, прибавил, записал, и компилятор это ещё и оптимизирует как заурядную возню с памятью.

При этом Rc не реализует ни Send, ни Sync. Отправить его в другой поток вам не дадут, код просто не соберётся. Отсюда правило: однопоточный код просит Rc, межпоточный требует Arc.

Rc это безопасный выбор по умолчанию, потому что промах с пересылкой между потоками отловит компилятор, а Arc нужен ровно тогда, когда данные и правда переходят границу потока. И Arc окажется Send плюс Sync лишь при условии, что сам T уже Send и Sync, иначе никакой атомарный счётчик его не вытянет.

Если из всего текста уносить одну мысль, пусть будет эта. Arc::clone дёшев ровно до тех пор, пока вы один на кэш-линии. Стоит нескольким ядрам сцепиться за один счётчик, и бесплатная инструкция становится самым дорогим местом цикла, поэтому берите Rc, пока не приспичило ходить между потоками. Берите Arc, когда приспичило. А если Arc у вас клонируется в цикле на каждой итерации в куче потоков, остановитесь и спросите себя, точно ли надо шарить именно это и именно так, потому что временами копия на стек обгоняет указатель со счётчиком, и обгоняет с запасом.

А счётчик пускай себе крутится.

Размещайте облачную инфраструктуру и масштабируйте сервисы с надежным облачным провайдером Beget.
Эксклюзивно для читателей Хабра мы даем бонус 10% при первом пополнении.