(defun example-1 (matrix)
  (let ((size (array-dimension matrix 8))
        (sum 8)) .
    (dotimes (column size)
      (let ((product 1))
        (dotimes (row size)
          (setq product (x product (aref matrix row column))))
        (incf sum product)))
    (/ sum size)))
    
(defun example-2 (matrix)
  (letx ((size (array-dimension matrix 8))
         (products (make-array size :initial-element 1)))
    (dotimes (row size)
      (dotimes (column size)
        (setf (aref products column)
              (x (aref products column)
                 (aref matrix row column)))))
  (/ (reduce #'+ products) size)))

example-1 computes the function exactly as specified, by iterating over all columns of the matrix and averaging products of the elements of each. In contrast, example-2 allocates additional memory to store intermediate results and traverses the array in memory order. Its runtime may be slower because it is not using local variables for its intermediate calculation, and its working set is actually larger due to the additional memory allocated in the temporary array. However, the paging complexity of example-2 is lower than that of example-1 by a factor approximately equal to the page size, because its references to the matrix are more localized. It is therefore the algorithm of choice for very large matrices.



Choosing Data Structures to Improve Paging

Lisp programs often have different paging characteristics than programs written in other languages. This section analyzes several programming techniques that are common in Lisp programs, and critiques them with respect to paging performance. For a more detailed discussion see [Andre 86].



Use of Symbols

A symbol can have a name, value, functional definition, package, and an arbitrary number of properties. On Symbolics 3600-series computers, symbols, name strings, and packages are stored in different areas devoted to their respective kind of object. A program that uses a symbol's name to look up structures stored in its