List <T> .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;

可以说,接口的简单性(只有一个InsertRange的重载)证明了运行时类型切换和转换的性能开销.但是,我指出的3条线路背后的原因是(*)什么？我认为它可以改写为更快的替代方案:

is2.CopyTo(this._items, index);

你认为没有理由不使用这种更简单,更明显更快的替代方案吗？

编辑:

谢谢你的回答.因此,一致意见认为,这是针对以缺陷/恶意方式实施CopyTo的输入集合的保护措施.对我来说,不断付出代价1)运行时类型检查2)临时数组的动态分配3)复制操作的两倍,当所有这些都可以通过定义2或更多的InsertRange重载来保存时一个IEnumerable像现在一样,第二个得到一个List<T>,第三个得到T[].后两个可能已经实现,运行速度是当前情况的两倍.

编辑2:

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

Answer 1

它们阻止了ICollection<T>在插入范围之外访问目标列表的索引的实现.上面的实现导致调用IndexOutOfBoundsException错误(或"操纵")实现CopyTo.

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

编辑:我发现奇怪的部分是在调用后ICollection<T>.CopyTo不会立即调用(复制到临时数组)EnsureCapacity.如果它被移动到该位置,则在任何同步异常之后,列表将保持不变.原样,只有当插入发生在列表的末尾时,该条件才成立.这里的推理是:

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

编辑2(对OP编辑的回应):你有没有对此进行分析？您正在做出一些大胆的声明,即Microsoft应该选择更复杂的API,因此您应该确保在当前方法速度慢的断言中是正确的.我从未遇到过性能方面的问题InsertRange,而且我很确定通过重新设计算法而不是通过重新实现动态列表,可以更好地解决某人遇到的任何性能问题.所以你不要以负面的方式对我采取严厉的态度,请记住以下几点:

• 我不想让我的开发团队的人们不喜欢重新发明方形轮.
• 我绝对希望我的团队中的人关注潜在的性能问题,并询问他们的代码可能产生的副作用.这一点在出现时胜出 - 但只要人们提出问题,我就会驱使他们将问题转化为可靠的答案.如果你可以告诉我一个应用程序通过最初似乎是一个坏主意获得了显着的优势,那么这就是事情的发展方式.