CSE 413 Spring 2011 -- Garbage Collection

Scheme, like Smalltalk, Java, C#, Ruby, and many others uses garbage collection to manage storage.

When an expression such as (cons 'fred ()) is evaluated, the cons function allocates a new cons cell (bit of storage) from the heap. There is no explicit deallocation procedure; rather, when the cons cell is no longer accessible it can be garbage collected.

Scheme implementations typically keep a free list of unused cons cells. Except for not being directly accessible to the user, this is just an ordinary list, sprinkled through memory. The cons function just grabs the first cell at the head of the free list, and then sets the free list pointer to the next available cell.

There are lots of variations on garbage collectors. One of the simplest is mark-and-sweep. When free storage is exhausted, first the system marks all the cells that can be reached by following pointers. (The pointers will be from the global symbol table or any local variables on the stack.) Then the system sweeps through memory. Every unmarked cell is no longer accessible and can be added to the free list.

Some variations:

• Classic mark-and-sweep requires additional stack space to keep track of where you are while following list structures -- just when there isn't any space! One solution is to save a bit of space for this stack space. There is also a clever algorithm that flips pointers while traversing list structures to keep track of where you are, then flips them back, avoiding the need for the auxiliary stack.
• Copying collectors partition memory into a working half and a free half. When the working half is exhausted, copy the accessible cells to the free half. If most of the cells are no longer accessible, this is more efficient. (Copying garbage collectors make more sense for systems with virtual memory.)
• Incremental garbage collectors do the work incrementally, avoiding pauses for garbage collection. (Also you can have a separate processor devoted to garbage collection.)
• Generational garbage collectors concentrate on collecting recently-allocated objects and scan older objects less frequently. The rationale behind this is that both functional and object-oriented programs tend to allocate a large number of short-lived data items, so there is a bigger payoff in looking at recently allocated areas first. Data that has survived several collections is more likely to persist for a longer time, so frequent scans of older objects are not likely to be particularly productive.

There are lots of other versions. In all cases the system has to be careful to distinguish pointers from other kinds of data (such as characters and numbers).

In reference counting the systems keeps track of how many references there are to an object. When the count drops to zero the storage is reclaimed. This is naturally incremental, but doesn't reclaim circular structures.