Nested Dictionary Size Growth

Question

I have a simple Dictionary<long, long> object which takes up 500 MB space when i populate 10 million entries in it. But when I use nested dictionary Dictionary<long, Dictionary<long, long>>, the same 10 million entries were taking 2.5 GB space. The internal dictionary was filled with only single entry.

Can someone help in explaining how the dictionary in .net is allocated memory and how does it grow in size?

Answer 1

If you look at the definition of Dictionary you'll see that it has quite a few members, so even an empty one will take more space than just the key and the element that are in it.

If you look at how it is initialized you'll come across the following function

private void Initialize(int capacity)
{
    int prime = HashHelpers.GetPrime(capacity);
    this.buckets = new int[prime];
    for (int i = 0; i < this.buckets.Length; i++)
    {
        this.buckets[i] = -1;
    }

    this.entries = new Entry<TKey, TValue>[prime];
    this.freeList = -1;
}

HashHelpers.GetPrime gets the next largest prime, so for an initial capacity of 0, the number 3 is returned. So the function will also create a bucket array of int with 3 elements and also an array of Entry of 3 elements.

Entry is a struct that is defined as:

[StructLayout(LayoutKind.Sequential)]
private struct Entry
{
    public int hashCode;
    public int next;
    public TKey key;
    public TValue value;
}

When you add an element, if there is enough space to add the element the dictionary remains the same size. If there is not, the dictionary is grown using this function:

public static int ExpandPrime(int oldSize)
{
    int min = 2 * oldSize;
    if ((min > 0x7feffffd) && (0x7feffffd > oldSize))
    {
         return 0x7feffffd;
    }

    return GetPrime(min);
}

The implementation of GetPrime is this:

[ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
public static int GetPrime(int min)
{
    if (min < 0)
    {
        throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow"));
    }

    for (int i = 0; i < primes.Length; i++)
    {
         int num2 = primes[i];
         if (num2 >= min)
         {
             return num2;
         }
    }

    for (int j = min | 1; j < 0x7fffffff; j += 2)
    {
        if (IsPrime(j) && (((j - 1) % 0x65) != 0))
        {
             return j;
        }
    }

    return min;
}

And the primes array is initialized as follows:

static HashHelpers()
{
    primes = new int[] { 
    3, 7, 11, 0x11, 0x17, 0x1d, 0x25, 0x2f, 0x3b, 0x47, 0x59, 0x6b, 0x83, 0xa3, 0xc5, 0xef, 
    0x125, 0x161, 0x1af, 0x209, 0x277, 0x2f9, 0x397, 0x44f, 0x52f, 0x63d, 0x78b, 0x91d, 0xaf1, 0xd2b, 0xfd1, 0x12fd, 
   0x16cf, 0x1b65, 0x20e3, 0x2777, 0x2f6f, 0x38ff, 0x446f, 0x521f, 0x628d, 0x7655, 0x8e01, 0xaa6b, 0xcc89, 0xf583, 0x126a7, 0x1619b, 
   0x1a857, 0x1fd3b, 0x26315, 0x2dd67, 0x3701b, 0x42023, 0x4f361, 0x5f0ed, 0x72125, 0x88e31, 0xa443b, 0xc51eb, 0xec8c1, 0x11bdbf, 0x154a3f, 0x198c4f, 
   0x1ea867, 0x24ca19, 0x2c25c1, 0x34fa1b, 0x3f928f, 0x4c4987, 0x5b8b6f, 0x6dda89
 };
}