c# - List.AddRange 实现次优

Question

分析我的 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;

有人会争辩说接口(interface)的简单性(只有一个 InsertRange 重载)证明了运行时类型检查和转换的性能开销是合理的。但是我用 (*) 表示的 3 行背后的原因可能是什么？ ？我认为它可以重写为更快的替代方案:

is2.CopyTo(this._items, index);

您认为有什么理由不使用这种更简单且显然更快的替代方案吗？

编辑:

感谢您的回答。因此，一致认为这是一种保护措施，可防止以有缺陷/恶意的方式实现 CopyTo 的输入集合。对我来说，不断付出以下代价似乎有点矫枉过正:1) 运行时类型检查 2) 临时数组的动态分配 3) 复制操作加倍，而所有这些都可以通过定义 2 个或更多 InsertRange 重载来保存, 一得到 IEnumerable和现在一样，第二个获得 List<T> , 第三次得到T[] .后两者的实现速度可能是当前情况的两倍。

编辑 2:

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

Answer 1

他们正在阻止 ICollection<T> 的实现从访问插入范围之外的目标列表的索引。上面的实现导致 IndexOutOfBoundsException如果 CopyTo 的错误(或“操纵”)实现被称为。

请记住 T[].CopyTo实际上在内部实现为 memcpy ，因此添加该行的性能开销很小。当您以如此低的成本为大量调用增加安全性时，您不妨这样做。

编辑: 我觉得奇怪的部分是对 ICollection<T>.CopyTo 的调用(复制到临时数组)不会在调用 EnsureCapacity 后立即发生.如果它被移动到那个位置，那么跟随任何 synchronous exception该 list 将保持不变。按原样，该条件仅在插入发生在列表末尾时成立。这里的推理是:

• 所有必要的分配都发生在更改列表元素之前。
• 调用Array.Copy不能失败因为
  • 内存已经分配
  • 边界已经检查过
  • 源数组和目的数组的元素类型匹配
  • 没有像 C++ 中那样使用的“复制构造函数”——它只是一个 memcpy
• 唯一可以抛出异常的项目是对 ICollection.CopyTo 的外部调用以及调整列表大小和分配临时数组所需的分配。如果所有这三个都发生在为插入而移动元素之前，则更改列表的事务不能抛出同步异常。
• 最后说明:这解决了严格的异常行为 - 上述基本原理不增加线程安全。

编辑 2(对 OP 编辑​​的回应):您对此进行了分析吗？您大胆地声称 Microsoft 应该选择更复杂的 API，因此您应该确保当前方法速度慢的断言是正确的。我从来没有遇到过 InsertRange 的性能问题，而且我很确定，与重新实现动态列表相比，重新设计算法可以更好地解决某人确实面临的任何性能问题。为了不让您认为我在消极方面很苛刻，请记住以下几点:

• 我 不想 无法忍受我的开发团队中喜欢reinvent the square wheel的人.
• 我绝对希望我的团队中的人关心潜在的性能问题，并询问有关他们的代码可能产生的副作用的问题。这一点在出现时胜出 - 但只要人们提出问题，我就会促使他们将他们的问题转化为可靠的答案。如果您能向我展示一个应用程序通过最初看起来是个坏主意而获得显着优势，那么事情有时就是这样。