Instantly share code, notes, and snippets.

@Knium /4.md
Last active Dec 23, 2018

Embed
What would you like to do?
UEC MMA プログラミングRust輪読会資料第4章

プログラミング Rust 輪読会 4章

<必要があれば,スタックとヒープの話をする(スタックとヒープの理解があるとこの章は理解が厳しいかもしれない, というか用語で苦しくなって死ぬ)> https://keens.github.io/blog/2017/04/30/memoritosutakkutohi_puto/ よさそう!!!(読んでない)

https://docs.python.org/3.6/c-api/memory.html#overview Pythonはスタックで変数を管理することはおそらくしてない, 判断基準は stack でCMD+Fをしても見つからなかっただけどほんまか?

<C++を全く書いたことないので何もわからんし,freeとか多少Cっぽさはあるけどまあそこまで大筋からずれてないと信じたい>

前書き

プログラミングはメモリのシンタックスシュガーなのでRustの所有権を用いた安全なメモリ管理の元でのプログラミングをしましょう(雑)

4.1 所有権

次のC++のコードを例として考える.std::string s = "frayed know";

一般的な話

図に書いてあるスタックフレーム上の変数s(std::string型)は,3ワード長のオブジェクトである. 最大容量(capacity), 文字列の長さ(length),そしてヒープ上の文字列の実体へのポインタ(buffer | バッファ), が3ワードの中身である. この時, 「sはそのバッファを"所有"している」 と言うことができる. プログラムがsを破棄したら,sのデストラクタによりこのバッファは解放される.

ちなみに昔は1つのバッファを複数のstd::string値から共有し,参照カウントを使ってバッファを解放するタイミングを決定していたが今は上で述べたデストラクタ制を使っている?

じゃあC++の何が問題なの?

std::string s = "frayed knot";
char *t = s.buffer; // 多分プライベートフィールドだけど例なので許して

| s | t | on stack frame
  |   |
  |   /
  |  /
  | /
  ------------
  |frayed knot| on heap
  -------------

t < 使ったからバッファ解放しとくか(良心) free(t)っと・・・
そのあとのs < よっしゃ,バッファいじるか〜〜 は??ちょ,勝手に解放されてるんだけど〜〜〜〜〜〜〜〜〜(pointer being freed was not allocated)

C++ではこういう解放の規則を持ったコードを書くことをプログラマが意識しないといけないが,Rustではこの原則を言語として強制している. Rustでは,全ての値はその生存期間を決定する唯一の所有者を持つ.言い換えると,さきほどのtはsのバッファを勝手に解放することをコンパイラが許さない.

std::string s = "frayed knot";
char *t = s.buffer; // 多分プライベートフィールドだけど例なので許して

| s | t | on stack frame
  |   |
  |   /
  |  /
  | /
  ------------
  |frayed knot| on heap
  -------------

t < 使ったからヒープ解放しとくか(良心) ってあれ,俺はバッファを解放しなくていい(できない?)のか〜 じゃあs任せたわ!!!
そのあとのs < Rustなら誰に貸しても勝手に解放されずに済むな〜〜〜(嬉しい)

このように安全に参照を使うことができる.つまり,メモリの解放タイミングを我々が考える必要がなく,コンパイラがいい感じにしてくれる.

じゃあいつ解放されるのかっていうと, その変数が宣言されたブロックを制御が離れた時である.

fn print_padovan() {
    let mut padovan = vec![1,1,1];
    for i in 3..10 {
        let next = padovan[i - 3] + padovan[i - 2];
        padovan.push(next);
    }
    println!("{:?}", padovan);
} // ここでpadovanと,そのバッファは解放される.

また,Rustでもベクタや文字列みたいに動的にメモリを変化させる必要がない型でもヒープ上に確保することができる.それがBox型だ. <この辺必要があればする,そんな難しくないだろうし理解ができてればテキトーに飛ばしてよさそう>

enum AST {
    Int(i32),
    Add(AST, AST) // これは型のサイズが決まらないのでだめ
    Add(Box<AST>, Box<AST>) // ポインタなので型が決まる
}

4.2 移動

Rustでは,ほとんど全ての型が変数への値の代入,関数への引数の受け渡し,関数からの返り値の返却の際にコピーされず,移動(move)される.簡単なコードを例とすると,

{
    let x = vec![1, 2, 3];
    let y = x; // この行でxは使えなくなる
    println!("{:?}", x); // 使えないのに呼ぼうとしてるのでコンパイルエラーになる.
}

こんな感じである.どうしてこうなってしまったのか,どのような利点はあるのか? 他の言語(Python, C++)における代入プロセスとそのメリット/デメリットを述べて説明したいと思う.

例えば,Pythonの次のコードについて考える.

s = ["udon", "ramen", "soba"]
t = s
u = s

(図4-5, 4-6)

このようにPythonでは参照カウントと呼ばれる手法を使っている. メリットは,代入を安価に行えるところにある.なぜなら同一のPyListObjectを参照しているローカル変数が1個増えるだけで済むからだ. デメリットは,GCがアレコレ動いているのでその分のコストがかかるなど?<要出典>

一方C++では,俗に言う深いコピーをしている. (図4-7, 4-8) メリットは,各々の変数が所有権を持っているため勝手に意図しない解放が起きない事 こっちの問題点は,毎回複製してるのでめっちゃ大きいオブジェクトに対して代入をした際のコストが半端ない.

2つの言語のメリット/デメリットを見た,最後にRustではどうなるだろうか.

let s = vec!["udon".to_string(),"ramen".to_string(),"soba".to_string()];
let t = s;
let u = s;

(図4-9) (図4-10) 移動では代入時にコストはかからないし,各々の変数が所有権を持っているので両方のメリット(代入が安価/所有権をそれぞれ持っている)を受け継いてる. また,移動ではなくてC++のように深いコピーが欲しい場合は,

let s = vec!["udon".to_string(),"ramen".to_string(),"soba".to_string()];
let t = s.clone();
let u = s.clone();

とcloneメソッドを呼べば良い.

4.2.1 移動を伴う他の操作

let mut s = "Govinda".to_string();
s = "Siddhartha".to_string();

と言うコードがあった時に

1行目実行時
| s | on stack frame
  |
  |
  |
  |
  --------
  |Govinda| on heap
  --------
~~~~~~~~~~~~~~~~~~~~~~~~~~
2行目実行時
s = "Siddhartha".to_string();
| s | on stack frame
  |
  |
-
|  
|  --------
|  |Govinda| on heap < ほな・・・さいなら・・・(drop)
|  --------
|
| - |
 ------------
 |Siddhartha| on heap
 ------------

というコードがあった時に,sに"Siddhartha"が代入される際にsに入っていた値"Govinda"がまずドロップされる.しかし,

let mut s = "Govinda".to_string();
let t = s;
s = "Siddhartha".to_string();

は,

1行目実行時
| s | on stack frame
  |
  |
  |
  |
  --------
  |Govinda| on heap
  --------
~~~~~~~~~~~~~~~~~~~~~~~~~~
2行目実行時
| s | t | on stack frame
      |
      |
      |
      |
  --------
  |Govinda| on heap
  --------
~~~~~~~~~~~~~~~~~~~~~~~~~~
3行目実行時
| s | t | on stack frame
  |   |
  |   |
  |   |
--    |
|  --------
|  |Govinda| on heap
|  --------
|
| - |
 ------------
 |Siddhartha| on heap
 ------------

と言う風に元の所有権をtがsから引き継ぐので,sに代入しようとする時点でsは初期化状態になっている.

ここでは,初期化と代入を例に用いたが,他にも移動が伴う操作は以下の通りである.

  • 関数からの値の返却: let mut composers = Vec::new();
  • 新しい値の作成: Person { name
  • 関数への値渡し: f(x)

このように値を動かして回るのは非効率的に思えるかもしれないが,2つ注意するべきことがある. 1つは,移動されるのは値だけであって,それが保有するヒープ上のストレージ部分は移動されないってことだ.どう言うことかというと,

exec: let s = "kuruton".to_string();
| s |
  | 
  |
  |-----------------------------------
  | buffer | capacity: 8 | length: 8 |
  ------------------------------------
      |
      |
      |
      --------
      |kuruton|
      --------
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
exec: let t = s;
| s | t |
      | 
      |
      |-----------------------------------
      | buffer | capacity: 8 | length: 8 | on stack frame < ここの3ワードがぴょんぴょんするんじゃ^〜
      ------------------------------------
          |
          |
          |
       -------
       |kuruton| on heap <この部分が再確保されるわけじゃない
       -------

次にRustコンパイラのコード生成はこの移動を見通すのが上手だということだ.

4.2.2 移動と制御フロー

let x = vec![10,20,30];
if c {
    f(x);
} else {
    g(x);
}
h(x);

があった時にどちらにせよxは使われるのでコンパイルエラーが起きる話? でも普通に考えて

if false {
    f(x);
}
h(x);
~~~~~~~~~~~~~~~~~~~~~~~~
  --> src/bin/4-2.rs:40:7
   |
38 |         f(x);
   |           - value moved here
39 |     }
40 |     h(x);
   |       ^ value used here after move

となるし普通になんでこんな回りくどい言い方してるのか何もわからん.

let x = vec![10,20,30];

while f() {
    g(x);
} // uninitialized ... 
let mut x = vec![10,20,30];

while f() {
    g(x);
    x = vec![10,20,30];
} // uninitialized ... 
e(x);

https://www.oreilly.co.jp/books/9784873118550/ ここに誤字があったっぽい

ほがすの質問: while文の中でのx = g(x) とかできる?

fn g(x: Vec<i32>) -> Vec<i32> {
    x
}

fn main() {
    let mut x = vec![10,20,30];
    let mut y = 0;
    while y < 10 {
        x = g(x);
        y += 1;
    }
}

4.2.3 移動とインデックスされる値

<Rust書き始めた時からgetメソッドを使ってたのでなんでこんな回りくどいことかいてるのかわからん,後回し>

  • RustではVecの歯抜けが許されていない
  • 何故か?
    • もしそれを許すと, Vecが全ての要素についてその所有権があるかどうかを保持していないといけないから
    • そういったコストが掛かるため, これを許していない

4.3 コピー型

ここまで示した例で移動した値は,ベクタや文字列などの大量のメモリを使用したりそもそもサイズが不定なのでスタックフレーム上に置けずにヒープを使う必要性があったものだ.しかし,整数や文字などのより単純な型(主にスタックフレーム上で完結する?)の場合は移動が起きない. つまり,

let n = 10;
let m = n;
~~~~~~~~~~
 | m | n |
   |    |
| 10 | 10 | on stack frame

と言う風になる.ここで,代入を使っても移動が起きずにコピーされる型をCopy型という. Copy型には

  • i32, u8, etc...な数値型
  • char
  • bool などがある.他にも独自で定義した structenumもCopy型として扱える場合があるが,デフォルトではCopyではないので明示しなければならない. また,メンバの型やヴァリアントによってはできない.まあStringはヒープにバッファを持つ型だからCopy型を満たさないのに,メンバにString型がある構造体はそりゃ満たしませんわなぐらいの話なので自明. じゃあなんでデフォルトでenumやstructをCopy型を満たしているかどうかに関わらずオフにするかと言うと,それがプログラム上でのその型の使い方に大きな影響を与えるためだ. Copiableなenumを実装した後に「あ,Stringを保持するヴァリアント生やすわ」としたらもう破滅である.なので,enumやstructをCopy型としてderiveする際には「本当にいいのか?」と確認してからやろう!(1敗) また,Copy型といってしまったがこれはインスタンスが作れる型ではなく,Copyトレイトを満たす型を安直にCopy型と言ってしまっただけなのでゆるして,みんな大好きトレイトは11章にあるので読みましょう.

4.4 RcとArc

SICPとかに出てくるリスト構造や他にもグラフなどのデータ構造を表現するときに使えるらしい.試しにリスト構造としてconsを実装しようと思ったが,set-car!, set-cdr!をメソッドとして実装しようと思ったけどできなかったので辛い.誰かプロ各位チャレンジしてみてください,任せました.

Rcは以下のように使う.

use std::rc::Rc;

let s = Rc::new("shirataki".to_string()); // Rc<String>
let t = s.clone();
let u = s.clone();

こうすると,図4-12のようにヒープ上にStringオブジェクトに加えて参照カウントが確保される. (src/liballoc/rc.rs)より

pub fn new(value: T) -> Rc<T> {
    Rc {
        // there is an implicit weak pointer owned by all the strong
        // pointers, which ensures that the weak destructor never frees
        // the allocation while the strong destructor is running, even
        // if the weak pointer is stored inside the strong one.
        ptr: Box::into_raw_non_null(box RcBox {
            strong: Cell::new(1),
            weak: Cell::new(1),
            value,
        }),
        phantom: PhantomData,
    }
}

この実装を見るとわかるかもしれないが.図4-12のヒープ上の強い参照カウントとshiratakiへのバッファの間には1個スペースがあるのだが,おそらくここにはweakな参照カウンタが入っているはずである.(この気づきが何の役にたつかはわからない.)

(Ref: https://github.com/rust-lang/rust/blob/b76ee83254ec0398da554f25c2168d917ba60f1c/src/liballoc/rc.rs#L314)

番外編

$ cargo new --bin hoge
$ cd hoge
$ mkdir src/bin
$ touch src/bin/fuga.rs
$ touch src/bin/bar.rs

<fuga.rsとbar.rsをそれぞれいじる>

$ cargo run --bin fuga
$ cargo run --bin bar
.
├── Cargo.lock
├── Cargo.toml
├── src
   ├── bin
   │   ├── bar.rs
   │   └── fuga.rs
   └── main.rs
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment