.NET source 系列：System.Collections.Generic.List

发表于 2024-08-25 更新于 2024-08-29 分类于计算机科学，编程语言， C# 阅读次数：本文字数： 7.2k 阅读时长 ≈ 7 分钟

System.Collections.Generic.List

参考版本为 .net framework 4.8

https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs

摘要

泛型类型 List<T>，实现接口 IList<T>，IReadOnlyList<T>
使用数组 T[] _items 实现，当前已存储的元素个数为 _size / Count，当前容量大小通过 Capacity得到，直接返回数组 _items 的长度。

主要行为

构造函数 ctor

使用 List 的无参构造函数，会将List内部的静态空数组 static readonly T[] _emptyArray = new T[0] 设置到 _items 上，这是一个使用静态变量避免零大小数组重复创建的技巧。
使用带 capacity 参数的构造函数，可以在构造时就分配出指定大小的数组，避免后续添加元素时的扩容。
使用 IEnumerable<T> collection 参数的构造函数，会在内部先检查是否能转换为 ICollection<T>，这样直接开辟定长数组并直接 CopyTo 是更高效的；否则即使用 GetEnumerator 并遍历元素进行 Add() 的方式进行构造。

(prop) Capacity

getter 获取时直接返回内部数组的长度

setter 首先保证设置的容量大于元素个数；其次设置的容量值非0，直接分配对应大小的新数组，并将原内容 Array.Copy ，在容量值为0的情况下直接令 _items 指向 _emptyArray

(prop) Count

仅 getter，直接返回代表当前元素个数的 _size

EnsureCapacity(int min)

只有在传入的min大于内部数组长度时才会工作。

若内部数组长度为0，那么第一次扩容的长度会是_defaultCapacity，这个值在参考的源码中是4。

若不是第一次扩容，那么预期的扩容长度是当前数组长度 x2。

Capacity存在上界，这个值为 Array_ReferenceSources.MaxArrayLength，这个值为 0X7FEFFFFF（2亿多一些）。扩容的大小不会超过这个数值。

若预期扩容后的个数仍然没有达到传入的min，那么直接让新的容量大小等于传入的min。

最后这个 newCapactiy 通过上述 Capacity 的 setter 进行扩容。

Add(T item)

若当前元素个数已达内部数组大小上限，通过 EnsureCapacity(_size+1) 来扩容

扩容后，新元素 item 会被放置到新数组的 _size++ 位置上

*此方法会更新 _version

Clear()

Clear 方法只是释放了内部数组中每个元素的引用，并且将 _size 重置为0，即内部数组仍然存在 Capacity 即相应的内存占用，同时也很可能不会在下一次 Add() 中发生扩容。

*此方法会更新 _version

Contains(T item)

若传入item为null，则进行内部数组所有元素（转换为Object）的null-check

若不为null，则获取类型T的默认比较器进行遍历比较

EqualityComparer<T> c = EqualityComparer<T>.Default;
for(int i=0; i<_size; i++) {
    if (c.Equals(_items[i], item)) return true;
}
return false;

Insert(int index, T item)

若List内部元素以达到内部数组上限，触发 _size + 1 扩容。

将插入位置往后的所有元素使用 Array.Copy 全部右移。List内部元素数增加。

*此方法会更新 _version

InsertRange(int index, IEnumerable<T> collection)

同样会检测传入的 collection 是否是 ICollection，对于不是 ICollection 的情况比较简单，使用 GetEnumerator() 遍历整个 collection，逐一进行 Insert()即可。

对于是 ICollection 的情况：

使用 _size + collection.Count 大小进行扩容
将插入 index 往后的内容 copy 到 index + count 位置
若当前插入的 collection 是自己：
1. 将插入 index 前的内容复制到 index 位置
2. 将前面保存在 index + count 位置的尾部内容重新复制为 index * 2 的位置 [ part1 | (index) part1 | (index*2) part2 | (index+count) part2 ]
若当前插入的 collection 不是自己：新开辟指定 Count 大小的数组，直接 Copy 到 index 位置

*此方法会更新 _version

Remove(T item)

实现为 IndexOf(T item) 和 RemoveAt(int index) 的组合

RemoveAt(int index)

若指定小标大于等于 _size 将抛出越界异常

减小List的元素数量 _size，当 index < _size 时进行 Array.Copy

因为若需要移除的位置是当前元素的末尾，直接执行后续的 _items[_size] = default(T) 即可，不需要移动数组元素

*此方法会更新 _version

RemoveRange(int index, int count)

RemoveRange会在方法起始做一系列越界检测。

剩下的内容与 RemoveAt 差别不大，_size 会减去指定的Count，同时进行数组的Copy。

差别较大的是这里并不将数组元素逐一设置为 default(T)，而是直接使用 Array.Clear 抹掉指定位上的内容。

个人而言 Array.Clear 并不特别常用，后续可以多关注这一类数组提供的方法。

*此方法会更新 _version

TrimExcess()

将List的内部数组大小，即容量大小，设置为严格与 _size 一致。只有用这个方法（或者手动设置Capacity）能够真正缩小List的内部数组内存占用，这在已知List不会再有新元素时相当有用。

想要完全清空一个List并且释放所有内存，正确的做法是：

list.Clear();
list.TrimExcess();

Enumerator

构造 Enumerator 时，内部会存有原 List 对象引用，新增表示遍历下标的index，表示当前元素的Current（构造时设置为 default(T)），并且记录构造时list的版本 list._version，防止遍历过程中list内容发生改变。

如果在MoveNext过程中，version发生了改变，那么将会立即抛出 InvalidOperation_EnumFailedVersion 异常。

第一次调用 MoveNext() 后，index和Current便会是List内部的第一个元素位置。最后一次调用 MoveNext() 后，将会进入方法 MoveNextRare()，此时index等于_size，Current恢复为default(T)，MoveNextRare() 将会返回 False 保证遍历过程停止。

What about Unity?

working with 2018.4.11f1

测试环境信息：

API Compatibiliy Level: .NET 2.0 Subset
Scripting Runtime: 3.5 equivalent
Unity version: 2018.4.11f1

写到这里时，正好在一个使用较低版本Unity的项目组中参与开发工作，因此虽然已有耳闻高版本的Unity在泛型共享方面有做优化，阅读il2cpp输出可能意义不大，但还是出于好奇观察了下 System.Collections.Generic.List 在低版本 unity / il2cpp 下的生成内容。

粗看之下类型成员，以及静态类型成员看上去没有什么不同。

// System.Collections.Generic.List`1<System.Int32>
struct  List_1_t4A961510635950236678F1B3B2436ECCAF28713A  : public RuntimeObject
{
public:
    // T[] System.Collections.Generic.List`1::_items
    Int32U5BU5D_t20AF77B812DFA3168922AE8F35FB9FD20D7EA074* ____items_1;
    // System.Int32 System.Collections.Generic.List`1::_size
    int32_t ____size_2;
    // System.Int32 System.Collections.Generic.List`1::_version
    int32_t ____version_3;
};

struct List_1_t4A961510635950236678F1B3B2436ECCAF28713A_StaticFields
{
public:
    // T[] System.Collections.Generic.List`1::EmptyArray
    Int32U5BU5D_t20AF77B812DFA3168922AE8F35FB9FD20D7EA074* ___EmptyArray_4;
};

但是没有发现 EnsureCapacity，取而代之的是 GrowIfNeeded 方法。

// System.Void System.Collections.Generic.List`1<System.Object>::GrowIfNeeded(System.Int32)
extern "C" IL2CPP_METHOD_ATTR void List_1_GrowIfNeeded_m3C3B2872122BDF013830789D49EE77F7880CDEC5_gshared (List_1_tE72A517BD14F52539FF78EA90F58D1387FEED660 * __this, int32_t ___newCount0, const RuntimeMethod* method)
{
    int32_t V_0 = 0;
    {
        int32_t L_0 = (int32_t)__this->get__size_2();
        int32_t L_1 = ___newCount0;
        V_0 = (int32_t)((int32_t)il2cpp_codegen_add((int32_t)L_0, (int32_t)L_1));
        int32_t L_2 = V_0;
        ObjectU5BU5D_t8D571697F3A1B33B696E2F80500C21F1A1748C5D* L_3 = (ObjectU5BU5D_t8D571697F3A1B33B696E2F80500C21F1A1748C5D*)__this->get__items_1();
        NullCheck(L_3);
        if ((((int32_t)L_2) <= ((int32_t)(((int32_t)((int32_t)(((RuntimeArray *)L_3)->max_length)))))))
        {
            goto IL_0031;
        }
    }
    {
        NullCheck((List_1_tE72A517BD14F52539FF78EA90F58D1387FEED660 *)__this);
        int32_t L_4 = ((  int32_t (*) (List_1_tE72A517BD14F52539FF78EA90F58D1387FEED660 *, const RuntimeMethod*))IL2CPP_RGCTX_METHOD_INFO(method->klass->rgctx_data, 18)->methodPointer)((List_1_tE72A517BD14F52539FF78EA90F58D1387FEED660 *)__this, /*hidden argument*/IL2CPP_RGCTX_METHOD_INFO(method->klass->rgctx_data, 18));
        int32_t L_5 = Math_Max_m8B815B13982D8738EF051EA87C1CCB722CDF29B2((int32_t)((int32_t)il2cpp_codegen_multiply((int32_t)L_4, (int32_t)2)), (int32_t)4, /*hidden argument*/NULL);
        int32_t L_6 = V_0;
        int32_t L_7 = Math_Max_m8B815B13982D8738EF051EA87C1CCB722CDF29B2((int32_t)L_5, (int32_t)L_6, /*hidden argument*/NULL);
        NullCheck((List_1_tE72A517BD14F52539FF78EA90F58D1387FEED660 *)__this);
        ((  void (*) (List_1_tE72A517BD14F52539FF78EA90F58D1387FEED660 *, int32_t, const RuntimeMethod*))IL2CPP_RGCTX_METHOD_INFO(method->klass->rgctx_data, 19)->methodPointer)((List_1_tE72A517BD14F52539FF78EA90F58D1387FEED660 *)__this, (int32_t)L_7, /*hidden argument*/IL2CPP_RGCTX_METHOD_INFO(method->klass->rgctx_data, 19));
    }

IL_0031:
    {
        return;
    }
}

这就需要我们按照上述测试环境找到准确的Mono版本了，已知当前的 Scripting runtime 对齐（equivalent） .NET framework 3.5，根据以下表格可以对应到 C# 3.0 版本。

再根据这张表格可以得到 Mono 实现 C# 3.0 的相应版本为 mono 2.0，这样就找到我们的源码目标了。需要额外注意的是，这里的表格中的 .net 2.0 是与现代 .net 6/7/8 的同一套标准的不同版本，而不是指 .NET Standard 2.0，不要把（很容易搞混的）概念搞混了。

from: https://www.cnblogs.com/zhaoqingqing/p/5762867.html

最后跳转到相应的 mono-2.0 源码，就能看到方法 GrowIfNeeded 了。可以发现在实现上与 EnsureCapacity 不同的是传入的数值为此次操作的元素个数增量，而不是元素个数的目标大小。

// https://github.com/mono/mono/blob/a1f3cf39287ceaca189ae1b4c06ad1677c8988cf/mcs/class/corlib/System.Collections.Generic/List.cs#L83

        public void Add (T item)
        {
            // If we check to see if we need to grow before trying to grow
            // we can speed things up by 25%
            if (_size == _items.Length)
                GrowIfNeeded (1);
            _items [_size ++] = item;
            _version++;
        }
        
        void GrowIfNeeded (int newCount)
        {
            int minimumSize = _size + newCount;
            if (minimumSize > _items.Length)
                Capacity = Math.Max (Math.Max (Capacity * 2, DefaultCapacity), minimumSize);
        }

再一次说明了在做Unity性能调优，或者在预测Unity上的业务代码性能表现情况时，有一份版本正确的源码很重要。如果觉得在诸多版本之间定位C#源码过于麻烦，直接阅读il2cpp输出的cpp源码，或许也是一种办法。