3.7.1 Why Dynamic Memory?

Why is storage efficiency important? Why not find storage for a new record in the array simply by placing it sequentially below the last new record's storage? After all, this would be very easy to do and would certainly use the storage as efficiently as possible. The answer is that this simple solution is a great idea?/FONT>provided that all the storage needed for the array to be of sufficient length is available. The catch is that this proviso is rarely the case. Often, the amount required isn't known in advance; even when it is known, not enough storage may be available.

Reconsider the prime number example of Chapter 1. It is probably evident by now that the list is a good data structure to use for collection. The program to generate all the primes between 2 and n uses very little storage besides that needed for the list, but how large should you make the array in which to store the list? It is possible to modify the program so that it need not actually store all integers between 2 and n in the list, but only those that are prime. Still, how many primes are there no greater than n? It is even possible to write such a program so that it efficiently generates and prints all primes ?/FONT> n yet stores only those n in the list, but again, how many of these are there?

Suppose you are a programmer asked to store the contents of ten manuscripts in ten lists. If each can have a maximum length of 50,000 words, then storage for 500,000 words is needed. How long is the longest word? You see the problem. Even if the amount of storage could be estimated, sufficient storage may not be available. You might conclude that the task cannot be done, or you might use secondary storage (magnetic tape, disks). However, in secondary storage access is relatively slow, and it requires techniques different from those described so far. One possibility remains. Maybe the manuscripts to be stored, perhaps even more than 10, are compatible (in the sense that they are not all of great length simultaneously). Perhaps the lengths will vary as the manuscripts are processed by a program, so that at any one time the manuscripts being stored can fit. This means that they may be growing and shrinking in length at different points in the program. If the storage no longer needed for one manuscript is relinquished and reused for another, then the total array length may not ever be exceeded. In other words, if storage can be allocated, then reused for new allocations when no longer needed for its original purpose, problems may be solved that are otherwise out of range. This is the reason to manage storage.

This also explains why dynamic memory makes better use of storage than individual program management using arrays of records. Each program may, to ensure its execution, ask for a large amount of storage to be used for its array. The total amount needed by all the programs may not be at hand. It is better to take all available storage and dole it out to each program as needed, the hope being that whenever some programs need a great deal of storage, the others need little. Instead of dedicating amounts to each user for each one's worst case, the programmer manages the storage and gives out only what is needed at any moment.