Since you need to input the length of an array at the time of creation, I assume that it requires a solid, continuous block of memory. A List can be dynamically expanded, so does this mean that it does NOT require contiguous memory allocation? Would this mean it is less likely for a List to throw an "Out of Memory" Exception?
3 Answers
No, it is more likely to run out of memory (assuming that you are comparing creating an array of the correct size with creating a default List and adding the items to it one at a time).
A List uses an array internally, and when it needs to resize it, it creates a new array twice the size of the original and copies the original into it and then frees the original array.
This means that there are two copies of the data in memory during the resize, meaning more likely to run out of memory.
You can avoid this for a List if you know the maximum size before creating the list, but in that case you could also use an array.
8 Comments
John3136
implicit in the above: An array will throw OOM on create if there isn't enough memory. A list will throw it at some point when you add an item. Those semantics might also influence your choice...
Tim Schmelter
I dont agree with
a list is more likely to run out of memory. If you want to compare both you need to compare a list with an array that will also be resized with a doubling algorithm or with the correct size. Then both behave similarly. However, the constraint that an array needs the exact size whereas a list just needs to be >= the minimum size causes ToArray to be less efficient in terms of memory consumption than ToList. Read: stackoverflow.com/a/16323412/284240
Matthew Watson
@TimSchmelter The OP implied that he was creating an array of a fixed size, but is allowing the list to dynamically expand. In that situation, the list is more likely to run out of memory. But of course if you are resizing an array manually then it has the same problem (assuming you resize it by doubling it like a list does).
Matthew Watson
@TimSchmelter I've clarified my answer to include the above assertion.
Adam Houldsworth
@All
List can be trimmed to size using TrimExcess: msdn.microsoft.com/en-us/library/ms132207.aspx But obviously this won't help you if the list is in the middle of growing. |
List<T> is a wrapper around T[]. That means a List<T> does need a contiguous memory region and more memory than a T[]. See the Answer of Matthew Watson for more details on this.
If you want to avoid OutOfMemoryExceptions, then instead of trying to cut you data structures into pieces, I suggest to run your program in 64bit mode, as it is more likely to run out of contiguous free ADDRESS SPACE rather than running out of physical RAM and SWAP nowadays. In order to run your program in x64 mode, compile it as anycpu (not prefering x86).
Raymond Chen, a programmer at Microsoft wrote a blog post about this: http://blogs.msdn.com/b/oldnewthing/archive/2013/06/28/10429807.aspx?Redirected=true#comments
Comments
In C# List is array-backed and not a linked list. It is like vector in C++. The list that does not require contiguous block of memory is LinkedList. However, be careful as it is known to be slower and more error prone.
See articles from Starcraft developers (a good read in itself): http://www.codeofhonor.com/blog/avoiding-game-crashes-related-to-linked-lists
List<T>is "almost always the right choice".