Why can arrays not be trimmed?

Solution 1:

Unused memory is not actually unused. It is the job of any heap implementation to keep track of holes in the heap. At a minimum, the manager needs to know the size of the hole and needs to keep track of their location. That always costs at least 8 bytes.

In .NET, System.Object plays a key role. Everybody knows what it does, what isn't so obvious that it continues to live on after an object is collected. The two extra fields in the object header (syncblock and type handle) then turn into a backward and forward pointer to the previous/next free block. It also has a minimum size, 12 bytes in 32-bit mode. Guarantees that there is always enough space to store the free block size after the object is collected.

So you probably see the problem now, reducing the size of an array does not guarantee that a hole is created that's big enough to fit those three fields. Nothing it could do but throw a "can't do that" exception. Also depends on the bitness of the process. Entirely too ugly to consider.

Solution 2:

To answer your question it has to do with the design of the memory management system.

In theory if you were writing your own memory system you could totally design it to behave exactly the way you said.

The question then becomes why wasn't it designed that way. The answer is that the memory management system made a trade off between efficient use of memory versus performance.

For example most memory management systems don't manage memory down to the byte. Instead they break up the memory into 8 KB chunks. There are bunch of reasons for this most of which are around performance.

Some of the reason have to do with how well the processor moves memory around. For example let's say that the processor was much better at copying 8 KB of data at a time then it was at copying 4 KB. Then there is a performance benefit to storing the data in 8 KB chunks. That would be a design trade off based on CPU architecture.

There are also algorithmic performance trade offs. For example say from studying the behavior of most applications you find that 99% of the time applications allocate blocks of data that are 6 KB to 8 KB in size.

If the memory system allowed you to allocate and release 4KB it would be left with a with free 4KB chunk that 99% of allocations won't be able to use. If instead of over allocated to 8 KB even though only 4KB were needed it would be much more reusable.

Consider yet another design. Say you had a list of free memory locations which could be of any size and a request was made to allocate 2KB of memory. One approach would be to look through your list of free memory and find one that is at least 2KB in size, but do you look through the whole list to find that smallest block, or you do find the first one that is big enough and use that.

The first approach is more efficient, but slower, the second approach is less efficient but faster.

It gets even more interesting in languages like C# and Java that have "managed memory". In a managed memory system the memory isn't even freed; it just stops getting used, which the garbage collector later, in some cases much later, detects and frees.

For more information different memory management and allocation you might want to check out this article on Wikipedia:

https://en.wikipedia.org/wiki/Memory_management

Solution 3:

I was looking for an answer to your question since I found it a very interesting question. I found this answer which has an interesting first line:

You can't free part of an array - you can only free() a pointer that you got from malloc() and when you do that, you'll free all of the allocation you asked for.

So actually the problem is the register that keeps which memory is allocated. You can't just free a part of the block you have allocated, you have to free it entirely or you don't free it at all. That means in order to free that memory, you have to move the data first. I don't know if .NET memory management does something special in this regard, but I think this rule applies to the CLR too.