13.5 示例: 存储池 (Example: Pools)

对于涉及数据结构的应用，你可以通过在一个存储池 (pool)中预先分配一定数量的结构来避免动态分配。当你需要一个结构时，你从池中取得一份，当你用完后，再把它送回池中。为了演示存储池的使用，我们将快速的编写一段记录港口中船舶数量的程序原型 (prototype of a program)，然后用存储池的方式重写它。

  1. (defparameter *harbor* nil)
  3. (defstruct ship
  4.   name flag tons)
  6. (defun enter (n f d)
  7.   (push (make-ship :name n :flag f :tons d)
  8.         *harbor*))
  10. (defun find-ship (n)
  11.   (find n *harbor* :key #'ship-name))
  13. (defun leave (n)
  14.   (setf *harbor*
  15.         (delete (find-ship n) *harbor*)))

图 13.4 港口

图 13.4 中展示的是第一个版本。 全局变量 harbor 是一个船只的列表， 每一艘船只由一个 ship 结构表示。 函数 enter 在船只进入港口时被调用； find-ship 根据给定名字 (如果有的话) 来寻找对应的船只；最后， leave 在船只离开港口时被调用。

一个程序的初始版本这么写简直是棒呆了，但它会产生许多的垃圾。当这个程序运行时，它会在两个方面构造：当船只进入港口时，新的结构将会被分配；而 harbor 的每一次增大都需要使用构造。

我们可以通过在编译期分配空间来消除这两种构造的源头 (sources of consing)。图 13.5 展示了程序的第二个版本，它根本不会构造。

  1. (defconstant pool (make-array 1000 :fill-pointer t))
  3. (dotimes (i 1000)
  4.   (setf (aref pool i) (make-ship)))
  6. (defconstant harbor (make-hash-table :size 1100
  7.                                      :test #'eq))
  9. (defun enter (n f d)
  10.   (let ((s (if (plusp (length pool))
  11.                (vector-pop pool)
  12.                (make-ship))))
  13.     (setf (ship-name s)        n
  14.           (ship-flag s)        f
  15.           (ship-tons s)        d
  16.           (gethash n harbor) s)))
  18. (defun find-ship (n) (gethash n harbor))
  20. (defun leave (n)
  21.   (let ((s (gethash n harbor)))
  22.     (remhash n harbor)
  23.     (vector-push s pool)))

图 13.5 港口（第二版）

严格说来，新的版本仍然会构造，只是不在运行期。在第二个版本中， harbor 从列表变成了哈希表，所以它所有的空间都在编译期分配了。 一千个 ship 结构体也会在编译期被创建出来，并被保存在向量池(vector pool) 中。(如果 :fill-pointer 参数为 t ，填充指针将指向向量的末尾。) 此时，当 enter 需要一个新的结构时，它只需从池中取来一个便是，无须再调用 make-ship 。 而且当 leave 从 harbor 中移除一艘 ship 时，它把它送回池中，而不是抛弃它。

我们使用存储池的行为实际上是肩负起内存管理的工作。这是否会让我们的程序更快仍取决于我们的 Lisp 实现怎样管理内存。总的说来，只有在那些仍使用着原始垃圾回收器的实现中，或者在那些对 GC 的不可预见性比较敏感的实时应用中才值得一试。