Rustの `Arc` を読む(1): Arc/Rcの基本

概要: Rustの Arc 型の実装は宝の宝庫です。そこで、これを隅から隅まで解説してみます。

第1回「Arc/Rcの基本」では、実際に Arc のソースを読む前に Arc/Rc の使い方を解説します。

• 第1回 Arc/Rcの基本
• 第2回 Rcを読む基本編
• 第3回 Rcを読む発展編
• 第4回 アトミック変数とメモリ順序
• 第5回 Arcを読む

はじめに

Arc<T> はRustの基本的な型のひとつですが、 Box<T> のようにコンパイラに特別扱いされているわけでもなく、実装も比較的コンパクトです(コメントやテスト、安定性に関する指示などを除いて500LOC程度) その一方で Arc は並行性制御や Deref, ドロップチェッカー, Unpin, Layoutの扱いなどRustをよりよく理解するための題材を多く含んでいます。そこで本記事では Arc<T> の実装を読んでいきます。

とはいえ、 Arc/Rc に対する理解度は人それぞれだと思います。そこで第1回ではできるだけ前提知識を揃えるために、 Arc/Rc の基本的な使い方を解説します。(今回はソースコードは読みません)

まとめ

• Arc/Rc は参照カウントを使ったスマートポインタであり、データや状態を共有できる。
• 状態を共有するには内部可変性コンテナである RefCell や Mutex と組み合わせる必要がある。
• Rc は Arc よりコストが低いが、スレッドセーフではない。間違った使い方はコンパイラが指摘してくれるので、スレッド安全性に注意しながら書く必要はない。
• 循環参照を作ると問題が発生するので、その場合は弱参照 Weak で循環性を解消する必要がある。

Arc/Rcとは

Arc<T> と Rc<T> は参照カウントされた共有スマートポインタです。

use std::rc::Rc;

fn main() {
    // スマートポインタを作成
    let x = Rc::new(42);
    // 参照カウントは1
    assert_eq!(Rc::strong_count(&x), 1);

    // ポインタを複製
    let y = x.clone();
    // 参照カウントは2
    assert_eq!(Rc::strong_count(&y), 2);

    // 2つは同じポインタを指す
    assert!(Rc::ptr_eq(&x, &y));
    eprintln!("x = {0:p} (points to {0:})", x);
    eprintln!("y = {0:p} (points to {0:})", y);
}

Rustの原則として「共有されているものには書き込めない」ので、以下のように参照先を書き換えることはできません。

use std::rc::Rc;

fn main() {
    let mut rc = Rc::new(42);
    *rc = 53;
    // ^^^^^ cannot assign
    eprintln!("rc = {}", rc);
}

Arc と Rc の違い

Arc と Rc の違いはスレッド安全性です。 Rc はスレッド安全ではないため、他のスレッドに送ったり、複数スレッドで共有しようとしたりするとコンパイルエラーになります。

use std::rc::Rc;
use std::thread;

fn main() {
    let rc = Rc::new(42);
    let thread = thread::spawn(move || {
        //       ^^^^^^^^^^^^^ `std::rc::Rc<i32>` cannot be sent between threads safely
        eprintln!("value = {}", rc);
    });
    thread.join().unwrap();
}

Arc にすればコンパイルが通ります。

use std::sync::Arc;
use std::thread;

fn main() {
    let rc = Arc::new(42);
    let thread = thread::spawn(move || {
        eprintln!("value = {}", rc);
    });
    thread.join().unwrap();
}

コンパイラ任せにできるので、プログラムを書く段階で違いを気にする必要はありません。よりコストの低い Rc で実装を開始して、必要になったら Arc に切り替えるというので問題ないでしょう。ただし、不特定多数が使うライブラリの場合ははじめから Arc でもいいかもしれません。

Arc/Rcの2つの使い方

Arc/Rcには大きく2つの使い方があります。

状態共有

1つ目は状態共有です。状態共有をするには RefCell や Mutex など内部可変性コンテナと組み合わせて使います。

use std::sync::{Arc, Mutex};
use std::thread;

fn main() {
    // カウンタを作成
    // Mutex: 共有書き込みのために必要
    // Arc: ライフタイムに依存しない共有のために必要
    let counter = Arc::new(Mutex::new(0));

    // 以下、2スレッド間でカウンタを共有して作業する

    let thread = thread::spawn({
        let counter = counter.clone();
        move || {
            for _ in 0..100000 {
                // カウンタのロックを取得
                let mut counter = counter.lock().unwrap();
                // 偶数なら1を足す
                if *counter % 2 == 0 {
                    *counter += 1;
                }
            }
        }
    });

    for _ in 0..100000 {
        // カウンタのロックを取得
        let mut counter = counter.lock().unwrap();
        // 奇数なら1を足す
        if *counter % 2 == 1 {
            *counter += 1;
        }
    }

    // 起動したスレッドと合流
    thread.join().unwrap();

    // カウンタの最終的な値を取得
    let counter = *counter.lock().unwrap();
    eprintln!("counter = {}", counter);
}

上の例ではマルチスレッドプログラミングを例に挙げていますが、シングルスレッドでも状況は同じです。複数のオブジェクトから共有されている状態を持ちたいときは、 Rc<RefCell<T>> などの組み合わせを使うのが定石です。

イミュータブルデータ構造

もう1つの使い方は、大きなデータの共有、特にイミュータブルなデータ構造です。この場合は内部可変性コンテナは使わずに、そのままArc/Rcにデータを突っ込むことになります。以下は最もシンプルなイミュータブルデータ構造であるイミュータブルスタックの実装例です。

use std::rc::Rc;

// イミュータブルスタック
#[derive(Debug)]
pub struct Stack<T>(Option<Rc<(T, Stack<T>)>>);

// O(1) コピー
impl<T> Clone for Stack<T> {
    fn clone(&self) -> Self {
        Self(self.0.clone())
    }
}

impl<T> Stack<T> {
    pub fn new() -> Self {
        Self(None)
    }

    pub fn push(self, x: T) -> Self {
        Self(Some(Rc::new((x, self))))
    }

    pub fn peek(&self) -> Option<&T> {
        if let Some(rc) = &self.0 {
            Some(&rc.0)
        } else {
            None
        }
    }
}

impl<T: Clone> Stack<T> {
    pub fn pop(self) -> (Self, Option<T>) {
        if let Some(rc) = self.0 {
            let (head, tail) = Rc::try_unwrap(rc).unwrap_or_else(|rc| (*rc).clone());
            (tail, Some(head))
        } else {
            (Self(None), None)
        }
    }
}

fn main() {
    let s = Stack::new();
    assert_eq!(s.peek(), None);
    let s = s.push(42);
    assert_eq!(s.peek(), Some(&42));
    let (s, head) = s.pop();
    assert_eq!(head, Some(42));
    assert_eq!(s.peek(), None);
}

ただし、Rustでは &mut を安全に扱うことができるので、上記のように他言語のイミュータブルデータ構造でよく見るインターフェースよりも、以下のようにコピーオンライトなインターフェースのほうが好まれると思われます。

use std::rc::Rc;

// イミュータブルスタック
#[derive(Debug)]
pub struct Stack<T>(Option<Rc<(T, Stack<T>)>>);

// O(1) コピー
impl<T> Clone for Stack<T> {
    fn clone(&self) -> Self {
        Self(self.0.clone())
    }
}

impl<T> Stack<T> {
    pub fn new() -> Self {
        Self(None)
    }

    pub fn push(&mut self, x: T) {
        let this = Self(self.0.take());
        self.0 = Some(Rc::new((x, this)));
    }

    pub fn peek(&self) -> Option<&T> {
        if let Some(rc) = &self.0 {
            Some(&rc.0)
        } else {
            None
        }
    }
}

impl<T: Clone> Stack<T> {
    pub fn pop(&mut self) -> Option<T> {
        let this = Self(self.0.take());
        if let Some(rc) = this.0 {
            let (head, tail) = Rc::try_unwrap(rc).unwrap_or_else(|rc| (*rc).clone());
            *self = tail;
            Some(head)
        } else {
            None
        }
    }
}

fn main() {
    let mut s = Stack::new();
    assert_eq!(s.peek(), None);
    s.push(42);
    assert_eq!(s.peek(), Some(&42));
    assert_eq!(s.pop(), Some(42));
    assert_eq!(s.peek(), None);
}

drop順と循環参照

参照カウントGCには循環参照を回収できないという弱点が知られています。 Arc/Rc も例外ではありません。

use std::rc::Rc;
use std::cell::RefCell;

// RcとRefCellを使った簡易的なグラフ構造 (※メモリリークする)
struct Node {
    name: &'static str,
    neighbors: RefCell<Vec<Rc<Node>>>,
}

impl Node {
    fn new(name: &'static str) -> Rc<Self> {
        eprintln!("Created: {}", name);
        Rc::new(Self {
            name,
            neighbors: RefCell::new(Vec::new()),
        })
    }
}

impl Drop for Node {
    fn drop(&mut self) {
        eprintln!("Dropped: {}", self.name);
    }
}

fn main() {
    // 1 -> 2, 2 -> 1, 3 -> 1 という3つの辺を持つグラフを作る
    let node1 = Node::new("node1");
    let node2 = Node::new("node2");
    let node3 = Node::new("node3");

    node1.neighbors.borrow_mut().push(node2.clone());
    node2.neighbors.borrow_mut().push(node1.clone());
    node3.neighbors.borrow_mut().push(node1.clone());

    // Dropped: node3 だけが表示される
    // 1 <-> 2 は循環参照になっているので回収されない
}

図にすると以下のようになります。 main を抜ける直前は、各ノード同士のリンクのほかに、 main 自身が保有するリンクがあります。

main を抜けるときに node1, node2, node3 がそれぞれdropされます。このとき node3 は参照カウントが0になることで消滅しますが、 node1, node2 はどちらも参照カウントが1までしか減らないため、 main 終了後も存続してしまいます。

一般的に、Arc/Rc の循環参照に由来するメモリリークを仕組みで防ぐのは簡単ではありません。このことからRustではメモリリークを「安全」な操作に分類しています。(もちろん、メモリリークを推奨しているわけではありません。ほとんどのライブラリはメモリリークを意図せず行うことがないように慎重に設計されています。) これに関連して起きたLeakpocalypseはRustの安全性を考える上では興味深い事例だといえます。

なお、この「循環参照を回収できない」という制約は単なる実装上の問題というだけではなく、きちんとした意味があります。RustはRAII、つまり所有権を用いた外部リソースの管理に対応しています。「リソース確保は初期化である」が直訳ですが、実態はむしろ逆で「所有権の解放はリソース解放である」と考えるのがよいでしょう。スマートポインタである Arc, Rc, Box などの所有権が解放されるときに対応するヒープ領域が解放されるのはもちろんのこと、 File など外部リソースに対応する値に関してもユーザー定義のデストラクタ (Drop::drop) が即座に呼ばれることがRustの重要な特徴の1つです。

では、循環参照があるとき、どちらのデストラクタを先に呼べばいいでしょうか？答えはどちらでもダメです。というのも、後から呼ばれたほうのデストラクタは、部分的に解放された状態のデータを渡されるからです。Rustの Arc/Rc を含めたほとんどの型は、それが生きている限りは参照先も生きているという保証があるので、こういった普通のコンテナを使っている限りは、循環参照の解決は不可能です。

Weak

上記のような問題を解決するための仕組みとして弱参照があり、Rustでは Weak と呼ばれています。 Rc に対応する std::rc::Weak と Arc に対応する std::sync::Weak があります。

弱参照は、他の強参照に寄生する形でのみ参照先を保持できます。(実際に参照するときは、強参照への昇格を試みます)

use std::rc::Rc;

fn main() {
    let rc = Rc::new(42);
    let weak = Rc::downgrade(&rc);
    {
        // 強参照があるので、upgrade可能
        let rc2 = weak.upgrade().unwrap();
        assert_eq!(*rc2, 42);
    }
    drop(rc); // ここで強参照を回収
    {
        // 強参照がもうないので、upgrade不可能
        let rc2 = weak.upgrade();
        assert!(rc2.is_none());
    }
}

図で描くとこんな感じです。強参照と弱参照は別々にカウントされます。

強参照がなくなっても、ヒープ領域自体は残りますが、中身はdropされます。

弱参照は、非対称な循環参照を解消するために使われることがあります。たとえば、子リンクと親リンクの両方を持つ木構造では、どちらかを弱参照にすることで循環参照を解消できます。

use std::rc::{Rc, Weak};
use std::cell::RefCell;

/// 木の所有権。
/// 中では `Rc` を使っているが、強参照は通常時は1個だけ。
#[derive(Debug)]
pub struct Tree(Rc<RefCell<TreeInner>>);

/// 他で所有されている木のノードに対する弱参照。
/// 所有者が `Tree` を破棄した場合、こちらの参照は無効になる。
#[derive(Debug, Clone)]
pub struct TreeNode(Weak<RefCell<TreeInner>>);

#[derive(Debug)]
struct TreeInner {
    // 子リンクは強参照。
    children: Vec<Tree>,
    // 親リンクは弱参照。
    parent: Option<TreeNode>,
}

impl Tree {
    pub fn new() -> Self {
        Self(Rc::new(RefCell::new(TreeInner {
            children: Vec::new(),
            parent: None,
        })))
    }

    /// 根ノードへの弱参照を取り出す。
    pub fn to_node(&self) -> TreeNode {
        TreeNode(Rc::downgrade(&self.0))
    }
}

impl TreeNode {
    pub fn parent(&self) -> Option<Self> {
        // 弱参照を昇格。一時的に強参照が増える
        let rc = self.0.upgrade().expect("This tree is already disposed");
        let locked = rc.borrow();
        locked.parent.clone()
    }

    pub fn children(&self) -> Vec<Self> {
        // 弱参照を昇格。一時的に強参照が増える
        let rc = self.0.upgrade().expect("This tree is already disposed");
        let locked = rc.borrow();
        locked.children.iter().map(|child| Self(Rc::downgrade(&child.0))).collect()
    }

    pub fn push(&self, child: Tree) {
        // 弱参照を昇格。一時的に強参照が増える
        let rc = self.0.upgrade().expect("This tree is already disposed");
        {
            // TreeのRcは原則として強参照を1個だけもつので、このborrow_mutは基本的に成功する
            let mut child_locked = child.0.borrow_mut();
            // ユーザーから渡されたTreeは基本的に親を持たない
            assert!(child_locked.parent.is_none(), "Cannot have multiple parents");
            child_locked.parent = Some(self.clone())
        }
        let mut locked = rc.borrow_mut();
        locked.children.push(child);
    }

    pub fn pop(&self) -> Option<Tree> {
        // 弱参照を昇格。一時的に強参照が増える
        let rc = self.0.upgrade().expect("This tree is already disposed");
        let mut locked = rc.borrow_mut();

        let child = locked.children.pop()?;
        {
            // TreeのRcは原則として強参照を1個だけもつので、このborrow_mutは基本的に成功する
            let mut child_locked = child.0.borrow_mut();
            child_locked.parent = None;
        }
        Some(child)
    }
}

上の例の場合、子から親へのリンクに弱参照を使っているので、このリンクは(強)参照カウントには数えられません。そのため、木構造が不要になったタイミングで適切にメモリが解放されます。

対称な循環データを表現する

先ほどの例では、「親リンク」「子リンク」という非対称なリンクのうち片方を弱参照にすることで循環性の解消をすることができました。ではグラフのように対称な循環参照をもつデータはどのように表現すればよいでしょうか。これにはいくつかの方法があります。

1. Arena allocatorと &'a RefCell<T> を組み合わせる。この方法はRustコンパイラでも使われており、効率的で正当な方法ですが、構造体ライフタイムが絡むのでやや扱いが難しい面もあります。
2. 相互参照を Weak<RefCell<T>> で表現し、強参照を一箇所にまとめる。Arena allocatorの挙動を Arc/Rc で近似する方法で、グローバルライフタイムが不要になる利点があります。
3. gc や pgc など、トレースGCのライブラリを利用する。
4. 明示的に参照を持たず、一意なIDとHashMapで表現する。

本稿のテーマは Arc/Rc なので、2の実装例だけ掲載します。

use std::sync::{Arc, Mutex, Weak};

#[derive(Debug, Clone)]
pub struct Graph(Arc<Mutex<Vec<Arc<Mutex<NodeInner>>>>>);

impl Graph {
    pub fn new() -> Self {
        Self(Arc::new(Mutex::new(Vec::new())))
    }

    pub fn new_node(&self) -> Node {
        let node = Arc::new(Mutex::new(NodeInner {
            neighbors: Vec::new(),
        }));
        let node_weak = Node(Arc::downgrade(&node));
        let mut lock = self.0.lock().unwrap();
        lock.push(node);
        node_weak
    }
}

#[derive(Debug, Clone)]
pub struct Node(Weak<Mutex<NodeInner>>);

impl Node {
    pub fn push(&self, neighbor: Node) {
        let rc = self.0.upgrade().expect("The graph is dead");
        let mut lock = rc.lock().unwrap();
        lock.neighbors.push(neighbor);
    }
}

#[derive(Debug)]
struct NodeInner {
    neighbors: Vec<Node>,
}

まとめ

• Arc/Rc は参照カウントを使ったスマートポインタであり、データや状態を共有できる。
• 状態を共有するには内部可変性コンテナである RefCell や Mutex と組み合わせる必要がある。
• Rc は Arc よりコストが低いが、スレッドセーフではない。間違った使い方はコンパイラが指摘してくれるので、スレッド安全性に注意しながら書く必要はない。
• 循環参照を作ると問題が発生するので、その場合は弱参照 Weak で循環性を解消する必要がある。