[Rust] [T; N], Vec<T>, &[T] のメモリレイアウト

思うところがあり array や `Vec<T>`, スライスのメモリレイアウトについて検証したのでまとめです. コード全体は [こちら](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=05790a7be0208f830e6bb2c714a62ad5).

# スタックの中身

## `[T; N]` の場合

array `[T; N]` のデータは __スタックにアロケートされます__. [Reference](https://doc.rust-lang.org/reference/types/array.html) のコード例のコメントの中で明示されています. これは array のサイズ `N` がコンパイル時に決定されていなければならないという要求によって可能になっています. ですから `[T; N]` を確保するとき, そのデータの実体はいきなりスタックに確保され, メモリサイズは `T` のメモリサイズの `N` 倍になります ([std](https://doc.rust-lang.org/std/mem/fn.size_of.html) 参照). 

```rust
fn main() {
    let x: [u8; 3] = [ 4, 1, 16 ];
    assert_eq!(size_of_val(&x), x.len() * size_of::<u8>()); // スタックのサイズ
}
```

ヒープにアロケートしない分アロケーションに要する時間が短い気がしますが, `N` が大きすぎるとスタックオーバーフローの可能性がありますし, そもそも `Debug` 等のトレイトは `N = 32` までしか実装されていません.

## `Box<[T; N]>` の場合

`Box` を使えば array の実体をヒープに確保することができます. 用途があまり思いつきませんが, 固定長かつ `N` が大きいという場合には有用かもしれません (`N` が違うとコンパイルエラーになって欲しい場合に特に有効でしょう).

```rust
fn main() {
    let x: Box<[u8; 3]> = Box::new([ 4, 1, 16 ]);
    assert_eq!(size_of_val(&x), size_of::<usize>()); // スタックのサイズ

    let p = &x as *const Box<[u8; 3]> as *const usize;
    println!("0x{:x}", unsafe { *p }); // スタックの中身 (ヒープのアドレス: usize)
    assert_eq!(format!("0x{:x}", unsafe{*p}), format!("{:?}", x.as_ptr()));
}
```

ここで注目すべきは, スタックに確保されるメモリは `usize` 分だけだという点です. `Box<[T; N]>` の実体はヒープにありますから, そのアドレスをスタックに積んでおけば良いという訳です. 長さ `N` はいらないのか？ と一瞬思いますが, コンパイラは型という形でそれを知っていますから, わざわざスタックにそれを書き込んでおく必要はありません. よく考えれば `[T; N]` も同じことですね.

## `Vec<T>` の場合

わざわざヒープにアロケートするのはたいていは可変長の配列が欲しいからで, これは `Vec<T>` が提供する機能です.

`Box<[T; N]>` の場合と同じく, `Vec<T>` のデータの実体はヒープにアロケートされます. 一方, `Vec<T>` がスタックに保持するデータは `Box<[T; N]>` の場合より多く, データの先頭アドレスに加えて capacity とデータの長さを保持しています. これはいずれも動的に変化し得る量ですからね. 従って `Vec<T>` がスタックに確保するのは, データを確保したヒープアドレス (`usize`), キャパシティサイズ (`usize`), 長さ (`usize`) という `usize` 3 個です.

```rust
fn main() {
    let x: Vec<u8> = { // キャパシティ 4, 長さ 3 の Vec<u8>
        let mut x = Vec::with_capacity(4);
        x.extend_from_slice(&[ 4, 1, 16 ]);
        x
    };
    assert_eq!(size_of_val(&x), 3*size_of::<usize>()); // スタックのサイズ

    let p = &x as *const Vec<u8> as *const [usize; 3];
    let stack_mem: [usize; 3] = unsafe { *p }; // スタックの中身を取得
    println!("0x{:x}", stack_mem[0]); // ヒープアドレス
    assert_eq!( stack_mem[1], x.capacity() );
    assert_eq!( stack_mem[2], x.len() );
}
```


# 参照とスライス

次に, これらのデータの参照について議論します. 

## `[T; N]` の場合

`[T; N]` への参照 `&[T; N]` は実体としては元データの先頭アドレスに過ぎません. 従ってそのサイズは `usize` に等しいです. 一般に, 参照 `&T` はポインタ型 `*const T` と同じサイズを持ちます.

```rust
fn main() {
    let x: [u8; 3] = [ 4, 1, 16 ];
    assert_eq!(size_of_val(&x), x.len() * size_of::<u8>()); // スタックのサイズ

    let p: &[u8; 3] = &x; // 実体としては usize. 中身は x の先頭アドレス.
    assert_eq!(size_of_val(&p), size_of::<usize>());
}
```

ところで, `&[T; N]` は `&[T]` に型強制できます. そして, `&[T]` は `&[T; N]` とは異なる型であり, メモリレイアウトの観点からも両者は異なるものです. 

```rust
fn main() {
    let x: [u8; 3] = [ 4, 1, 16 ];

    let p1: &[u8; 3] = &x;
    assert_eq!(size_of_val(&p1), size_of::<usize>()); // x の先頭アドレスだけを持つ

    let p2: &[u8] = &x;
    assert_eq!(size_of_val(&p2), 2*size_of::<usize>()); // これはファットポインタ

    assert_eq!(p1.as_ptr(), p2.as_ptr()); // p1 と p2 が指し示すアドレスは同じ (x の先頭アドレス)

    let p2 = &p2 as *const &[u8] as *const [usize; 2]; // p2 のスタックの内容
    let stack_mem: [usize; 2] = unsafe { *p2 };
    // 最初の `usize` はデータのアドレス (上手に比較できなかった…)
    assert_eq!(format!("0x{:x}", stack_mem[0]), format!("{:?}", p1.as_ptr())); 
    // 次の `usize` はデータの長さ
    assert_eq!(stack_mem[1], x.len());
}
```

このコードからわかるように, `&[T]` は __ファットポインタ__ (fat pointer) と呼ばれるもので, 実体としては `[usize; 2]` です. 最初の `usize` がスライス `[T]` の先頭アドレスを, 次の `usize` がスライスの長さを表します.

## `Box<[T; N]>` の場合

deref すれば当然 `[T; N]` と同じですが, しなくても結局同じです. というのも, `x` という束縛はデータの所有権を持つ点を除けば単にヒープのアドレスを保持しているだけなので.

```rust
fn main() {
    let x: Box<[u8; 3]> = Box::new([ 4, 1, 16 ]);

    let p0: &Box<[u8; 3]> = &x;
    let p1: &[u8; 3] = &*x;
    let p2: &[u8]    = &*x;
    assert_eq!(p0.as_ptr(), p1.as_ptr());
    assert_eq!(p1.as_ptr(), p2.as_ptr());
    assert_eq!(size_of_val(&p0), size_of::<usize>());
    assert_eq!(size_of_val(&p1), size_of::<usize>());
    assert_eq!(size_of_val(&p2), 2*size_of::<usize>());
}
```

## `Vec<T>` の場合

これも `Box<_>` と同じです.

```rust
fn main() {
    let x: Vec<u8> = {
        let mut x = Vec::with_capacity(4);
        x.extend_from_slice(&[ 4, 1, 16 ]);
        x
    };
    assert_eq!(size_of_val(&x), 3*size_of::<usize>()); // スタックのサイズ

    let p1: &Vec<u8> = &x;
    let p2: &[u8] = &x;
    assert_eq!(p1.as_ptr(),  x.as_ptr());
    assert_eq!(p1.as_ptr(), p2.as_ptr());
    assert_eq!(size_of_val(&p1), size_of::<usize>());
    assert_eq!(size_of_val(&p2), 2*size_of::<usize>());
}
```

# 参考文献

* [std::mem::size_of - Rust](https://doc.rust-lang.org/std/mem/fn.size_of.html)
* [[Rust] &strとStringを理解しようと思ったらsliceやmutを理解できてないことに気づいた話](https://qiita.com/yagince/items/e7474839246ced595f7a)
* [RustのSizedとfatポインタ](https://qnighy.hatenablog.com/entry/2017/03/04/131311)