`Rc`,`RefCell`を使用しない方法

smallcultfollowing.com

struct Graph {
    nodes: Vec<NodeData>,
    edges: Vec<EdgeData>
}

type EdgeIndex = usize;
type NodeIndex = usize;

struct NodeIndex {
    firest_outgoing_edge: Option<EdgeIndex>
}

struct EdgeIndex {
    target: NodeIndex,
    next_outgoing_edge: Option<EdgeIndex>
}

グラフのノードとエッジをそれぞれのvectorのエッジとして管理してしまうというものです。グラフの数学的な定義をそのまま実装したような感じです。この方法だと、オブジェクトへのポインタを考える必要がないのでRcやRefCellなどを使用する必要はありません。そのため、この構造体は簡単にスレッド間でデータ共有できます。

一方で、このデータ構造では、グラフを結合などは結構大変です。結合する場合、どちらかのIndexを全て加算しないといけません。削除する場合も同様に、インデックスを削除する範囲を考えるなどは大変です。

`Rc`,`RefCell`を使用する方法

github.com

以下のような実装になります。

struct Node {
    datum: &'static str,
    edges: Vec<Rc<RefCell<Node>>>,
}

また一才unsafeなコードを使うことなくGraphを結合が可能です。 RefCellは実行時に可変参照を作成して良いかのチェックを行うためオーバーヘッドが存在します。

`RefCell`を使用する理由

内部可変性を持たせたいからです。 RefCellを使用しない場合、以下のような実装になります

struct Node {
    datum: &'static str,
    edges: Vec<Rc<Node>>,
}

この実装では、先頭のNodeからedgesをもとに葉の方向へ辿っていき、たどった先のNodeになんらかのmutableな操作を行う際にNodeへの可変参照が作成できません。具体的なコードで説明します。全ての葉Nodeにノードを追加する操作を実装してみましょう。

impl Node {
    /// edgesを辿って一番末端の`Node`の`Vec`を得る
    fn leaf(&self) -> Vec<Rc<Node>> {
        self
            .edges
            .iter()
            .map(|node| {
                if node.edges.len() == 0 {
                    return vec![Rc::clone(node)];
                } else {
                    return node.leaf();
                }
            })
            .flatten()
            .collect()
    }

    /// 全ての末端のノードの`edges`に引数の`leaf_node`を追加する
    fn extend_tail(&mut self, new_tail: Node) {
        let mut binding = self.leaf();
        let rc = Rc::new(new_tail);
        for i in 0..binding.len() {
            let mut a = binding[i]; // <- error
        }
    }

}

この場合、RcにはDerefMutがimplされていません。そのためRc自体がmutableであっても、Rcが指し示すオブジェクトにはmutableにアクセスすることはできません。 Rc::get_mut()などもありますが、このメソッドはRcの参照カウンタが1の時のみ動作可能です。つまり、edgesを上書きしたいNodeが他の複数のNodeのedgesに指定されている場合、get_mutで可変参照を取り出すことは不可能です。そのため、上記のような処理を行うことはできません。このような理由からRefCellなどの内部可変性を持つスマートポインタを使用する必要があります。

`Rc`を使う理由

Rcを使用しないときの問題点について説明します。 Rcを使用しないNodeは以下のような場合が考えられると思います。

struct Node {
    name: String,
    edges: Vec<RefCell<Node>>
}

この実装方法では、任意のNodeをedgeとして持つNodeは一つになります。または、以下のような実装も考えられます。

struct Node<'a> {
    name: String,
    edges: Vec<&'a RefCell<Node>>
}

以下の場合に破綻します。

impl<'a> Node<'a> {
    fn new(name: String) -> Self {
        Node { name, edges: Vec::new() }
    }
    fn add_node_from_string(&mut self, string: String) {
        let new_node = RefCell::new(Self::new(string));
        self.edges.push(&new_node); // error new_nodeのlifetimeは`add_node_from_string`内なのでnew_nodeがdropされる
    }
}

Nodeのメソッドとして新しいedgesを名前指定で作成したい場面でdropされてしまいます。

以下、RcとRefCellの内部の構造を読んだ際のメモです。

`Rc`

参照カウント式のスマートポインタです。ポインタが指し示すオブジェクトの所有権を共有できます。 Rustでは可変参照が存在する場合は、他に参照が存在しない。他に参照が存在する場合は、可変参照は存在しない。というルールがあります。 Rustの参照のルールに乗っとており、基本的にimmutableです。所有権を共有しなおかつ内部可変性を持たせたい場合は、Rc<RefCell<T>>などを行う必要があります。

Rcの構造体の中身は以下のようになっています。

doc.rust-lang.org

pub struct Rc<T: ?Sized> {
    ptr: NonNull<RcBox<T>>,
    phantom: PhantomData<RcBox<T>>,
}

なぜ幽霊型を用いてTを消費しているのかに関しては、今後調べたいと思います。 RcBox<T>の中身に関しては、

doc.rust-lang.org

struct RcBox<T: ?Sized> {
    strong: Cell<usize>,
    weak: Cell<usize>,
    value: T,
}

になっています。 strongは強参照の数つまり、Rcがvalueを指し示している数です。 weakは弱参照の数です。Weakによりvalue が指し示されている数です。それぞれ、RcやWeakが生成されるたびにインクリメントされ、 dropされる際にデクリメントされます。 strongとweakでの違いはカウンタが0になった際の挙動です。 strongが0になった場合はvalueもdropされますが、weakの場合はvalueはdropされません。(以下該当コード)

doc.rust-lang.org

`RefCell`

RefCellを用いて可変参照を取得する部分に関してコードを読みます。まず、RefCellの中身は

pub struct RefCell<T: ?Sized> {
    borrow: Cell<BorrowFlag>,
    // Stores the location of the earliest currently active borrow.
    // This gets updated whenever we go from having zero borrows
    // to having a single borrow. When a borrow occurs, this gets included
    // in the generated `BorrowError/`BorrowMutError`
    #[cfg(feature = "debug_refcell")]
    borrowed_at: Cell<Option<&'static crate::panic::Location<'static>>>,
    value: UnsafeCell<T>,
}

まず、UnsafeCellの中身を確認します。

pub struct UnsafeCell<T: ?Sized> {
    value: T,
}

また、Cellの中身は

pub struct Cell<T: ?Sized> {
    value: UnsafeCell<T>,
}

になっています。

BorrowFlagは以下です

type BorrowFlag = isize;
const UNUSED: BorrowFlag = 0;

`UnsafeCell`の内部可変性の仕組み

UnsafeCellでは変数を可変参照または、mut Tで取り出すメソッドが用意されています。

const fn get(&self) -> *mut T 一切のチェックなしで中身にmutableな生ポインタを返します。
get_mut(&mut self) -> &mut T mutableな参照からmutableな中身を返します(これはもはや内部可変性とかではなく普通にやってるだけなきが...)
raw_get(this: *const Self) -> *mut T UnsafeCellのポインタから中身を取り出します。getとは異なり、生ポインタから直接呼べるので参照を作る必要がありません。

コードを書く側がgetやraw_getのアクセスがユニークであることを担保しないといけません。そういった意味でUnsafeなのでしょうか。

`Cell`の内部可変性の仕組み

Cellに関してはUnsafeCellと同様に可変参照を返すmethodは存在しません。そのため、Rustの可変参照のルールに抵触することはありません。(getを使うと中身の可変生ポインタを複数作成することも可能ですが)

`RefCell`の内部可変性の仕組み

immutableの参照をとる

immutableな参照のデータ型として、Refが定義されています。これはborrowから取得できますが、中身はほぼtry_borrowなのでそれを読みます。中身としては

    pub fn try_borrow(&self) -> Result<Ref<'_, T>, BorrowError> {
        match BorrowRef::new(&self.borrow) {
            Some(b) => {
                #[cfg(feature = "debug_refcell")]
                {
                    // `borrowed_at` is always the *first* active borrow
                    if b.borrow.get() == 1 {
                        self.borrowed_at.set(Some(crate::panic::Location::caller()));
                    }
                }

                // SAFETY: `BorrowRef` ensures that there is only immutable access
                // to the value while borrowed.
                let value = unsafe { NonNull::new_unchecked(self.value.get()) };
                Ok(Ref { value, borrow: b })
            }
            None => Err(BorrowError {
                // If a borrow occurred, then we must already have an outstanding borrow,
                // so `borrowed_at` will be `Some`
                #[cfg(feature = "debug_refcell")]
                location: self.borrowed_at.get().unwrap(),
            }),
        }
    }

となっています。 BorrowRefは、

struct BorrowRef<'b> {
    borrow: &'b Cell<BorrowFlag>,
}

で定義されています。中身は、RefCell::borrowの参照に1を加えてその後条件分岐を行う BorrowRefがマイナス1の時は可変参照が存在している BorrowRefがプラスの時はその数だけ参照が存在している BorrowRefに1を加える

BorrowRef == 0 -> 可変参照が存在している -> 参照を作れない
BorrowRef > 0 -> 可変参照は存在していない(参照は存在しているかもしれない) -> 参照は作成できる -> Ok<Ref<'_, T>>がreturn

のようになっている. RefにはDeref がimplされているので、Tと同様に扱える。

`RefCell`からmutableな参照を得る方法

immutableなものと同じでBorrowRefで管理を行います。

BorrowRefに-1を加える

BorrowRef != -1 -> 可変参照or参照が存在している -> 可変参照を作れない
BorrowRef == -1 -> 可変参照or参照は存在していない -> 可変参照は作成できる -> Ok<RefMut<'_, T>>がreturn

RefMutにはDerefMutが実装してある

普通にsshでゲートウェイサーバーにログインしたあと、

qlogin -l gpu

でloginできる

nvidia-smi

すると、

+-----------------------------------------------------------------------------+
| NVIDIA-SMI 440.33.01    Driver Version: 440.33.01    CUDA Version: 10.2     |
|-------------------------------+----------------------+----------------------+
| GPU  Name        Persistence-M| Bus-Id        Disp.A | Volatile Uncorr. ECC |
| Fan  Temp  Perf  Pwr:Usage/Cap|         Memory-Usage | GPU-Util  Compute M. |
|===============================+======================+======================|
|   0  Tesla V100-SXM2...  On   | 00000000:15:00.0 Off |                    0 |
| N/A   36C    P0    40W / 300W |     11MiB / 16160MiB |      0%      Default |
+-------------------------------+----------------------+----------------------+
|   1  Tesla V100-SXM2...  On   | 00000000:16:00.0 Off |                    0 |
| N/A   35C    P0    39W / 300W |     11MiB / 16160MiB |      0%      Default |
+-------------------------------+----------------------+----------------------+
|   2  Tesla V100-SXM2...  On   | 00000000:3A:00.0 Off |                    0 |
| N/A   34C    P0    39W / 300W |     11MiB / 16160MiB |      0%      Default |
+-------------------------------+----------------------+----------------------+
|   3  Tesla V100-SXM2...  On   | 00000000:3B:00.0 Off |                    0 |
| N/A   35C    P0    40W / 300W |     11MiB / 16160MiB |      0%      Default |
+-------------------------------+----------------------+----------------------+
                                                                               
+-----------------------------------------------------------------------------+
| Processes:                                                       GPU Memory |
|  GPU       PID   Type   Process name                             Usage      |
|=============================================================================|
|  No running processes found                                                 |
+-----------------------------------------------------------------------------+

冒頓単于

RustでGraphを実装する方法

`Rc`,`RefCell`を使用しない方法

`Rc`,`RefCell`を使用する方法

`RefCell`を使用する理由

`Rc`を使う理由

`Rc`

`RefCell`

`UnsafeCell`の内部可変性の仕組み

`Cell`の内部可変性の仕組み

`RefCell`の内部可変性の仕組み

immutableの参照をとる

`RefCell`からmutableな参照を得る方法

2022年の振り返りと2023年の目標

2022年の振り返り

所感

2023年の目標

アセンブリのメモx64(x86-64)

intel記法で書く

割り算

function prologue, function epilogue

アセンブリを出力するときに読みやすくするためのオプション

cfi_**みたいなやつを出力しないオプション

intel記法で出力するほうほ

`--target=[arch]`

Rustで自動微分

tokioなどで非同期処理を行う際の関数をasyncを付けずに呼ぶ方法。

遺伝研のスパコンにGPU付きでloginする方法

Rc,RefCellを使用しない方法

Rc,RefCellを使用する方法

RefCellを使用する理由

Rcを使う理由

Rc

RefCell

UnsafeCellの内部可変性の仕組み

Cellの内部可変性の仕組み

RefCellの内部可変性の仕組み

immutableの参照をとる

RefCellからmutableな参照を得る方法

2022年の振り返り

所感

2023年の目標

intel記法で書く

割り算

function prologue, function epilogue

cfi_**みたいなやつを出力しないオプション

intel記法で出力するほうほ

--target=[arch]

`Rc`,`RefCell`を使用しない方法

`Rc`,`RefCell`を使用する方法

`RefCell`を使用する理由

`Rc`を使う理由

`Rc`

`RefCell`

`UnsafeCell`の内部可変性の仕組み

`Cell`の内部可変性の仕組み

`RefCell`の内部可変性の仕組み

`RefCell`からmutableな参照を得る方法

`--target=[arch]`