RustのNULLポインタ最適化

概要: RustのNULLポインタ最適化について説明する。

NULLポインタ最適化とは

以下のようにポインタ型のOptionが、元のポインタと同じサイズになる最適化である。NULLをNoneに割り当てている。

fn main() {
    println!("{}", std::mem::size_of::<Box<u32>>()); // 8
    println!("{}", std::mem::size_of::<Option<Box<u32>>>()); // 8
}

non-zero typeの定義

NULLポインタ最適化は、non-zero typeをoption-like typeで包んだ場合に発生する。以下が1.17.0時点でのnon-zero typeの定義である。

  • 関数ポインタ
  • 参照 (fat pointerも含む)
  • Box<T> (fat pointerも含む)
  • NonZero<*mut T>, NonZero<*const T> (fat pointerも含む)
  • NonZero<i32> 他、組込み整数型を包んだもの
  • C-like enum であって、全てのバリアントのdiscriminantが非0であるもの
  • Univariant ADT (NonZero 以外) であって、1つ以上のフィールドがnon-zero typeをもつもの
  • サイズ1以上の固定長配列であって、要素型がnon-zero typeであるもの

ただし、

  • レイアウト決定の観点からいうC-like enumとは、1つ以上のバリアントからなり、各バリアントのフィールドの個数が0である列挙型である。discriminantはバリアントを区別するためのタグであり、構文上のC-like enum (全てのバリアントがユニットバリアントであるもの) であればdiscriminantを明示的に指定できる。
  • Univariant ADTとは、レイアウト上構造体と同様に扱われる型のことで、次のいずれかである。
    • 列挙型であって、高々1個のバリアントからなり、#[repr(C)]#[repr(u8)] (あるいは他の整数型) も指定されていないもの。ただし、C-like enumに該当する場合はそれが優先されるバグがある。 (Rust Issue #37649)
    • 構造体 (NonZero, Box以外)。
    • タプル。
    • クロージャ
  • Univariant ADTや固定長配列では、non-zero fieldの候補が複数ある場合がある。Univariant ADTでは、ソースコード順で最も若いフィールドが選択される。固定長配列では、0番目の要素が選択される。

なお、 core::nonzero::NonZeroalloc::boxed::Box もlang item (処理系により特別扱いされるアイテム) である。 NonZero のインターフェースはunstableである。

option-like typeの定義

option-like typeという用語があるわけではないが、わかりやすいのでこのように称する。option-like typeは以下のような型である。

  • 列挙型である。
  • ちょうど2個のバリアントからなる。
  • #[repr(C)]#[repr(u8)] (あるいは他の整数型) も指定されていない。
  • 一方のバリアントのフィールドが全てzero-sizedである。

このoption-like typeがさらに以下の条件を満たすとき、NULLポインタ最適化が行われる。

  • もう一方のバリアントに、non-zero typeをもつフィールドがある。 (このときそのフィールドはzero-sizedでないことに注意)

NULLポインタ最適化の実装

NULLポインタ最適化の対象になった列挙型は、Univariant ADTでないにもかかわらずdiscriminantが削除される。かわりに、発見された最も若いnon-zero fieldを(再帰的に)探し、その部分がゼロかどうかで、どちらのバリアントであるかを判断する

逆にバリアントを代入する際は、該当のフィールドにゼロを代入する。ただしARMアーキテクチャではLLVMのバグを踏まないために列挙型全体をゼロで初期化する

まとめ

Rustには、参照を直接的または間接的に含む型など、全体がゼロにはなりえない型がいくつか存在する。これらの型に1つの特別な値を付与した列挙型は、もとの型と同じデータ長で表現される。