Rustの構造体/列挙型フィールドの並べ替え

Rust

現在の安定版では無効化されているが、Rustのbeta/nightlyには構造体/列挙型フィールドの自動並べ替えが実装されている。この動作を説明する。

例

以下のようなプログラムを書くと、現在の安定版では6が表示され、beta/nightlyでは4が表示される。

use std::mem::size_of;
struct A(u8, u16, u8);

fn main() {
    println!("{}", size_of::<A>()); // 6 or 4
}

これはアラインメントと関係がある。通常 u8 は1バイト、 u16 は2バイトの境界に揃えられている必要がある。そのためこの構造体/列挙型のフィールドを宣言順に並べると、

  • u8, 1バイトパディング、 u16, u8, 1バイトパディング

となる。 (配列として並べることもあるため、最後にもパディングが必要である。)

一方、これを並び替えると、

  • u16, u8, u8

となり、アラインメントの制約を満たしつつよりコンパクトに構造体を表現することができる。

構造体/列挙型フィールドの並べ替えが発生する条件

並べ替え処理は rustc::ty::layout に書いてあるのでここを読むとわかる。

  • #[repr(C)], #[repr(packed)], #[repr(simd)], #[repr(linear)] のいずれでもない。
  • 以下のいずれかである。
    • univariantなデータ型(構造体と等価なデータ型。以前の記事で説明済み)で、要素数が2以上である。
    • 判別子つきの列挙型であり、判別子が1byteである。

構造体/列挙型フィールドの最適性条件

まず、フィールドのアラインメントが小→大→小のときのみ無駄が発生する、という性質を把握しておくとよい。例えば上の例でも u8→u16→u8の順になっている。対偶をとると以下のことが言える。

フィールドのアラインメントの前半が降順、後半が昇順に並んでいるとき、最小バイト数(フィールドのサイズの和を、アラインメントの倍数になるように切り上げた値)を達成する。

証明: まずは、全体が降順に並んでいる場合を考える。このときはパディングは構造体の末尾にしか存在しない。最後のパディングはちょうど、構造体全体が構造体のアラインメントの倍数になるように切り上げる最小限のサイズになるから、最小バイト数が達成される。

次に、一般に全体が降順→昇順の場合に、全体が降順の場合と同じサイズが達成されることを、フィールド数に関する帰納法で示す。まずフィールド数が0のときは明らかである。1つ以上のフィールドがあるとき、最初のフィールドと最後のフィールドのうち少なくとも一方が、アラインメント最大のフィールドである。

  • アラインメント最大のフィールド + 残り+パディング のとき: 「残り」の開始位置は「残り」の要求するアラインメントに沿っているため、この部分単体で考えたときの配置と一致する。帰納法の仮定よりこの部分を降順に並べ替えても同じサイズとなる。このとき全体でみても降順である。
  • 残り+パディング + アラインメント最大のフィールド のとき: これを アラインメント最大のフィールド + 残り+パディング と入れ替えてもアラインメントの制約に反しない。これにより上に帰着される。

構造体/列挙型フィールドの並べ替え順

さて、現在のbeta/nightly Rustでは先ほどの条件を満たすとき、以下のようにフィールドが並べ替えられる。

  • univariantなデータ型では、「最後の要素が !Sized になり得るかどうか」により異なる動作をする。
    • 最後の要素も必ず Sized である場合は、全ての要素が降順に並べ替えられる。
    • 最後の要素が !Sized になりえる場合は、最後以外の全ての要素が降順に並べ替えられる。
  • 判別子をもつ列挙型では、判別子を除く全ての要素が昇順に並べ替えられる。

このように、並び替えてはまずいケースが考慮されている。例えば、以下のように動作する。

macro_rules! offset_of {
    ($x:expr, $field: tt) => (
        (&$x.$field as *const _ as usize - &$x as *const _ as usize)
    )
}

struct A<X>(i8, i8, X);
struct B<X: ?Sized>(i8, i8, X);

fn main() {
    let x = A(0, 0, 0i32);
    let y = B(0, 0, 0i32);
    let z = B(0, 0, 0i16);
    // 4, 5, 0
    println!("{}, {}, {}",
        offset_of!(x, 0), offset_of!(x, 1), offset_of!(x, 2));
    // 0, 1, 4
    println!("{}, {}, {}",
        offset_of!(y, 0), offset_of!(y, 1), offset_of!(y, 2));
    // 0, 1, 2
    println!("{}, {}, {}",
        offset_of!(z, 0), offset_of!(z, 1), offset_of!(z, 2));
}

このように、同じような構造体でも、 X: Sized の有無によって配置が異なることがあり得る。

理由はもちろん、型強制やキャストによりこれを別の型に読み替える可能性があるからである。例えば上の &y や &z は、 &B<Debug> という型に変換することができる。このとき最後以外の要素は一定の位置にあってほしいから、可変長である最後の要素が途中に来るのは好ましくない。

なお、 y と z で最後の要素の位置は異なるから、この要素に統一的にアクセスするのは簡単ではない。vtableの中にサイズとアラインメントの情報があり、これを使うことでこの要素にうまくアクセスするようになっている。

列挙型ではフィールドは降順ではなく昇順に並べ替えられる。これは、構造体とは反対に、列挙型では先頭にある判別子を動かせないからである。そこで判別子以外を昇順にすることで必ず降順→昇順となり、同じく最適性が保証される。

まとめ

  • Rustの構造体/列挙型のメンバは動作や互換性に影響のない範囲内で並べ替えられることがある。
  • 現在のbeta/nightlyで採用されているアルゴリズムは最適である。アラインメントを守る配列のうちパディングが最も少なくする配置のうちの1つが得られる。