03-02-线性-List-T-动态数组布局-扩容与操作成本

ListT动态数组布局、扩容与操作成本系列C#与常用数据结构源码剖析 · 数据结构-线性篇阅读时间约 45 分钟源码位置dotnet/runtime/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/List.cs版本基线私有字段与关键路径以.NET 8.0.0tag 为准增长、收缩与 JIT 优化不是跨版本契约一、引言ListT是 .NET 中最常用的可变长序列之一。它的主干是一个T[]数组加上_size和_version两个整数承载了从 Web API 反序列化到 Unity 每帧循环的大量场景。理解 ListT 的全部行为——扩容策略的数学依据、_version版本检测的设计困境、struct Enumerator 的低分配路径与装箱边界、JIT 对属性访问的内联条件——是掌握 C# 数据结构体系的第一个里程碑。二、核心字段_items、_size、_version2.1 源码全景// dotnet/runtime: src/libraries/System.Private.CoreLib/src/System/Collections/Generic/List.cs public class ListT : IListT, IList, IReadOnlyListT { internal T[] _items; // 内部数组 internal int _size; // 实际元素数量≤ _items.Length internal int _version; // 修改计数器 private const int DefaultCapacity 4; internal static readonly T[] s_emptyArray Array.EmptyT(); }三个字段各有深意_itemsvs_size的分离_items.Length是容量Capacity——底层数组能容纳的最大元素数。_size是实际数量——真正有效的元素数。两者分离允许你在知道最终大小时预分配 Capacity一次性搞定所有扩容。如果你不预分配List 会从 0 开始自动扩容——这带来均摊 O(1) 的效率但每一次扩容都会留下一块旧数组作为 GC 垃圾。_version不是线程安全机制它是枚举修改检测的一部分。它不能防止多线程同时改写元素、计数、版本与数组引用。应用锁保护完整业务不变式或按 FIFO、LIFO、无序复用、背压等真实语义选并发集合ConcurrentBagT不是任意 List 的通用替代。2.2 空 List 的内存状态var list new Listint(); // _items s_emptyArray (单例空数组), _size 0新 List 的_items不是null而是指向共享零长度数组。这避免为每个空 List 新建数组但 List 对象仍要分配。具体字节数取决于架构、对象头、对齐和运行时不应写成固定值。三、扩容策略4 → 8 → 16 → ... 的数学3.1 扩容触发的完整路径public void Add(T item) { _version; T[] array _items; int size _size; // 关键用 uint 转换来一次比较同时检查 size 0 size array.Length if ((uint)size (uint)array.Length) { _size size 1; array[size] item; // 快速路径直接写入 } else { AddWithResize(item); // 慢速路径扩容后写入 } }注意(uint)size (uint)array.Length这个技巧——它将两个 int 转为 uint 比较一次操作同时处理了size 不能为负和size 必须小于容量两个条件。如果size是负数转为 uint 后会变成一个巨大的正数如 -1 → 0xFFFFFFFF必然大于array.Length从而触发扩容路径。AddWithResize 的内部private void AddWithResize(T item) { int size _size; Grow(size 1); // 确保容量至少为 size1 _size size 1; _items[size] item; } private void Grow(int capacity) { int newCapacity _items.Length 0 ? DefaultCapacity // 4 : _items.Length * 2; // 翻倍 if ((uint)newCapacity Array.MaxLength) newCapacity Array.MaxLength; if (newCapacity capacity) newCapacity capacity; Capacity newCapacity; // 触发重新分配 Array.Copy }3.2 翻倍策略的均摊分析为什么翻倍×2而不是加固定大小100考虑连续 Add N 个元素翻倍策略×2扩容发生 log₂(N/4) 次总复制元素数 ≈ 2N。均摊每元素 O(1)。固定增量K扩容发生 N/K 次总复制元素数 ≈ N²/(2K)。均摊每元素 O(N)。翻倍策略背后的原理是几何级数击败算术级数。扩容次数以对数增长而每次扩容的成本以指数增长——两者的乘积保持在线性范围内。3.3 Capacity 属性与构造函数// 最常用完全信任自动扩容 var list new Listint(); // 预知大小一次性分配零扩容、零 GC 垃圾 var list new Listint(10000); // 从集合构造先分配容量再批量复制 var list new Listint(existingCollection); // 内部先设 capacity collection.CountCapacity setter 的内部public int Capacity { get _items.Length; set { if (value _size) throw new ArgumentOutOfRangeException(); if (value ! _items.Length) { if (value 0) { T[] newItems new T[value]; if (_size 0) Array.Copy(_items, newItems, _size); _items newItems; } else { _items s_emptyArray; } } } }显式改变 Capacity 可创建新数组并复制有效前缀旧数组在无其他引用后才可回收。设为 0 时 List 可重新指向共享空数组但先前的非空数组仍是待 GC 处理的对象不能说成“无 GC 垃圾”。3.4 TrimExcess收缩的艺术public void TrimExcess() { int threshold (int)(((double)_items.Length) * 0.9); if (_size threshold) { Capacity _size; // 只在实际使用率 90% 时收缩 } }90% 阈值的设计智慧如果刚收缩到_size紧接着又 Add 一个元素就会立即触发扩容——抖动thrashing。90% 阈值确保只有显著浪费至少 10% 空间未使用才收缩。四、关键操作逐行源码分析4.1 Add vs AddRange单兵 vs 军团public void AddRange(IEnumerableT collection) { if (collection is ICollectionT c) { int count c.Count; if (count 0) { if (_items.Length - _size count) Grow(_size count); c.CopyTo(_items, _size); _size count; _version; } } else { // 未知大小的集合逐个 Add foreach (T item in collection) Add(item); } }AddRange的优化点如果传入的集合是ICollectionT可以获取 Count它一次性扩容到位然后CopyTo批量复制——没有多次扩容的中间垃圾数组。如果是IEnumerableT不知道大小只能逐个 Add每次都可能扩容。4.2 InsertO(n) 的真正代价public void Insert(int index, T item) { if ((uint)index (uint)_size) throw new ArgumentOutOfRangeException(); if (_size _items.Length) Grow(_size 1); if (index _size) { Array.Copy(_items, index, _items, index 1, _size - index); } _items[index] item; _size; _version; }Array.Copy(_items, index, _items, index 1, _size - index)这行是性能核心将[index, _size)范围的元素整体后移一位。对于值类型这是memmove块内存移动对于引用类型还要更新 GC 卡表。头插需要移动当前全部有效元素如果同时触发扩容还要复制到新数组。具体时间取决于T的宽度、是否含引用、规模、CPU 和运行时未附原始报告时不写死毫秒数。4.3 RemoveAll双指针的就地过滤public int RemoveAll(PredicateT match) { int freeIndex 0; // 写指针 while (freeIndex _size !match(_items[freeIndex])) freeIndex; if (freeIndex _size) return 0; int current freeIndex 1; // 读指针 while (current _size) { while (current _size match(_items[current])) current; if (current _size) _items[freeIndex] _items[current]; } // 清理尾部 if (RuntimeHelpers.IsReferenceOrContainsReferencesT()) { Array.Clear(_items, freeIndex, _size - freeIndex); } int result _size - freeIndex; _size freeIndex; _version; return result; }两个 while 循环交替工作第一个 while 找第一个不匹配的元素确定写指针起点。第二个 while 的外层是读指针遍历内层跳过要删除的元素。整个过程中没有分配新数组——就地操作。4.4 索引器与 JIT 优化public T this[int index] { get { if ((uint)index (uint)_size) throw new ArgumentOutOfRangeException(); return _items[index]; } set { if ((uint)index (uint)_size) throw new ArgumentOutOfRangeException(); _items[index] value; _version; } }索引器自带边界检查(uint)index (uint)_size。但在for (int i 0; i list.Count; i)循环中如果 JIT 能够通过范围分析证明i始终在[0, _size)范围内它会在 Tier1 编译中消除这个检查——使得list[i]等价于直接数组访问。Count 属性的内联public int Count _size;是很小的 getter在当代 CoreCLR 的优化发布构建中通常具备良好的内联条件内联后可表现为直接字段读取。这不是 C# 或 BCL 契约Debug/未优化构建、Tier 状态、AOT 后端、泛型实例化与调用上下文都可能改变决定。只有目标环境的生成代码才能证明某一调用点是否真正消除了调用。五、Enumeratorstruct 的低分配路径与装箱边界5.1 为什么不设计为 classpublic struct Enumerator : IEnumeratorT, IEnumerator { private readonly ListT _list; private int _index; private readonly int _version; private T? _current; }Enumerator 是struct——这是 .NET 设计中最精妙的性能决策之一。考虑foreach的展开// C# 源码 foreach (var item in list) { ... } // 编译器展开简化 Listint.Enumerator e list.GetEnumerator(); try { while (e.MoveNext()) { int item e.Current; // 循环体 } } finally { e.Dispose(); }因为e是 struct具体ListTforeach 通常可按值保存枚举器不需要为它单独分配对象。局部值可位于寄存器或栈不应概括为 struct 永远“在栈上分配”。是否内联由 JIT 决定。但 struct 枚举器有一个隐藏陷阱当它转成IEnumeratorT/IEnumerator或object时可装箱。是否需要避免必须看调用频率与目标 Mono/IL2CPP 构建的 Profiler 证据不应声称所有 Unity 项目一律禁止。5.2 _version 检测与并发陷阱public bool MoveNext() { ListT localList _list; if (_version ! localList._version) { ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); } if ((uint)_index (uint)localList._size) { _current localList._items[_index]; _index; return true; } _index _list._size 1; _current default; return false; }_version检查在每次 MoveNext 时执行——即使是第 10000 次迭代。在本文的 .NET 8.0.0 基线中枚举期间执行会改变该ListT_version的公开修改操作会使枚举器失效并在后续检查中抛出异常。这与修改引用类型元素所指对象的内部状态不同_version也不是并发同步或内存安全机制。如果该检查在已测量的热路径上成为瓶颈极少见可比较for循环但仍需由调用方保证不发生未同步的结构修改。六、多版本演进如何核验ListT在 .NET Framework、历代 .NET Core/.NET 中的 Add、批量复制、清尾引用、搜索与容量 API 都可演进JIT 又会改变内联与范围检查。但不应用没有对应 commit/基准的“提升 5—10%”或“快 20%”构造版本史也不应把与 List 本体无直接关系的 API 写成它的集成优化。核验版本差异应对比明确发布 tag 的List.cs记录具体 commit 和方法差异分开 BCL 源码变化与 RyuJIT 代码生成变化在每个目标 TFM/runtime 编译并运行同一基准保留机器码与原始报告检查 API 引入版本不把当前 SDK 参考程序集与旧 runtime 混用CollectionsMarshal.AsSpan之类低级视图要单独审查失效、容量变化与并发边界。七、复杂度、分配与引用生命周期操作时间可能分配顺序/生命周期索引读写O(1)否set 是结构修改枚举版本变化尾部 Add均摊 O(1)容量不足时新数组保持已有顺序Insert/RemoveAtO(n)扩容时可分配移动后缀索引失效RemoveAllO(n) predicate委托/闭包可分配稳定保留未删元素的相对顺序Clear含引用T时需清有效前缀通常不换数组释放元素引用保留 CapacityTrimExcess/Capacity 收缩O(n)可新建数组降低驻留可导致随后扩容抖动Clear()不等于释放支持数组。它将_size置零对引用或含引用的T清除有效槽使元素可回收但容量为下一批复用保留。这对稳定峰值有利对偶发巨大峰值则可造成长期驻留应用内存预算决定是保留、收缩还是丢弃整个 List。RuntimeHelpers.IsReferenceOrContainsReferencesT()让实现仅在必要时清引用槽。对纯值T移除后无效尾部字节可保留而不影响 GC它们已在_size之外不能通过公开索引器读取。八、实战建议预分配 Capacity在有合理上界/估计时减少扩容但避免过度预留峰值内存先测 for 与 foreach具体 List foreach 本身可无枚举器分配不应只为版本检查牺牲可读性尾部 Add 通常是 List 最低成本的单项插入在已选择ListT且业务顺序允许尾插时list.Add(item)为均摊 O(1)但扩容当次仍是 O(n) 并可产生延迟尖峰。list.Insert(0, item)是 O(n)——每次都要移动所有元素若需批量构建、队头操作或已知精确长度还应比较AddRange、队列或数组等更匹配语义的方案RemoveAll 优于循环 RemoveAt前者是单次 O(n) 就地操作后者是 O(n²)审查CollectionsMarshal.AsSpan所有权视图存活期间不得让 List 改变容量/结构不跨异步、不并发保存并确认目标 TFM 提供 API九、可复现验证与审查清单9.1 差分正确性测试用普通数组模型与 List 同时执行随机 Add、Insert、RemoveAt、set、Clear 和 RemoveAll每步比较 Count 与序列。覆盖 0/1/刚好 Capacity/Capacity1以及引用类型、纯值 struct、含引用 struct。9.2 分配与局部性实验对比从空自动增长、合理预分配、过度预分配三组报告扩容次数、分配、峰值与遍历。再对比ListSmallStruct、ListLargeStruct与ListClass将元素拷贝、对象数和缓存局部性分开解释。9.3 枚举路径实验比较具体ListTforeach、IEnumerableTforeach、索引 for 与 Span 视图用 IL 确认静态调用形状用分配诊断查装箱用 disassembly 查内联/边界检查。在 Unity 中分别跑 Mono 和 IL2CPP 真机不从 CoreCLR 结果推断。9.4 版本升级与容量峰值回归升级 SDK、Unity 或脚本后端时不要只重跑一个固定数量的 Add 微基准。建立阶梯负载空表开始依次写到预期容量前一项、恰好容量、容量后一项、典型高分位和业务硬上限每个阶段记录Count、Capacity、扩容次数、每操作分配、峰值托管堆、操作尾延迟和清空后的驻留量。这样能把“普通追加成本”“跨扩容边界的复制尖峰”和“峰值数组长期保留”分开而不会被平均值稀释。三组容量策略应处理完全相同的输入默认增长、按典型规模预留、按理论最大值预留。除时间与分配外还要验证最终序列、顺序、重复项、异常位置以及引用对象是否在 Clear/Remove 后可回收。过度预留若降低了扩容次数却让每个场景实例长期保留巨大数组应记为内存回归而非单向优化主动收缩若造成下一轮再次扩容也应报告抖动周期。版本对照一次只改变一个轴并保存 SDK/runtime、源码 commit、构建配置和设备。若新版本结果不同先区分是ListT源码、JIT/AOT 代码生成、GC 策略还是测试噪声只有差异在重复进程和真实场景中稳定出现且正确性与峰值预算都通过才能把它写成升级收益。报告还应保留每轮原始数据而不只保留最优样本结果方向反复变化时正确结论是“尚未证明”不是挑一次符合预期的数据发布。审查时确认_size _items.Length不变式永远成立未使用尾部不会保留已删引用不依赖增长倍数、Trim 阈值或枚举顺序作为未来契约并发访问由容器外的所有权/锁协议保护可变键/可变元素的业务契约不由 List 自动保护低级 Span 视图没有跨越结构修改、await 或多线程边界优化在目标 runtime/backend 上有原始报告和正确性回归。十、总结ListT的不变式很少_items是支持数组_size定义有效前缀_version帮助枚举器检测结构修改。正因为结构简单它的成本能够被精确解释尾部添加用几何增长换取均摊 O(1)中间增删移动后缀删除后的引用槽要清理收缩容量需要新数组并可与后续增长抖动。成熟使用不是一律“预分配、for、AsSpan”而是从实际数量上界、顺序契约、元素宽度、所有权和目标运行时做选择。预分配可减少扩容也可浪费驻留struct 枚举器可避免对象也可在接口边界装箱Span 视图可去掉某些抽象也会暴露失效风险。用不变式证明正确性再用固定 tag 源码、IL、分配与真机基准选择优化才是理解这个“简单动态数组”的完整方式。下一篇LinkedListT双向链表的实现与选择困境