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

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%.

Это было полезно?

Решение

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

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

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

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

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

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

Другие советы

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

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

Это не очень хорошие объяснения.

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top