RustでGraphを実装する方法
Rc
,RefCell
を使用しない方法
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
を使用する方法
以下のような実装になります。
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
の構造体の中身は以下のようになっています。
pub struct Rc<T: ?Sized> { ptr: NonNull<RcBox<T>>, phantom: PhantomData<RcBox<T>>, }
なぜ幽霊型を用いてT
を消費しているのかに関しては、今後調べたいと思います。
RcBox<T>
の中身に関しては、
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
されません。(以下該当コード)
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
が実装してある
2022年の振り返りと2023年の目標
アセンブリのメモx64(x86-64)
intel記法で書く
.intel_syntax noprefix .global main ...
割り算
x64のdiv
,idiv
の仕様は二つのレジスタを引数に取りそれを割るのではない。
動作としては
商:rax = rdx:rax / 第一オペラント あまり : rdx 表記 div 第一オペラント
マジでこの使用は謎
また、rax
のレジスタをrdx:rax
に変換する方法としてcwd
,cdq
,cqo
などがある。
これらは、何ビットかによって異なる
function prologue, function epilogue
呼び出し元のスタックポインタをrbpに退避させてそれをスタックにプッシュする。
push rbp mov rbp, rsp
(書きかけ)
tokioなどで非同期処理を行う際の関数をasyncを付けずに呼ぶ方法。
遺伝研のスパコンにGPU付きでloginする方法
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 | +-----------------------------------------------------------------------------+