Boxing and unboxing with generics

When it comes to collections, generics make it possible to avoid boxing/unboxing by utilizing actual T[] arrays internally. List<T> for example uses a T[] array to store its contents.

The array, of course, is a reference type and is therefore (in the current version of the CLR, yada yada) stored on the heap. But since it's a T[] and not an object[], the array's elements can be stored "directly": that is, they're still on the heap, but they're on the heap in the array instead of being boxed and having the array contain references to the boxes.

So for a List<int>, for example, what you'd have in the array would "look" like this:

[ 1 2 3 ]

Compare this to an ArrayList, which uses an object[] and would therefore "look" something like this:

[ *a *b *c ]

...where *a, etc. are references to objects (boxed integers):

*a -> 1
*b -> 2
*c -> 3

Excuse those crude illustrations; hopefully you know what I mean.

Your confusion is a result of misunderstanding what the relationship is between the stack, the heap, and variables. Here's the correct way to think about it.

• A variable is a storage location that has a type.
• The lifetime of a variable can either be short or long. By "short" we mean "until the current function returns or throws" and by "long" we mean "possibly longer than that".
• If the type of a variable is a reference type then the contents of the variable is a reference to a long-lived storage location. If the type of a variable is a value type then the contents of the variable is a value.

As an implementation detail, a storage location which is guaranteed to be short-lived can be allocated on the stack. A storage location which might be long-lived is allocated on the heap. Notice that this says nothing about "value types are always allocated on the stack." Value types are not always allocated on the stack:

int[] x = new int[10];
x[1] = 123;

x[1] is a storage location. It is long-lived; it might live longer than this method. Therefore it must be on the heap. The fact that it contains an int is irrelevant.

You correctly say why a boxed int is expensive:

The price of boxing is the need to create an object on the heap, copy the stack allocated integer to the new object and vice-versa for unboxing.

Where you go wrong is to say "the stack allocated integer". It doesn't matter where the integer was allocated. What matters was that its storage contained the integer, instead of containing a reference to a heap location. The price is the need to create the object and do the copy; that's the only cost that is relevant.

So why isn't a generic variable costly? If you have a variable of type T, and T is constructed to be int, then you have a variable of type int, period. A variable of type int is a storage location, and it contains an int. Whether that storage location is on the stack or the heap is completely irrelevant. What is relevant is that the storage location contains an int, instead of containing a reference to something on the heap. Since the storage location contains an int, you do not have to take on the costs of boxing and unboxing: allocating new storage on the heap and copying the int to the new storage.

Is that now clear?

Generics allows the list's internal array to be typed int[] instead of effectively object[], which would require boxing.

Here's what happens without generics:

1. You call Add(1).
2. The integer 1 is boxed into an object, which requires a new object to be constructed on the heap.
3. This object is passed to ArrayList.Add().
4. The boxed object is stuffed into an object[].

There are three levels of indirection here: ArrayList -> object[] -> object -> int.

With generics:

1. You call Add(1).
2. The int 1 is passed to List<int>.Add().
3. The int is stuffed into an int[].

So there are only two levels of indirection: List<int> -> int[] -> int.

A few other differences:

• The non-generic method will require a sum of 8 or 12 bytes (one pointer, one int) to store the value, 4/8 in one allocation and 4 in the other. And this will probably be more due to alignment and padding. The generic method will require only 4 bytes of space in the array.
• The non-generic method requires allocating a boxed int; the generic method does not. This is faster and reduces GC churn.
• The non-generic method requires casts to extract values. This is not typesafe and it's a bit slower.