Allocating Dynamic Objects

The techniques we considered in Session 20 tell us how to allocate space for static objects, those whose addresses can be determined in at compile time. But what about arrays, variable-length records, or pointers to objects created at run-time?

When a program is done using an object that was allocated dynamically, the space allocated to the object can be returned to the run-time system to be used for another object. We will consider deallocation and some of the problems it introduces in the next section.

Because the compiler doesn't know the number or size of dynamically-allocated objects at compile-time, it must create a mechanism for allocating memory for the objects at run-time. We can use one of two basic techniques:

• Allocate memory in fixed-sized blocks.

  These blocks can come from a contiguous chunk of memory in which blocks are linked using slots treated as pointers. The compiler treats the rest of the block as untyped, while the compiled program can treat the block (even the pointer slot) as of a specific type.

  As memory is deallocated at run-time, a block can be returned to the list of unused memory for allocation again later, using the pointer slot to link it back in.

  Suppose that a program is using three of its six blocks, and the program releases the object stored in Block 1. Here is a before-and-after picture:

  

  The advantage of this approach is simplicity; the disadvantage is wasted space. If the compiler uses block that are too large, then often the allocated space will be larger than required by the object. If the compiler uses block that are too small, then the percentage of space allocated to pointers will be too high.



• Allocate memory in variable-sized blocks.

  In order to manage its memory more efficiently, the run-time system can allocate just the amount of memory needed for each object. Allocation and deallocation can then result in fragmented memory:

  

  This causes two problems. First, managing free memory in a list becomes more complicated, because the system needs to maintain information about the size of each block in the list. Second, and more troublesome, the system may have enough free memory to allocate a particular object, but not in a chunk large enough to hold the object.

  These problems make it desirable to manage free memory not in a list, but in a heap. When a block is returned to the heap at run-time, it can be merged with any free blocks adjacent to it to create a single, larger free block. Blocks can be allocated using a variety of approaches, such as first-fit, best-fit, and worst-fit.

  This approach uses space much more efficiently, but at the cost of (perhaps substantial) run-time overhead manipulating the heap.

Choosing among competing alternatives is often driven by the needs of the programmers that use the language, or the implementation in question.

The Problems Associated with Deallocating Dynamic Objects

Allocating dynamic objects introduces problems associated with deallocating objects. Consider this Java code:

    int[] grades;
    grades = new int[10];
    ...
    grades = new int[5];
    ...
    grades = new int[20];

The variable grades first points to an array of ten ints allocated dynamically. Unless another variable has been set to refer to this array, the second assignment to grades results in the first array never again being used by the program. The memory associated with this array is now garbage. A program can create garbage in other ways, too, such as by an object going out of scope.

    {
        int[] grades = new int[10];
        ...
    }
    // no more grades!

Garbage exists between the time of the last reference to the object and the time when deallocation occurs.

The flip side of garbage is the dangling reference. Consider this simple little C program:

    main()
    {
        int *p;
        p = dangle();
    }

    int *dangle()
    {
        int i = 23;
        return &i;
    }

The procedure dangle declares a temporary variable named i. When an activation of dangle terminates, the object bound to i disappears as soon as the corresponding activation record is popped from the control stack. Yet dangle has returned its address to main, which assigned the address to the variable p. Thus, p now points to a chunk of memory no longer allocated to the program!

A program can create a dangling reference in other ways, too, such as when the user explicitly releases the memory associated with an object before all references to the object are gone. For example, in C++ a programmer can call dispose() to release the memory associated with an object at any time. (Java does not have a corresponding operator.)

A dangling reference exists between the time when deallocation occurs and the time of the last reference to the object.

Garbage and dangling references arise depending on how the run-time system handles the deallocation of memory. A compiler can use several different approaches to deallocation:

• It can ignore the problem. The run-time system never deallocates memory, even for objects that can no longer be used, and programmers cannot explicitly deallocate memory. The risk of this approach is that a program can run out of memory long before using all of the memory available to it.


• It can charge programmers with explicitly releasing the memory associated with objects no longer in use. The result can be highly efficient usage of memory, at the cost of the risk that the programmer will not forget to release unneeded memory (creating garbage) and will not deallocate an object too soon (creating dangling pointers). C++ adopts this policy.
  
  
• It can reclaim memory that can no longer be used. This can be called 'implicit' deallocation, though it's more commonly known as garbage collection. Java and Scheme adopt this policy.

In order for garbage collection to work, a program must cooperate with the run-time system, by letting it know the size of the object and letting it know when an object is out of use.

Communicating size is straightforward. When surrendering an object, a program can store the size of the block at the top of the block. Communicating that a block is out of use is much more difficult. Two common approaches are:

• reference counting -- Have each block store in one of its fields the number of objects that refer to it. If the count ever becomes 0, then the block can be reclaimed. This technique works quite well, but it is expensive... The assignment p := q may change the counts in two blocks!


• marking -- Periodically stop execution of the program and trace all pointers to find what memory is in use. Any memory from the heap that cannot be reached from an existing reference can be returned to the free list. This trades the small but frequent costs of reference counting for infrequent but much more expensive overhead.

With the popularity of Java and now scripting languages over the last decade, garbage collection has become an even more active area of programming languages research. Up to a quarter of the technical papers presented at some recent OOPSLAs have been on the topic of garbage collection!