Why can arrays not be trimmed?

On the MSDN Documentation site it says the following about the Array.Resize method:

> If newSize is greater than the Length of the old array, a new array is > allocated and all the elements are copied from the old array to the > new one. > > If newSize is less than the Length of the old array, a new array is > allocated and elements are copied from the old array to the new one > until the new one is filled; the rest of the elements in the old array > are ignored.

An array is a sequence of adjoined memory blocks. If we need a bigger array I understand that we cannot add memory to it since the memory next to it may already be claimed by some other data. So we have to claim a new sequence of adjoined memory blocks with the desired bigger size, copy our entries there and remove our claim of the old space.

But why create a new array with smaller size? Why can the array not just remove its claim of the last memory blocks? Then it would be an O(1) operation instead of O(n), as it is now.

Does it have something to do with how the data is organized on a computer architectural or physical level?

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.

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

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.

I think this is because the old array is not destroyed. It is still there if it is being referenced somewhere else and it still can be accessed. This is why the new array is created in a new memory location.

Example:

int[] original = new int[] { 1, 2, 3, 4, 5, 6 };
int[] otherReference = original; // currently points to the same object

Array.Resize(ref original, 3);

Console.WriteLine("---- OTHER REFERENCE-----");

for (int i = 0; i < otherReference.Length; i++)
{
    Console.WriteLine(i);
}

Console.WriteLine("---- ORIGINAL -----");

for (int i = 0; i < original.Length; i++)
{
    Console.WriteLine(i);
}

Prints:

---- OTHER REFERENCE-----
0
1
2
3
4
5
---- ORIGINAL -----
0
1
2

There are two reasons for the definition of realloc as it is: First, it makes it absolutely clear that there is no guarantee that calling realloc with a smaller size will return the same pointer. If your program makes that assumption, your program is broken. Even if the pointer is the same 99.99% of the time. If there is a large block right smack in the middle of lots of empty space, causing heap fragmentation, then realloc is free to move it out of the way if possible.

Second, there are implementations where it is the absolutely necessary to do this. For example, MacOS X has an implementation where one large memory block is used to allocate malloc blocks of 1 to 16 bytes, another large memory block for malloc blocks of 17 to 32 bytes, one for malloc blocks of 33 to 48 bytes, etc. This makes it very naturally that any size change that stays in the range say 33 to 48 bytes returns the same block, but changing to either 32 or 49 bytes must reallocate the block.

There is no guarantee for the performance of realloc. But in practice, people don't make the size a little bit smaller. The main cases are: Allocate memory to an estimated upper bound of the needed size, fill it, then resize to the actual much smaller required size. Or allocate memory, then resize it to something very small when it's not needed anymore.

Only the designers of the .NET runtime can tell you their actual reasoning. But my guess is that memory safety is paramount in .NET, and it would be very expensive to maintain both memory safety and mutable array lengths, not to mention how much complicated any code with arrays would be.

Consider the simple case:

var fun = 0;
for (var i = 0; i < array.Length; i++)
{
  fun ^= array[i];
}

To maintain memory safety, every array access must be bounds-checked, while ensuring that the bounds checking isn't broken by other threads (the .NET runtime has much stricter guarantees than, say, the C compiler).

So you need a thread-safe operation that reads data from the array, while checking the bounds at the same time. There's no such instruction on the CPU, so your only option is a synchronization primitive of some kind. Your code turns into:

var fun = 0;
for (var i = 0; i < array.Length; i++)
{
  lock (array)
  {
    if (i >= array.Length) throw new IndexOutOfBoundsException(...);

    fun ^= array[i];
  }
}

Needless to say, this is hideously expensive. Making the array length immutable gives you two massive performance gains:

• Since the length cannot change, the bounds checking doesn't need to be synchronized. This makes each individual bounds check vastly cheaper.
• ... and you can omit the bounds checking if you can prove the safety of doing so.

In reality, what the runtime actually does ends up being something more like this:

var fun = 0;
var len = array.Length; // Provably safe

for (var i = 0; i < len; i++)
{
  // Provably safe, no bounds checking needed
  fun ^= array[i];
}

You end up having a tight loop, no different from what you'd have in C - but at the same time, it's entirely safe.

Now, let's see the pros and cons of adding array shrinking the way you want it:

Pros:

• In the very rare scenario where you'd want to make an array smaller, this would mean the array doesn't need to be copied over to change its length. However, it would still require a heap compaction in the future, which involves a lot of copying.
• If you store object references in the array, you might get some benefits from cache locality if the allocation of the array and the items happens to be colocated. Needless to say, this is even rarer than Pro #1.

Cons:

• Any array access would become hideously expensive, even in tight loops. So everyone would use unsafe code instead, and there goes your memory safety.
• Every single piece of code dealing with arrays would have to expect that the length of the array can change at any time. Every single array access would need a try ... catch (IndexOutOfRangeException), and everyone iterating over an array would need to be able to deal with the changing size - ever wondered why you can't add or remove items from List<T> you're iterating over?
• A huge amount of work for the CLR team that couldn't be used on another, more important feature.

There's some implementation details that make this even less of a benefit. Most importantly, .NET heap has nothing to do with malloc/free patterns. If we exclude the LOH, the current MS.NET heap behaves in a completely different way:

• Allocations are always from the top, like in a stack. This makes allocations almost as cheap as stack allocation, unlike malloc.
• Due to the allocation pattern, to actually "free" memory, you must compact the heap after doing a collection. This will move objects so that the free spaces in the heap are filled, which makes the "top" of the heap lower, which allows you to allocate more objects in the heap, or just free the memory for use by other applications on the system.
• To help maintain cache locality (on the assumption that objects that are commonly used together are also allocated close to one another, which is quite a good assumption), this may involve moving every single object in the heap that's above the freed space down. So you might have saved yourself a copy of a 100-byte array, but then you have to move 100 MiB of other objects anyway.

Additionally, as Hans explained very well in his answer, just because the array is smaller doesn't necessarily mean that there's enough space for a smaller array in the same amount of memory, due to the object headers (remember how .NET is designed for memory safety? Knowing the right type of an object is a must for the runtime). But what he doesn't point out is that even if you do have enough memory, you still need to move the array. Consider a simple array:

ObjectHeader,1,2,3,4,5

Now, we remove the last two items:

OldObjectHeader;NewObjectHeader,1,2,3

Oops. We need the old object header to keep the free-space list, otherwise we couldn't compact the heap properly. Now, it could be done that the old object header would be moved beyond the array to avoid the copy, but that's yet another complication. This is turning out to be quite an expensive feature for something that noöne will ever use, really.

And that's all still in the managed world. But .NET is designed to allow you to drop down to unsafe code if necessary - for example, when interoperating with unmanaged code. Now, when you want to pass data to a native application, you have two options - either you pin the managed handle, to prevent it from being collected and moved, or you copy the data. If you're doing a short, synchronous call, pinning is very cheap (though more dangerous - the native code doesn't have any safety guarantees). The same goes for e.g. manipulating data in a tight loop, like in image processing - copying the data is clearly not an option. If you allowed Array.Resize to change the existing array, this would break entirely - so Array.Resize would need to check if there's a handle associated with the array you're trying to resize, and throw an exception if that happens.

More complications, much harder to reason about (you're going to have tons of fun with tracking the bug that only occurs once in a while when it so happens that the Array.Resize tries to resize an array that just so happens to right now be pinned in memory).

As others have explained, native code isn't much better. While you don't need to maintain the same safety guarantees (which I wouldn't really take as a benefit, but oh well), there's still complications related to the way you allocate and manage memory. Called realloc to make a 10-item array 5-item? Well, it's either going to be copied, or it's still going to be the size of a 10-item array, because there's no way to reclaim the left-over memory in any reasonable manner.

So, to make a quick summary: you're asking for a very expensive feature, that would be of very limited benefit (if any) in an extremely rare scenario, and for which there exists a simple workaround (making your own array class). I don't see that passing the bar for "Sure, let's implement this feature!" :)

There might be many sophisticated data-structures operating "under the hood" in any heap-management system. They might, for instance, store blocks according to their present size. It would add a lot of complications if blocks were allowed to "be split, grow, and shrink." (And, it really wouldn't make things any 'faster.')

Therefore, the implementation does the always-safe thing:   it allocates a new block, and moves values as needed. It is known that "this strategy will always work reliably, on any system." And, it really won't slow things down at all.

Under the hood, Arrays are stored in continuous memory block but is still a primitive type in many languages.

To answer your question, the space allocated to an array is considered as one single block and stored in stack in case of local variables or bss/data segments when it is global. AFAIK, when you access an array like array[3], at low level, OS will get you a pointer to the first element and jumps/skip till it reaches (thrice in case of above example) the required block. So it might be an architectural decision that an array size can't be changed once it is declared.

Similar way, OS cannot know if it's valid index of an array before it accesses the required index. When it tries to access the requested index by reaching memory block after the jumping process and finds out that the memory block reached is not part of the array, it'll throw an Exception