. navigate
Minimizing Paging    Page 18 left arrow
right arrow Page 20    Minimizing Paging

LISP Pointers
Volume I, Number 1
April-May 1987

Minimizing Paging
page 19

Prev Article               Start of This Article                Next Article

a single list whose elements alternate between keys and values. A cdr-coded plist of n associations takes up only 2n memory locations, the minimum possible number. Common Lisp functions for plist manipulation are often more convenient than alist primitives because they treat the plist more like an abstract table. Plists are most suitable for applications where the key set (table size) is relatively static; that is, insertions and deletions are rare. In this case, plists can be cdr-coded and quickly traversed for lookup or modification.

Lists are often used to represent sets. When the element space is large and the typical set is small, lists are an efficient representation of sets. However, if the element space is small, using fixnums or bit vectors is much more efficient. Other altemative implementations include trees and hash tables.

In summary, lists should be used when they are appropriate to the application, but other data types should be used when they are more appropriate. The choice of representation should be made based on the requirements of the application, not the apparent ease of implementation.

Use of Objects

Common Lisp programs often use some object-oriented programming paradigm, such as defstruct in Common Lisp, or Flavors in Symbolics Common Lisp. Object-oriented systems can greatly simplify the development task, but they encourage a programming style in which all information about the object is stored with the object in memory. In order to access any piece of that information, the object must be brought into physical memory. This is an efficient practice for accessing all information from a single object, but is inefficient for mapping over many objects, because memory references are scattered. An alternative is to store certain associations in a separate table, so that for mapping operations, individual objects need not be brought into physical memory.

Using Knowledge of the Implementation

This section discusses how to improve Lisp programs by exploiting knowledge of the underlying implementation. Specific examples in this section refer to the Common Lisp implementation on the Symbolics 3600, and may not be applicable to other architectures.

Data Type and Consistency Checklng

A knowledge of storage formats and function requirements helps in selecting s functions and objects that minimize memory references. As a general rule, functions reference memory only when insufficient information exists in argument data types and virtual addresses. The following table lists the circumstances

Page Left left arrow         
right arrow Page Right
Vol. I, No. 1
Table of Contents

Home   Favorites   Computers   Map

IME logo Copyright © 2009, Mary S. Van Deusen