13.4 避免垃圾 (Garbage Avoidance)

Lisp 除了可以让你推迟考虑变量的类型以外，它还允许你推迟对内存分配的考虑。 在程序的早期阶段，暂时忽略内存分配和臭虫等问题，将有助于解放你的想象力。 等到程序基本固定下来以后，就可以开始考虑怎么减少动态分配，从而让程序运行得更快。

但是，并不是构造（consing）用得少的程序就一定快。 多数 Lisp 实现一直使用着差劲的垃圾回收器，在这些实现中，过多的内存分配容易让程序运行变得缓慢。 因此，『高效的程序应该尽可能地减少 cons 的使用』这种观点，逐渐成为了一种传统。 最近这种传统开始有所改变，因为一些实现已经用上了相当先进（sophisticated）的垃圾回收器，它们实行一种更为高效的策略：创建新的对象，用完之后抛弃而不是进行回收。

本节介绍了几种方法，用于减少程序中的构造。 但构造数量的减少是否有利于加快程序的运行，这一点最终还是取决于实现。 最好的办法就是自己去试一试。

减少构造的办法有很多种。 有些办法对程序的修改非常少。 例如，最简单的方法就是使用破坏性函数。 下表罗列了一些常用的函数，以及这些函数对应的破坏性版本。

安全破坏性
appendnconc
reversenreverse
removedelete
remove-ifdelete-if
remove-duplicatesdelete-duplicates
substnsubst
subst-ifnsubst-if
unionnunion
intersectionnintersection
set-differencenset-difference

当确认修改列表是安全的时候，可以使用 delete 替换 remove ，用 nreverse 替换 reverse ，诸如此类。

即便你想完全摆脱构造，你也不必放弃在运行中 (on the fly)创建对象的可能性。 你需要做的是避免在运行中为它们分配空间和通过垃圾回收收回空间。通用方案是你自己预先分配内存块 (block of memory)，以及明确回收用过的块。预先可能意味着在编译期或者某些初始化例程中。具体情况还应具体分析。

例如，当情况允许我们利用一个有限大小的堆栈时，我们可以让堆栈在一个已经分配了空间的向量中增长或缩减，而不是构造它。Common Lisp 内置支持把向量作为堆栈使用。如果我们传给 make-array 可选的 fill-pointer 参数，我们将得到一个看起来可扩展的向量。 make-array 的第一个参数指定了分配给向量的存储量，而 fill-pointer 指定了初始有效长度：

  1. > (setf *print-array* t)
  2. T
  3. > (setf vec (make-array 10 :fill-pointer 2
  4.                            :initial-element nil))
  5. #(NIL NIL)

我们刚刚制造的向量对于操作序列的函数来说，仍好像只含有两个元素，

  1. > (length vec)
  2. 2

但它能够增长直到十个元素。因为 vec 有一个填充指针，我们可以使用 vector-push 和 vector-pop 函数推入和弹出元素，就像它是一个列表一样：

  1. > (vector-push 'a vec)
  2. 2
  3. > vec
  4. #(NIL NIL A)
  5. > (vector-pop vec)
  6. A
  7. > vec
  8. #(NIL NIL)

当我们调用 vector-push 时，它增加填充指针并返回它过去的值。只要填充指针小于 make-array 的第一个参数，我们就可以向这个向量中推入新元素；当空间用尽时， vector-push 返回 nil 。目前我们还可以向 vec 中推入八个元素。

使用带有填充指针的向量有一个缺点，就是它们不再是简单向量了。我们不得不使用 aref 来代替 svref 引用元素。代价需要和潜在的收益保持平衡。

  1. (defconstant dict (make-array 25000 :fill-pointer 0))
  3. (defun read-words (from)
  4.   (setf (fill-pointer dict) 0)
  5.   (with-open-file (in from :direction :input)
  6.     (do ((w (read-line in nil :eof)
  7.             (read-line in nil :eof)))
  8.         ((eql w :eof))
  9.       (vector-push w dict))))
  11. (defun xform (fn seq) (map-into seq fn seq))
  13. (defun write-words (to)
  14.   (with-open-file (out to :direction :output
  15.                           :if-exists :supersede)
  16.     (map nil #'(lambda (x)
  17.                  (fresh-line out)
  18.                  (princ x out))
  19.              (xform #'nreverse
  20.                     (sort (xform #'nreverse dict)
  21.                           #'string<)))))

图 13.3 生成同韵字辞典

当应用涉及很长的序列时，你可以用 map-into 代替 map 。 map-into 的第一个参数不是一个序列类型，而是用来存储结果的，实际的序列。这个序列可以是该函数接受的其他序列参数中的任何一个。所以，打个比方，如果你想为一个向量的每个元素加 1，你可以这么写：

  1. (setf v (map-into v #'1+ v))

图 13.3 展示了一个使用大向量应用的例子：一个生成简单的同韵字辞典 (或者更确切的说，一个不完全韵辞典)的程序。函数 read-line 从一个每行仅含有一个单词的文件中读取单词，而函数 write-words 将它们按照字母的逆序打印出来。比如，输出的起始可能是

  1. a amoeba alba samba marimba...

结束是

  1. ...megahertz gigahertz jazz buzz fuzz

利用填充指针和 map-into ，我们可以把程序写的既简单又高效。

在数值应用中要当心大数 (bignums)。大数运算需要构造，因此也就会比较慢。 即使程序的最后结果为大数，但是，通过调整计算，将中间结果保存在定长数中，这种优化也是有可能的。

另一个避免垃圾回收的方法是，鼓励编译器在栈上分配对象而不是在堆上。 如果你知道只是临时需要某个东西，你可以通过将它声明为 dynamic extent 来避免在堆上分配空间。

通过一个动态范围 (dynamic extent)变量声明，你告诉编译器，变量的值应该和变量保持相同的生命期。 什么时候值的生命期比变量长呢？这里有个例子：

  1. (defun our-reverse (lst)
  2.   (let ((rev nil))
  3.     (dolist (x lst)
  4.       (push x rev))
  5.     rev))

在 our-reverse 中，作为参数传入的列表以逆序被收集到 rev 中。当函数返回时，变量 rev 将不复存在。 然而，它的值 ── 一个逆序的列表 ── 将继续存活：它被送回调用函数，一个知道它的命运何去何从的地方。

相比之下，考虑如下 adjoin 实现：

  1. (defun our-adjoin (obj lst &rest args)
  2.   (if (apply #'member obj lst args)
  3.       lst
  4.       (cons obj lst)))

在这个例子里，我们可以从函数的定义看出， args 参数中的值 (列表) 哪儿也没去。它不必比存储它的变量活的更久。在这种情形下把它声明为动态范围的就比较有意义。如果我们加上这样的声明：

  1. (defun our-adjoin (obj lst &rest args)
  2.   (declare (dynamic-extent args))
  3.   (if (apply #'member obj lst args)
  4.       lst
  5.       (cons obj lst)))

那么编译器就可以 (但不是必须)在栈上为 args 分配空间，在 our-adjoin 返回后，它将自动被释放。