Minimizing Paging in Lisp Applications

David L. Andre
Symbolics, Inc.



Introduction

Paging is an important aspect of performance in any program and can be the overriding consideration in a large system. When developing large applications, the programmer should be as aware of paging overhead as he is of runtime overhead. The programmer should seek to avoid large working sets that cause ` page faults, just as he avoids order n2 and exponential algorithms.

This paper concentrates on techniques available to the Common Lisp application programmer to improve paging performance by: understanding the paging implications of algorithms, choosing appropriate data structures, and exploiting knowledge of the implementation of the underlying Lisp system. Although the primary focus of this paper is the Symbolics 3600-series implementation of Common Lisp, many of the topics covered are widely applicable to other Lisp dialects, and architectures with similar features.



Paging and Virtual Memory

A typical modern processor uses two types of random-access memory: a fast main, memory (usually consisting of semiconductor chips), and a larger and much slower secondary memory (usually consisting of magnetic disks). The processor addresses all memory in terms of virtual addresses, thus operating under the illusion of a single memory. This virtual memory is implemented transparently using main and secondary memories. Thus a virtual address can correspond to a physical address


*****************
David L. Andre is a Senior Member of the Technical Staff at Symbolics, lnc. He holds an M.S. in Computer Sdence from University of Maryland, and an S.B. in Electrical Engineering from Massachusetts Institute of Technology. This paper is based on a section of [Andre 86], which is available from the author or University of Maryland.

Copyright © 1987 David l. Andre