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
|