Реализация списка<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) оправдывает снижение производительности при проверке и приведении типов во время выполнения. Но что может быть причиной трех строк, которые я указал (*)? Я думаю, что это может быть переписано для более быстрой альтернативы:

is2.CopyTo(this._items, index);

Видите ли вы причину не использовать эту более простую и, очевидно, более быструю альтернативу?

Редактировать:

Спасибо за ответы. Таким образом, общее мнение заключается в том, что это защитная мера против набора ввода, реализующего CopyTo дефектным / злонамеренным образом. Мне кажется излишним постоянно платить цену: 1) проверка типа во время выполнения 2) динамическое выделение временного массива 3) двойная операция копирования, когда все это можно было бы сохранить, определив 2 или несколько дополнительных перегрузок InsertRange, получая IEnumerable как сейчас, второй получая List<T>Третье получение T[], Последние два могли быть реализованы так, чтобы бегать вдвое быстрее, чем в текущем случае.

Изменить 2:

Я реализовал класс FastList, идентичный List, за исключением того, что он также обеспечивает перегрузку AddRange, которая принимает аргумент T[]. Эта перегрузка не требует динамической проверки типов и двойного копирования элементов. Я сделал профиль этого FastList.AddRange для List.AddRange, добавив 4-байтовые массивы 1000 раз в список, который изначально был emtpy. Моя реализация превосходит скорость стандартного List.AddRange с коэффициентом 9 (девять!). List.AddRange занимает около 5% времени выполнения в одном из важных сценариев использования нашего приложения, замена List классом, обеспечивающим более быстрый AddRange, может улучшить время выполнения приложения на 4%.

Answer 1

Они мешают осуществлению ICollection<T> от доступа к индексам списка адресатов за пределами вставки. Реализация выше приводит к IndexOutOfBoundsException если неисправная (или "манипулятивная") реализация CopyTo называется.

Имейте в виду, что T[].CopyTo вполне буквально внутренне реализовано как memcpyТаким образом, производительность при добавлении этой строки составляет всего минуту. Когда у вас такая низкая стоимость повышения безопасности для огромного количества звонков, вы можете сделать это.

Редактировать: часть, которую я нахожу странным, это то, что призыв к ICollection<T>.CopyTo (копирование во временный массив) не происходит сразу после вызова EnsureCapacity, Если бы он был перемещен в это место, то после любого синхронного исключения список остался бы неизменным. Как есть, это условие выполняется только в том случае, если вставка происходит в конце списка. Аргументация здесь такова:

• Все необходимое распределение происходит перед изменением элементов списка.
• Призывы к Array.Copy не может потерпеть неудачу, потому что
  • Память уже выделена
  • Границы уже проверены
  • Типы элементов массивов источника и назначения совпадают
  • Здесь нет "конструктора копирования", как в C++ - это просто memcpy
• Единственные элементы, которые могут вызвать исключение, это внешний вызов ICollection.CopyTo и выделения, необходимые для изменения размера списка и выделения временного массива. Если все три из них происходят до перемещения элементов для вставки, транзакция для изменения списка не может вызвать синхронное исключение.
• Конечное примечание: этот адрес строго исключительное поведение - приведенное выше обоснование не добавляет потокобезопасности.

Правка 2 (ответ на правку ОП): Профилировали ли вы это? Вы делаете смелые заявления о том, что Microsoft должна была выбрать более сложный API, поэтому вы должны убедиться, что вы правы в утверждениях, что текущий метод медленный. У меня никогда не было проблем с производительностью InsertRangeи я вполне уверен, что любые проблемы с производительностью, с которыми кто-то сталкивается, будут лучше решены с помощью редизайна алгоритма, чем путем переопределения динамического списка. Просто, чтобы вы не воспринимали меня как грубого в негативном смысле, помните следующее:

• Я не хочу терпеть людей из моей команды разработчиков, которые любят изобретать квадратное колесо.
• Я определенно хочу, чтобы в моей команде были люди, которые заботятся о потенциальных проблемах с производительностью и задают вопросы о побочных эффектах, которые может иметь их код. Этот момент выигрывает, когда присутствует, но пока люди задают вопросы, я буду заставлять их превращать свои вопросы в твердые ответы. Если вы можете показать мне, что приложение получает значительное преимущество за счет того, что изначально кажется плохой идеей, то иногда так и происходит.

Answer 2

Это хороший вопрос, я изо всех сил пытаюсь найти причину. Там нет подсказки в справочном источнике. Одна возможность состоит в том, что они пытаются избежать проблемы, когда класс, который реализует метод ICollection<>.CopyTo(), не копирует в начальный индекс, отличный от 0. Или как мера безопасности, предотвращающая смешивание коллекции с элементами массива. он не должен иметь доступа к.

Другое - то, что это контрмера, когда коллекция используется потокобезопасным способом. Если элемент был добавлен в коллекцию другим потоком, то это будет метод CopyTo () класса коллекции, который завершится ошибкой, а не код Microsoft. Правильный человек получит сервисный звонок.

Это не великие объяснения.

Answer 3

Существует проблема с вашим решением, если вы подумаете об этом на минуту, если вы измените код таким образом, вы по сути дадите коллекции, которой следует добавить доступ к внутренней структуре данных.

Это не очень хорошая идея, например, если автор структуры данных List выясняет лучшую базовую структуру для хранения данных, чем массив, нет способа изменить реализацию List, поскольку вся коллекция ожидает массив в функцию CopyTo.,

По сути, вы бы цементировали реализацию класса List, хотя объектно-ориентированное программирование говорит нам, что внутренняя реализация структуры данных должна быть чем-то, что можно изменить, не нарушая другой код.