[PLT logo] Lecture 21, Comp 311

How To Eat Your Memory and Have It, Too

From our previous lecture, we can see that our machine requires five registers:

=M=: the program text
=env=: the lexical context [variable-value pairs]
=k=: the control context [list of frames]
=val=: the result value from evaluating the contents of =M=
=param-val=: the value of a function's parameter

=M= is a pointer into the program code. =k= holds a stack, which can be implemented as a pointer into a separate array. The other three are registers that (may) directly point to allocate data structures such as closures and lists.

Let us name the following expressions 

M1 = (lambda (x) (+ x 3))
M2 = (lambda (f) (+ (f 7) 4))
M3 = (lambda (z) (- z y))
and consider the evaluation of 
(M1 (M2 (let (y 2) M3)))
We will study the evaluation of this expression by looking at ``snapshots'' of the machine at various stages.

Snapshot 1

We have evaluated M1 and are in the process of evaluating the argument to the resulting closure. 

=k=    =  [appR -> <M1,empty>]
=env=  =  empty
=val=  =  <M1,empty>
where =val= shares its contents with =k=.

Snapshot 2

We have evaluated the left and right terms from Snapshot 1, and are about to apply the closure formed from M2. 

=k=    =  [appR -> <M2,empty> , appR -> <M1,empty>]
=env=  =  empty
=val=  =  <M3,[<y,2>]>

Snapshot 3

We are just done evaluating the subtraction inside M3, which is bound to f. 

=k=    =  [+R -> 4 , appR -> <M1,empty>]
=env=  =  [<z,7> , <y,2>]
=val=  =  5
Note that we have opened up the environment of the closure bound to f in showing the value of =env=.

Snapshot 4

We are in the midst of the addition inside the closure <M1,empty>; the x has just been evaluated. 

=k=    =  [+R -> 3]
=env=  =  [<x,9>]
=val=  =  9
However, recall that there are several old fragments of environment still to be found in memory, such as [<z,7> , <y,2>] from Snapshot 3.

If we look carefully in the final step, there are many items that were formerly in the environment that are unnecessary for the remaining evaluation. However, these unnecessary items are still present in memory and could potentially cause our program to exhaust available memory before finishing its task. Hence, we should try to recycle such unnecessary memory. Id est:

  1. Memory is a forest, rooted in registers.
  2. As the computation progresses, some portions of it become unreachable.
  3. Therefore, memory is reusable.
Assume we divide up available memory into two halves, called ``memory 1'' and ``memory 2''. Say we begin by allocating in memory 1, and hit the boundary. Then we can switch our current half to memory 2, copy the tree of reachable memory from the memory 1 into memory 2, and proceed with the computation. This copying is done by picking a register, each one in turn, and walking pointers into memory until we hit a cons cell; we copy this into the new memory 2, and repeat the procedure along each component of the cell. The process is repeated when memory 2 is exhausted, switching the rôles of the two parts.

This method might make intuitive sense, but what if we have sharing in our language? In LC, we currently have no way of checking sharing constraints (as with eq? in Scheme), but it is reasonable to assume we might be called upon to do so. In addition, if we duplicated objects, we would in fact use more space in the new half than in the old one, which would ruin the purpose of our attempt at recycling memory. To prevent this, when we visit a cell, we have to indicate that it has been forwarded; then, if it is visited again, the appropriate sharing relationship can be mimicked in the new half.

Thus, with the help of this process, which is called garbage collection, if the two memory banks are of equal size, and if there are indeed unreachable objects in the exhausted space, then we will have space left over in the new bank, and we can proceed with our allocation. However, there are two problems:

  1. What if everything is reachable? Then we are forced to signal an error and halt computation. (Note that this doesn't mean there aren't ``unusable'' objects in memory, just that our notion of reachability isn't strong enough to distinguish these objects. The objects that are truly necessary are said to be live.)

  2. The collector itself needs space for recursion and computations. We know we can get rid of recursion using CPS, which also tells us how many registers we need (which is fixed). The remaining variable is the depth of the stack, but this is proportional to the depth of the tree being copied. Using these insights, it is possible to write the collector that uses a small, fixed amount of additional memory.
A simple model of the garbage collector might look like this: 
(define gc
  (lambda (ptr)
    (cond
      ((null? ptr) null)
      ((cons? ptr) (cons_mem1 (gc (car_mem2 ptr))
		     (gc (cdr_mem2 ptr)))))))
but this loses sharing. So we have to break cons_mem1 up into its two constituent parts: allocation and initialization. 
((cons? ptr)
  (let ((new (alloc ...)))
    (make-as-forwarded ptr)
    (init_mem1 new (gc (car_mem2 ptr)) (gc (cdr_mem2 ptr)))
    new))
However, this still doesn't check for forwarding. A simple modification takes care of that: 
((cons? ptr)
  (if (forwarded? ptr)
    ...
    (let ((new (alloc ...)))
      (make-the-orange-thing)
      (init_mem1 new (gc (car_mem2 ptr)) (gc (cdr_mem2 ptr)))
      new)))

Perspective

In summary, the traditional view of garbage collection is roughly as follows:

  1. Reachability corresponds to liveness.
  2. Non-reachable memory can be garbage collected.
  3. The registers are the roots from which to perform the sweep.

Recently, a new view of garbage collection has been emerging. In this view,

  1. Every program evaluation state in the register machine corresponds to memory, registers and the program text.

  2. It is impossible to decide whether any given cell in some machine state is live or dead.

  3. Every algorithm that conservatively identifies live cells (ie, does not mistakenly claim some cell to be dead when it is useful) is a garbage collection algorithm.
The new view of gc has given raise to new gc algorithms. The new algorithms reconstruct the types of all phrases, including memory cells, at run-time and use type information to determine which cells are live or dead. For example, if an implicitly polymorphic system is used and a cell has type alpha, the program evaluation will work for all possible values in that cell. In particular, it will work if the cell's content is replaced by the null pointer. Doing so frees all memory that the cell (may) point to.

The new view is logical: it distinguishes between truly live and provably live cells, between truth and provability. As always, the latter is an approximation of the former. It is another indication of how tightly logic and computation are intertwined.

Shriram Krishnamurthi / shriram@cs.rice.edu