High memory consumption with Enumerable.Range?

Question

Originally i wanted to know whether ToList allocates more memory than using the constructor of List<T> which takes an IEnumerable<T> (no difference).

For test purposes i used Enumerable.Range to create a source array that i could use to create an instance of List<int> via 1.ToList and 2.constructor. Both are creating copies.

This is how I came to notice a great difference in memory consumption between:

1. Enumerable.Range(1, 10000000) or
2. Enumerable.Range(1, 10000000).ToArray()

When i use the first and call ToList the resulting object ineeds ~60% more memory than the Array(38,26MB/64MB).

Q: What is the reason for this or where is my error in reasoning?

var memoryBefore = GC.GetTotalMemory(true);
var range = Enumerable.Range(1, 10000000);
var rangeMem = GC.GetTotalMemory(true) - memoryBefore; // negligible
var list = range.ToList();
var memoryList = GC.GetTotalMemory(true) - memoryBefore - rangeMem;

String memInfoEnumerable = String.Format("Memory before: {0:N2} MB List: {1:N2} MB"
    , (memoryBefore / 1024f) / 1024f
    , (memoryList   / 1024f) / 1024f);
// "Memory before: 0,11 MB List: 64,00 MB"

memoryBefore = GC.GetTotalMemory(true);
var array = Enumerable.Range(1, 10000000).ToArray();
var memoryArray = GC.GetTotalMemory(true) - memoryBefore;
list = array.ToList();
memoryList = GC.GetTotalMemory(true) - memoryArray;

String memInfoArray = String.Format("Memory before: {0:N2} MB Array: {1:N2} MB List: {2:N2} MB"
   , (memoryBefore / 1024f) / 1024f
   , (memoryArray  / 1024f) / 1024f
   , (memoryList   / 1024f) / 1024f);
// "Memory before: 64,11 MB Array: 38,15 MB List: 38,26 MB"

Burgin

Just an FYI, you could also just call list.TrimExcess(); on line 5 instead of initializing list to the exact size. – Dinky

@Marc: Yes, but therefor you need to know first that it might be useful here. As Marc Gravell has noted, another way is to initialize the list with range.Count() and use AddRange(range) afterwards. – Burgin

Answer 1

This probably relates to the doubling algorithm used to resize the backing buffer when adding to a list. When you allocate as an array, the length of that is known, and can be queried by checking for IList[<T>] and/or ICollection[<T>]; thus it can allocate a single array, right-sized the first time, and then just block-copy the contents.

With the sequence this is not possible (the sequence does not expose the length in any accessible way); thus it must instead fall back to "keep filling up the buffer; if full, double it and copy".

Obviously this needs approx double the memory.

An interesting test would be:

var list = new List<int>(10000000);
list.AddRange(Enumerable.Range(1, 10000000));

This will allocate the right size initially, while still using the sequence.

tl;dr; the constructor, when passed a sequence, first checks to see if it can obtain the length by casting to a well-known interface.

Edelmiraedelson

Answer 2

List is implemented as an array. When you exceed what it has allocated, it allocates another array double the size (essentially doubling the memory allocation). The default capacity is 4, and it doubles things from here on.

Most likely if you drop the number of items to say 7,500, you'll see the array drop to a little under 32 MBs, and the IList size to be 32 MBs.

You can tell IList<T> what the initial size should be, which is why if you give it the IEnumerable<T> at construction time, it shouldn't over allocate memory.

[Edit] after comments

In the case of Enumerable.Range(a, b) it returns an IEnumerable<T> only rather than an ICollection<T>. For List<T> to not overallocate the item passed during construction must also be an ICollection<T>

Walkout

which is why if you give it the IEnumerable<T> at construction time, it shouldn't over allocate memory. This is incorrect. It will only not overallocate when the IEnumerable<T> is also an ICollection<T> – Dinky

@Dinky deserves an upvote, that's correct. Given Enumerable.Range returns an IEnumerable and doesn't appear to return an ICollection, Enumerater.Range(a, b).ToList() will always overallocate. – Walkout

A List doesn't have linked arrays. When one fills up it makes a new, bigger one, and then the old one is left for garbage collection, rather than a linked list of buffers (which is what StringBuider does if anyone cares). – Kike

Answer 3

It's because of the doubling algorithm used to create the backing array in a List. IEnumerable has no Count property so it can't pre-allocate the backing array to be the target size when you call ToList. In fact, on each call to MoveNext you are calling a corresponding Add on the List.

However Array.ToList can override the base ToList behaviour to initialise the list to the correct capacity. Also, it could be the List in it's constructor which tries to downcast the IEnumerable reference it has to known collection types such as IList, ICollection, Array, etc...

Update

In fact it is in the constructor of List that it figures out if the argument implements ICollection:

public List(IEnumerable<T> collection)
{
  if (collection == null)
    ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
  ICollection<T> collection1 = collection as ICollection<T>;
  if (collection1 != null)
  {
    int count = collection1.Count;
    if (count == 0)
    {
      this._items = List<T>._emptyArray;
    }
    else
    {
      this._items = new T[count];
      collection1.CopyTo(this._items, 0);
      this._size = count;
    }
  }
  else
  {
    this._size = 0;
    this._items = List<T>._emptyArray;
    foreach (T obj in collection)
      this.Add(obj);
  }
}

Eusebiaeusebio

Answer 4

I guess that:

• Enumerable.Range(1, 10000000) only creates an IEnumerable and doesn't create items yet.

• Enumerable.Range(1, 10000000).ToArray() creates an array, using memory for the numbers

• Enumerable.Range(1, 10000000).ToList() creates the numbers and additional data to manage the list (links between parts. The list can change its size and needs to allocate memory in blocks).

Plastid