Efficiency of ToList()

Question

A lot of the developers I work with feel more comfortable working with a List as opposed to IEnumerable (for example). I am wondering whether there is any performance impact for ToList() overuse. For example, or, will use ToList() after ordering to get a list back out again i.e.

private void ListThinger(List<T> input)
{
  input = input.OrderBy(s => s.Thing).ToList();
  foreach(var thing in input)
  {
      // do things
  }
}

My question is:

How efficient is the ToList() method? Will it create a new list and how much memory does that take, assuming the contents are POCOs? Does this change if its a value type rather than a POCO?
Will the size of the list determine efficiency or does size of list not determine cost of ToList()?
If a list is cast to an IEnumerable and then ToList() is called on it, will it just return the original object?

P.s. I understand that a single use of ToList won't break any backs, but we are building a highly concurrent system that is currently CPU bound so I am looking for little wins that, when scaled, will add up to a big improvement

As documentation says it **Creates** a `List` from an `IEnumerable`. So question 1p2 and 3 are already answered (your first question is actually 4 questions, which should be split apart) — Sergey Berezovskiy, Sep 14 '17 at 12:31
In your specific example, the `ToList` should be removed since it adds no value (since all you do is iterate over it a single time). — mjwills, Sep 14 '17 at 12:32
`If a list is cast to an IEnumerable and then ToList() is called on it, will it just return the original object?` No. — mjwills, Sep 14 '17 at 12:32
Possible duplicate of [Is there a performance impact when calling ToList](https://stackoverflow.com/q/15516462/69809). — vgru, Sep 14 '17 at 12:33
`ToList()` is very efficient. Calling it when you don't need to is inefficient. — Matthew Watson, Sep 14 '17 at 12:45

Gilad Green · Answer 1 · 2017-09-14T12:50:23.400

How efficient is the ToList() method? Will it create a new list and how much memory does that take, assuming the contents are POCOs? Does this change if its a value type rather than a POCO?

The ToList() method materializes the given collection by creating a new list and populating it with the items of the given collection. Linq.ToList() implementation:

public static List<TSource> ToList<TSource>(this IEnumerable<TSource> source) {
    if (source == null) throw Error.ArgumentNull("source");
    return new List<TSource>(source);
}

By doing so you are not gaining the power of deffered execution if needed

Will the size of the list determine efficiency or does size of list not determine cost of ToList()?

As it calls Lists copy constructor and it creates a new list then it'll work on each of the items. So it'll run in O(n) - meaning that list's size matters. MSDNs documentation about the operation of the copy constructor:

Initializes a new instance of the List class that contains elements copied from the specified collection and has sufficient capacity to accommodate the number of elements copied.

As @Jason mentioned in the comment bellow the Copy Constructor is smart and is efficient but doing it when not needed is still an O(n) operation that doesn't have to happen

If a list is cast to an IEnumerable and then ToList() is called on it, will it just return the original object?

No. It will create a new list as seen above

As for your example code:

input = input.OrderBy(s => s.Thing).ToList();
foreach(var thing in input)
{
   // do things
}

As you are getting a materialized list (rather than an IQueriable/IEnumerable that might perform in deffered execution) adding the ToList after the adding gives you no benefit.

You can look here, might also help: When to use LINQ's .ToList() or .ToArray()

May at least be worth noting that in the constructor, it tries to be somewhat efficient by using the `Array.CopyTo` if it can cast to `ICollection`, which while still O(n), it is more efficient than you can do yourself since it uses unmanaged internal `Copy` method. — Jason W, Sep 14 '17 at 12:45
Not as efficient as the new `ToArray` stuff in .NET core that creates a linked list of buffers, instead of doing copy-resize whenever the internal array runs out. It does a full iteration capturing all elements in a cluster of buffers, then copies them all into the final array at the end. — Adam Houldsworth, Sep 14 '17 at 12:58
@AdamHouldsworth and with `OrderBy` if the source is fixed-length then it doesn't even need that linked list as it knows the size to begin with, (an efficiency also used with `ToList()` in such cases) but even the most efficient `ToList()` is going to be less efficient than not doing one when it gains nothing. — Jon Hanna, Sep 14 '17 at 13:00

score 1 · Answer 2 · edited Sep 19 '17 at 17:46

Yes is creates a new list. It is hard to accurately measure the memory usage but it is likely to be class size + (system word size * element count). I recommend a memory profiler.
Algorithmic efficiency of operations will of course be impacted by the element count
Yes, you get a brand new list every time. References inside are not duplicated but primitives are.

Try it yourself:

var list = new List<int>();
bool areListsTheSame = list == ((IEnumerable<int>)list).ToList();

Efficiency of ToList()

2 Answers2