List memory allocation with initial capacity

Question

I'm trying to understand how a C# .NET 4.0 List<T>(initSize) allocates memory.

My problem is that I have a List<foo> where class foo needs at least 20 bytes of memory. I have two cases where I'll end up having either X or X+60 elements of foo. I don't know at allocation time which of the two cases it will be.

Since X is greater than 36,000 elements, I'm trying to minimize unnecessary memory allocations, and I don't want to allocate twice for one List if I can avoid it. My understanding is the size of the allocation (36k elements * 4B reference ~= 144kB) pushes the allocation on the large heap. Adding to my woes is that I have a Dictionary<key, List<foo>> with roughly 4,000 elements.

My questions:

Does the C# run-time allocate an amount beyond the initial, specified capacity? For example, if I initialize to 36,000 entries, do I really have 65,536 entries allocated since that's the next power of 2 greater than 36,000?
Should I just allocate to X+60 in all cases instead of X to avoid a 2nd allocation? 60 happens to be a constant value in this case that won't vary.

My question is similar, but different from the following:

Memory allocation for collections in .NET - because they do not initialize the List<T> in this question.

Initial capacity of collection types, e.g. Dictionary, List - is an implementation issue in specifying initial capacity.

How to initialize a List<T> to a given size (as opposed to capacity)? - appears to be wrestling with Array vs List<T>, which is not my issue.

For the record the limit for LOH allocations is 85000 bytes. — Brian Rasmussen, Sep 09 '13 at 15:06
Except for doubles, for which the threshold is only 1000 elements (8K bytes) — Matthew Watson, Sep 09 '13 at 15:09
Well, there is one unnecessary field inside the Dictionary class that is not being used thus it add a little bit of memory allocation — 123 456 789 0, Sep 09 '13 at 15:10
How big is each `foo`? If each one is less than 85000 bytes as @BrianRasmussen indicated, then they will not be stored on the LOH. I'm not sure how the runtime will handle the List itself. It may end up on the LOH. — Chris Dunaway, Sep 09 '13 at 15:12
@ChrisDunaway `foo` is approximately 20B. And it's the `List` allocation I'm worried about, not the `foo` allocation. I have 4000 `List`s to deal with. `List` will definitely be on the LOH per some of the comments. `foo` allocs should not be. — , Sep 09 '13 at 15:13

Brian Rasmussen · Accepted Answer · 2013-09-09T15:16:54.643

The compiler doesn't allocate anything. Allocation happens at run-time. The way List<T> works is that it will double the size of its internal T[] as needed. If you specify an initial size it will allocate that and double from there as needed.

Keep in mind since T is class in your example, the list only holds references. I.e. the list will only be allocated on LOH when you have more than 85000 bytes worth of references (plus the overhead of the list itself).

Also, since the list doesn't hold instances of foo the excess space is just for the references.

score 4 · Answer 2 · answered Sep 09 '13 at 15:11

The implementation is like this:

public List(int capacity)
{
    if (capacity < 0x0)
    {
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
    }
    if (capacity == 0x0)
    {
        this._items = List<T>._emptyArray;
    }
    else
    {
        this._items = new T[capacity];
    }
}

So it will use the exact capacity. Whether this will be true in the future is uncertain, since it's not defined by the List interface.

List memory allocation with initial capacity

2 Answers2