Concepts of Programming Languages

6.11 Pointer and Reference Types 301

reverses pointers as it traces out linked structures. Then, when the end of a list

is reached, the process can follow the pointers back out of the structure.

The most serious problem with the original version of mark-sweep was that

it was done too infrequently—only when a program had used all or nearly all of

the heap storage. Mark-sweep in that situation takes a good deal of time, because

most of the cells must be traced and marked as being currently used. This causes

a significant delay in the progress of the application. Furthermore, the process

may yield only a small number of cells that can be placed on the list of avail-

able space. This problem has been addressed in a variety of improvements. For

example, incremental mark-sweep garbage collection occurs more frequently,

long before memory is exhausted, making the process more effective in terms

of the amount of storage that is reclaimed. Also, the time required for each run

of the process is obviously shorter, thus reducing the delay in application execu-

tion. Another alternative is to perform the mark-sweep process on parts, rather

than all of the memory associated with the application, at different times. This

provides the same kinds of improvements as incremental mark-sweep.

Both the marking algorithms for the mark-sweep method and the processes

required by the reference counter method can be made more efficient by use

of the pointer rotation and slide operations that are described by Suzuki (1982).

Variable-Size Cells Managing a heap from which variable-size cells^9 are allo-

cated has all the difficulties of managing one for single-size cells, but also has

additional problems. Unfortunately, variable-size cells are required by most

9. The cells have variable sizes because these are abstract cells, which store the values of vari-
   ables, regardless of their types. Furthermore, a variable could be a structured type.

Figure 6.11

An example of the
actions of the marking
algorithm
x

x

x

x

x

x

x x

x x

x

1

2

3

4

5

(^68)
9
10
12
7
11
r
Dashed lines show the order of node_marking