Why doesn't Stack, Queue and List shrink the internal array after removing an item?

Question

In .NET, Stack, Queue and List (as well as their generic implementations) use an array internally to hold the items.

When adding new element, the size of the internal array doubles on Push(), Enqueue() or Add() if it is full.

The question is, why doesn't these data structures halve an internal array when item is being removed? It would be a good idea to halve the size of the array on Pop(), Dequeue() or Remove() if it is less than one-quarter full to prevent the waste of memory.

I used the following code to check this behavior:

var s = new Stack<int>();
for (int i = 0; i <= 512; i++) s.Push(i); // Increases the array capacity to 1024.
for (int i = 0; i <= 512; i++) s.Pop();   // Doesn't decrease array capacity.

// Stack is empty, but internal array capacity is still 1024:
var fieldInfo = typeof(Stack<int>).GetField("_array", BindingFlags.NonPublic | BindingFlags.Instance);
Console.WriteLine((fieldInfo.GetValue(s) as int[]).Length);

Answer 1

Most likely efficiency.

Shrinking and growing an array involves copying the array around in memory; you can't simply tag a small amount of new memory onto an existing allocation and subsequently remove it from an allocation: allocations are of a fixed size in the operating system, so if you want to increase the size of an array, you actually have to allocate a new block of memory, copy all the contents over from the source to the destination, and then delete the old allocation. It's a similar operation for shrinking as well. This can be time consuming.

Now given that an array has already grown to a given size, it's a good indicator for .NET (or any other framework) for the optimal size of that array. Even if items are removed from it, there's a chance that the array could grow to the same size again: .NET isn't Mystic Meg so won't know that you're never going to use blocks of that array again. So rather than constantly allocate and deallocate blocks of memory, it's more efficient to grow the allocation until it doesn't need to grow again, and then only worry about cleaning it up when the variable is goes out of scope and becomes a target for the GC.

Answer 2

Because often, when you shrink a list, it is only temporary, and you intend to allow it to grow again later. So removing the memory would incur a double cost: first, you have to release the current array and allocate a new, smaller one (and copy the contents to the new array). And then later on, you would have to release that again to allocate a bigger one (and then copy all the elements again).

At the same time, if you know that you want to permanently shrink a list, and the amount of memory saved is worth it, then you have a method for doing that: just allocate a new list and copy the relevant entries to that. So when you do want to shrink the list, you have a way to do that. But at the same time, the default behavior tries to avoid needless copies of data. There's generally no reason to copy data to a smaller array.