Dictionary and memory usage

Consider this code using Dictionary<TKey, TValue>:

private static void DictionaryTest()
{
    var c = new Dictionary<int, int>();
    Stopwatch stopwatch = Stopwatch.StartNew();
    for (int b = 1; b < 100000000; b <<= 1)
    {
        for (int i = 0; i < b; ++i)
        {
            c.Add(i, i);
        }

        // Get memory usage when full
        long mem1 = GC.GetTotalMemory(false);

        c.Clear();

        // Get memory usage after GC when empty
        int cap = GetCapacity(c);
        long mem2 = GC.GetTotalMemory(true);

        Console.WriteLine("[{0:0.000000}] {1:0000000000} -> {2:0000000000} (cap={3:00000000})", stopwatch.Elapsed.TotalSeconds, mem1, mem2, cap);
    }
}

private static int GetCapacity(Dictionary<int, int> c)
{
    var field = c.GetType().GetField("buckets", BindingFlags.NonPublic | BindingFlags.Instance);
    return ((int[])field.GetValue(c)).Length;
}

One might assume that the capacity (actually bucket count in this case) and memory usage will stabilize after repeatedly filling then clearing the collection. Unfortunately, this is not the case. Here is the output on my system (compiling in Release mode as a 64-bit EXE):

[0.000401] 0000055600 -> 0000046240 (cap=00000003)
[0.001003] 0000062624 -> 0000057784 (cap=00000003)
[0.001152] 0000065976 -> 0000057864 (cap=00000007)
[0.001283] 0000066056 -> 0000058064 (cap=00000017)
[0.001410] 0000066256 -> 0000058064 (cap=00000017)
[0.001546] 0000066256 -> 0000058464 (cap=00000037)
[0.001674] 0000066656 -> 0000059504 (cap=00000089)
[0.001801] 0000067696 -> 0000061664 (cap=00000197)
[0.001934] 0000078048 -> 0000066344 (cap=00000431)
[0.002072] 0000089288 -> 0000076104 (cap=00000919)
[0.002228] 0000123432 -> 0000096344 (cap=00001931)
[0.002421] 0000185616 -> 0000138704 (cap=00004049)
[0.002684] 0000315384 -> 0000226104 (cap=00008419)
[0.002906] 0000234296 -> 0000226104 (cap=00008419)
[0.003461] 0000584784 -> 0000408128 (cap=00017519)
[0.004278] 0001143496 -> 0000784808 (cap=00036353)
[0.005701] 0002301704 -> 0001566368 (cap=00075431)
[0.008462] 0004703384 -> 0003186488 (cap=00156437)
[0.013970] 0009683744 -> 0006546728 (cap=00324449)
[0.025663] 0020011576 -> 0013514288 (cap=00672827)
[0.049834] 0041427824 -> 0027963008 (cap=01395263)
[0.099440] 0085836264 -> 0057922728 (cap=02893249)
[0.205534] 0177920424 -> 0120047168 (cap=05999471)
[0.412975] 0360034456 -> 0240036728 (cap=11998949)
[0.831726] 0720003176 -> 0480015888 (cap=23997907)
[1.650525] 1439941256 -> 0959974808 (cap=47995853)
[3.272893] 2879817856 -> 1919892488 (cap=95991737)

As it turns out, memory just keeps growing and growing with the dictionary capacity never getting any smaller. (Side note, Doug Cook would probably roll his eyes at all those prime number bucket sizes.)

Unfortunately, Dictionary does not provide access to its Capacity or a TrimExcess() method like List does.

For this reason, if you need a dictionary which widely varies in size over its lifetime, you may want to consider replacing the old, worn out one occasionally with a fresh new one:

// Either replace the reference rather than clearing...
existing = new Dictionary<int, int>();

// ...or copy the contents to a new one
var newOne = new Dictionary<int, int>(existing);
existing = newOne;

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload the CAPTCHA.