1. Dynamic Memory Allocation

1.1. Static vs Dynamic Memory Allocation

The issue we address in this lecture is the efficient use of memory. The issue arises because of inefficiencies inherent in the way memory is allocated for arrays. When you declare an array of size 1000, all 1000 memory locations are reserved for the exclusive use of that array. No matter how many values you actually store in the array, you will always use 1000 memory locations. The same memory allocation strategy is used for most implementations of strings. I will use the term static allocation to refer to this memory allocation strategy, in which all the memory that a data structure might possibly need (as specified by the user) is allocated all at once without regard for the actual amount needed at execution time. The opposite strategy, dynamic allocation, involves allocating memory on an as-needed basis.

There always is an absolute maximum of memory that can be allocated: this is simply the amount of memory that is physically available on your computer (more precisely, the amount of memory that is addressable by your computer). No allocation strategy can get around this. The difference between static and dynamic allocation is illustrated by the following example.

Example: Recording Names of Individuals

Suppose I have a total of 3000 memory locations available with which to store the first and last names of everyone in this class. If I use an array of strings to store this data, storage will be allocated statically, and consequently I must set a maximum on how long a name can be, and a maximum number of people in the class. It is quite hard to set these limits, especially when, as in this case, they interact: in order to allow longer names I have to reduce the possible size of the class. To be perfectly `safe' I would have to allow for those rare cases of people with extraordinarily long names, say 100 characters. Given that there are only 3000 memory locations in total, this name-size imposes a limit of 30 people per class. Now, this is clearly wrong. Even if there are 30-plus government employees with 100-character names, it is unthinkable that 30 of them will simultaneously register for the same course.

With dynamic allocation, I will not even have to think about how many people might join the class, or how long their names might be. I can just as easily accommodate 30 people with 100-character names and 300 people with 10-character names.

1.2. How Does Dynamic Allocation of Memory Work?

The key idea is to regard all the available memory as a large global pool that can be used for any purpose whatsoever. When you need memory, you ask for just the amount you need; it is given to you from the global pool and is marked as being no longer `free' so that a subsequent request for memory does not allocate this same block again for a different purpose. Memory allocation is done by some sort of procedure call; in C, malloc(n) allocates a block of memory of size n bytes.

It is your responsibility to return memory to the global pool when you are finished with it; when you do so it will be marked `free' again and be available for other uses (you might get it again the next time you request some memory).

To continue our class-names example, we imagine that all the available memory is one large array to be used as a global pool:

We use gray shading to indicate the regions of memory that belong to the global pool, i.e. which are free. At present, all of it is free.

Now, if the user needs memory to store the name JOE, he must requests enough space to store the string "JOE". As it happens, in C, all strings must be terminated by a special character called `NUL' whose code is 0 and which is written \0. Therefore, the user needs 3 bytes to store J, O, and E, plus an additional byte for NUL. Thus he requests 4 bytes by calling malloc(4).

Suppose he is given the first 4 bytes from the pool; then memory would now look like this:

The memory allocator keeps track of what memory is free and what memory has been allocated. It now knows that the 4 bytes which it gave to the user are no longer free; they are no longer in the global pool. This we represent visually by the fact that these bytes are no longer shaded gray.

The question marks now visible indicate that we do not know in what state the bits of this block of memory really are.

Note: Why not? (1) what's a valid initialization? (2) It is inefficient to initialize large blocks, especially when the next thing the user does is overwrite this initialization with the useful values s/he really wanted to put in.

A memory allocator typically makes no guarantee about this issue. The block of memory which is allocated and returned to the user must be presumed to contain garbage. It is the responsibility of the user to then initialize this block properly so that its contents become meaningful.

In the present case, the user simply copies the string "JOE" into it:

You can see that it takes up exactly the space that is needed for it. The rest of memory can be used to store the other names.

Suppose the next name is MARYJANE: 8 characters + 1 NUL. The user asks for 9 bytes and copies the string into them:

You may wonder why this new block is not contiguous with the previous one. The reason is that, in general, it won't be. This, mainly for two reasons:

The memory allocator might very well decide to allocate the next block from some other part of memory.
Often, the memory allocator needs to allocate a little bit more than the user requested so that it can store, just before the user's block, some information about it, such as its size. Thus, when the user wants to `free' the block, the memory allocator can find out how big it is and return the correct number of memory locations to the global pool.

For example, the real situation might look like this:

where the arrows point to the start of the blocks allocated to the user. In the following, we are going to ignore these details.

What to remember

The memory allocator keeps track of what is allocated and what is free.
When we obtain memory from the global pool, we must assume that it contains garbage, and properly initialize it.
We must not assume that successive requests will allocate contiguous memory blocks.

If the user now says he is finished with the name JOE, the corresponding block of memory is returned to the global pool and becomes free:

1.3. Problems With Dynamic Allocation of Memory

I have stressed so far the advantage of dynamic memory allocation. Now let me mention its two main disadvantages or dangers.

Freeing Memory

The user is responsible for freeing up memory when he is finished with it. This is a serious responsibility, a potential source of bugs that are very hard to find.

For example, suppose you free up a location before you're actually finished with it. Then further access to the location will either cause a run-time error (memory violation) or, what is worse (but more common), you will get access to a location that is being used for some completely unrelated purpose.

Trouble also occurs if you forget to free up some space. If you do this, you are losing the advantages of dynamic allocation. And in some circumstances - e.g. if you were writing the program that manages the space on a disk drive - this could be disastrous.

There are no surefire safeguards against these problems, you must be very careful when writing programs to return memory when you are finished with it, but not before.

Fragmentation of Memory

As the preceding example demonstrated, with dynamic allocation the `free' parts of memory are not all together in one contiguous block. When we returned JOE's memory, we had 4 free cells on one side of MARYJANE and all the rest on the other side. This is called fragmentation of memory, and it can grow into a very serious problem: it is possible to have a large amount of free memory but for it to be broken up into such tiny fragments that there is not enough contiguous free space to store another name.

Suppose that after using dynamic allocation for a while memory becomes fragmented thus:

and that we need to obtain a block this big:

If only the remaining free blocks were contiguous, we'd have enough room, but, in the present configuration, it looks like we are doomed. There are several possible solutions to this problem. The one we will study is based on the insight that a large data structure does not necessarily have to be allocated in one single contiguous chunk of memory. Instead it might be decomposed into smaller components that are somehow linked together in a chain.

Each component in this chain can very well be allocated in a different region of the global pool. Thus, when using linked data structures, fragmentation becomes much less of a problem.