. navigate
Minimizing Paging    Page 17 left arrow
right arrow Page 19    Minimizing Paging

LISP Pointers
Volume I, Number 1
April-May 1987

Minimizing Paging
page 18

Prev Article               Start of This Article                Next Article

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

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