management from a programmer, it can impose a significant paging demand on Lisp programs. First, the garbage-collection process must reference memory to prove that storage can be reused. Second, garbage collection can affect the ordering of objects in memory, causing the working set of the application to change between different executions. Third, the memory references of the garbage collector are often not local with the memory references of the application.

Modern garbage-collection algorithms such as ephemeral garbage collection [Moon 84] can be very efficient. Many programs realize better performance by using ephemeral garbage collection rather than by turning off the garbage collector and implementing their own memory management. This performance advantage is most notable when programs take care to fit the garbage-collector's model.

Fit the ephemeral model: The ephemeral model assumes that newly-created objects are highly likely to become garbage, and that references between objects are more common between objects of similar ages. In cases where these assumptions are not valid, simple modifications will usually make objects fit the ephemeral model better. For instance, dynamically changing trees and lists should be copied occasionally, both to improve locality with cdr-coding and to ensure that the older portions of the structure become garbage more quickly. More permanent objects can be explicitly created as dynamic or static objects, rather than ephemeral objects, allowing the garbage collector to concentrate its efforts on objects more likely to become garbage.

Allow the garbage collector to do its job: All garbage-collection algorithms are assisted if pointers to large data structures are removed as soon as they are no longer needed. As long as these pointers exist, the objects cannot be reclaimed, resulting in more fragmented memory, possibly an increased working set, and more frequent garbage collections.

In summary:

• Copy dynamically changing objects to increase locality, ensure that components of different ages do not become scattered, and ensure reclamation by the efficient ephemeral garbage collector.

• Create more permanent or frequently referenced objects so that they are not ephemeral, thereby saving overhead in both ephemeral and dynamic garbage collection.

• Remove pointers to objects that are no longer necessary so they may be reclaimed by garbage collection.

System Facilities for Paglng Control

This section describes system-level methods for improving paging performance. Many techniques discussed in this section are not unique to the 3600 or even Lisp, although the examples are taken from the 3600 environment.