Use of Lists
The list is the most easily manipulated structure in Lisp. However, lists often
require more storage than other data types, and iterative operations on lists
reference memory more frequently than equivalent operations on non-list
structures. While the memory structure of alternative data types is usually
contiguous, lists are often scattered through memory, increasing the working set
as well as the memory bandwidth required.
The inherent linearity of the list is a major drawback. Although one can use lists
to construct trees that are logarithmic in access time, constant access-time
structures cannot be created with lists. Nevertheless, Common Lisp defines many
primitive functions that conveniently operate on lists, including set functions,
sorting and merging, iteration, mapping, reduction, searching, and so on. The
paging performance of these operations is adversely affected by the linear
traversal of memory required for the list structure.
Cdr-coding [Cheney 70] is a list-compaction technique used on Lisp machines to
minimize program working sets and reduce the number of memory references
necessary for traversing lists. However, these benefits are achieved at the
expense of one operation on conses: modifying the cdr. Whenever the cdr of a
cdr-coded list is modified, the resulting structure has much worse paging and
runtime characteristics than even normal list coding. It is therefore important to
be aware of which functions create cdr-coded lists (such as copy-list and list);
which functions create normally coded lists (reverse and cons); which functions
are efficient operating on cdr-coded lists (search, getf, delete and sort); and
which functions are inefficient operating on cdr-coded lists (nreverse, rplacd, and
ncouc). `
An alist (association list) is a list of sublists, each of which represents an
association between its car, the key, and its cdr, the value. When used as a table,
however, an alist is somewhat inefficient as a binary relation; it requires 3n (cdr-coded)
to 4n (normally coded) memory locations for n associations, rather than the
minimum 2n locations required. Linear traversal of the list is required for lookup,
requiring two or three list references per iteration (depending on cdr-codes).
Fragmentation depends on the application, but alists are typically used where
insertion and deletion are common. Thus they are typically not cdr-coded, and the
ages of the entries and top-level conses vary. With ephemeral memory
management, the differently aged conses are scattered throughout differently aged
areas. If the top-level list is cdr-coded, any sublist is likely to reside on a
separate page due to the size of the top-level list. Finally, because deletion from
alists involves cdr modification, programs should ensure that cdr-coding is not
used when deletions are expected. Alists are best used in applications where the
table size is small. For most other applications, different structures such as
plists, 2-dimensional arrays, hash tables, or trees are more suitable.
A plist (property list) is another representation of associations. A plist consists of
|