Garbage Collection


One of a series of tutorials about Scheme in general
and the Wraith Scheme interpreter in particular.

Copyright © 2011 Jay Reynolds Freeman, all rights reserved.
Personal Web Site: http://JayReynoldsFreeman.com
EMail: Jay_Reynolds_Freeman@mac.com.


Things in the main memory of a Lisp system, which are provably not usable in future operations of that system, are called garbage, in the sense of waste material that takes up space. The storage space containing them may in principle be reclaimed for other uses.

The process of identifying garbage and reclaiming its space for subsequent reuse is called garbage collection.

This is really isn't the place for a technical discussion of how garbage collection works. There is a more detailed description of Wraith Scheme's garbage collectors in the "Glossary" section of the Wraith Scheme Dictionary and a lower-level description of the implementations in the Wraith Scheme Internals document, both of which are available from within Wraith Scheme, via the "Help" menu. You might also look at Jones and Lins [1996], which is listed in the Bibliography tutorial.

This is the place, however, for some discussion of how to use the different garbage collection methods built into Wraith Scheme, and of their good and bad qualities.

Wraith Scheme has two different garbage collectors, which interact. The first is of the kind that stops all Scheme processing and reclaims all the garbage in all of memory, all at once. That garbage collector is called a full garbage collector. It can do the whole job of garbage collection all by itself, but if you are using a large Wraith Scheme main memory, the time required to garbage collect may be long enough to be a bother. Lisp users say that you should never use a Lisp system to control a toaster, because the toast may burn while the system has stopped to collect garbage.

The second Wraith Scheme garbage collector is a generational garbage collector. Its operation is based on the principle -- well-known in the Lisp community -- that most objects that a Lisp system creates are for temporary use: They become garbage very soon. Therefore, if you have some way to keep track of just those objects that have been created recently, you can reclaim a lot of garbage very quickly -- and not burn the toast -- by looking at only the recently-created objects. There usually aren't very many of them, so that task can be accomplished quickly. On the average, when Wraith Scheme is using the generational garbage collector, it spends a higher proportion of its time collecting garbage than when it is not, but its response time is quicker, so the toast does not burn.

The problem with a generational garbage collector is that there are always a few of those recently-created objects that are not garbage when you look at them, but become garbage eventually. Little by little, they fill up Scheme main memory, and eventually it is necessary to do a full garbage collection to get rid of them. Wraith Scheme will not be able to get on with your work -- your programs -- while a full garbage collection is happening.

Wraith Scheme offers you two basic options for garbage collection. You can set it up to use just the full garbage collector, which will run automatically whenever Scheme main memory is nearly full, or to use the combination of generational and full garbage collectors that I just described. You cannot switch back and forth between these two schemes while Wraith Scheme is running, but there is one tab in Wraith Scheme's preferences, the "GC" tab, that allows you to select which kind of garbage collection you want Wraith Scheme to use the next time it starts up.


GC Preferences Window

If you select that tab, you will find it contains a check box for using the generational garbage collector; with it checked, you get the combination of full and generational garbage collection; without it, you just get full garbage collection. There is also a way to select the generation size, which is simply the amount of memory that is allowed to fill up between consecutive generational garbage collections. I suggest you leave it set at its default setting, at least while you are learning what it does.

Without regard to which of the two garbage collection systems is running, you can force a full garbage collection to take place at any time, by evaluating


Several of the displays in the Wraith Scheme Instrument Panel have to do with garbage collection.


Instrument Panel

There is a red light near the top right corner of the instrument panel that glows whenever garbage collection is happening. From top center through top right of the instrument panel are displays that show how much Scheme main memory Wraith Scheme has, how much of it is in use, and how many garbage collections have taken place. These displays alternate back and forth between describing the full garbage collector and describing the generational garbage collector: When the numbers for memory size are in parentheses, they pertain to the generational collector; the different kinds of garbage collections -- full and generational -- simply have different labels.


Instrument Panel Generational Garbage Collector Display


-- Jay Reynolds Freeman (Jay_Reynolds_Freeman@mac.com)


Wraith Face