こんにちは。マイクロアドで機械学習エンジニアをしている大庭です。

今回の記事では多くのプログラミング言語で採用されているメモリ管理機能である「ガベージコレクション」とRustで導入され現在注目されている「所有権」について、最近調べる機会があったため備忘録を兼ねてまとめてみようと思います。

スタック領域とヒープ領域

プログラムが利用するメモリはおおよそ以下の４つの領域に分けられます。

テキスト領域：機械語に翻訳されたプログラムを保存する領域
静的領域：グローバル変数やstatic 変数など実行中に削除しない変数を保存する領域
スタック領域：使用するサイズ順序が決まっている変数を保存する領域
ヒープ領域：コンパイル時にサイズや寿命を判断できない動的な変数を保存する領域

プログラムの使用する変数の大部分はスタック領域とヒープ領域に記録されるため、プログラミング言語におけるメモリ管理ではスタック領域とヒープ領域をどのように使い分けるか、どのように管理するかが主な関心事となっています。そのためこの記事では、はじめにスタック領域とヒープ領域について解説します。

スタック領域

スタック領域とはその名前の通りスタックで管理されるメモリ領域です。スタック領域ではメモリの確保と解放は常に末尾に対してのみ実行されるため非常に高速に動作します。また参照する場合も常に末尾にアクセスするため参照の局所性*1が高くメモリキャッシュが効きやすくなっています。

スタック領域は操作が高速な反面、スタック構造で自動的にメモリの確保と解放を行うためコンパイラによって寿命が判断できない値を扱えないという制限があります。

ヒープ領域

スタック領域では扱えない寿命の判断できない変数やサイズが実行時に変わる変数を保存するメモリ領域がヒープ領域です。ヒープは山積みという意味で、事前に確保した潤沢なメモリに対して実行時に必要になった分だけメモリを検索し確保します。

配列のようなメモリ確保は参照の局所性を保つために連続したメモリ領域として確保されるのですが、ヒープメモリを確保する場合必要なサイズが連続している場所を検索する必要があり高価になりがちです。特にメモリが虫食いのような状態になるフラグメンテーション*2が起きると検索に時間がかかったり、そもそも必要なサイズを確保できなくなってしまったりします。

PythonやJavaScriptのような動的言語はそもそもコンパイラを持たないため、ほぼ全ての値をヒープ領域で扱っています。

ヒープ領域の管理方法

プログラミング言語におけるヒープ領域の管理方法は以下の３つに分けられます。

手作業(malloc / free)でのメモリ管理
ガベージコレクション
所有権

Cなど高いパフォーマンスを求めている言語ではエンジニアが直接のヒープメモリを管理する手作業でのメモリ管理が行われているのですが、考慮漏れが即メモリリークに繋がるため要求される技術レベルが高くなってしまっています。

そのため、現在利用されているプログラミング言語の多くはガベージコレクションを採用しています。

ガベージコレクション

ガベージコレクション(GC)とは、ヒープ領域のうち不要になった領域を自動的に解放する仕組みのことです。

Java、Python、JavaScript、Goなど主要な言語で採用されていますが、そのアルゴリズムは言語毎に微妙に異なっています。

以下ではガベージコレクションの代表的なアルゴリズムを４つ紹介しようと思います。

参照カウント
マーク・アンド・スイープ
コピーGC
世代別ガーベージコレクション

参照カウント

値を参照するポインタの数をカウントしておき、参照するポインタの数がゼロになったら解放するというアルゴリズムです。

単純なアルゴリズムで参照がなくなってすぐにオブジェクトの解放が行えることが利点ですが、一方でオブジェクトが相互に参照をもつ循環参照に何らかの対処をする必要があります。

マーク・アンド・スイープ

循環参照に対処するため、必須とわかるオブジェクト（ルートオブジェクトと呼ぶ）からの参照をたどっていき、何からも参照されていないオブジェクトを破棄するアルゴリズムです。

具体的な手順は以下のようになります。

ルートオブジェクトに印をつける（スタック領域のオブジェクトなど）
直前にマークをつけたオブジェクトから参照されているオブジェクトにマークをつける
2の操作を、マークがつかなくなるまで行う
マークがついてないオブジェクトを破棄（スイープ）する

マーク・アンド・スイープは必要が無くなったオブジェクトの検索と破棄をまとめて行う都合上、一度のGCに時間がかかるためバックグラウンドで処理を実行する必要があり、Go言語など並列実行性の高い言語で利用されています。

コピーGC

ヒープ領域内に2つの領域（From領域とTo領域）を用意してGC実行時にメモリを詰めて再配置するコンパクションを行いながらFrom領域からTo領域へのコピーを行うアルゴリズムです。

フラグメンテーションに対処できますが、ヒープ領域を２つに分ける分通常の半分のサイズまでしか使えないというデメリットがあります。

世代別ガーベージコレクション

「作られたばかりのオブジェクトはすぐに利用されなくなる可能性が高く、ある程度長生きしたオブジェクトは以降も利用されやすい」という傾向を利用したアルゴリズムで、生存期間でオブジェクトを分類しておいてGCを行う頻度を調整するアルゴリズムです。

所有権

最後にRustで用いられているヒープメモリ管理に用いられている「所有権」機能について紹介します。

「所有権」をざっくり説明すると、ヒープ領域の値でもコンパイラが寿命を判断できるよう３つの原則を設けることでスタック領域のような自動的な値の解放をヒープ領域で可能にする機能です。

所有権の原則

Rustのメモリ管理は以下の３つの原則に基づいています。

Rust上の「値」は「変数」に入れられていて、その変数をその値の「所有者」と呼ぶ
値の所有者になれる変数は一時期に一つだけ
所有者である変数が「スコープ」を出た時、その値は解放される

スコープによる値の解放

Rustではヒープに確保されるデータ型は宣言と同時に作成され、スコープを抜けると同時に解放されます。

fn hoge() {
    let s = String::from("hello");  // 可変長文字列がヒープメモリに確保される
    // sを使った処理
}
//　スコープを抜けると変数sとその値が破棄される

この動作からも所有権でのヒープメモリ管理はスタック領域に似ていることがわかるかと思います。

Rustは所有権システムとそれを満たしているかをコンパイル時の厳密にチェックすることでユーザの技術力に依らずに安全性を担保しています。

所有権の移動

以下のようなコードを実行すると、多くのプログラミング言語では文字列 hello の値のコピーは行われず、参照のコピーのみが行われます。

let s1 = String::from("hello");
let s2 = s1;

これは可変長データで要素数が多い場合に値のコピーを行ってしまうと処理が高価になってしまうためです。新しい参照を作成する処理をshallow copy、値自体を複製する処理はdeep copyと呼びます。

Rustではこのshallow copyの際に、値の「所有者」の移動が行われます。

let s1 = String::from("hello");
let s2 = s1;
println!("{}, world!", s1);

play.rust-lang.org

上記のコードを実行すると次のようなエラーが出力されます。

error[E0382]: borrow of moved value: `s1`
 --> src/main.rs:5:28
  |
2 |     let s1 = String::from("hello");
  |         -- move occurs because `s1` has type `String`, which does not implement the `Copy` trait
3 |     let s2 = s1;
  |              -- value moved here
4 |
5 |     println!("{}, world!", s1);
  |                            ^^ value borrowed here after move
  |
  = note: this error originates in the macro `$crate::format_args_nl` which comes from the expansion of the macro `println` (in Nightly builds, run with -Z macro-backtrace for more info)
help: consider cloning the value if the performance cost is acceptable
  |
3 |     let s2 = s1.clone();
  |                ++++++++

値の所有権がすでに s1 から s2 に移動しているため、所有権を持たない s1 の参照でエラーが起きています。

この「値の所有権をもつ変数は常に１つだけ」というルールがあることで、所有権を持った変数の寿命が値の寿命とイコールになっています。

これによりGCのように全ての参照を把握する必要がなく所有者がスコープから抜けると同時に値の解放を行えることが所有権の中心的なアイディアです。

所有権の弊害

所有権はスタック領域のようなメモリの解放を行うため、ヒープ上の値に対して複数の変数が同じ値を指すことを禁止しコンパイラで値の寿命を把握できるようにしていますが、それによって利便性が下がってしまう面もあります。

その典型的な例が関数の引数に参照を渡す場合です。

fn main() {
    let s = String::from("hello");
    takes_ownership(s);  // sの所有権が関数内に移動
    println("{}", s);    // sの所有権がない!!
}
fn takes_ownership(s: String) { 
    println!("{}", s);
}

play.rust-lang.org

このように関数の引数として参照を渡してしまうと所有権が関数内に移動し元のスコープでは値を利用できなくなってしまいます。

これを回避する直感的な方法としては戻り値として値を返すことで所有権を返却する方法があります。

fn main() {
    let mut s = String::from("hello");
    s = takes_and_return_ownership(s);
    println!("{}", s);  // 所有権が返ってきた！！
}
fn takes_and_return_ownership(s: String) -> String {
    println!("{}", s);
    s
}

play.rust-lang.org

この方法で対処はできますが、記述が冗長になってしまい所有権の移動が複数だったり所有権の返却以外にも返り値がある場合に関数の目的が読み取りづらくなってしまいます。

この問題を解決するためRustでは「参照と借用」という機能を用意しています。

参照と借用

「参照」とは所有権を移動させずに値へアクセス可能な変数を作成する機能で、以下のように固名に & をつける形で定義します。

fn main() {
    let s = String::from("hello");
    takes_reference(&s);
    println!("{}", s);  // 所有権が移ってない!!
}
fn takes_reference(s: &String) {
    println!("{}", s);
}

play.rust-lang.org

また、関数の引数に参照を取ることを「借用」と呼びます。

可変な参照

& での参照定義は不変な参照で借用先での変更が制限されています。代えて &mut をつけることで可変な参照を取得することができます。

fn main() {
    let mut s = String::from("hello");
    modify_reference(&mut s);
    println!("{}", s);  // 所有権が移ってないし変更されてる!!
}
fn modify_reference(s: &mut String) {
    s.push_str(", world")
}

play.rust-lang.org

可変な参照を利用する場合、その値も mut をつけて可変な変数として定義する必要があります。

可変な参照は便利な反面、Rustでは以下の制限が設定されています。

可変な参照は（可変不変問わず）他の参照と同時に利用できない。
可変な参照を利用中は所有者による値の変更が行えない。

例えば以下のコードではコンパイルエラーが起きてしまいます。

fn main() {
    let mut s = String::from("hello");
    let r1 = &s;
    let r2 = &mut s;  // 不変な参照を取得しているので可変な参照は利用できない!!
    println!("{}, {}", r1, r2);
}

play.rust-lang.org

error[E0502]: cannot borrow `s` as mutable because it is also borrowed as immutable
 --> src/main.rs:4:14
  |
3 |     let r1 = &s;
  |              -- immutable borrow occurs here
4 |     let r2 = &mut s;  // 不変な参照を取得しているので可変な参照は利用できない!!
  |              ^^^^^^ mutable borrow occurs here
5 |     println!("{}, {}", r1, r2);
  |                        -- immutable borrow later used here

この制限はデータの競合をコンパイル時に防ぐためで、