Boxing and unboxing with generics

Question

The .NET 1.0 way of creating collection of integers (for example) was:

ArrayList list = new ArrayList(); list.Add(i);          /* boxing   */ int j = (int)list[0]; /* unboxing */ 

The penalty of using this is the lack of type safety and performance due to boxing and unboxing.

The .NET 2.0 way is to use generics:

List<int> list = new List<int>(); list.Add(i); int j = list[0]; 

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

How does the use of generics overcome this? Does the stack-allocated integer stays on the stack and being pointed to from the heap (I guess this is not the case because of what will happen when it will get out of scope)? It seems like there is still a need of copying it somewhere else out of the stack.

What is really going on?

Answer 1

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.

Answer 2

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?