How much memory does null pointer use?

Question

In C# if i use the following code

Dictionary<int,object> dictionary = new Dictionary<int, object>();
dictionary.Add(1,null);
dictionary.Add(2,new object());
dictionary[2] = null;

How much memory is being allocated? does each object reference in the dictionary (dictionary[1], dictionary[2]) takes a pointer size (32 or 64 bit) on the heap? in other words when i do dictionary.Add(1,null) does the CLR automatically create 2 allocations on the heap, one for the int and one for a null pointer?

Answer 1

The null pointer does not allocate any extra memory to store anything on the heap (since there is nothing to store). However, your dictionary has to store the null pointer itself, which takes just as much space as any other pointer.

Whether every add call results in new allocations (to store the pointer) or not depends on the Dictionary implementation. Usually, it has an internal array which gets re-sized as necessary.

In your example, I would assume that enough space for a few elements is already allocated when you create the dictionary. So the add(1, null) will not allocate any more space.

Update: The default initial capacity for Dictionary is not specified. In .NET 4.0, it starts out at 0, actually, so the first add will create the storage array.

Answer 2

In itself a null pointer will take up 4 or 8 bytes, depending on whether it is running as 32-bit or 64-bit, as you've surmised.

There can be more than this in a given collection. The implementation of Dictionary<TKey, TValue> uses both an array of Entry<TKey, TValue> structures, which contains two ints as well as the key and value, and also an array of integers used in indexing into that array. Hence even if there was no "growing room" (and there generally is) each entry would need 20bytes or 24bytes of memory (rather than just the 8 or 12 entailed by the size of the key and value), on top of the overhead for the dictionary itself (including the overhead of each array).

Other implementations and other collections will have other overheads. They may not even store a null for a null entry. null can be a useful way of indicating a value has not been written in which case a special value will indicate an actual value of null (particularly useful in lock-free dictionary implementations, where it can be useful to distinguish between not just an unset and set value, but between an unset, set, and partially set value).

All you can really say is that setting adding a value of null A) takes up some memory and B) does not take up the memory that with a non-null value would be taken up by the object itself. Even B) doesn't really hold, since if that object was also stored elsewhere, then there's no extra memory cost in having another reference elsewhere, beyond that of the reference itself, which makes the real cost of it the same as storing null.