Почему AddRange быстрее, чем использование цикла foreach?

Question

var fillData = new List<int>();
for (var i = 0; i < 100000; i++)
{
     fillData.Add(i);
}

var stopwatch1 = new Stopwatch();
stopwatch1.Start();
var autoFill = new List<int>();
autoFill.AddRange(fillData);
stopwatch1.Stop();

var stopwatch2 = new Stopwatch();
stopwatch2.Start();
var manualFill = new List<int>();
foreach (var i in fillData)
{
    manualFill.Add(i);
}
stopwatch2.Stop();

Когда я беру 4 , получаемые из stopwach1 и stopwach2, stopwatch1 всегда имеет меньшее значение, чем stopwatch2.Это означает, что addrange всегда быстрее, чем foreach.Кто-нибудь знает почему?

Answer 1

Потенциально, AddRange может проверить, где переданное ему значение реализует IList или IList<T>. Если это так, он может узнать, сколько значений находится в диапазоне, и, следовательно, сколько места ему нужно выделить ... тогда как цикл foreach может потребоваться перераспределить несколько раз.

Кроме того, даже после выделения, List<T> может использовать IList<T>.CopyTo для выполнения массового копирования в базовый массив (для диапазонов, которые реализуют IList<T>, конечно.)

Я подозреваю, что вы обнаружите, что если вы попробуете свой тест еще раз, но вместо List<T> вместо *1016* будете использовать Enumerable.Range(0, 100000), то оба будут занимать примерно одинаковое время.

Answer 2

Если вы используете Add, он постепенно изменяет размер внутреннего массива по мере необходимости (удваивает), начиная с начального размера по умолчанию 10 (IIRC). Если вы используете:

var manualFill = new List<int>(fillData.Count);

Я ожидаю, что это радикально изменится (больше не нужно изменять размеры / копировать данные).

От отражателя AddRange делает это внутренне, а не удваивается:

ICollection<T> is2 = collection as ICollection<T>;
if (is2 != null)
{
    int count = is2.Count;
    if (count > 0)
    {
        this.EnsureCapacity(this._size + count);
        // ^^^ this the key bit, and prevents slow growth when possible ^^^

Answer 3

Поскольку AddRange проверяет размер добавляемых элементов и увеличивает размер внутреннего массива только один раз.

Answer 4

Разборка из отражателя для метода List AddRange имеет следующий код

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;
    }
}

Как вы можете видеть, есть некоторые оптимизации, такие как вызов EnsureCapacity () и использование Array.Copy ().

Answer 5

При использовании AddRange Коллекция может увеличить размер массива один раз, а затем скопировать в него значения.

Используя оператор foreach, коллекция должна увеличить размер коллекции более одного раза.

Увеличение размера означает копирование всего массива, что требует времени.

Answer 6

Это все равно, что попросить официанта принести вам одно пиво десять раз и попросить его принести вам 10 пива сразу.

Что ты думаешь быстрее?)

Answer 7

Полагаю, это результат оптимизации распределения памяти. для AddRange память выделяется только один раз, и в то время как foreach на каждой итерации перераспределение выполняется.

также может быть некоторая оптимизация в реализации AddRange (например, memcpy)

Answer 8

Это потому, что цикл Foreach будет добавлять все значения, которые цикл получает по одному, и
метод AddRange () соберет все значения, которые он получает, в виде «чанка» и сразу же добавит этот чанк в указанное место.

Просто понимая, это как если бы у вас был список из 10 предметов, которые можно было бы принести с рынка, что было бы быстрее, если бы все это доставлялось по одному или все одновременно.

Answer 9

Попробуйте инициализировать начальный объем списка, прежде чем вручную добавлять элементы:

var manualFill = new List<int>(fillData.Count); 

Answer 10

Расширение AddRange не выполняет итерацию по каждому элементу, но применяет каждый элемент в целом.Оба foreach и .AddRange имеют цель.Addrange победит в конкурсе скорости для вашей текущей ситуации.

Подробнее об этом здесь:

Addrange Vs Foreach