借り初めのひみつきち

仮ブログです。

Rust の Null Pointer Optimization

古き良き C 言語では NULL ポインターがよく使われましたが、 NULL の発明者は10億ドルを超える莫大な経済損失を引き起こしたとのちに後悔しました。 モダンな言語は NULL に対する安全性を担保する仕組みを持っています。

Rust では Null 安全性のために Option<T> という型をよく使います。

Option<T>

Option<T> は、 NULL のような値を使わずに値が存在する場合と存在しない場合を明確に区別するために使います。 なぜこれで Null 安全性を確保できるかというと、 Option<T>T は明確に別の型になっているので、値が Null かどうか検証されてない状況でコードが動いてしまう危険な状況を回避できます。

Option<T> の実体は以下のような単なる enum です。

pub enum Option<T> {
    None,
    Some(T),
}

Option<usize> の実際のメモリ配置を考えてみると、 NoneSome を判別するための usize 値、 Some(v) の場合の値 v の2つの usize 値が必要です。

すべての Option<T> でこのようなメモリ配置を採用するととても嵩張ってしまいますが、実は多くの場合この配置を使いません。 それが Null Pointer Optimization と呼ばれている最適化です。

Null Pointer Optimization

Rust では有効な参照、 NonNull<T>、あるいは NonZeroUsize のような型は絶対に Null あるいは 0 の値を取りません。 これらの値を Option<T> でラッピングした場合、実際のメモリ上では Some(v) の場合は元の値そのまま、 None の場合は値 0 を使います。 NoneSome の判別は値が 0 かどうかで判別できますし、 Some(v) だった場合は元の値をそのままアンラップで取り出せます。

内部でこのような最適化を行うことで、 Option<T> は実際のメモリ上の値は T と同じ領域しか使わないように節約しながら Null 安全性を担保することができます。

なお、この最適化は実際には Option に限定されるわけではなくいくつかの条件を満たした他の enum でも同様の最適化が行われるようです。

という事までは以前から知っていました。

Option<char> の場合

Option<char> の場合を考えてみます。

char 型は任意の Unicode コードポイントリテラルなので 0 (U+00000) になり得ます。 一方、現行の UnicodeU+10FFFF までが有効なコードポイントです。

つまり、 char 型は 0x0000_0000 〜 0x0010_FFFF までの範囲を取ることができ、 0x0011_0000 〜 0xFFFF_FFFF の範囲の値にはなることができません。

実際に Rust で Option<char> を使ったコードをビルドして出力バイナリをみていたところ、 1114112 という値と比較する処理が見つかりました。 1114112 というのは 0x0011_0000 のことを指しています。

つまり、 Option<char> では char 型として不正な値の 0x0011_0000 を None の代わりに使うことで Null Pointer Optimization と同じような最適化をしていることがわかりました。

いかがだったでしょうか?

Rust でよく使われる Option<T> には追加のリソースをほとんど使わずに Null 安全性を担保するための高度が仕組みがあることがわかりましたが、 Option<char> にも同様の少しトリッキーな最適化がされていることもわかりました。