InternalList<T>：低级别的List<T>

引言

对于我们这些编写旨在紧凑且快速的底层代码的人来说，标准的List<T>似乎有点大材小用。它需要两个独立的堆对象，并且必须执行普通数组不需要的额外检查。因此，如果您正在编写需要尽可能快的代码，则可以考虑使用T[]数组而不是List<T>。

List<T>的缺点

从性能角度来看，有两件事使List<T>比普通数组“差”：大小和速度。

大小

List<T>至少需要两次堆分配：一次用于List<T>对象本身，另一次用于支持List<T>的数组。每个.NET对象都有一个两字的头，而List<T>有四个字段。

private T[] _items;
private int _size;
private object _syncRoot; // not used unless you call SyncRoot
private int _version;

因此，与数组相比，List<T>需要六个额外的字内存（我的意思是传统的“机器字”，即一个IntPtr大小的内存区域，因此在32位进程中总共额外占用24字节，在64位进程中可能占用40字节，假设CLR将_size和_version放入一个字中）。这听起来可能不多，但有时我编写一个使用数十万个小型列表的应用程序。积少成多。

速度

List<T>还必须执行额外的范围检查。例如，索引器看起来像这样：

public T this[int index]
{
    get {
        if ((uint)index >= (uint)_size)
            ThrowHelper.ThrowArgumentOutOfRangeException();
        return _items[index];
    }
    set {
        if ((uint)index >= (uint)_size)
            ThrowHelper.ThrowArgumentOutOfRangeException();
        _items[index] = value;
        _version++;
    }
}

请注意，_items[index]操作隐式包含一个范围检查：CLR在实际从数组读取或写入数组之前，会执行等效于(uint)index < (uint)_items.Length的检查。因此，这里实际上有两个范围检查。JIT通常不知道_size < _items.Length，因此无法基于第一个检查的结果删除第二个检查。

T[]的缺点

不幸的是，如果您改用普通数组，则无法简单地“添加”或“删除”项，因为数组的大小是固定的。因此，如果您决定真的想要一个普通数组，但需要添加、删除或（天哪！）插入项，您将不得不自己重新实现List<T>。您将有一个数组变量和一个计数变量...

private T[] _array;
private int _count;

然后，您可能会编写大量代码来执行List<T>已有的操作，例如插入。

static T[] Insert<T>(int index, T item, T[] array, ref int count)
{
    Debug.Assert((uint)index <= (uint)count);
    if (count == array.Length) {
        int newCap = array.Length * 2;
        array = CopyToNewArray(array, count, newCap);
    }
    for (int i = count; i > index; i--)
        array[i] = array[i - 1];
    array[index] = item;
    count++;
    return array;
}
static T[] CopyToNewArray<T>(T[] _array, int _count, int newCapacity)
{
    T[] a = new T[newCapacity];
    Array.Copy(_array, a, _count);
}

当然，这条路通向疯狂。幸运的是，您永远不需要编写这样的代码：只需改用InternalList<T>！

介绍InternalList

InternalList<T>是List<T>的即插即用替代品，定义如下：

[Serializable]
public struct InternalList<T> : IListAndListSource<T>, 
              IListRangeMethods<T>, ICloneable<InternalList<T>>
{
    public static readonly T[] EmptyArray = new T[0];
    public static readonly InternalList<T> Empty = new InternalList<T>(0);

    private T[] _array;
    private int _count;

    public InternalList(int capacity) {...}
    public InternalList(T[] array, int count) { _array=array; _count=count; }
    public InternalList(IEnumerable<T> items) : this(items.GetEnumerator()) {}
    public InternalList(IEnumerator<T> items) {}

    public int Count {...}
    public int Capacity {...}
    public void Resize(int newSize, bool allowReduceCapacity = true) {...}
    public void Add(T item) {...}
    ...
    ...
}

为了消除List<T>所需的额外内存，InternalList是一个struct而不是class；并且为了获得最大的性能，它在使用了不正确的数组索引时会发出断言而不是抛出异常，这样Release构建（其中Debug.Assert会消失）就能尽可能快地运行。

InternalList还有一个InternalArray属性，可以访问内部数组。这实际上允许您绕过普通List<T>的一些棘手问题。例如，普通的List不允许您这样做：

List<Point> pts;
...
// error CS1612: Cannot modify the return value of 'List<Point>.this[int]' because it is not a variable
pts[0].X = 5;

但是，如果pts是一个InternalList，那么您可以编写pts.InternalArray[0].X = 5;。

InternalList<T>还拥有List<T>所没有的其他功能，例如Resize()方法（以及Count的等效设置器），以及一个方便的Last属性来获取或设置最后一个项。

但是应该理解的是，InternalList仅用于少数需要比List<T>更好的性能的罕见情况。它确实存在主要缺点：

1. 您不得编写new InternalList<T>()，因为C#不支持struct的默认构造函数，而InternalList<T>需要非null初始化；Add()、Insert()和Resize()等方法假定_array不为null。正确的初始化方法是InternalList<T> list = InternalList<T>.Empty;。

2. 按值传递此结构是危险的，因为对结构副本的更改可能会或可能不会反映在原始列表中。特别是原始列表的_count不会改变，但_array的内容可能会改变。最好根本不要传递它，但如果必须传递，请按引用传递。这也意味着InternalList<T>不应通过任何public API公开，并且存储InternalList<T>在另一个集合中（例如Dictionary<object, InternalList<T>>）是可以的，但必须小心进行，以避免编写可以编译但不起作用的代码。

同样，根本问题在于，当您按值传递InternalList时，会复制_count和_array变量。对这些变量的更改不会影响其他副本，但对_array元素的更改会影响其他副本（顺便说一句，这与D语言中切片的变异行为类似）。如果您想从公共API返回一个内部列表，您可以将其强制转换为IList<T>或IReadOnlyList<T>，但请注意，您代码对InternalList的未来更改可能不会被使用IList<T>的客户端正确看到，反之亦然。

最后，与InternalList<T>并存的是一个static class InternalList，它包含一些静态方法（CopyToNewArray、Insert、RemoveAt、Move）来帮助管理原始数组。InternalList<T>的大多数方法只是调用InternalList的方法。

下载

InternalList<T>是Loyc.Essentials.dll的一部分，而Loyc.Essentials.dll是“LoycCore”NuGet包的一部分。

您可以在这里看到原始源代码，但不能直接将其复制到另一个项目中，因为它引用了Loyc.Essentials.dll中的几个外部项。因此，我制作了这个独立版本。尽情享用！

历史

• 大约在2008年：编写了InternalList<T>。
• 2014年8月13日：文章发布。