在 .NET 里数组、集合、Span 以及很多相关 API 都是围绕 32 位长度和索引设计的。GitHub 上曾经有一个很长的 issue 讨论 64 位数组支持但最后以 wont fix 关闭因为这件事会牵涉到运行时、GC、JIT、类型系统、反射以及大量现有代码。常见的解决办法大概有两类一类是分配非托管内存再用一个类包起来另一类是用交错数组模拟一个更大的数组。这两种方案在某些场景下都能用但代价也很明显。手动管理内存很容易出错而且它更适合非托管数据。像string、object这样的引用类型就不适合这个方向。交错数组避开了非托管内存但本质上仍然是一组数组。你需要管理每个内部数组的大小访问时要处理跨段边界和那些期待连续内存区域的 API 配合起来也很别扭。于是我决定自己做一个方案能容纳超过 20 亿个元素并且仍然用一个索引访问。索引应该跟架构相关32 位系统上保持普通数组的限制64 位系统上可以支持更大的范围。支持string和object之类的引用类型。连续托管内存分配。由 GC 管理用户不需要手动释放内存。支持 NativeAOT因此不能依赖运行时代码生成或反射。基本思路#在 .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 FourElementsT { private T _first; }这样一来一个FourElementsT数组的每个物理元素就可以容纳四个逻辑上的T。如果物理数组本身可以有接近 20 亿个块那么四倍宽度的块就能表示接近 80 亿个逻辑元素。这就是BigArrayT的核心思路。底层仍然是一个托管数组但数组元素类型不一定是T本身也可能是一个块类型。BigArrayT另外记录真实的逻辑长度再把这些块里的数据看成一段连续的T。构建块类型#最直观的实现是为每一种块长度都定义一个类型Copy[InlineArray(1)] struct ElementChunk1T { private T _first; } [InlineArray(2)] struct ElementChunk2T { private T _first; } [InlineArray(3)] struct ElementChunk3T { private T _first; } // ... [InlineArray(65535)] struct ElementChunk65535T { private T _first; }这显然不现实而且对任意T来说也不一定合法。这里有一个重要的运行时类型加载限制作为数组元素的值类型不能超过 65,535 字节。对某个T来说块长度是Copy65535 / Unsafe.SizeOfT()所以byte可以使用 65,535 的块长度。大小为 8 字节的类型可以使用 8,191。大小为 32 字节的类型可以使用 2,047。确定这个值之后分配时只需要计算请求的逻辑长度需要多少个物理块。这也意味着实现不需要为每一个整数都准备一个块类型。只要覆盖65535 / size可能产生的那些值就够了。这样块类型数量从 65,535 降到了 510但仍然不少。更进一步块结构体本身也可以组合。Copy[InlineArray(2)] struct ElementChunk2T { private T _first; } [InlineArray(3)] struct ElementChunk3T { private T _first; }ElementChunk2ElementChunk3T表示 2 个包含 3 个值的块也就是 6 个逻辑T。ElementChunk23ElementChunk89T表示 2047 个逻辑元素。byte能使用的最大块长度也就是 65,535可以写成CopyElementChunk3ElementChunk5ElementChunk17ElementChunk257byte因为Copy3 * 5 * 17 * 257 65535因此我们可以只保留一组质数长度的基础块类型再通过嵌套组合出其他长度。为了覆盖 1 到 65,535 之间需要的块长度最后只需要 85 个基础块类型从ElementChunk2T到ElementChunk8191T。其他长度都可以由这些基础长度相乘得到。这比手写几万个字段或者为每一个长度准备一个 struct 要容易维护得多。有了这些块类型之后就可以组合出 1 到 65,535 之间任意需要的块类型Copyvar chunkSize 65535 / Unsafe.SizeOfT(); var chunks length / chunkSize (length % chunkSize 0 ? 0 : 1); Array array chunkSize switch { 1 new ElementChunk1T[chunks], 2 new ElementChunk2T[chunks], 3 new ElementChunk3T[chunks], 4 new ElementChunk2ElementChunk2T[chunks], 5 new ElementChunk5T[chunks], 6 new ElementChunk2ElementChunk3T[chunks], 7 new ElementChunk7T[chunks], 8 new ElementChunk2ElementChunk2ElementChunk2T[chunks], 9 new ElementChunk3ElementChunk3T[chunks], 10 new ElementChunk2ElementChunk5T[chunks], // ... 21845 new ElementChunk5ElementChunk17ElementChunk257T[chunks], 32767 new ElementChunk7ElementChunk31ElementChunk151T[chunks], 65535 new ElementChunk3ElementChunk5ElementChunk17ElementChunk257T[chunks], };这里的chunks表示真实托管数组的长度和BigArrayT暴露出来的逻辑长度不同。比如逻辑长度是 10,000而块大小是 4,095那么实现会分配 3 个物理块。最后一个块只用到一部分真正的逻辑终点由_length记录。这种做法会不会多分配一些没有用到的空间答案是会但非常小。sizeof(T)chunkSize最坏情况多出的元素数最坏情况多出的字节数1655356553465534 B2327673276665532 B3218452184465532 B4163831638265528 B88191819065520 B164095409465504 B25725525465278 B32768100 B可以看到最坏情况是逻辑长度刚好比块大小的整数倍多 1而且块大小是 65,535。这时最后一个块只使用 1 个字节剩下的部分都空着。类型加载#现在假设T是 64 位运行时上的object。一个引用是 8 字节所以合法的块长度是 8,191Copy65535 / 8 8191这意味着ElementChunk8191object是合法的。但ElementChunk3ElementChunk5ElementChunk17ElementChunk257object就太大了因为它包含 65,535 个 object 引用作为数组元素的值类型会占用8 * 65535 524,280字节。这样的类型不能被加载否则运行时在创建数组时会抛出TypeLoadException。麻烦的地方在于代码不会执行和类型不会被加载不能简单画等号。如果一个方法里引用了很多已经构造好的泛型数组类型JIT 和类型加载器在导入或编译方法时仍然可能碰到非法组合。结果就是抛出TypeLoadException即使真正想分配的是另一个块形状CopyAllocateArrayobject(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 AllocateArrayT(int length) { if (length 8191) return new ElementChunk8191T[length]; else return new ElementChunk3ElementChunk5ElementChunk17ElementChunk257T[length]; }解决办法是把真正的分配延迟到选中分支之后。分配路径会先计算T对应的合法块长度然后从 switch 里拿到这个块长度对应的分配器最后只调用这个分配器。分配器来自一个针对块长度的 switch。每个分支都返回一个静态 lambdalambda 里只分配一种块类型Copyinternal static Funcint, bool, bool, Array CreateBigArrayAllocator(int chunkLength) { return chunkLength switch { 1 static (chunks, pinned, uninitialized) AllocateArrayElementChunk1T(chunks, pinned, uninitialized), ..., 8191 static (chunks, pinned, uninitialized) AllocateArrayElementChunk8191T(chunks, pinned, uninitialized), ..., 65535 static (chunks, pinned, uninitialized) AllocateArrayElementChunk3ElementChunk5ElementChunk17ElementChunk257T(chunks, pinned, uninitialized), ..., _ throw new UnreachableException(), }; }实际的 switch 有 510 个 case但最重要的是它的实现真正的分配藏在 lambda 后面而且分配用的辅助方法标记为NoInlining。Copy[MethodImpl(MethodImplOptions.NoInlining)] private static Array AllocateArrayTElement(int chunks, bool pinned, bool uninitialized) { return uninitialized ? GC.AllocateUninitializedArrayTElement(chunks, pinned) : GC.AllocateArrayTElement(chunks, pinned); }