List<T>.AddRange实现亚优化

21

对我的C#应用程序进行性能分析表明,大量时间花费在List<T>.AddRange上。使用反编译工具Reflector查看该方法中的代码表明,它调用了List<T>.InsertRange,而后者的实现如下:

public void InsertRange(int index, IEnumerable<T> collection)
{
    if (collection == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
    }
    if (index > this._size)
    {
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
    }
    ICollection<T> is2 = collection as ICollection<T>;
    if (is2 != null)
    {
        int count = is2.Count;
        if (count > 0)
        {
            this.EnsureCapacity(this._size + count);
            if (index < this._size)
            {
                Array.Copy(this._items, index, this._items, index + count, this._size - index);
            }
            if (this == is2)
            {
                Array.Copy(this._items, 0, this._items, index, index);
                Array.Copy(this._items, (int) (index + count), this._items, (int) (index * 2), (int) (this._size - index));
            }
            else
            {
                T[] array = new T[count];          // (*)
                is2.CopyTo(array, 0);              // (*)
                array.CopyTo(this._items, index);  // (*)
            }
            this._size += count;
        }
    }
    else
    {
        using (IEnumerator<T> enumerator = collection.GetEnumerator())
        {
            while (enumerator.MoveNext())
            {
                this.Insert(index++, enumerator.Current);
            }
        }
    }
    this._version++;
}

private T[] _items;

有人认为界面的简单性(只有一个InsertRange重载)可以证明运行时类型检查和强制类型转换的性能开销。 但是,我标记的这3行代码有什么原因呢? 我认为它可以重写为更快的替代方案:

is2.CopyTo(this._items, index);

您看到使用这种更简单、看起来更快的替代方案没有任何理由不使用吗?

编辑:

感谢回答。因此,共识意见是这是一项防护措施,针对实现CopyTo的输入收集方式存在缺陷/恶意的情况。对我来说,似乎不必要地付出了以下代价:1)运行时类型检查 2)暂存数组的动态分配 3)复制操作加倍,当定义了2个或多个重载的InsertRange时,所有这些都可以得到节省,其中一个获取IEnumerable,第二个获取List<T>,第三个获取T[]。后两者可以实现两倍于当前情况的运行速度。

编辑2:

我实现了一个类FastList,与List相同,除了它还提供了一个接受T[]参数的AddRange的重载。这个重载不需要动态类型验证和双重复制元素。我通过将4字节数组1000次添加到最初为空的列表中来测试了这个FastList.AddRange。我的实现以9(九!)倍于标准List.AddRange的速度击败了它。在我们应用程序的一个重要使用场景中,List.AddRange占有大约5%的运行时间,用提供更快的AddRange的类替换List可以提高应用程序运行时间4%。


@shojtsy:确保你注意到我的第二次编辑 :) - Sam Harwell
你在测试中使用了最坏的情况。尝试使用Insert插入单个int,而不是使用InsertRange插入4字节数组,你会得到更大的提升。 - Sam Harwell
测试场景代表了我的应用程序中的实际使用情况。该列表是一个字节流,其中4-10个字节数组被多次追加。我知道将简单的数组传递给AddRange是标准实现性能惩罚最明显的地方。这正是我的观点。 - shojtsy
3个回答

12
他们正在阻止实现对插入位置之外的目标列表索引进行访问的ICollection<T>。上述实现如果调用了有误(或“操纵性”)的CopyTo,则会导致IndexOutOfBoundsException
请记住,T[].CopyTo 实际上是作为 memcpy 在内部实现的,因此添加该行的性能开销微不足道。当您在大量调用中添加安全性的成本非常低时,您可能也应该这样做。
编辑:我觉得奇怪的是对ICollection<T>.CopyTo的调用(复制到临时数组)并未紧随EnsureCapacity的调用。如果将其移动到该位置,则在任何同步异常之后,列表将保持不变。如今,只有在插入发生在列表末尾时才满足该条件。原因如下:
  • 在更改列表元素之前,所有必要的分配都会发生。
  • Array.Copy 的调用不可能失败,因为
    • 内存已经分配
    • 边界已经检查
    • 源数组和目标数组的元素类型匹配
    • 没有像 C++ 中那样使用“复制构造函数” - 它只是一个 memcpy
  • 唯一可能引发异常的项是对 ICollection.CopyTo 的外部调用以及需要调整列表大小和分配临时数组所需的分配。如果在移动元素进行插入之前这三个操作都发生了,那么更改列表的事务就不会抛出同步异常。
  • 最后说明: 这仅涉及严格的异常行为 - 上述理由并不添加线程安全性。

编辑 2(回应 OP 的编辑):您进行了性能测试吗?您做出了一些大胆的声明,认为微软应该选择更复杂的 API,因此您应该确保在当前方法速度缓慢的断言中是正确的。我从来没有遇到过 InsertRange 的性能问题,而且我相当确定,任何人遇到的性能问题都可以通过算法重新设计来更好地解决,而不是通过重新实现动态列表。这样你就不会认为我是以消极的方式苛刻对待你,记住以下事项:

  • 我不能忍受开发团队中喜欢重复造轮子的人。
  • 我绝对希望我的团队成员关心潜在的性能问题,并询问他们的代码可能产生的副作用。只要有人提出问题,我就会鼓励他们将问题变成确定的答案。如果你能向我展示一个应用程序通过最初看起来是一个坏主意而获得显着优势,那么这就是事情的发展方向。

CLR分配器非常快,临时数组很可能在达到第一代之前被收集,因此不应该会引起问题。 - Sam Harwell

2
这是个好问题,我很难找到原因。在参考源代码中没有任何提示。可能的一个原因是,它们试图避免实现ICollection<>.CopyTo()方法的类对象复制到非0起始索引时出现问题。或者作为安全措施,防止集合干扰它不应该访问的数组元素。
另一个原因是,当集合以线程不安全的方式使用时,这是一种对策。如果另一个线程向集合添加了一个项,则会失败的是集合类的CopyTo()方法,而不是Microsoft的代码。正确的人将得到服务调用。
这些并不是很好的解释。

List<T> 的成员明确声明为非线程安全。只要手动同步 List<T> 和要插入的项目集合,对 CopyTo 的调用就永远不会以危险的方式发生。 - Sam Harwell
1
是的,但那不是重点。重点是:当手机爆炸时,谁会接到电话。这对于像微软这样的公司来说是一个非常真实的关注点。这个热修复就是一个很好的例子,它实际上是客户端代码忘记锁定而触发的异常:http://support.microsoft.com/kb/831730 - Hans Passant
在上述情况下,原始代码和建议更改都不比另一个更加线程安全。奇怪的是,ICollection<T>.CopyTo 的调用并不紧跟在 EnsureCapacity 的调用之后 - 如果是这样的话,在任何同步异常发生时,列表将保持操作前的状态。 - Sam Harwell
这与线程安全无关,而是与在线程不安全的方式下使用时会出现什么问题有关。当前的List<>代码使集合的CopyTo()方法失败并引发异常。而建议的代码则会破坏List<>。 - Hans Passant
EnsureCapacity 不是线程安全的,并且设置 Capacity 确实允许缩小数组。根据插入点,两个调用 Insert 的线程实际上可能导致元素不仅在错误的位置,而且在例程结束时 _size 实际上大于 Capacity。在所有这些可能失败的地方中,线程安全性问题影响到 CopyTo 的调用的可能性比其他状态变量和内部数组要小。 - Sam Harwell

0

如果你仔细想一下,你的解决方案存在一个问题,如果你以那种方式改变代码,你实际上是给应该添加的集合访问内部数据结构的权限。

这不是一个好主意,例如,如果List数据结构的作者发现了一种更好的底层结构来存储数据,那么就没有办法改变List的实现,因为所有的集合都期望将数组传递到CopyTo函数中。

本质上,你会固定List类的实现,尽管面向对象编程告诉我们,数据结构的内部实现应该是可以更改而不会破坏其他代码的东西。


-1: 他在谈论现有的内部实现。该实现已经依赖于一个对象来实现ICollection<T>,以正确实现该接口的CopyTo成员。建议的替代方案既不增加也不删除这些假设。 - Sam Harwell
这是正确的,但这并不改变他的建议仍然会破坏List<T>内部数据结构的封装性,并且依赖于传入集合的正确实现。不能保证添加到列表中的集合具有良好或快速的CopyTo实现,更糟糕的是,它可能具有访问列表内部数据的实现,否则它将不会有并且不应该有,并且可以用来窃取不应该访问的数据。我相信我的观点仍然成立。 - Kjartan Þór Kjartansson
你的初始陈述是正确的,但你在第二和第三段提供的推理不是得出那个结论的原因。此外,你必须假设 ICollection<T>.CopyTo 的实现是正确的 - 这就是标准接口存在的原因。推理很简单,托管 VM 中的一个主要目标是为非法内存访问获取越界异常,而这是一种廉价的方法。 - Sam Harwell
很遗憾,框架没有提供一些标准的密封CopyableArray类,其中包含一个System.Array引用并包括一个CopyTo方法,该方法将指定范围的数组复制到目标数组。这样的类将允许基于数组的集合彼此高效地复制数据,而不会暴露对其内部数组的引用(将数组引用传递给保证不会持久化它的非虚拟框架方法不会违反封装)。 - supercat

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接