
基本思路#在 .NET 中最常见的一维、从零开始的数组是 SZArray也就是 T[]。它的长度受 int 大小限制。想要直接放宽这个限制就会碰到 GC、JIT、类型系统、反射和基础类库等很多地方。但这个限制针对的是数组的元素个数而不是元素背后的字节数。byte[1024] 存 1024 字节int[1024] 存 4096 字节。它们的数组长度相同只是每个元素更大。所以第一个想法很简单让一个数组元素代表多个逻辑元素。Copystruct TwoBytes{public byte A;public byte B;}一个包含 20 亿个 TwoBytes 的数组可以存下 40 亿个字节。它仍然是一个托管数组对象只是每个元素变成了一小块。从 .NET 8 开始我们有了 InlineArrayAttribute。它可以让一个 struct 表示固定数量的重复字段而不用把每个字段都手写出来。Copyusing System.Runtime.CompilerServices;[InlineArray(4)]struct FourBytes{private byte _first;}它有一个很方便的地方InlineArray 也能用于引用类型。Copy[InlineArray(4)]struct FourStrings{private string _first;}它也能用于泛型Copy[InlineArray(4)]struct FourElements{private T _first;}这样一来一个 FourElements 数组的每个物理元素就可以容纳四个逻辑上的 T。如果物理数组本身可以有接近 20 亿个块那么四倍宽度的块就能表示接近 80 亿个逻辑元素。这就是 BigArray 的核心思路。底层仍然是一个托管数组但数组元素类型不一定是 T 本身也可能是一个块类型。BigArray 另外记录真实的逻辑长度再把这些块里的数据看成一段连续的 T。构建块类型#最直观的实现是为每一种块长度都定义一个类型Copy[InlineArray(1)] struct ElementChunk1 { private T _first; }[InlineArray(2)] struct ElementChunk2 { private T _first; }[InlineArray(3)] struct ElementChunk3 { private T _first; }// …[InlineArray(65535)] struct ElementChunk65535 { private T _first; }这显然不现实而且对任意 T 来说也不一定合法。这里有一个重要的运行时类型加载限制作为数组元素的值类型不能超过 65,535 字节。对某个 T 来说块长度是Copy65535 / Unsafe.SizeOf()所以 byte 可以使用 65,535 的块长度。大小为 8 字节的类型可以使用 8,191。大小为 32 字节的类型可以使用 2,047。确定这个值之后分配时只需要计算请求的逻辑长度需要多少个物理块。这也意味着实现不需要为每一个整数都准备一个块类型。只要覆盖 65535 / size 可能产生的那些值就够了。这样块类型数量从 65,535 降到了 510但仍然不少。更进一步块结构体本身也可以组合。Copy[InlineArray(2)]struct ElementChunk2{private T _first;}[InlineArray(3)]struct ElementChunk3{private T _first;}ElementChunk2ElementChunk3 表示 2 个包含 3 个值的块也就是 6 个逻辑 T。ElementChunk23ElementChunk89 表示 2047 个逻辑元素。byte 能使用的最大块长度也就是 65,535可以写成CopyElementChunk3ElementChunk5ElementChunk17ElementChunk257因为Copy3 * 5 * 17 * 257 65535因此我们可以只保留一组质数长度的基础块类型再通过嵌套组合出其他长度。为了覆盖 1 到 65,535 之间需要的块长度最后只需要 85 个基础块类型从 ElementChunk2 到 ElementChunk8191。其他长度都可以由这些基础长度相乘得到。这比手写几万个字段或者为每一个长度准备一个 struct 要容易维护得多。有了这些块类型之后就可以组合出 1 到 65,535 之间任意需要的块类型Copyvar chunkSize 65535 / Unsafe.SizeOf();var chunks length / chunkSize (length % chunkSize 0 ? 0 : 1);Array array chunkSize switch{1 new ElementChunk1[chunks],2 new ElementChunk2[chunks],3 new ElementChunk3[chunks],4 new ElementChunk2ElementChunk2[chunks],5 new ElementChunk5[chunks],6 new ElementChunk2ElementChunk3[chunks],7 new ElementChunk7[chunks],8 new ElementChunk2ElementChunk2ElementChunk2[chunks],9 new ElementChunk3ElementChunk3[chunks],10 new ElementChunk2ElementChunk5[chunks],// …21845 new ElementChunk5ElementChunk17ElementChunk257[chunks],32767 new ElementChunk7ElementChunk31ElementChunk151[chunks],65535 new ElementChunk3ElementChunk5ElementChunk17ElementChunk257[chunks],};这里的 chunks 表示真实托管数组的长度和 BigArray 暴露出来的逻辑长度不同。比如逻辑长度是 10,000而块大小是 4,095那么实现会分配 3 个物理块。最后一个块只用到一部分真正的逻辑终点由 _length 记录。这种做法会不会多分配一些没有用到的空间答案是会但非常小。sizeof(T) chunkSize 最坏情况多出的元素数 最坏情况多出的字节数1 65535 65534 65534 B2 32767 32766 65532 B3 21845 21844 65532 B4 16383 16382 65528 B8 8191 8190 65520 B16 4095 4094 65504 B257 255 254 65278 B32768 1 0 0 B可以看到最坏情况是逻辑长度刚好比块大小的整数倍多 1而且块大小是 65,535。这时最后一个块只使用 1 个字节剩下的部分都空着。类型加载#现在假设 T 是 64 位运行时上的 object。一个引用是 8 字节所以合法的块长度是 8,191Copy65535 / 8 8191这意味着 ElementChunk8191 是合法的。但 ElementChunk3ElementChunk5ElementChunk17ElementChunk257 就太大了因为它包含 65,535 个 object 引用作为数组元素的值类型会占用 8 * 65535 524,280 字节。这样的类型不能被加载否则运行时在创建数组时会抛出 TypeLoadException。麻烦的地方在于代码不会执行和类型不会被加载不能简单画等号。如果一个方法里引用了很多已经构造好的泛型数组类型JIT 和类型加载器在导入或编译方法时仍然可能碰到非法组合。结果就是抛出 TypeLoadException即使真正想分配的是另一个块形状CopyAllocateArray(42); // TypeLoadException: Array of type ‘ElementChunk31[ElementChunk51[ElementChunk171[ElementChunk2571[System.__Canon]]]]’ from assembly ‘ConsoleApp1’ cannot be created because base value type is too large.Array AllocateArray(int length){if (length 8191)return new ElementChunk8191[length];elsereturn new ElementChunk3ElementChunk5ElementChunk17ElementChunk257[length];}解决办法是把真正的分配延迟到选中分支之后。分配路径会先计算 T 对应的合法块长度然后从 switch 里拿到这个块长度对应的分配器最后只调用这个分配器。分配器来自一个针对块长度的 switch。每个分支都返回一个静态 lambdalambda 里只分配一种块类型Copyinternal static Funcint, bool, bool, Array CreateBigArrayAllocator(int chunkLength){return chunkLength switch{1 static (chunks, pinned, uninitialized) AllocateArrayElementChunk1(chunks, pinned, uninitialized),…,8191 static (chunks, pinned, uninitialized) AllocateArrayElementChunk8191(chunks, pinned, uninitialized),…,65535 static (chunks, pinned, uninitialized) AllocateArrayElementChunk3ElementChunk5ElementChunk17ElementChunk257(chunks, pinned, uninitialized),…,_ throw new UnreachableException(),};}实际的 switch 有 510 个 case但最重要的是它的实现真正的分配藏在 lambda 后面而且分配用的辅助方法标记为 NoInlining。Copy[MethodImpl(MethodImplOptions.NoInlining)]private static Array AllocateArray(int chunks, bool pinned, bool uninitialized){return uninitialized? GC.AllocateUninitializedArray(chunks, pinned): GC.AllocateArray(chunks, pinned);}这里强行要求间接调用很关键。它可以防止未选中的块数组类型被提前加载。只有和当前 Unsafe.SizeOf() 匹配的块形状会真正实例化因为 JIT 只会编译实际创建出来的 lambda 背后的方法。对于 object代码会选择 8191 分支并创建 ElementChunk8191[]65535 分支仍然存在给用于 byte 这样的类型使用但它不会在 object 路径上被加载。BigArray#有了块机制之后BigArray 本身可以保持得很小。它只保存两个东西Copyinternal readonly Array _storage;internal readonly nint _length;普通长度下它会分配一个 ElementChunk1[]布局基本上接近带了一层包装的普通 T[]。更大的长度下它会计算块长度分配选中的块数组并把逻辑长度记录为 nint。这也是为什么 _storage 的类型是 Array实际运行时类型取决于 T。它可能是 ElementChunk1[]也可能是 ElementChunk8191[]或者是 ElementChunk3ElementChunk5ElementChunk17ElementChunk257[] 这样的组合块类型。Copypublic BigArray(nint length){if ((nuint)length (nuint)MaxLength){ThrowHelpers.ThrowOutOfRange(nameof(length));}if (length Array.MaxLength) { _storage new ElementChunk1T[length]; } else { _storage CreateBigArraySlow(length); } _length length;}然后是索引器实现。这里我们不需要在每次访问时都除以块大小。底层是一个托管数组数组数据区里连续排列着块结构体而元素又内联保存在这些块里因此代码只需要拿到第一个逻辑 T 的引用然后用普通的引用偏移往后移动。Copypublic 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 得到的Copyprivate static ref T GetDataReference(Array storage){return ref Unsafe.Asbyte, T(ref MemoryMarshal.GetArrayDataReference(storage));}这就是为什么连续存储这个特性很重要。拿到第一个数据引用之后Unsafe.Add(ref first, index) 会移动 index 个逻辑 T 元素。跨过一个块到下一个块只是在同一段数组数据区里继续往前走。这样一来BigArray 不需要像交错数组包装器那样在每次访问时都做除法和取余它只是把一个托管数组对象视作一段更大的逻辑序列。最大长度则跟架构有关Copypublic static nint MaxLength nint.Size 4 ? Array.MaxLength : GetChunkLength() * (nint)Array.MaxLength;在 32 位运行时上nint 本身无法表示更大的索引空间所以 BigArray 保持普通数组的限制。在 64 位运行时上最大长度会随块大小增长。对 byte 来说大约是 Array.MaxLength * 65535对 64 位运行时上的 long 或对象引用来说大约是 Array.MaxLength * 8191。对于 byte这意味着它理论上可以表示接近 128 TiB 的数组准确地说是 127.998 TiB。这里当然说的是理论上限机器仍然需要真的有足够的内存。BigSpan 和 BigMemory#只有持有存储的类型还不够。普通 .NET 代码里数组只是编程模型的一部分。我们还会用 Span、ReadOnlySpan、Memory 和 ReadOnlyMemory 来传递视图。BigSpan 是一个面向超大连续区域的栈上视图Copypublic readonly ref struct BigSpan{internal readonly ref T _first;internal readonly nint _length;}它的基本形状和 Span 一样一个起始引用加一个长度。不同的是长度是 nint索引也使用 nint。和 Span 一样它不拥有内存只是查看由别的对象保持存活的内存通常是 BigArray 或 BigMemory。CopyBigArray buffer new((nint)Array.MaxLength 1024);BigSpan span buffer.AsBigSpan();span[Array.MaxLength] 42;BigMemory 和 BigReadOnlyMemory 则是可以保存起来的视图。它们记录底层托管数组、起始偏移和长度Copyinternal readonly Array? _storage;internal readonly nint _start;internal readonly nint _length;当你需要高效的引用访问时它们的 Span 属性会生成 BigSpan 或 BigReadOnlySpan。由于 BigMemory 把底层托管数组保存在 _storage 里它可以被放进字段或从方法返回同时仍然让这段存储对 GC 可见。CopyBigMemory page buffer.AsBigMemory(1024, 4096);page.Span.Fill(0);API 的设计则尽量沿用了普通 Span/Memory 的习惯切片、复制、搜索、排序、trim、split、ToArray、ToBigArray 以及只读转换。实现内部如果需要调用只接受 Span 或 ReadOnlySpan 的 BCL API就把数据拆成能放进 int 的片段来处理。BigSpan 并不指望让所有现有 API 都接受超过 int.MaxValue 个元素。它给你一个大索引视图并且在需要和现有 API 互操作时允许你取出普通的 Span 片段。Copynint offset (nint)5_000_000_000L;Span window buffer.AsSpan(offset, length: 4096);分配 API#最简单的分配方式自然是调用构造函数Copynint length (nint)10_000_000_000L;BigArray buffer new(length);不过 .NET 的数组也有显式的 GC 分配辅助方法所以我也提供了对应的 APICopynint length (nint)10_000_000_000L;BigArray zeroed GC.AllocateBigArray(length);BigArray scratch GC.AllocateUninitializedBigArray(length);BigArray pinned GC.AllocateBigArray(length, pinned: true);这样你可以控制分配是否清零、是否允许未初始化、以及是否固定。pinned 适合需要把指针传给非托管代码的互操作场景未初始化分配适合那种马上会覆盖整块内存、不需要清零的性能敏感场景尤其是在大分配的情况下。写在最后#