I'm trying to do the following:
int count = 50;
List<float> myList = new List<float>(50);
output[0] = 0.0f;
But I get the error:
ArgumentOutOfRangeException: Argument is out of range.
Parameter name: index
Clearly I've misunderstood what the initial capacity of a List (or perhaps any other collection?) does. Can someone please explain to me what the initial capacity is for?
A list has an array under the hood. This decreases the amount of memory reallocation as you .add up to your 50 elements. This takes time and memory and gives the garbage collector stuff to do.
That's why List(T).Capacity is a thing.
Here are some benchmarks for 100 .Adds:
Method A: Dictionary, no capacity
Time: 1350 ms
Method B: Dictionary, has capacity
Time: 700 ms
Method C: Dictionary, const capacity
Time: 760 ms
Method D: Dictionary, over-large capacity
Time: 1005 ms
Method E: List, no capacity
Time: 1010 ms
Method F: List, accurate capacity
Time: 575 ms
So when you're adding 100 elements, pre allocating seems to to half the time it takes. While I'm not a fan of premature optimisation, giving the CLR a hint if you know how big your list will be really sounds worth it.
First, why are you getting the exception:
By defining initial capacity, you just specify the number of elements a list can store before resizing is required.
That doesn't mean that you have accessible index in your list. Your list is still empty, so when you do:
myList[0] = 0.0f;
You get an exception, but if you do:
List<float> myList = new List<float>(50);
myList.Add(0);
myList[0] = 2.0f;
Now you will not get an exception because there is an element at index 0.
Now the second part of your question, What does Capacity actually mean:
See: List<T>.Capacity property:
Capacity is the number of elements that the List can store before resizing is required, whereas Count is the number of elements that are actually in the List.
Capacity is always greater than or equal to Count. If Count exceeds Capacity while adding elements, the capacity is increased by automatically reallocating the internal array before copying the old elements and adding the new elements.
The List is dynamic. It can add items and remove items dynamically at runtime.
The List implementation uses an underlying array for storing the list's items.
The underlying array's length is called the list's Capacity.
Each item in the list is stored in the underlying array.
When there is an attempt to add a new item to the list and there is no more empty spaces in the underlying array, then a new and a bigger array will be created.
All of the items in the old array will be moved to the new array, which also contains more space for new items.
Then the new array will be set as the underlying array of the list (the old one will be disposed).
This operation of allocating a new array and then moving the items from the old array to the new one is expensive (performance wise).
Therefore, if you know from the start how many items you are going to add to the list.Then you can create the List with an underlying array with the initial capacity you need.
And so there will be a smaller chance that your list will allocate a new underlying arrays during runtime.
You can set the underlying array's initial length by calling the List(T) Constructor(int32)
You can get the current array's length by calling the List(T).Capacity Property
The list is still empty, in that there are no elements, but internally it has reserved memory for 50 items. This is an optimization because as you add items to the list it has to allocate a new array twice that size, and then copy the items from the old array to the new one.
Note that during this transition, for example going from 256 items and adding one more, it has a total of (256+512) 768 items worth of memory allocated for that moment when it is copying to the new array. Essentially triple the previous capacity. Depending on the size of the array this might result in an out of memory exception. So if you knew up front that you would only be adding 257 items to the list, then you can use the capacity of 257 up front. This will avoid this tripled memory usage since the array will not have to grow in size since it is already large enough. Note the chances of out of memory exceptions occurring is increased by the fact that very large arrays are allocated on a heap that is not compacted, and thus fragmentation can lead to situations where it is difficult to find a contiguous block of memory for the entire array. So sometimes this issue leads you to experience out of memory exceptions when you seem to have plenty of free memory. Of course you'd probably want to avoid such large Lists if you can.
In summary, use capacity anytime you know in advance how many items you will be adding, or can estimate(probably padding a little larger).
It is used to pre-allocate the internal array used by the list. (The size of this internal array is given by List.Capacity.)
However, just because this internal array is of a certain size, doesn't mean that those elements of the list are available; they are not, until you (for example) use List.Add() to add the appropriate elements. The current addressable size of the list is given by List.Count.
When you add a new element to the list, it first checks if there's enough space in the internal array and if there is it just increments an internal counter and uses a slot from the internal array.
If there is not enough space, it allocates a new buffer twice the size of the old one, copies all the elements from the old buffer into the new one, and then discards the old buffer. It can then use a slot from the new buffer. This is obviously quite an expensive operation.
By setting an initial size, you can avoid some (or all) buffer reallocations.
A common use is when you know the maximum possible size of a list, but not the minimum size, and you want to fill the list while performing as few reallocations as possible.
