My Talk at ILC (International Lisp Conference) 2002,
San Francisco, October 26, 2002.

Title: Return Barrier

Subtitle: Incremental Stack Scanning for Snapshot Real-time Garbage Collection

Garbage collection (GC) is the most popular method in list processing systems such as Lisp to reclaim discarded cells. GC periodically suspends the execution of the main list processing program. In order to avoid this problem, real-time GC has been proposed, which runs in parallel with the main program so that the time for each list processing primitive is bounded by some small constant.

The snapshot GC, which is one of the most popular real-time GC methods, has to mark all cells directly pointed to from the root area at the beginning of a GC process. The suspension of the main program by this root marking cannot be ignored when the root area is large.

We propose ``return barrier" in order to divide the process of root marking into small chunks and to reduce the suspension time of the main program. The root area on the stack is marked frame by frame each time a new cell is required. When a function returns, the garbage collector checks if cells pointed to from the frame of the caller function have been already marked, and marks them if not. After marking all cells directly pointed to from the root area, other cells are marked as in the original snapshot GC.

We implemented the snapshot GC equipped with the return barrier in several language processors including a Common Lisp system, a multi-threaded Lisp system for robot control, a Scheme system with conservative GC, and a JVM.

Slides (PDF file, 1,394,870 bytes)
Paper (PDF file, 265,429 bytes)
Paper (PostScript file, 647,409 bytes)