CODEWITHSUNDEEP
c#.netperformancegenericsgeneric-list
Matt Davis
Matt Davis

Reputation: 46034

Why Extra Copy in List<T>.AddRange(IEnumerable<T>)?

I'm looking at the open source code for System.Collections.Generic.List<T>. The AddRange(IEnumerable<T>) method looks like this:

public void AddRange(IEnumerable<T> collection) {
     Contract.Ensures(Count >= Contract.OldValue(Count));
 
     InsertRange(_size, collection);
}

and the InsertRange(int, IEnumerable<T>) methods looks like this:

public void InsertRange(int index, IEnumerable<T> collection) {
    if (collection==null) {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
    }
        
    if ((uint)index > (uint)_size) {
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
    }
    Contract.EndContractBlock();

    ICollection<T> c = collection as ICollection<T>;
    if( c != null ) {
        int count = c.Count;
        if (count > 0) {
            EnsureCapacity(_size + count);
            if (index < _size) {
                Array.Copy(_items, index, _items, index + count, _size - index);
            }
                
            if (this == c) {
                Array.Copy(_items, 0, _items, index, index);
                Array.Copy(_items, index+count, _items, index*2, _size-index);
            }
            else {
                T[] itemsToInsert = new T[count];        // WHY?
                c.CopyTo(itemsToInsert, 0);              // WHY?
                itemsToInsert.CopyTo(_items, index);     // WHY?

                // c.CopyTo(_items, index);              // WHY NOT THIS INSTEAD???
            }
            _size += count;
        }             
    }
    else {
        using(IEnumerator<T> en = collection.GetEnumerator()) {
            while(en.MoveNext()) {
                Insert(index++, en.Current);                                    
            }                
        }
    }
    _version++;            
}

Assume we make a call like this:

var list1 = new List<int> {0, 1, 2, 3};
var list2 = new List<int> {4, 5, 6, 7};
list1.AddRange(list2);

When this hits InsertRange(int, IEnumerable<T>) internally, it ultimately hits the else condition highlighted by // WHY? comments.

Why is an array allocated, elements from list2 are copied into that temporary array, and then the elements are copied from that temporary array to the end of list1? Why the extra copy? Why not just copy the elements straight from list2 to the end of list1 using the ICollection<T>.CopyTo() method?

EDIT

I would respectfully submit that while the question is subject to speculation by those of us who did not write the code to begin with, there nevertheless is an answer to the question. There is a reason the code was written the way it was, and my hope was that someone with that knowledge might provide an explanation, even if only for historical purposes.

Upvotes: 11

Views: 379

Answers (1)

Matt Davis
Matt Davis

Reputation: 46034

As noted in the comments section by @OlivierJacot-Descombes, the extra copy in question has been removed in the current version of List.cs in the .NET Core Libraries (CoreFX) and replaced by the single copy version, i.e., c.CopyTo(_items, index);.

Thanks to @elgonzo and @IvanStoev for providing thought-provoking comments. Summing things up, it may be that this is simply an artifact of the evolution of List<T> and represents the best option at the time it was developed, but that is just a guess.

Upvotes: 1

Related Questions