It's All Geek to Me!

Dynamic memory allocation

Computer programs can allocate memory to store values in two ways: statically and dynamically. Static memory allocation refers to a situation where the amount of memory needed is known in advance and can be specified in the source code of the program itself. Dynamic memory allocation refers to a situation where a program may request an amount of memory which may change depending on conditions during its execution. Dynamic memory allocators dole out memory from an area of program-accessible memory called the heap. Typically, they maintain a linked list of available blocks of memory, using which they respond to dynamic memory allocation requests. Given a request for a certain number of bytes of heap memory, an allocation could take place in several ways. An allocator could traverse its list of available blocks and return the first block that would accommodate the number of bytes requested. Such an allocation is called a first-fit allocation. Alternatively, an allocator could traverse its list of available blocks until it finds an available block, whose size is closest to the number of bytes requested. This type of allocation is called a best-fit allocation. For the sake of simplicity, we will assume for the rest of this entry that allocators perform first-fit allocations.

Resizable collections

Collections are entities in a program that can be treated as one cohesive object and addressed in a unified and predictable manner. For example, arrays are contiguous areas of memory which start at a well-known address in memory and have a fixed length once they are allocated. Dynamically resizable collections are those that grow to accommodate any number of items that are added to them, even if the number of items to be added was not known in advance. An example of a dynamically resizable collection is the ArrayList class in Java and C#. This collection is based upon an array which is usually larger than the number of items in the collection. It is time to resize an array when it gets "too crowded" and the number of items in the collection comes too close to the size of the array. A new array of a bigger size is dynamically allocated from the heap and the members of the old array are copied to the new array.

Let's consider how the size of the new array is related to the size of the old array. Let us suppose the size of the old array is x. The size of the new array could then be some multiple of x, say k · x. A naive implementation would request the new array to be simply twice the size of the old array. This expansion would guarantee that all the items from the old array would fit into the new array, leaving plenty of room for any new additions. In this case, k = 2. However, let us see if we can get away with smaller values of k to save some space.

Let us say the initial allocation of an array is x.
Upon the first resize, the allocation would be k · x.
Upon the second resize, the allocation would be k · k · x.

We have to ensure that the second resize can accommodate the results of the previous two allocations. In other words, x + k · x <= k · k · x. Assuming a nonzero initial allocation (why would anyone want to dynamically allocate *no* memory?), we can factor out x, leaving the quadratic inequality

k2 - k - 1 <= 0

which can be solved to produce k <= (1 + √5)/2. In other words, we can get away with a resizing factor as low as the Golden Ratio, or even lower! A few STL implementations resize their collections using a factor of 1.5, for a good mix of efficiency and convenient memory.

This has been a presentation by the World's Largest Repository of Useless Knowledge, me. For more information, look up Andrew Koenig's paper on this subject using Google.