Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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.

like image 214
Matt Davis Avatar asked Feb 22 '19 20:02

Matt Davis


People also ask

Is IEnumerable faster than list C#?

1) if you iterate elements from IEnumerable or List only one time, so both are same, no differences. 2) if you iterate elements many times, or if you get an one element for multiple times, so, IEnumerable will be slow.

What is AddRange in list C#?

An array of strings is created and passed to the constructor, populating the list with the elements of the array. The AddRange method is called, with the list as its argument. The result is that the current elements of the list are added to the end of the list, duplicating all the elements.

What is a list T?

The List<T> is a collection of strongly typed objects that can be accessed by index and having methods for sorting, searching, and modifying list. It is the generic version of the ArrayList that comes under System. Collections. Generic namespace.

What is AddRange in Linq?

List<T>. AddRange(IEnumerable<T>) Method is used to add the elements of the specified collection to the end of the List<T>.


1 Answers

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.

like image 148
Matt Davis Avatar answered Oct 16 '22 10:10

Matt Davis