List<T>.AddRange 实现不理想

StackOverflow https://stackoverflow.com/questions/2123161

题

对我的 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 次来针对 List.AddRange 分析 FastList.AddRange。我的实现比标准 List.AddRange 的速度快了 9 倍（九！）。在我们应用程序的重要使用场景之一中，List.AddRange 占用大约 5% 的运行时间，用提供更快 AddRange 的类替换 List 可以将应用程序运行时间提高 4%。

有帮助吗？

解决方案

他们正在阻止实施 ICollection<T> 访问插入边界之外的目标列表的索引。上面的实现结果是 IndexOutOfBoundsException 如果错误（或“操纵”）实施 CopyTo 叫做。

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

编辑： 我觉得奇怪的部分是调用 ICollection<T>.CopyTo （复制到临时数组）不会在调用后立即发生 EnsureCapacity. 。如果它被移动到该位置，则遵循任何 同步异常 该清单将保持不变。按原样，仅当插入发生在列表末尾时，该条件才成立。这里的推理是：

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

编辑2（对OP编辑的回应）： 您对此进行过简介吗？您大胆声称 Microsoft 应该选择更复杂的 API，因此您应该确保当前方法速度慢的断言是正确的。我从来没有遇到过性能问题 InsertRange, ，而且我非常确定，与重新实现动态列表相比，重新设计算法可以更好地解决某人遇到的任何性能问题。为了避免您认为我的态度是消极的严厉，请记住以下几点：

  • 我 不想要 无法忍受我的开发团队中喜欢这样做的人 重新发明方轮.
  • 我 确实 希望我的团队中的人关心潜在的性能问题，并询问有关他们的代码可能产生的副作用的问题。当这一点出现时，就会获胜——但只要人们提出问题，我就会促使他们将问题转化为可靠的答案。如果您可以向我展示应用程序通过最初看似糟糕的想法获得了显着的优势，那么有时事情就是这样的。

其他提示

这是个好问题，我正在努力找出理由。参考来源中没有任何提示。一种可能性是，当实现 ICollection<>.CopyTo() 方法对象的类反对复制到非 0 的起始索引时，它们会尝试避免出现问题。或者作为一种安全措施，防止集合弄乱它不应该访问的数组元素。

另一个原因是，这是以线程不安全方式使用集合时的一种对策。如果某个项目被另一个线程添加到集合中，则失败的是集合类的 CopyTo() 方法，而不是 Microsoft 代码。合适的人会接到服务电话。

这些都不是很好的解释。

如果您想一想，您的解决方案就会出现问题，如果您以这种方式更改代码，那么您实际上是在向应该添加对内部数据结构的访问权限的集合授予权限。

这不是一个好主意，例如，如果 List 数据结构的作者找到了比数组更好的底层结构来存储数据，则无法更改 List 的实现，因为所有集合都期望将数组放入 CopyTo 函数中。

本质上，您将巩固 List 类的实现，尽管面向对象编程告诉我们数据结构的内部实现应该是可以在不破坏其他代码的情况下进行更改的东西。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top