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 相同，只是它还提供了一个 AddRange 的重载，它接受一个 T[] 参数。这种重载不需要动态类型验证和元素的双重复制。我确实通过将 4 字节数组添加到最初为 emtpy 的列表中 1000 次来针对 List.AddRange 分析此 FastList.AddRange。我的实现比标准 List.AddRange 的速度快了 9 倍（九倍！）。在我们应用程序的一个重要使用场景中，List.AddRange 占用了大约 5% 的运行时间，将 List 替换为提供更快 AddRange 的类可以将应用程序运行时间提高 4%。

4

3 回答 3

12

他们正在阻止实现在ICollection<T>插入范围之外访问目标列表的索引。上面的实现会导致IndexOutOfBoundsException一个错误（或“操纵”）的实现CopyTo被调用。

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

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

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

编辑 2（响应 OP 的编辑）：您对此进行了分析吗？您提出了一些大胆的主张，即 Microsoft 应该选择更复杂的 API，因此您应该确保您对当前方法缓慢的断言是正确的。我从来没有遇到过 的性能问题InsertRange，而且我很确定，与重新实现动态列表相比，重新设计算法可以更好地解决某人遇到的任何性能问题。为了不让您认为我以消极的方式严厉，请记住以下几点：

  • 我不想忍受我的开发团队中喜欢重新发明方轮的人。
  • 我绝对希望我的团队中的人关心潜在的性能问题，并就他们的代码可能产生的副作用提出问题。这一点在出现时会胜出——但只要人们提出问题，我就会促使他们将他们的问题变成可靠的答案。如果您可以向我展示一个应用程序通过最初看起来是一个坏主意的方式获得了显着优势，那么这就是有时事情的发展方式。
于 2010-01-23T15:37:56.973 回答
2

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

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

这些都不是很好的解释。

于 2010-01-23T13:39:28.570 回答
0

如果您考虑一下，您的解决方案就会出现问题，如果您以这种方式更改代码，您实际上是在为应该添加的集合提供对内部数据结构的访问权限。

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

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

于 2010-01-23T14:49:38.153 回答