Субоптимальная реализация <T>.AddRange списка

Профилирование моего приложения C# указало то значительное время, потрачен в List<T>.AddRange. Используя Отражатель для рассмотрения кода в этом методе указал, что он звонит 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) выравнивает по ширине производительность наверху типа выполнения cheching и кастинга. Но что могло быть причиной позади этих 3 строк, я указал с (*) ? Я думаю, что это могло быть переписано к более быстрой альтернативе:

is2.CopyTo(this._items, index);

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

Править:

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

Редактирование 2:

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

20
задан shojtsy 29 January 2010 в 21:38
поделиться

3 ответа

Они препятствуют реализации ICollection доступа к индексам списка получателей вне пределов вставки. В результате реализации вышеприведенной реализации IndexOutOfBoundsException, если вызывается ошибочная (или "манипулятивная") реализация CopyTo, то это приводит к появлению IndexOutOfBoundsException.

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

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

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

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

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

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

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

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

0
ответ дан 30 November 2019 в 01:26
поделиться

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

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

Это не отличные объяснения.

2
ответ дан 30 November 2019 в 01:26
поделиться
Другие вопросы по тегам:

Похожие вопросы: