.NET の配列サイズの話

.NET の配列サイズの上限についての悩みは、以前から何度も目にしてきました。

.NET では、配列、コレクション、Span、そして関連する多くの API が 32 ビットの長さとインデックスを前提にしています。64 ビット配列を求める長い issue も GitHub にありましたが、ランタイムや既存コードへの影響が大きすぎるため、最終的には "won't fix" として閉じられました。

この問題に対してよく見るやり方は、大きく二つです。非マネージドメモリを確保してクラスで包むか、ジャグ配列で大きな配列のように扱うかです。どちらも用途によっては使えますが、それぞれに少しずつ扱いづらさがあります。

手動のメモリ管理は気を使いますし、素直に扱えるのは基本的にアンマネージドなデータです。string や object のような参照型はこの手法には向きません。ジャグ配列なら非マネージドメモリは避けられますが、中身は結局複数の配列です。内側の配列サイズを管理し、セグメント境界をまたぐアクセスを考え、連続したメモリ領域を期待する API と組み合わせるときにも余計な手間が出ます。

そこで、自分で作ってみることにしました。やるなら、次の条件を満たしたいところです。

20 億個を超える要素を保持でき、それでも一つのインデックスでアクセスできる
インデックスはアーキテクチャ依存。32 ビット環境では通常の配列上限に留まり、64 ビット環境ではより大きくできる
string や object のような参照型をサポート
ジャグ配列ではなく、一つの連続したマネージドな割り当てとして持つ
GC で管理
NativeAOT でも動く

最初の発想

.NET で普通に使う一次元で 0 始まりの配列は SZArray、つまり T[] です。この配列の長さは int サイズに制限されています。これをそのまま広げようとすると、GC、JIT、型システム、リフレクション、基本クラスライブラリの広い範囲に手を入れることになります。

ここで少し見方を変えると、この制限が見ているのは配列の要素数です。要素の背後にあるバイト数を直接制限してはいません。byte[1024] は 1024 バイトを持ちますが、int[1024] は 4096 バイトを持ちます。配列の要素数は同じです。

最初の発想は単純です。一つの配列要素に、複数の論理要素を持たせます。

struct TwoBytes
{
    public byte A;
    public byte B;
}

20 億要素の TwoBytes 配列なら、40 億バイトを格納できます。それでも一つのマネージド配列オブジェクトであり、各要素が小さなチャンクになっただけです。

.NET 8 以降には InlineArrayAttribute があります。これを使うと、同じ型のフィールドを固定個数並べた struct を、フィールドを一つずつ手書きせずに表現できます。

using System.Runtime.CompilerServices;

[InlineArray(4)]
struct FourBytes
{
    private byte _first;
}

便利なのは、InlineArray が参照型にも使えることです。

[InlineArray(4)]
struct FourStrings
{
    private string _first;
}

ジェネリックにもできます。

[InlineArray(4)]
struct FourElements<T>
{
    private T _first;
}

これで、FourElements<T> の配列は、物理的な配列要素一つあたり四つの論理的な T を持てます。物理配列が約 20 億個のチャンクを持てるなら、幅 4 のチャンクで約 80 億個の論理要素を表現できます。

この考え方を使うと、BigArray<T> が作れます。ストレージは今でも一つのマネージド配列ですが、その配列要素型は T 自身ではなくチャンク型になることがあります。BigArray<T> は本当の論理長を別に持ち、チャンクの中のデータを一続きの T として扱います。

チャンク型を作る

一番わかりやすい実装は、すべてのチャンク長に対して型を用意することです。

[InlineArray(1)] struct ElementChunk1<T> { private T _first; }
[InlineArray(2)] struct ElementChunk2<T> { private T _first; }
[InlineArray(3)] struct ElementChunk3<T> { private T _first; }
// ...
[InlineArray(65535)] struct ElementChunk65535<T> { private T _first; }

さすがにこのままでは現実的ではなく、任意の T に対して常に有効とも限りません。

ここで効いてくるのが、ランタイムの型ロード時の制限です。配列要素になる値型は 65,535 バイトを超えられません。ある T に対して、チャンク長は次のようになります。

65535 / Unsafe.SizeOf<T>()

つまり、byte ならチャンク長 65,535 を使えます。サイズが 8 バイトの型なら 8,191、32 バイトの型なら 2,047 です。この値が決まれば、あとは欲しい論理長に対して物理チャンクがいくつ必要かを計算するだけです。

この性質のおかげで、実装はすべての整数に対応するチャンク型を持つ必要がありません。サポートする要素サイズに対して 65535 / size が返し得る値だけを用意すれば十分です。これでチャンク型の数は 65,535 から 510 まで減ります。ここまで減っても、まだ多いですね。

さらに、チャンクの struct 自体も組み合わせられます。

[InlineArray(2)]
struct ElementChunk2<T>
{
    private T _first;
}

[InlineArray(3)]
struct ElementChunk3<T>
{
    private T _first;
}

ElementChunk2<ElementChunk3<T>> は、3 個の値を持つチャンクが 2 個ある、つまり 6 個の論理 T を持つチャンクです。ElementChunk23<ElementChunk89<T>> は 2047 個の論理要素になります。byte で使える最大のチャンク長 65,535 は、次のように表せます。

ElementChunk3<ElementChunk5<ElementChunk17<ElementChunk257<byte>>>>

なぜなら：

3 * 5 * 17 * 257 = 65535

このように、チャンク型は素数長を持つ少数の基本チャンク型へ分解できます。1 から 65,535 までの必要なチャンク長を作るには、最終的に 85 個の基本チャンク型で済みます。ElementChunk2<T> から ElementChunk8191<T> までです。残りはそれらの積として表現できます。

何万ものフィールドを手書きしたり、長さごとに struct を一つずつ用意したりするより、ずっと見通しやすい形です。

チャンク型がそろえば、1 から 65,535 までの任意のチャンク型を合成できます。

var chunkSize = 65535 / Unsafe.SizeOf<T>();
var chunks = length / chunkSize + (length % chunkSize == 0 ? 0 : 1);

Array array = chunkSize switch
{
    1 => new ElementChunk1<T>[chunks],
    2 => new ElementChunk2<T>[chunks],
    3 => new ElementChunk3<T>[chunks],
    4 => new ElementChunk2<ElementChunk2<T>>[chunks],
    5 => new ElementChunk5<T>[chunks],
    6 => new ElementChunk2<ElementChunk3<T>>[chunks],
    7 => new ElementChunk7<T>[chunks],
    8 => new ElementChunk2<ElementChunk2<ElementChunk2<T>>>[chunks],
    9 => new ElementChunk3<ElementChunk3<T>>[chunks],
    10 => new ElementChunk2<ElementChunk5<T>>[chunks],
    // ...
    21845 => new ElementChunk5<ElementChunk17<ElementChunk257<T>>>[chunks],
    32767 => new ElementChunk7<ElementChunk31<ElementChunk151<T>>>[chunks],
    65535 => new ElementChunk3<ElementChunk5<ElementChunk17<ElementChunk257<T>>>>[chunks],
};

ここでの chunks が表しているのは、実際のマネージド配列の長さです。BigArray<T> が公開する論理長とは別です。たとえば論理長が 10,000 でチャンクサイズが 4,095 なら、実装は 3 個の物理チャンクを確保します。最後のチャンクは一部だけ使われ、本当の終わりは _length が覚えておきます。

この方式では、使われない領域が少し出るとはいえ、上限は小さく抑えられます。

`sizeof(T)`	`chunkSize`	最悪時の余分な要素数	最悪時の余分なバイト数
1	65535	65534	65534 B
2	32767	32766	65532 B
3	21845	21844	65532 B
4	16383	16382	65528 B
8	8191	8190	65520 B
16	4095	4094	65504 B
257	255	254	65278 B
32768+	1	0	0 B

最悪なのは、論理長がチャンクサイズの倍数より 1 だけ大きく、かつチャンクサイズが 65,535 の場合です。このとき最後のチャンクは 1 バイトしか使われません。それでも、余る量は最大でもだいたい 64 KiB です。

型ロード

次に、64 ビットランタイムで T が object だとします。参照は 8 バイトなので、有効なチャンク長は 8,191 です。

65535 / 8 = 8191

つまり ElementChunk8191<object> は有効です。一方で、ElementChunk3<ElementChunk5<ElementChunk17<ElementChunk257<object>>>> は大きすぎます。65,535 個の object 参照を含むため、配列要素になる値型だけで 8 * 65535 = 524,280 バイトになります。この型をロードしてしまうと、配列を作ろうとした時点で TypeLoadException になります。

ここでハマりやすいのは、「実行されない」ことと「ロードされない」ことが同じではない点です。構築済みのジェネリック配列型を一つのメソッド内でたくさん参照していると、JIT や型ローダーがメソッドのインポートやコンパイル中に不正な組み合わせに触れてしまうことがあります。実際に割り当てたいチャンク形状ではなかったとしても、TypeLoadException が出ます。

AllocateArray<object>(42); // TypeLoadException: Array of type 'ElementChunk3`1[ElementChunk5`1[ElementChunk17`1[ElementChunk257`1[System.__Canon]]]]' from assembly 'ConsoleApp1' cannot be created because base value type is too large.

Array AllocateArray<T>(int length)
{
    if (length <= 8191)
        return new ElementChunk8191<T>[length];
    else
        return new ElementChunk3<ElementChunk5<ElementChunk17<ElementChunk257<T>>>>[length];
}

そこで、実際の割り当てを、分岐が選ばれた後まで遅らせます。割り当てパスでは、まず T に対して有効なチャンク長を計算し、そのチャンク長に対応する割り当て処理を switch から取り出し、それだけを呼びます。

実装はチャンク長に対する switch になっています。各分岐は、ちょうど一つのチャンク型だけを割り当てる static ラムダを返します。

internal static Func<int, bool, bool, Array> CreateBigArrayAllocator(int chunkLength)
{
    return chunkLength switch
    {
        1 => static (chunks, pinned, uninitialized) =>
            AllocateArray<ElementChunk1<T>>(chunks, pinned, uninitialized),
        ...,
        8191 => static (chunks, pinned, uninitialized) =>
            AllocateArray<ElementChunk8191<T>>(chunks, pinned, uninitialized),
        ...,
        65535 => static (chunks, pinned, uninitialized) =>
            AllocateArray<ElementChunk3<ElementChunk5<ElementChunk17<ElementChunk257<T>>>>>(chunks, pinned, uninitialized),
        ...,
        _ => throw new UnreachableException(),
    };
}

実際の switch には 510 個の case がありますが、ポイントは形です。割り当てはラムダの内側にあり、割り当て用の補助メソッドは NoInlining です。

[MethodImpl(MethodImplOptions.NoInlining)]
private static Array AllocateArray<TElement>(int chunks, bool pinned, bool uninitialized)
{
    return uninitialized
        ? GC.AllocateUninitializedArray<TElement>(chunks, pinned)
        : GC.AllocateArray<TElement>(chunks, pinned);
}

この一段階の遅延がよく効きます。選ばれなかったチャンク配列型が先にロードされることを防いでくれます。実際の Unsafe.SizeOf<T>() に合うチャンク形状だけが実体化されます。JIT は実際に作られたラムダの先にあるメソッドだけをコンパイルするからです。object なら 8191 分岐を選び、ElementChunk8191<object>[] を作ります。65535 分岐は byte などのために残りますが、object の経路ではロードされません。

BigArray

チャンクの仕組みができると、BigArray<T> 本体は意外と小さくできます。

保持するフィールドは二つだけです。

internal readonly Array _storage;
internal readonly nint _length;

通常サイズでは ElementChunk1<T>[] を割り当てます。これは普通の T[] に近いレイアウトを、薄く一枚包んだようなものです。より大きな長さではチャンク長を計算し、選ばれたチャンク型の配列を割り当て、論理長を nint として記録します。

_storage が Array 型なのはそのためです。実際のランタイム型は T によって変わります。ElementChunk1<T>[] かもしれませんし、ElementChunk8191<T>[] かもしれませんし、ElementChunk3<ElementChunk5<ElementChunk17<ElementChunk257<T>>>>[] のような合成チャンク型かもしれません。

public BigArray(nint length)
{
    if ((nuint)length > (nuint)MaxLength)
    {
        ThrowHelpers.ThrowOutOfRange(nameof(length));
    }

    if (length <= Array.MaxLength)
    {
        _storage = new ElementChunk1<T>[length];
    }
    else
    {
        _storage = CreateBigArraySlow(length);
    }

    _length = length;
}

そしてインデクサーは、アクセスのたびにチャンクサイズで割る必要がありません。ストレージは一つのマネージド配列で、そのデータ領域にはチャンク struct が連続して並び、各チャンクの中に要素がインラインに入っています。そのため、最初の論理 T への参照を取って、そこから参照を進めるだけでアクセスできます。

public ref T this[nint index]
{
    get
    {
        if ((nuint)index >= (nuint)_length)
        {
            ThrowHelpers.ThrowOutOfRange(nameof(index));
        }

        return ref Unsafe.Add(ref GetDataReference(), index);
    }
}

ここで使っている Unsafe は、実装の内側だけの話です。公開 API の入力は先に検証されます。そのうえで参照の加算を使うことで、論理アクセスごとに通常の配列境界チェックをもう一度走らせずに済ませています。index、length、slice が範囲外なら、この経路に入る前に失敗します。公開 API としての安全性を保ちながら、実装はできるだけ速い形にしています。

データ参照は、配列データの先頭を T として解釈し直して取得します。

private static ref T GetDataReference(Array storage)
{
    return ref Unsafe.As<byte, T>(ref MemoryMarshal.GetArrayDataReference(storage));
}

だからこそ、連続ストレージであることが重要です。最初のデータ参照が取れた後は、Unsafe.Add(ref first, index) が index 個の論理 T だけ進みます。チャンクの境界を越えても、同じ配列データ領域を前へ進んでいるだけです。ジャグ配列ラッパーのように、アクセスごとに除算と剰余を計算する必要はありません。一つのマネージド配列オブジェクトを、より大きな論理シーケンスとして見ているだけです。

最大長はアーキテクチャ依存です。

public static nint MaxLength =>
    nint.Size == 4 ? Array.MaxLength : GetChunkLength() * (nint)Array.MaxLength;

32 ビットランタイムでは、nint 自体がそれ以上のインデックス空間を表現できないため、BigArray<T> は通常の配列上限に留まります。

64 ビットランタイムでは、最大長はチャンクサイズに応じて伸びます。byte ならおおよそ Array.MaxLength * 65535、64 ビットランタイム上の long や object 参照ならおおよそ Array.MaxLength * 8191 です。byte の場合、理論上は 128 TiB 近い配列を表現できます。正確にはバイナリ単位で 127.998 TiB です。もちろんこれは理論上限なので、実際に割り当てるにはその分のメモリが必要です。

BigSpan と BigMemory

データを所有する型だけではまだ足りません。普通の .NET コードでは、配列はプログラミングモデルの一部にすぎません。ビューを渡すために Span<T>、ReadOnlySpan<T>、Memory<T>、ReadOnlyMemory<T> も使います。

BigSpan<T> は、大きな連続領域に対する、スタック上でしか使えないビューです。

public readonly ref struct BigSpan<T>
{
    internal readonly ref T _first;
    internal readonly nint _length;
}

形は Span<T> と同じです。開始位置への参照と長さを持ちます。違いは、長さが nint で、インデックスにも nint を使うことです。Span<T> と同じく、BigSpan<T> は割り当てを所有しません。通常は BigArray<T> や BigMemory<T> など、別のオブジェクトが保持しているメモリを見るだけです。

BigArray<byte> buffer = new((nint)Array.MaxLength + 1024);
BigSpan<byte> span = buffer.AsBigSpan();

span[Array.MaxLength] = 42;

BigMemory<T> と BigReadOnlyMemory<T> は、フィールドに保存したり戻り値にしたりできるビューです。元になるマネージド配列、開始オフセット、長さを持ちます。

internal readonly Array? _storage;
internal readonly nint _start;
internal readonly nint _length;

高速な参照アクセスが必要なときは、Span プロパティから BigSpan<T> または BigReadOnlySpan<T> を作ります。BigMemory<T> は _storage に元のマネージド配列を保持するので、フィールドに保存したりメソッドから返したりしても、GC はそのストレージを追跡できます。

BigMemory<byte> page = buffer.AsBigMemory(1024, 4096);
page.Span.Fill(0);

API はできるだけ普段の Span/Memory の使い方に寄せています。スライス、コピー、検索、ソート、trim、split、ToArray、ToBigArray、読み取り専用変換などです。実装内で Span<T> や ReadOnlySpan<T> しか受け取らない BCL API を呼ぶ必要がある場合は、int に収まる範囲に分けて処理します。

既存 API と組み合わせたいときには普通の Span<T> の範囲を取り出せます：

nint offset = (nint)5_000_000_000L;
Span<byte> window = buffer.AsSpan(offset, length: 4096);

割り当て API

一番単純な割り当て方法はコンストラクターです。

nint length = (nint)10_000_000_000L;
BigArray<byte> buffer = new(length);

ただ、.NET の配列には明示的な GC 割り当て用のヘルパーもあります。そこで同じような API を用意しました。

nint length = (nint)10_000_000_000L;

BigArray<byte> zeroed = GC.AllocateBigArray<byte>(length);
BigArray<byte> scratch = GC.AllocateUninitializedBigArray<byte>(length);
BigArray<byte> pinned = GC.AllocateBigArray<byte>(length, pinned: true);

これにより、ゼロ初期化するか、未初期化でよいか、pinned にするかを選べます。pinned は、アンマネージドコードへポインターを渡したい相互運用の場面で便利です。未初期化割り当ては、すぐに全体を上書きするためゼロ初期化が不要な性能重視の場面、とくに大きな割り当てで役に立ちます。

ストレージ自体はマネージドなままです。T が参照を含む場合でも、GC はその参照を理解できます。実体が、参照を含む値型の配列だからです。T がアンマネージド型なら、必要に応じて pinning 向け API も使えます。

おわりに

BigArray<T>、BigSpan<T>、BigMemory<T> によって、巨大な連続マネージドメモリを扱えるようになります。

巨大な配列を気軽に使うのは、一般的にはおすすめしません。GC の負担は増えますし、ランダムアクセスのパターンによっては小さな配列より遅くなることもあります。それでも、大きな連続データをどうしても扱う必要がある場面はあります。そのような場面に対して、これらの型はマネージドで、できるだけ自然に扱える選択肢を提供します。性能も大事ですが、必要なメモリをそもそも確保できなければ、その先の話は始まりません。

ソースコードは GitHub に公開しています。試してみたい方は、ぜひ NuGet からパッケージを導入して使ってみてください。