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?
Asked
Active
Viewed 3,421 times
5
-
Assuming you mean a List
here from the BCL, it uses an array internally. You could of course write your own list that uses smaller chunks. – usr Sep 06 '13 at 09:38 -
[`List
` is "almost always the right choice"](http://stackoverflow.com/a/434765/1386111). – Alvin Wong Sep 06 '13 at 09:42
3 Answers
9
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.
Matthew Watson
- 104,400
- 10
- 158
- 276
-
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... – John3136 Sep 06 '13 at 09:39
-
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: http://stackoverflow.com/a/16323412/284240 – Tim Schmelter Sep 06 '13 at 09:57
-
@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 Sep 06 '13 at 10:26
-
@TimSchmelter I've clarified my answer to include the above assertion. – Matthew Watson Sep 06 '13 at 10:34
-
@All `List` can be trimmed to size using `TrimExcess`: http://msdn.microsoft.com/en-us/library/ms132207.aspx But obviously this won't help you if the list is in the middle of growing. – Adam Houldsworth Sep 06 '13 at 10:38
-
@AdamHouldsworth Indeed, but even when you call TrimExcess it ends up with two copies of the data in memory during the resize. – Matthew Watson Sep 06 '13 at 10:40
-
I'm actually trying to create an array or list by splitting a very large string. In this case, I wouldn't manually supply the array size anyway. For splitting a string, is an array or a list
better? – Aeon2058 Sep 06 '13 at 11:29 -
@Aeon2058 It's difficult to say without knowing more about the context, but my default would be to use a `List<>` – Matthew Watson Sep 06 '13 at 11:38
1
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
Zotta
- 2,513
- 1
- 21
- 27
0
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
