Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

基本的なデータレイアウト

さて、連結リストとは何でしょうか？基本的には、ヒープ上のデータの断片（カーネルの人たちは黙っていてください！）が、順番に互いを指しているものです。連結リストは、手続き型プログラマーが絶対に手を出すべきではないものであり、関数型プログラマーがあらゆることに使うものです。であれば、連結リストの定義は関数型プログラマーに尋ねるのが公平でしょう。おそらく、次のような定義を示してくれるはずです。

List a = Empty | Elem a (List a)

これはおおよそ「List は Empty であるか、Element の後に List が続くものである」と読めます。これは 直和型 として表現された再帰的な定義です。直和型とは、「異なる値を持つことができ、その値が異なる型である場合もある型」を表す気取った名前です。Rust は直和型を enum と呼びます！C 風の言語から来た人にとっては、これはまさに皆さんが知っていて大好きな enum ですが、さらに強化されたものです。では、この関数型の定義を Rust に写してみましょう！

今のところは、話を簡単にするためにジェネリクスを避けます。符号付き 32 ビット整数の格納だけをサポートします。

// first.rs 内

// pub は、このモジュールの外部から List を使えるようにしたいことを示します
pub enum List {
    Empty,
    Elem(i32, List),
}

ふぅ、もう手一杯です。とりあえずこれをコンパイルしてみましょう。

> cargo build

error[E0072]: recursive type `first::List` has infinite size
 --> src/first.rs:4:1
  |
4 | pub enum List {
  | ^^^^^^^^^^^^^ recursive type has infinite size
5 |     Empty,
6 |     Elem(i32, List),
  |               ---- recursive without indirection
  |
  = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `first::List` representable

さて。皆さんはどうかわかりませんが、私は確かに関数型プログラミングコミュニティに裏切られた気分です。

実際にエラーメッセージを確認してみると（裏切られた件を乗り越えた後で）、rustc はこの問題を解決する方法を正確に教えてくれていることがわかります。

insert indirection (e.g., a Box, Rc, or &) at some point to make first::List representable

なるほど、box。それは何でしょう？rust box でググってみましょう……

std::boxed::Box - Rust

どれどれ……

pub struct Box<T>(_);

ヒープ割り当てのためのポインター型。 詳細については、モジュールレベルのドキュメントを参照してください。

リンクをクリック

Box<T> は、気軽に「box」と呼ばれ、Rust における最も単純なヒープ割り当ての形を提供します。Box はこの割り当ての所有権を提供し、スコープを抜けるとその内容を drop します。

例

box の作成:

let x = Box::new(5);

再帰的なデータ構造の作成:

#![allow(unused)]
fn main() {
#[derive(Debug)]
enum List<T> {
    Cons(T, Box<List<T>>),
    Nil,
}
}
fn main() {
    let list: List<i32> = List::Cons(1, Box::new(List::Cons(2, Box::new(List::Nil))));
    println!("{:?}", list);
}

これは Cons(1, Box(Cons(2, Box(Nil)))) を出力します。

再帰的な構造は boxed にする必要があります。なぜなら、Cons の定義が次のようになっていると、

Cons(T, List<T>),

動作しないからです。これは、List のサイズがリスト内の要素数に依存するため、Cons にどれだけのメモリを割り当てればよいかわからないからです。定義されたサイズを持つ Box を導入することで、Cons がどれだけ大きくある必要があるかがわかります。

うわ、ええと。これは私が今まで見た中で、おそらく最も関連性が高く、役に立つドキュメントです。ドキュメントの最初にある内容が、文字どおり 私たちが書こうとしているもの、それが動作しなかった理由、そして修正方法そのもの です。

いやあ、ドキュメント最高ですね。

では、そのようにしてみましょう。

pub enum List {
    Empty,
    Elem(i32, Box<List>),
}
> cargo build

   Finished dev [unoptimized + debuginfo] target(s) in 0.22s

やった、ビルドできました！

……しかし、これは実際には List の定義としてかなり愚かです。理由はいくつかあります。

2 つの要素を持つリストを考えてみましょう。

[] = Stack
() = Heap

[Elem A, ptr] -> (Elem B, ptr) -> (Empty, *junk*)

重要な問題が 2 つあります。

  • 「私は実際には Node ではありません」と言っているだけのノードを割り当てている
  • ノードの 1 つがまったくヒープ割り当てされていない

表面的には、この 2 つは互いに打ち消し合っているように見えます。余分なノードをヒープ割り当てしていますが、ノードの 1 つはまったくヒープ割り当てする必要がありません。しかし、リストの次のような潜在的なレイアウトを考えてみてください。

[ptr] -> (Elem A, ptr) -> (Elem B, *null*)

このレイアウトでは、ノードを常にヒープ割り当てするようになります。重要な違いは、最初のレイアウトにあった junk が存在しないことです。この junk とは何でしょうか？それを理解するには、enum がメモリ上でどのようにレイアウトされるかを見る必要があります。

一般に、次のような enum があるとします。

enum Foo {
    D1(T1),
    D2(T2),
    ...
    Dn(Tn),
}

Foo は、それが enum のどの バリアント を表しているか（D1、D2、.. Dn）を示すために、何らかの整数を格納する必要があります。これが enum の タグ です。また、T1、T2、.. Tn のうち 最大 のものを格納するのに十分な領域も必要になります（さらにアラインメント要件を満たすための追加領域も必要です）。

ここでの大きなポイントは、Empty が 1 ビットの情報でしかないにもかかわらず、ポインターと要素のために十分な領域を必然的に消費するということです。なぜなら、いつでも Elem になれるようにしておく必要があるからです。したがって、最初のレイアウトは、junk でいっぱいの余分な要素をヒープ割り当てし、2 つ目のレイアウトより少し多くの領域を消費します。

ノードの 1 つがまったく割り当てられていないことも、おそらく意外なことに、常に割り当てるよりも 悪い です。これは、ノードのレイアウトが 不均一 になるためです。これはノードの push や pop にはあまり目立った影響を与えませんが、リストの分割と結合には影響します。

両方のレイアウトでリストを分割することを考えてみましょう。

layout 1:

[Elem A, ptr] -> (Elem B, ptr) -> (Elem C, ptr) -> (Empty *junk*)

split off C:

[Elem A, ptr] -> (Elem B, ptr) -> (Empty *junk*)
[Elem C, ptr] -> (Empty *junk*)

layout 2:

[ptr] -> (Elem A, ptr) -> (Elem B, ptr) -> (Elem C, *null*)

split off C:

[ptr] -> (Elem A, ptr) -> (Elem B, *null*)
[ptr] -> (Elem C, *null*)

レイアウト 2 の分割では、B のポインターをスタックにコピーし、古い値を null にするだけです。レイアウト 1 も最終的には同じことをしますが、それに加えて C をヒープからスタックへコピーする必要があります。結合はその逆の手順です。

連結リストの数少ない良い点の 1 つは、要素をノード自体の中で構築でき、その後それを実際に移動することなく、リスト間で自由に入れ替えられることです。ポインターを少しいじるだけで、ものが「移動」します。レイアウト 1 はこの性質を台無しにします。

さて、レイアウト 1 が悪いということにはそれなりに納得しました。では、List をどのように書き直せばよいでしょうか？たとえば、次のようにできるかもしれません。

pub enum List {
    Empty,
    ElemThenEmpty(i32),
    ElemThenNotEmpty(i32, Box<List>),
}

これがさらに悪いアイデアに見えることを願います。特に注目すべきなのは、完全に無効な状態が存在するようになるため、ロジックが本当に複雑になることです。つまり、ElemThenNotEmpty(0, Box(Empty)) です。また、要素の割り当てが不均一であるという問題も 依然として 抱えています。 ただし、これには興味深い性質が1つあります。Empty のケースをアロケートすることを完全に避け、 ヒープアロケーションの総数を 1 つ減らします。残念ながら、 そうすることでさらに多くの空間を無駄にしてしまいます！これは、以前の レイアウトがnull ポインター最適化を活用していたためです。

以前見たように、すべての enum は、そのビットが enum のどのバリアントを 表しているのかを指定するためにタグを格納する必要があります。しかし、 次のような特別な種類の enum がある場合は:

enum Foo {
    A,
    B(ContainsANonNullPtr),
}

null ポインター最適化が働き、タグに必要な空間が不要になります。 バリアントが A の場合、enum 全体がすべて 0 に設定されます。そうでなければ、 バリアントは B です。B は非ゼロポインターを含むため、決してすべて 0 には なり得ないので、これが機能します。見事ですね！

この種の最適化が可能な他の enum や型を思いつきますか？ 実際にはたくさんあります！これが、Rust が enum のレイアウトを完全に未指定のままにしている理由です。 Rust は、もう少し複雑な enum レイアウト最適化をいくつか行ってくれますが、 null ポインターのものは間違いなく最も重要です！ これは、&、&mut、Box、Rc、Arc、Vec、そして Rust の他のいくつかの重要な型が Option に入れられてもオーバーヘッドを持たないことを意味します！ （これらの大半については、いずれ扱います。）

では、どうすれば余分なガラクタを避け、均一にアロケートし、さらにあの素晴らしい null ポインター最適化を得られるのでしょうか？要素を持つという考え方と、 別のリストをアロケートするという考え方を、もっと明確に分離する必要があります。 そのためには、もう少し C っぽく考える必要があります。つまり struct です！

enum が複数の値のうち1つを含められる型を宣言できるのに対して、 struct は複数の値を同時に含む型を宣言できます。List を 2 つの型に分けましょう。 List と Node です。

以前と同じように、List は Empty であるか、要素の後に別の List が続くものです。 「要素の後に別の List が続く」ケースをまったく別の型で表現することで、 Box をより最適な位置に持ち上げることができます:

struct Node {
    elem: i32,
    next: List,
}

pub enum List {
    Empty,
    More(Box<Node>),
}

優先事項を確認しましょう:

  • リストの末尾が余分なガラクタをアロケートしない: チェック！
  • enum が素晴らしい null ポインター最適化形式になっている: チェック！
  • すべての要素が均一にアロケートされる: チェック！

よし！実際のところ、最初のレイアウト（公式 Rust ドキュメントで提案されているもの）が 問題を抱えていることを示すために使ったレイアウトを、まさにそのまま構築したことになります。

> cargo build

warning: private type `first::Node` in public interface (error E0446)
 --> src/first.rs:8:10
  |
8 |     More(Box<Node>),
  |          ^^^^^^^^^
  |
  = note: #[warn(private_in_public)] on by default
  = warning: this was previously accepted by the compiler but
    is being phased out; it will become a hard error in a future release!

:(

Rust がまた怒っています。私たちは List を public にしました（人々に 使えるようにしたいからです）が、Node は public にしていません。問題は、 enum の内部は完全に public であり、private な型について public に語ることは 許されないという点です。Node 全体を完全に public にすることもできますが、 一般に Rust では、実装の詳細は private に保つことが好まれます。List を struct にして、 実装の詳細を隠せるようにしましょう:

pub struct List {
    head: Link,
}

enum Link {
    Empty,
    More(Box<Node>),
}

struct Node {
    elem: i32,
    next: Link,
}

List はフィールドを 1 つだけ持つ struct なので、そのサイズはそのフィールドと同じです。 ゼロコスト抽象化、やった！

> cargo build

warning: field is never used: `head`
 --> src/first.rs:2:5
  |
2 |     head: Link,
  |     ^^^^^^^^^^
  |
  = note: #[warn(dead_code)] on by default

warning: variant is never constructed: `Empty`
 --> src/first.rs:6:5
  |
6 |     Empty,
  |     ^^^^^

warning: variant is never constructed: `More`
 --> src/first.rs:7:5
  |
7 |     More(Box<Node>),
  |     ^^^^^^^^^^^^^^^

warning: field is never used: `elem`
  --> src/first.rs:11:5
   |
11 |     elem: i32,
   |     ^^^^^^^^^

warning: field is never used: `next`
  --> src/first.rs:12:5
   |
12 |     next: Link,
   |     ^^^^^^^^^^

よし、コンパイルできました！Rust はかなり怒っています。というのも、Rust から見ると、 私たちが書いたものはすべて完全に役立たずだからです。私たちは head を一度も使っておらず、 私たちのライブラリを使う人も、それが private なので使えません。推移的に、 これは Link と Node も役立たずであることを意味します。では、それを解決しましょう！ List のためのコードをいくつか実装してみましょう！