Initial capacity of collection types, e.g. Dictionary, List

Certain collection types in .Net have an optional "Initial Capacity" constructor parameter. For example:

Dictionary<string, string> something = new Dictionary<string,string>(20);

List<string> anything = new List<string>(50);

I can't seem to find what the default initial capacity is for these objects on MSDN.

If I know I will only be storing 12 or so items in a dictionary, doesn't it make sense to set the initial capacity to something like 20?

My reasoning is, assuming that the capacity grows like it does for a StringBuilder, which doubles each time the capacity is hit, and each reallocation is costly, why not pre-set the size to something you know will hold your data, with some extra room just in case? If the initial capacity is 100, and I know I will only need a dozen or so, it seems as though the rest of that memory is allocated for nothing.

Solution 1:

If the default values are not documented, the reason is likely that the optimal initial capacity is an implementation detail and subject to change between framework versions. That is, you shouldn't write code that assumes a certain default value.

The constructor overloads with a capacity are for cases in which you know better than the class what number of items are to be expected. For example, if you create a collection of 50 values and know that this number will never increase, you can initialize the collection with a capacity of 50, so it won't have to resize if the default capacity is lower.

That said, you can determine the default values using Reflector. For example, in .NET 4.0 (and probably previous versions as well),

• a List<T> is initialized with a capacity of 0. When the first item is added, it is reinitialized to a capacity of 4. Subsequently, whenever the capacity is reached, the capacity is doubled.

• a Dictionary<T> is intialized with a capacity of 0 as well. But it uses a completely different algorithm to increase the capacity: it increases the capacity always to prime numbers.

Solution 2:

If you know the size, then tell it; a minor optimisation in most "small" cases, but useful for bigger collections. I would mainly worry about this if I am throwing a "decent" amount of data in, as it can then avoid having to allocate, copy and collect multiple arrays.

Most collections indeed use a doubling strategy.

Solution 3:

Checking the source, the default capacity for both List<T> and Dictionary<TKey, TValue> is 0.

Solution 4:

Another issue with the ConcurrentDictionary (currently) and using its constructor to set an initial size is that its performance appears to be hindered.

For example, here's some example code and benchmarks I tried.

I ran the code on my machine and got similar results.

That is, when the initial size is specified, it does nothing to increase the ConcurrentDictionary's speed when adding objects. Technically, I think it should because it doesn't have to take time or resources to resize itself.

Yes, it may not run as fast as a normal Dictionary, but I would still expect a ConcurrentDictionary with its initial size set to have consistent, faster performance than a ConcurrentDictionary that doesn't have its initial size set, especially when one knows in advance the number of items that are going to be added to it.

So the moral of the story is setting the initial size doesn't always guarantee a performance improvement.