MIT 6.001                                       Fall, 1997
Instructor: A. Meyer

                 Recitation #7, Notes for Fri., 12/5/97

Hand simulation of Stop-and-Copy garbage collection procedure.  Main
features of Stop-and-Copy:
i.  sacrifice half of memory.
ii. the active portion of memory gets compacted by the garbage collection
    process; this is valuable for interacting with a disk (avoiding "page
    faults").
iii. free memory is one big block; this reduces allocation of a new
     CONS-cell to a lookup and increment of a single "free" pointer.
     Also, makes memory allocation is easy for data types like
     strings or arrays which require a contiguous block of memory.
iv.  time for garbage-collection is Theta of the size of ACCESSIBLE memory;
     so paradoxically, the more garbage, the faster the garbage collection.
v.  Scheme evaluation stops during garbage collection process; this would
    not be acceptable for applications requiring "real time" response --
    can't tolerate interrupting for garbage collection an impact
    assessment program which is deciding whether to inflate an air-bag.
 

Brief mention of Mark-and-Sweep garbage-collection:
i. mark phase is just graph-search as in PS6, where the nodes of the graph
   are CONS-cells, the sons of a node are the cells its CAR and CDR point
   to (if any), and the search starts at the STACK.
ii. all of memory is potentially usable.
iii. accessible memory does not move.
iv. garbage collection requires sweep of entire memory looking for
    unmarked cells, so time for garbage collection is always large,
    whether there is a lot or a little garbage.
v.  free cells are organized in a list; no easy way to allocate
     contiguous blocks.