【C#】配列、stringの内部実装とSpan<T>のありがたみ

## はじめに
C#で、組み込み型[^1]にできてユーザー定義型ではできないことの一つに可変長の型の作成があります。
つまり、配列型(`T[]`)と文字列型(`string`)は可変長の参照型という、特別扱いを受ける型なのです。
そこで、これらの型がメモリ上にどのように配置されるのかについて調べてみました。

## 調査

ポインタを用いて、`string`と`byte[]`のメモリ上での配置のされ方を実際に調べます。.NET6で実際に調べた結果ですので、すべての環境でこのようになることが保障されているわけではありません。ご了承ください。C#では参照型へのポインタは`unsafe`コンテキストでも禁止されていますが、`Unsafe`クラス(`System.Runtime.CompilerServices`名前空間)にあるメソッド群(`Unsafe.As`や`Unsafe.AsPointer`)を駆使すると、強引にポインタ化できます。[^2]


### stringの内部実装

#### 64bitの場合
(64bit OS , 64bit CPU , コンソールアプリケーション , x64ビルド)

| 開始アドレス | 終了アドレス | 長さ | 内容 |
|:-:|:-:|:-:|:-:|:-:|
| 0 | 7 | 8 | 型情報 |
| 8 | 11 | 4 | 文字列長(Int32) |
| 12 | 可変 | 文字数*2 | 文字データ(UTF-16) |
| 終端 |  | 2 | NULL文字 |

このようになっています。一般の`string`型への参照が指し示すアドレスを0として、相対値で表記しています。
`fixed(char* ptr = {string})`のようにして得た`char*`が指し示すのは文字データの開始アドレス、12ですので注意してください。
型情報は、`RuntimeType`の`RuntimeTypeHandle` [(ドキュメント)]( https://docs.microsoft.com/ja-jp/dotnet/api/system.runtimetypehandle?view=net-6.0 ) を参照して得られるものと同じ値で、仮想関数テーブルへのアドレスのようです。この値は、ボックス化された値型を含めヒープ上に存在するすべての型に共通して存在します。

#### 32bitの場合
(64bit OS , 64bit CPU , コンソールアプリケーション , x86ビルド)

| 開始アドレス | 終了アドレス | 長さ | 内容 |
|:-:|:-:|:-:|:-:|:-:|
| 0 | 3 | 8 | 型情報 |
| 4 | 7 | 4 | 文字列長(Int32) |
| 8 | 可変 | 文字数*2 | 文字データ(UTF-16) |
| 終端 |  | 2 | NULL文字 |

このようになっています。型情報はそれ自体ポインタなので、実行環境のポインタのサイズによりレイアウトが変わってしまうようです。

### WebAssemblyの場合

64bitと同様です。Wasmでは`IntPtr`の大きさが4byteなので、少し不思議な感じです。

### 配列の内部実装

#### 64bit nativeの場合
(64bit OS , 64bit CPU , コンソールアプリケーション , x64ビルド)

| 開始アドレス | 終了アドレス | 長さ | 内容 |
|:-:|:-:|:-:|:-:|:-:|
| 0 | 7 | 8 | 型情報 |
| 8 | 11 | 4 | 配列長(Int32) |
| 12 | 15 | 4 | 未使用領域 |
| 16 | 可変 | 配列長*sizeof(T) | 生データ |

配列はこのような構造になっています。生データのレイアウトを8の倍数に合わせるように未使用領域が入っているのだと思われます。
`fixed`して得られるアドレスはやはり生データの先頭アドレスであるので注意してください。この場合は16ずれます。

#### 32bit nativeの場合
(64bit OS , 64bit CPU , コンソールアプリケーション , x86ビルド)

| 開始アドレス | 終了アドレス | 長さ | 内容 |
|:-:|:-:|:-:|:-:|:-:|
| 0 | 3 | 4 | 型情報 |
| 4| 7 | 4 | 配列長(Int32) |
| 8 | 可変 | 配列長*sizeof(T) | 生データ |
型情報自体がポインタなので、全体的に小さくなりました。

#### WebAssemblyの場合
(64bit OS , 64bit CPU , WebAssembly , AOTなし)

やはり64bitのときと同じレイアウトです。0ばっかり入ってすっかすかなレイアウトになります。

<details><summary>検証に使用したコード</summary><div>
`byte[]`を調べるコードですが、全く同様に他の参照型も調べられます。

```cs
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;

unsafe
{
    Console.WriteLine($"IntPtr:{IntPtr.Size}");
    byte[] array = new byte[] { 1, 2, 3, 4, 5 };
    var pointer = Unsafe.AsPointer(ref array);
    var arrayAddress = *(IntPtr*)pointer;
    var arrayFirst = (*(Hoge*)arrayAddress.ToPointer());
    Console.WriteLine($"===trace array layout==={Environment.NewLine}{arrayFirst.ToString()}");
}

[StructLayout(LayoutKind.Sequential)]
struct Hoge
{
    long field1;
    long field2;
    long field3; 
    long field4;

    public override string ToString()
    {
        return $"{field1.ToString("x16")}{Environment.NewLine}{field2.ToString("x16")}{Environment.NewLine}{field3.ToString("x16")}{Environment.NewLine}{field4.ToString("x16")}";
    }
}
```

</div></details>

<details><summary>生データ</summary><div>
little-endianなことに注意して読んで下さい。

```plaintext:64bit-native
IntPtr:8
===trace array layout===
00007ff7b660fd50
0000000000000005
0000000504030201
0000000000000000
```

```plaintext:32bit-native
IntPtr:4
===trace array layout===
0000000508a4d798
0000000504030201
0ab273cc00000000
0000000000000000
```

```plaintext:wasm
IntPtr:4
===trace array layout===
0000000002e29d00
0000000500000000
0000000504030201
0000000000000000
```

</div></details>

## `string`は`char[]`でないし、`char[]`は`string`でない

`string`と`char[]`の相互変換ができたらいいと思ったことは一度くらいはあるでしょう。もちろん値をすべてコピーすれば可能ですが、コピーなしでできるでしょうか？

<details><summary>コピーなし再解釈の手法</summary><div>
`unsafe.As`メソッドは、C#の型システムを破壊し、低レベルで型の解釈を変更します。メモリ上には何も手を加えず、単にC#上での型解釈だけが変わります(いったん`void*`にキャストしてから目的の型のポインタにキャストするイメージ)。メモリレイアウトが厳密に一致していれば、これでコピーなしで変換ができます。参照型を扱う場合は型情報の書き換えも必要です(超アンセーフ)。
</div></details>

もし`string`を`char[]`に再解釈したとすると、`string`と`char[]`では奇遇にも長さの表現が同じなので、長さは正しく認識されます。しかし、32bit環境以外では`string`にはない未使用領域が`char[]`あるため、先頭の2文字は認識されません。そして、終端のnull文字とはみ出して2バイト分(**!未定義動作**)が末尾に追加されます。

逆もまたしかりで、`char[]`を`string`として解釈すると少なくとも意図したとおりにはなりません(はみだしはしないので幾分か安全)。やはり、`string`と`char[]`の相互変換ではコピーが避けられないのです。

## `byte[]`はバイナリを抽象化しない

結局、配列とは、型情報・長さ・未使用領域・生データが一列に並んだ特殊なデータです。例えば`byte[]`はバイナリを含みますが、任意のバイナリデータは`byte[]`ではありません。文字列も同様に、任意のUTF-16の文字データの並びは`string`ではないのです。これはパフォーマンスが必要な場面では足かせになりうることは先ほど見た通りでしょう(必要なさそうなコピーを強いられる)。

## 解決できる型を作ろう
型情報と長さを生データと一緒に並べるという規約により不都合が生じたのですから、これらを分離可能にすれば解決できます。型情報を並べるというのも今どきの実装でないので、型情報はジェネリック型引数として持つ実装にしましょう。パフォーマンス向上のためにこの新しい型は構造体にします。

```cs
public unsafe struct Hoge<T>
{
    private void* ptr; //生データへのポインタ
    private int length; //要素の長さ
}
```

## そうして、`Span<T>`が再発明された。
出来上がった新しい型、それは(ほぼ)`Span<T>`だった。実際には`Span<T>`はマネージドな型になるように、`void*`は使っていませんし`ref`制約が入りますが、そっくりです。
`Span<T>`は、高価なコピーコストをかけることなく、任意の生データを配列かのように扱うことができる、分離構造の型です。`char[]`も`string`も`ReadOnlySpan<char>`にできますし、その部分文字列も`ReadOnlySpan<T>`にできます。もちろんこの変換は0コストに近いです。


[^1]: C#での組み込み型の定義は様々ですが、ここではC#で専用の構文/キーワードを持つ型と、IL上専用命令を持つ型を組み込み型としています。

[^2]: GCが発生し、コンパクションが走ると未定義動作になるので実験以外では行ってはいけません。