レイアウト

さて、レイアウトについて振り出しに戻りましょう。

永続リストについて最も重要なのは、リストの末尾を基本的に無料で操作できるということです。

たとえば、永続リストでは次のようなワークロードは珍しくありません。

list1 = A -> B -> C -> D
list2 = tail(list1) = B -> C -> D
list3 = push(list2, X) = X -> B -> C -> D

しかし、最終的にはメモリが次のようになっていてほしいわけです。

list1 -> A ---+
              |
              v
list2 ------> B -> C -> D
              ^
              |
list3 -> X ---+

これは Box ではうまくいきません。なぜなら、B の所有権は共有されているからです。誰がそれを解放すべきでしょうか？ list2 を drop したら、B は解放されるのでしょうか？ Box なら当然そうなると期待するはずです！

関数型言語 — そして実際にはほとんどすべての他の言語 — は、 ガベージコレクションを使うことでこれを回避しています。ガベージコレクションの魔法があれば、 B は誰もそれを見なくなった後で初めて解放されます。やったね！

Rust には、これらの言語が持つようなガベージコレクタはありません。それらはトレーシング GC を持っており、実行時にそこら中にあるすべてのメモリを掘り進めて、何がガベージなのかを自動的に判断します。一方、現在の Rust にあるのは 参照カウントだけです。参照カウントは非常に単純な GC と考えることができます。多くのワークロードでは、トレーシングコレクタよりもスループットが大幅に低く、循環を作れてしまうと完全に破綻します。でもまあ、これしかないんです！ありがたいことに、今回のユースケースでは循環に遭遇することは決してありません（自分で証明してみても構いません — 私は絶対にやりません）。

では、参照カウントによるガベージコレクションはどう行うのでしょうか？ Rc です！ Rc は Box とよく似ていますが、複製でき、そのメモリは、それから派生したすべての Rc が drop されたときにのみ解放されます。残念ながら、この柔軟性には深刻な代償があります。内部に対して共有参照しか取得できないのです。これはつまり、リストの 1 つから実際にデータを取り出すことも、それらを変更することもできないということです。

では、レイアウトはどのようになるのでしょうか？以前はこうでした。

pub struct List<T> {
    head: Link<T>,
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

Box を Rc に変えるだけでよいのでしょうか？

// third.rs 内

pub struct List<T> {
    head: Link<T>,
}

type Link<T> = Option<Rc<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

cargo build

error[E0412]: cannot find type `Rc` in this scope
 --> src/third.rs:5:23
  |
5 | type Link<T> = Option<Rc<Node<T>>>;
  |                       ^^ not found in this scope
help: possible candidate is found in another module, you can import it into scope
  |
1 | use std::rc::Rc;
  |

おっと、痛烈な一撃です。可変リストで使っていたものとは違い、Rc はあまりにも冴えないので、すべての Rust プログラムに暗黙的にインポートされることすらありません。 なんて負け犬なんだ。

use std::rc::Rc;

cargo build

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

warning: field is never used: `elem`
  --> src/third.rs:10:5
   |
10 |     elem: T,
   |     ^^^^^^^

warning: field is never used: `next`
  --> src/third.rs:11:5
   |
11 |     next: Link<T>,
   |     ^^^^^^^^^^^^^

問題なさそうです。Rust で書くのは相変わらず完全に取るに足りない作業です。 Box を Rc に検索置換するだけで、それで終わりにできるに違いありません！

…

いいえ。いいえ、できません。

Keyboard shortcuts

Learning Rust With Entirely Too Many Linked Lists 日本語版

レイアウト