Why aren't arrays expandable?

When开发者_StackOverflow中文版 we create an array, we cannot change its size; it's fixed. OK, seems nice, we can create a new bigger array and copy the values one by one and that's little slow. What's the technical background of it?

This question didn't mention a language so I'm going to choose 'C' based arrays for my answer.

Arrays are allocated as a single chunk of memory. Growing an array is problematic because the only way to do it properly is to grow it at the end. For a growth of size N there must be at least N free bytes at the end of the array before the next allocated address.

Supporting this type of allocation necessitates that allocations be spread across the virtual address space. This both removes the benefits of having memory allocations closer to each other and serves to increase fragmentation. This flies in the face of most memory managers which try to pack memory together and reduce fragmentation.

Allocating a new array at a place in memory with sufficient space and copying the array there is simply not an option as a general solution. The reason why is that the previous location of the array is visible to consumers through pointers.

int* array = malloc(int*someSize);
int* pointer1 = &(arr[2]);
growArray(&array, 12);  // Can't move because pointer1 knows the address of the array

An array at its roots is a contiguous 'array' of memory. Other data can occupy data before and after this area of memory, hence it cannot be dynamically resized without allocating a new, different area of memory that fits the new, larger size.

Depends on your language, but typically arrays are arranged as a series of sequential spaces in memory. This way you don't have to store memory locations for each point in the array, you just store one memory location (the start of the array) then you add an offset (the offset would be the size of each entry multiplied by the index you wanted) to find out where a specific entry is in memory.

This is also why arrays typically only contain one type, otherwise you couldn't make such a simple calculation. Languages that do allow you to store multiple types are actually creating a normal array and placing pointers to each entry in the array--all pointers are typically the same size. This level of indirection costs and it's why "easier" languages tend to be a tad slower.

Anyway, when you allocate more memory you want to put the new memory right at the end of the array--otherwise you'd segment your memory with a hole--why would you do that?

So you can't just extend the array without physically moving it.

Computers have been doing this for years, so most languages have some way to allocate a new chunk of memory and then tell the CPU to block-copy all the entries to the new chunk and change your pointer to reflect that, but often (C, Java, ...) they leave this up to the programmers with specific commands to copy the array rather than doing it for you (Possibly just to let you know that expanding an array is not "Free"

It would be possible to add a pointer at the end of the array to jump to a block of new memory you want to add to the end of an array, but now your array lookup has just gotten slower by a pretty significant amount.

Many languages simply wrap arrays as collections that allow this kind of functionality. For instance, a Java Vector/ArrayList will automatically re-allocate memory for you. A linked list actually just allocates a single element each time with a pointer to the next. Makes it very fast to add elements, but really slow to go to element 5000 (you have to read every single element, whereas with an array reading element 1 is just as fast as element 5000)

It depends on the language.

In C (and similar languages like Java), when you declared an array like int ary[10], the system set aside exactly enough memory to hold ten integers back-to-back. Expanding it wasn't easy, because the system didn't set aside any extra space (since it has no idea whether you'd want to expand it or by how much) and the memory that came right after the array was probably being used by something else. So, the only way to get a larger array was to set aside a new block of memory that will hold the expanded array, then copy the old contents over and add the new items.

You are correct that this can be slow. One way around it is to declare your arrays larger than you need them in order to give you room to grow. Especially on older computers, this could lead to a program eating up a lot of memory that it never used.

Another way around it is to use a higher-level language that features expandable arrays. Ruby, for example, allows you to add more items onto an array without ever having to declare memory or copy array contents.

Generally speaking, programming language have somewhere an abstraction of something that allocate a fixed portion of memory. Then out of this abstraction, other abstractions can be created which hide the complexity of the memory management, possibly by moving/copying data around.

Most of the time, array are fixed -- a (somehow) low-level abstraction -- and lists or collections are built on top of arrays and know how to resize themselves dynamically.

It's handy to have such low-level abstraction to be able to implement efficient algorithm/optimizations sometimes. But in most of your code you can use lists and collections without worrying too much about performance.

Whether or not you can change the size of an array will depend on what language you are using. In those languages in which you cannot increase the size of an array, the reason is that arrays are laid out in consecutive locations in memory and the compiler cannot guarantee that the locations following the end of the array are available to be added to the array. Many programming languages support expandable array types, but those simply handle the reallocation and copying of the underlying memory for you.

For instance, in the Curl programming language, there is a FastArray type which has a size and a max-size. The max-size specifies the maximum size of the array, and determines how much memory will be allocated for the array. There is a more general Array type, which uses a FastArray as its underlying implementation and will replace the FastArray instance if the array needs to be expanded beyond the max-size of the underlying FastArray.

Back in assembly language, one was obliged to declare the memory space required for a variable. This was reserved memory into the Data Segment (DS) registry.

So, roughly looking like so (Borland Turbo Assembler):

.DATA
    myStringVariable   DB   "Hello world!", 13, 10
    myArrayVariable    DW   "                    " 'Reserving 20 bytes in memory (in a row)

.CODE

    MOV AX, @DATA
    MOV DS, AX
    ' ...

Then, once the .DATA segment was delimited, it couldn't be changed as the .CODE segment (CS) was beginning at a little few bytes futher.

So, if an array would have been extensible, like collections are in .NET, the data would have overwritten the code, causing the program to crash, etc.

C/C++ (3.0), Pascal (7.0), QBasic, PowerBasic and COM debug programs were based on this architecture and could do any better than what Assembler allowed.

Today, with the more flexible technology, we are now able, I guess, to allocate memory addresses on the fly as needed, and keep a reference on them with only one variable, so arrays have become extensible with collection. But there are some situation where you have a precise amount of byte to respect, like network packets, etc. for example, where arrays are still useful. Another example is for storing images in a database. You exactly know mow large in bytes is an image, so you may store it in a byte array (Byte[]).

Perhaps am I missing a few precisions here, I have written for what I remember of my old favorite programming languages. Maybe some peopple can bring up some more detailed stuff.

Hope this helps! =)