Lisp 實際上是兩種語言：一種能寫出快速執行的程序，一種則能讓你快速的寫出程序。 在程序開發的早期階段，你可以為了開發上的便捷舍棄程序的執行速度。一旦程序的結構開始固化，你就可以精煉其中的關鍵部分以使得它們執行的更快。
由于各個 Common Lisp 實現間的差異，很難針對優化給出通用的建議。在一個實現上使程序變快的修改也許在另一個實現上會使得程序變慢。這是難免的事兒。越強大的語言，離機器底層就越遠，離機器底層越遠，語言的不同實現沿著不同路徑趨向它的可能性就越大。因此，即便有一些技巧幾乎一定能夠讓程序運行的更快，本章的目的也只是建議而不是規定。
[TOC]
## 13.1 瓶頸規則 (The Bottleneck Rule)[](http://acl.readthedocs.org/en/latest/zhCN/ch13-cn.html#the-bottleneck-rule "Permalink to this headline")
不管是什么實現，關于優化都可以整理出三點規則：它應該關注瓶頸，它不應該開始的太早，它應該始于算法。
也許關于優化最重要的事情就是要意識到，程序中的大部分執行時間都是被少數瓶頸所消耗掉的。 正如[高德納](http://en.wikipedia.org/wiki/Donald_Knuth)所說，“在一個與 I/O 無關 (Non-I/O bound) 的程序中，大部分的運行時間集中在大概 3% 的源代碼中。”?[λ](http://acl.readthedocs.org/en/latest/zhCN/notes-cn.html#notes-213)?優化程序的這一部分將會使得它的運行速度明顯的提升；相反，優化程序的其他部分則是在浪費時間。
因此，優化程序時關鍵的第一步就是找到瓶頸。許多 Lisp 實現都提供性能分析器 (profiler) 來監視程序的運行并報告每一部分所花費的時間量。 為了寫出最為高效的代碼，性能分析器非常重要，甚至是必不可少的。 如果你所使用的 Lisp 實現帶有性能分析器，那么請在進行優化時使用它。另一方面，如果實現沒有提供性能分析器的話，那么你就不得不通過猜測來尋找瓶頸，而且這種猜測往往都是錯的！
瓶頸規則的一個推論是，不應該在程序的初期花費太多的精力在優化上。[高德納](http://en.wikipedia.org/wiki/Donald_Knuth)對此深信不疑：“過早的優化是一切 (至少是大多數) 問題的源頭。”?[λ](http://acl.readthedocs.org/en/latest/zhCN/notes-cn.html#notes-214)?在剛開始寫程序的時候，通常很難看清真正的瓶頸在哪，如果這個時候進行優化，你很可能是在浪費時間。優化也會使程序的修改變得更加困難，邊寫程序邊優化就像是在用風干非常快的顏料來畫畫一樣。
在適當的時候做適當的事情，可以讓你寫出更優秀的程序。 Lisp 的一個優點就是能讓你用兩種不同的工作方式來進行開發：很快地寫出運行較慢的代碼，或者，放慢寫程序的速度，精雕細琢，從而得出運行得較快的代碼。
在程序開發的初期階段，工作通常在第一種模式下進行，只有當性能成為問題的時候，才切換到第二種模式。 對于非常底層的語言，比如匯編，你必須優化程序的每一行。但這么做會浪費你大部分的精力，因為瓶頸僅僅是其中很小的那部分代碼。一個更加抽象的語言能夠讓你把主要精力集中在瓶頸上， 達到事半功倍的效果。
當真正開始優化的時候，還必須從最頂端入手。 在使用各種低層次的編碼技巧 (low-level coding tricks) 之前，請先確保你已經使用了最為高效的算法。 這么做的潛在好處相當大 ── 甚至可能大到你都不再需要玩那些奇淫技巧。 當然本規則還是要和前一個規則保持平衡。 有些時候，關于算法的決策必須盡早進行。
## 13.2 編譯 (Compilation)[](http://acl.readthedocs.org/en/latest/zhCN/ch13-cn.html#compilation "Permalink to this headline")
有五個參數可以控制代碼的編譯方式：?*speed*?(速度)代表編譯器產生代碼的速度；?*compilation-speed*?(編譯速度)代表程序被編譯的速度；?*safety*?(安全) 代表要對目標代碼進行錯誤檢查的數量；?*space*?(空間)代表目標代碼的大小和內存需求量；最后，?*debug*?(調試)代表為了調試而保留的信息量。
交互與解釋 (INTERACTIVE VS. INTERPRETED)
Lisp 是一種交互式語言 (Interactive Language)，但是交互式的語言不必都是解釋型的。早期的 Lisp 都通過解釋器實現，因此認為 Lisp 的特質都依賴于它是被解釋的想法就這么產生了。但這種想法是錯誤的：Common Lisp 既是編譯型語言，又是解釋型語言。
至少有兩種 Common Lisp 實現甚至都不包含解釋器。在這些實現中，輸入到頂層的表達式在求值前會被編譯。因此，把頂層叫做解釋器的這種說法，不僅是落伍的，甚至還是錯誤的。
編譯參數不是真正的變量。它們在聲明中被分配從?`0`?(最不重要) 到?`3`?(最重要) 的權值。如果一個主要的瓶頸發生在某個函數的內層循環中，我們或許可以添加如下的聲明：
~~~
(defun bottleneck (...)
(do (...)
(...)
(do (...)
(...)
(declare (optimize (speed 3) (safety 0)))
...)))
~~~
一般情況下，應該在代碼寫完并且經過完善測試之后，才考慮加上那么一句聲明。
要讓代碼在任何情況下都盡可能地快，可以使用如下聲明：
~~~
(declaim (optimize (speed 3)
(compilation-speed 0)
(safety 0)
(debug 0)))
~~~
考慮到前面提到的瓶頸規則?[[1]](http://acl.readthedocs.org/en/latest/zhCN/ch13-cn.html#id9)?，這種苛刻的做法可能并沒有什么必要。
另一類特別重要的優化就是由 Lisp 編譯器完成的尾遞歸優化。當?*speed*?(速度)的權值最大時，所有支持尾遞歸優化的編譯器都將保證對代碼進行這種優化。
如果在一個調用返回時調用者中沒有殘余的計算，該調用就被稱為尾遞歸。下面的代碼返回列表的長度：
~~~
(defun length/r (lst)
(if (null lst)
0
(1+ (length/r (cdr lst)))))
~~~
這個遞歸調用不是尾遞歸，因為當它返回以后，它的值必須傳給?`1+`?。相反，這是一個尾遞歸的版本，
~~~
(defun length/rt (lst)
(labels ((len (lst acc)
(if (null lst)
acc
(len (cdr lst) (1+ acc)))))
(len lst 0)))
~~~
更準確地說，局部函數?`len`?是尾遞歸調用，因為當它返回時，調用函數已經沒什么事情可做了。 和?`length/r`?不同的是，它不是在遞歸回溯的時候構建返回值，而是在遞歸調用的過程中積累返回值。 在函數的最后一次遞歸調用結束之后，?`acc`?參數就可以作為函數的結果值被返回。
出色的編譯器能夠將一個尾遞歸編譯成一個跳轉 (goto)，因此也能將一個尾遞歸函數編譯成一個循環。在典型的機器語言代碼中，當第一次執行到表示?`len`?的指令片段時，棧上會有信息指示在返回時要做些什么。由于在遞歸調用后沒有殘余的計算，該信息對第二層調用仍然有效：第二層調用返回后我們要做的僅僅就是從第一層調用返回。 因此，當進行第二層調用時，我們只需給參數設置新的值，然后跳轉到函數的起始處繼續執行就可以了，沒有必要進行真正的函數調用。
另一個利用函數調用抽象，卻沒有開銷的方法是使函數內聯編譯。對于那些調用開銷比函數體的執行代價還高的小型函數來說，這種技術非常有價值。例如，以下代碼用于判斷列表是否僅有一個元素：
~~~
(declaim (inline single?))
(defun single? (lst)
(and (consp lst) (null (cdr lst))))
~~~
因為這個函數是在全局被聲明為內聯的，引用了?`single?`?的函數在編譯后將不需要真正的函數調用。?[[2]](http://acl.readthedocs.org/en/latest/zhCN/ch13-cn.html#id10)?如果我們定義一個調用它的函數，
~~~
(defun foo (x)
(single? (bar x)))
~~~
當?`foo`?被編譯后，?`single?`?函數體中的代碼將會被編譯進?`foo`?的函數體，就好像我們直接寫以下代碼一樣：
~~~
(defun foo (x)
(let ((lst (bar x)))
(and (consp lst) (null (cdr lst)))))
~~~
內聯編譯有兩個限制： 首先，遞歸函數不能內聯。 其次，如果一個內聯函數被重新定義，我們就必須重新編譯調用它的任何函數，否則調用仍然使用原來的定義。
在一些早期的 Lisp 方言中，有時候會使用宏（ 10.2 節）來避免函數調用。這種做法在 Common Lisp 中通常是沒有必要的。
不同 Lisp 編譯器的優化方式千差萬別。 如果你想了解你的編譯器為某個函數生成的代碼，試著調用?`disassemble`?函數：它接受一個函數或者函數名，并顯示該函數編譯后的形式。 即便你看到的東西是完全無法理解的，你仍然可以使用?`disassemble`?來判斷聲明是否起效果：編譯函數的兩個版本，一個使用優化聲明，另一個不使用優化聲明，然后觀察由?`disassemble`?顯示的兩組代碼之間是否有差異。 同樣的技巧也可以用于檢驗函數是否被內聯編譯。 不論情況如何，都請優先考慮使用編譯參數，而不是手動調優的方式來優化代碼。
## 13.3 類型聲明 (Type Declarations)[](http://acl.readthedocs.org/en/latest/zhCN/ch13-cn.html#type-declarations "Permalink to this headline")
如果 Lisp 不是你所學的第一門編程語言，那么你也許會感到困惑，為什么這本書還沒說到類型聲明這件事來？畢竟，在很多流行的編程語言中，類型聲明是必須要做的。
在不少編程語言里，你必須為每個變量聲明類型，并且變量也只可以持有與該類型相一致的值。 這種語言被稱為*強類型*(*strongly typed*) 語言。 除了給程序員們徒增了許多負擔外，這種方式還限制了你能做的事情。 使用這種語言，很難寫出那些需要多種類型的參數一起工作的函數，也很難定義出可以包含不同種類元素的數據結構。 當然，這種方式也有它的優勢，比如無論何時當編譯器碰到一個加法運算，它都能夠事先知道這是一個什么類型的加法運算。如果兩個參數都是整數類型，編譯器可以直接在目標代碼中生成一個固定 (hard-wire) 的整數加法運算。
正如 2.15 節所講，Common Lisp 使用一種更加靈活的方式：顯式類型 (manifest typing)?[[3]](http://acl.readthedocs.org/en/latest/zhCN/ch13-cn.html#id11)?。有類型的是值而不是變量。變量可以用于任何類型的對象。
當然，這種靈活性需要付出一定的速度作為代價。 由于?`+`?可以接受好幾種不同類型的數，它不得不在運行時查看每個參數的類型來決定采用哪種加法運算。
在某些時候，如果我們要執行的全都是整數的加法，那么每次查看參數類型的這種做法就說不上高效了。 Common Lisp 處理這種問題的方法是：讓程序員盡可能地提示編譯器。 比如說，如果我們提前就能知道某個加法運算的兩個參數是定長數 (fixnums) ，那么就可以對此進行聲明，這樣編譯器就會像 C 語言的那樣為我們生成一個固定的整數加法運算。
因為顯式類型也可以通過聲明類型來生成高效的代碼，所以強類型和顯式類型兩種方式之間的差別并不在于運行速度。 真正的區別是，在強類型語言中，類型聲明是強制性的，而顯式類型則不強加這樣的要求。 在 Common Lisp 中，類型聲明完全是可選的。它們可以讓程序運行的更快，但(除非錯誤)不會改變程序的行為。
全局聲明以?`declaim`?伴隨一個或多個聲明的形式來實現。一個類型聲明是一個列表，包含了符號?`type`?，后跟一個類型名，以及一個或多個變量組成。舉個例子，要為一個全局變量聲明類型，可以這么寫：
~~~
(declaim (type fixnum *count*))
~~~
在 ANSI Common Lisp 中，可以省略?`type`?符號，將聲明簡寫為：
~~~
(declaim (fixnum *count*))
~~~
局部聲明通過?`declare`?完成，它接受的參數和?`declaim`?的一樣。 聲明可以放在那些創建變量的代碼體之前：如?`defun`?、?`lambda`?、`let`?、?`do`?，諸如此類。 比如說，要把一個函數的參數聲明為定長數，可以這么寫：
~~~
(defun poly (a b x)
(declare (fixnum a b x))
(+ (* a (expt x 2)) (* b x)))
~~~
在類型聲明中的變量名指的就是該聲明所在的上下文中的那個變量 ── 那個通過賦值可以改變它的值的變量。
你也可以通過?`the`?為某個表達式的值聲明類型。 如果我們提前就知道?`a`?、?`b`?和?`x`?是足夠小的定長數，并且它們的和也是定長數的話，那么可以進行以下聲明：
~~~
(defun poly (a b x)
(declare (fixnum a b x))
(the fixnum (+ (the fixnum (* a (the fixnum (expt x 2))))
(the fixnum (* b x)))))
~~~
看起來是不是很笨拙啊？幸運的是有兩個原因讓你很少會這樣使用?`the`?把你的數值運算代碼變得散亂不堪。其一是很容易通過宏，來幫你插入這些聲明。其二是某些實現使用了特殊的技巧，即便沒有類型聲明的定長數運算也能足夠快。
Common Lisp 中有相當多的類型 ── 恐怕有無數種類型那么多，如果考慮到你可以自己定義新的類型的話。 類型聲明只在少數情況下至關重要，可以遵照以下兩條規則來進行：
1. 當函數可以接受若干不同類型的參數(但不是所有類型)時，可以對參數的類型進行聲明。如果你知道一個對?`+`?的調用總是接受定長數類型的參數，或者一個對?`aref`?的調用第一個參數總是某種特定種類的數組，那么進行類型聲明是值得的。
2. 通常來說，只有對類型層級中接近底層的類型進行聲明，才是值得的：將某個東西的類型聲明為?`fixnum`?或者?`simple-array`?也許有用，但將某個東西的類型聲明為?`integer`?或者?`sequence`?或許就沒用了。
類型聲明對內容復雜的對象特別重要，這包括數組、結構和對象實例。這些聲明可以在兩個方面提升效率：除了可以讓編譯器來決定函數參數的類型以外，它們也使得這些對象可以在內存中更高效地表示。
如果對數組元素的類型一無所知的話，這些元素在內存中就不得不用一塊指針來表示。但假如預先就知道數組包含的元素僅僅是 ── 比方說 ── 雙精度浮點數 (double-floats)，那么這個數組就可以用一組實際的雙精度浮點數來表示。這樣數組將占用更少的空間，因為我們不再需要額外的指針指向每一個雙精度浮點數；同時，對數組元素的訪問也將更快，因為我們不必沿著指針去讀取和寫元素。
**圖 13.1：指定元素類型的效果**
你可以通過?`make-array`?的?`:element-type`?參數指定數組包含值的種類。這樣的數組被稱為*特化數組*(specialized array)。 圖 13.1 為我們展示了如下代碼在多數實現上求值后發生的事情：
~~~
(setf x (vector 1.234d0 2.345d0 3.456d0)
y (make-array 3 :element-type 'double-float)
(aref y 0) 1.234d0
(aref y 1) 2.345d0
(aref y 2）3.456d0))
~~~
圖 13.1 中的每一個矩形方格代表內存中的一個字 (a word of memory)。這兩個數組都由未特別指明長度的頭部 (header) 以及后續 三個元素的某種表示構成。對于?`x`?來說，每個元素都由一個指針表示。此時每個指針碰巧都指向雙精度浮點數，但實際上我們可以存儲任何類型的對象到這個向量中。對?`y`?來說，每個元素實際上都是雙精度浮點數。?`y`?更快而且占用更少空間，但意味著它的元素只能是雙精度浮點數。
注意我們使用?`aref`?來引用?`y`?的元素。一個特化的向量不再是一個簡單向量，因此我們不再能夠通過?`svref`?來引用它的元素。
除了在創建數組時指定元素的類型，你還應該在使用數組的代碼中聲明數組的維度以及它的元素類型。一個完整的向量聲明如下：
~~~
(declare (type (vector fixnum 20) v))
~~~
以上代碼聲明了一個僅含有定長數，并且長度固定為?`20`?的向量。
~~~
(setf a (make-array '(1000 1000)
:element-type 'single-float
:initial-element 1.0s0))
(defun sum-elts (a)
(declare (type (simple-array single-float (1000 1000))
a))
(let ((sum 0.0s0))
(declare (type single-float sum))
(dotimes (r 1000)
(dotimes (c 1000)
(incf sum (aref a r c))))
sum))
~~~
**圖 13.2 對數組元素求和**
最為通用的數組聲明形式由數組類型以及緊接其后的元素類型和一個維度列表構成：
~~~
(declare (type (simple-array fixnum (4 4)) ar))
~~~
圖 13.2 展示了如何創建一個 1000×1000 的單精度浮點數數組，以及如何編寫一個將該數組元素相加的函數。數組以行主序 (row-major order)存儲，遍歷時也應盡可能按此順序進行。
我們將用?`time`?來比較?`sum-elts`?在有聲明和無聲明兩種情況下的性能。?`time`?宏顯示表達式求值所花費時間的某種度量(取決于實現)。對被編譯的函數求取時間才是有意義的。在某個實現中，如果我們以獲取最快速代碼的編譯參數編譯?`sum-elts`?，它將在不到半秒的時間內返回：
~~~
> (time (sum-elts a))
User Run Time = 0.43 seconds
1000000.0
~~~
如果我們把?*sum-elts*?中的類型聲明去掉并重新編譯它，同樣的計算將花費超過5秒的時間：
~~~
> (time (sum-elts a))
User Run Time = 5.17 seconds
1000000.0
~~~
類型聲明的重要性 ── 特別是對數組和數來說 ── 怎么強調都不過分。上面的例子中，僅僅兩行代碼就可以讓?`sum-elts`?變快 12 倍。
## 13.4 避免垃圾 (Garbage Avoidance)[](http://acl.readthedocs.org/en/latest/zhCN/ch13-cn.html#garbage-avoidance "Permalink to this headline")
Lisp 除了可以讓你推遲考慮變量的類型以外，它還允許你推遲對內存分配的考慮。 在程序的早期階段，暫時忽略內存分配和臭蟲等問題，將有助于解放你的想象力。 等到程序基本固定下來以后，就可以開始考慮怎么減少動態分配，從而讓程序運行得更快。
但是，并不是構造（consing）用得少的程序就一定快。 多數 Lisp 實現一直使用著差勁的垃圾回收器，在這些實現中，過多的內存分配容易讓程序運行變得緩慢。 因此，『高效的程序應該盡可能地減少?`cons`?的使用』這種觀點，逐漸成為了一種傳統。 最近這種傳統開始有所改變，因為一些實現已經用上了相當先進（sophisticated）的垃圾回收器，它們實行一種更為高效的策略：創建新的對象，用完之后拋棄而不是進行回收。
本節介紹了幾種方法，用于減少程序中的構造。 但構造數量的減少是否有利于加快程序的運行，這一點最終還是取決于實現。 最好的辦法就是自己去試一試。
減少構造的辦法有很多種。 有些辦法對程序的修改非常少。 例如，最簡單的方法就是使用破壞性函數。 下表羅列了一些常用的函數，以及這些函數對應的破壞性版本。
| 安全 | 破壞性 |
| --- | --- |
| append | nconc |
| reverse | nreverse |
| remove | delete |
| remove-if | delete-if |
| remove-duplicates | delete-duplicates |
| subst | nsubst |
| subst-if | nsubst-if |
| union | nunion |
| intersection | nintersection |
| set-difference | nset-difference |
當確認修改列表是安全的時候，可以使用?`delete`?替換?`remove`?，用?`nreverse`?替換?`reverse`?，諸如此類。
即便你想完全擺脫構造，你也不必放棄在運行中 (on the fly)創建對象的可能性。 你需要做的是避免在運行中為它們分配空間和通過垃圾回收收回空間。通用方案是你自己預先分配內存塊 (block of memory)，以及明確回收用過的塊。*預先*可能意味著在編譯期或者某些初始化例程中。具體情況還應具體分析。
例如，當情況允許我們利用一個有限大小的堆棧時，我們可以讓堆棧在一個已經分配了空間的向量中增長或縮減，而不是構造它。Common Lisp 內置支持把向量作為堆棧使用。如果我們傳給?`make-array`?可選的?`fill-pointer`?參數，我們將得到一個看起來可擴展的向量。?`make-array`?的第一個參數指定了分配給向量的存儲量，而?`fill-pointer`?指定了初始有效長度：
~~~
> (setf *print-array* t)
T
> (setf vec (make-array 10 :fill-pointer 2
:initial-element nil))
#(NIL NIL)
~~~
我們剛剛制造的向量對于操作序列的函數來說，仍好像只含有兩個元素，
~~~
> (length vec)
2
~~~
但它能夠增長直到十個元素。因為?`vec`?有一個填充指針，我們可以使用?`vector-push`?和?`vector-pop`?函數推入和彈出元素，就像它是一個列表一樣：
~~~
> (vector-push 'a vec)
2
> vec
#(NIL NIL A)
> (vector-pop vec)
A
> vec
#(NIL NIL)
~~~
當我們調用?`vector-push`?時，它增加填充指針并返回它過去的值。只要填充指針小于?`make-array`?的第一個參數，我們就可以向這個向量中推入新元素；當空間用盡時，?`vector-push`?返回?`nil`?。目前我們還可以向?`vec`?中推入八個元素。
使用帶有填充指針的向量有一個缺點，就是它們不再是簡單向量了。我們不得不使用?`aref`?來代替?`svref`?引用元素。代價需要和潛在的收益保持平衡。
~~~
(defconstant dict (make-array 25000 :fill-pointer 0))
(defun read-words (from)
(setf (fill-pointer dict) 0)
(with-open-file (in from :direction :input)
(do ((w (read-line in nil :eof)
(read-line in nil :eof)))
((eql w :eof))
(vector-push w dict))))
(defun xform (fn seq) (map-into seq fn seq))
(defun write-words (to)
(with-open-file (out to :direction :output
:if-exists :supersede)
(map nil #'(lambda (x)
(fresh-line out)
(princ x out))
(xform #'nreverse
(sort (xform #'nreverse dict)
#'string<)))))
~~~
**圖 13.3 生成同韻字辭典**
當應用涉及很長的序列時，你可以用?`map-into`?代替?`map`?。?`map-into`?的第一個參數不是一個序列類型，而是用來存儲結果的，實際的序列。這個序列可以是該函數接受的其他序列參數中的任何一個。所以，打個比方，如果你想為一個向量的每個元素加 1，你可以這么寫：
~~~
(setf v (map-into v #'1+ v))
~~~
圖 13.3 展示了一個使用大向量應用的例子：一個生成簡單的同韻字辭典 (或者更確切的說，一個不完全韻辭典)的程序。函數?`read-line`?從一個每行僅含有一個單詞的文件中讀取單詞，而函數?`write-words`?將它們按照字母的逆序打印出來。比如，輸出的起始可能是
~~~
a amoeba alba samba marimba...
~~~
結束是
~~~
...megahertz gigahertz jazz buzz fuzz
~~~
利用填充指針和?`map-into`?，我們可以把程序寫的既簡單又高效。
在數值應用中要當心大數 (bignums)。大數運算需要構造，因此也就會比較慢。 即使程序的最后結果為大數，但是，通過調整計算，將中間結果保存在定長數中，這種優化也是有可能的。
另一個避免垃圾回收的方法是，鼓勵編譯器在棧上分配對象而不是在堆上。 如果你知道只是臨時需要某個東西，你可以通過將它聲明為?`dynamic?extent`?來避免在堆上分配空間。
通過一個動態范圍 (dynamic extent)變量聲明，你告訴編譯器，變量的值應該和變量保持相同的生命期。 什么時候值的生命期比變量長呢？這里有個例子：
~~~
(defun our-reverse (lst)
(let ((rev nil))
(dolist (x lst)
(push x rev))
rev))
~~~
在?`our-reverse`?中，作為參數傳入的列表以逆序被收集到?`rev`?中。當函數返回時，變量?`rev`?將不復存在。 然而，它的值 ── 一個逆序的列表 ── 將繼續存活：它被送回調用函數，一個知道它的命運何去何從的地方。
相比之下，考慮如下?`adjoin`?實現：
~~~
(defun our-adjoin (obj lst &rest args)
(if (apply #'member obj lst args)
lst
(cons obj lst)))
~~~
在這個例子里，我們可以從函數的定義看出，?`args`?參數中的值 (列表) 哪兒也沒去。它不必比存儲它的變量活的更久。在這種情形下把它聲明為動態范圍的就比較有意義。如果我們加上這樣的聲明：
~~~
(defun our-adjoin (obj lst &rest args)
(declare (dynamic-extent args))
(if (apply #'member obj lst args)
lst
(cons obj lst)))
~~~
那么編譯器就可以 (但不是必須)在棧上為?`args`?分配空間，在?`our-adjoin`?返回后，它將自動被釋放。
## 13.5 示例: 存儲池 (Example: Pools)[](http://acl.readthedocs.org/en/latest/zhCN/ch13-cn.html#example-pools "Permalink to this headline")
對于涉及數據結構的應用，你可以通過在一個存儲池 (pool)中預先分配一定數量的結構來避免動態分配。當你需要一個結構時，你從池中取得一份，當你用完后，再把它送回池中。為了演示存儲池的使用，我們將快速的編寫一段記錄港口中船舶數量的程序原型 (prototype of a program)，然后用存儲池的方式重寫它。
~~~
(defparameter *harbor* nil)
(defstruct ship
name flag tons)
(defun enter (n f d)
(push (make-ship :name n :flag f :tons d)
*harbor*))
(defun find-ship (n)
(find n *harbor* :key #'ship-name))
(defun leave (n)
(setf *harbor*
(delete (find-ship n) *harbor*)))
~~~
**圖 13.4 港口**
圖 13.4 中展示的是第一個版本。 全局變量?`harbor`?是一個船只的列表， 每一艘船只由一個?`ship`?結構表示。 函數?`enter`?在船只進入港口時被調用；?`find-ship`?根據給定名字 (如果有的話) 來尋找對應的船只；最后，?`leave`?在船只離開港口時被調用。
一個程序的初始版本這么寫簡直是棒呆了，但它會產生許多的垃圾。當這個程序運行時，它會在兩個方面構造：當船只進入港口時，新的結構將會被分配；而?`harbor`?的每一次增大都需要使用構造。
我們可以通過在編譯期分配空間來消除這兩種構造的源頭 (sources of consing)。圖 13.5 展示了程序的第二個版本，它根本不會構造。
~~~
(defconstant pool (make-array 1000 :fill-pointer t))
(dotimes (i 1000)
(setf (aref pool i) (make-ship)))
(defconstant harbor (make-hash-table :size 1100
:test #'eq))
(defun enter (n f d)
(let ((s (if (plusp (length pool))
(vector-pop pool)
(make-ship))))
(setf (ship-name s) n
(ship-flag s) f
(ship-tons s) d
(gethash n harbor) s)))
(defun find-ship (n) (gethash n harbor))
(defun leave (n)
(let ((s (gethash n harbor)))
(remhash n harbor)
(vector-push s pool)))
~~~
**圖 13.5 港口（第二版）**
嚴格說來，新的版本仍然會構造，只是不在運行期。在第二個版本中，?`harbor`?從列表變成了哈希表，所以它所有的空間都在編譯期分配了。 一千個?`ship`?結構體也會在編譯期被創建出來，并被保存在向量池(vector pool) 中。(如果?`:fill-pointer`?參數為?`t`?，填充指針將指向向量的末尾。) 此時，當?`enter`?需要一個新的結構時，它只需從池中取來一個便是，無須再調用?`make-ship`?。 而且當`leave`?從?`harbor`?中移除一艘?`ship`?時，它把它送回池中，而不是拋棄它。
我們使用存儲池的行為實際上是肩負起內存管理的工作。這是否會讓我們的程序更快仍取決于我們的 Lisp 實現怎樣管理內存。總的說來，只有在那些仍使用著原始垃圾回收器的實現中，或者在那些對 GC 的不可預見性比較敏感的實時應用中才值得一試。
## 13.6 快速操作符 (Fast Operators)[](http://acl.readthedocs.org/en/latest/zhCN/ch13-cn.html#fast-operators "Permalink to this headline")
本章一開始就宣稱 Lisp 是兩種不同的語言。就某種意義來講這確實是正確的。如果你仔細看過 Common Lisp 的設計，你會發現某些特性主要是為了速度，而另外一些主要為了便捷性。
例如，你可以通過三個不同的函數取得向量給定位置上的元素：?`elt`?、?`aref`?、?`svref`?。如此的多樣性允許你把一個程序的性能提升到極致。 所以如果你可以使用?`svref`?，完事兒！ 相反，如果對某段程序來說速度很重要的話，或許不應該調用?`elt`?，它既可以用于數組也可以用于列表。
對于列表來說，你應該調用?`nth`?，而不是?`elt`?。然而只有單一的一個函數 ──?`length`?── 用于計算任何一個序列的長度。為什么 Common Lisp 不單獨為列表提供一個特定的版本呢？因為如果你的程序正在計算一個列表的長度，它在速度上已經輸了。在這個 例子中，就像許多其他的例子一樣，語言的設計暗示了哪些會是快速的而哪些不是。
另一對相似的函數是?`eql`?和?`eq`?。前者是驗證同一性 (identity) 的默認判斷式，但如果你知道參數不會是字符或者數字時，使用后者其實更快。兩個對象?*eq*?只有當它們處在相同的內存位置上時才成立。數字和字符可能不會與任何特定的內存位置相關，因此?`eq`?不適用于它們 (即便多數實現中它仍然能用于定長數)。對于其他任何種類的參數，?`eq`?和?`eql`?將返回相同的值。
使用?`eq`?來比較對象總是最快的，因為 Lisp 所需要比較的僅僅是指向對象的指針。因此?`eq`?哈希表 (如圖 13.5 所示) 應該會提供最快的訪問。 在一個?`eq`?哈希表中，?`gethash`?可以只根據指針查找，甚至不需要查看它們指向的是什么。然而，訪問不是唯一要考慮的因素；?*eq*?和?*eql*?哈希表在拷貝型垃圾回收算法 (copying garbage collection algorithm)中會引起額外的開銷，因為垃圾回收后需要對一些哈希值重新進行計算 (rehashing)。如果這變成了一個問題，最好的解決方案是使用一個把定長數作為鍵值的?`eql`?哈希表。
當被調函數有一個余留參數時，調用?`reduce`?可能是比?`apply`?更高效的一種方式。例如，相比
~~~
(apply #'+ '(1 2 3))
~~~
寫成如下可以更高效：
~~~
(reduce #'+ '(1 2 3))
~~~
它不僅有助于調用正確的函數，還有助于按照正確的方式調用它們。余留、可選和關鍵字參數 是昂貴的。只使用普通參數，函數調用中的參量會被調用者簡單的留在被調者能夠找到的地方。但其他種類的參數涉及運行時的處理。關鍵字參數是最差的。針對內置函數，優秀的編譯器采用特殊的辦法把使用關鍵字參量的調用編譯成快速代碼 (fast code)。但對于你自己編寫的函數，避免在程序中對速度敏感的部分使用它們只有好處沒有壞處。另外，不把大量的參量都放到余留參數中也是明智的舉措，如果這可以避免的話。
不同的編譯器有時也會有一些它們獨到優化。例如，有些編譯器可以針對鍵值是一個狹小范圍中的整數的?`case`?語句進行優化。查看你的用戶手冊來了解那些實現特有的優化的建議吧。
## 13.7 二階段開發 (Two-Phase Development)[](http://acl.readthedocs.org/en/latest/zhCN/ch13-cn.html#two-phase-development "Permalink to this headline")
在以速度至上的應用中，你也許想要使用諸如 C 或者匯編這樣的低級語言來重寫一個 Lisp 程序的某部分。你可以對用任何語言編寫的程序使用這一技巧 ── C 程序的關鍵部分經常用匯編重寫 ── 但語言越抽象，用兩階段（two phases）開發程序的好處就越明顯。
Common Lisp 沒有規定如何集成其他語言所編寫的代碼。這部分留給了實現決定，而幾乎所有的實現都提供了某種方式來實現它。
使用一種語言編寫程序然后用另一種語言重寫它其中部分看起來可能是一種浪費。事實上，經驗顯示這是一種好的開發軟件的方式。先針對功能、然后是速度比試著同時達成兩者來的簡單。
如果編程完全是一個機械的過程 ── 簡單的把規格說明翻譯為代碼 ── 在一步中把所有的事情都搞定也許是合理的。但編程永遠不是如此。不論規格說明多么精確， 編程總是涉及一定量的探索 ── 通常比任何人能預期到的還多的多。
一份好的規格說明，也許會讓編程看起來像是簡單的把它們翻譯成代碼的過程。這是一個普遍的誤區。編程必定涉及探索，因為規格說明必定含糊不清。如果它們不含糊的話，它們就都算不上規格說明。
在其他領域，盡可能精準的規格說明也許是可取的。如果你要求一塊金屬被切割成某種形狀，最好準確的說出你想要的。但這個規則不適用于軟件，因為程序和規格說明由相同的東西構成：文本。你不可能編寫出完全合意的規格說明。如果規格說明有那么精確的話，它們就變成程序了。?[λ](http://acl.readthedocs.org/en/latest/zhCN/notes-cn.html#notes-229)
對于存在著可觀數量的探索的應用 (再一次，比任何人承認的還要多，將實現分成兩個階段是值得的。而且在第一階段中你所使用的手段 (medium) 不必就是最后的那個。例如，制作銅像的標準方法是先從粘土開始。你先用粘土做一個塑像出來，然后用它做一個模子，在這個模子中鑄造銅像。在最后的塑像中是沒有丁點粘土的，但你可以從銅像的形狀中認識到它發揮的作用。試想下從一開始就只用一塊兒銅和一個鑿子來制造這么個一模一樣的塑像要多難啊！出于相同的原因，首先用 Lisp 來編寫程序，然后用 C 改寫它，要比從頭開始就用 C 編寫這個程序要好。
## Chapter 13 總結 (Summary)[](http://acl.readthedocs.org/en/latest/zhCN/ch13-cn.html#chapter-13-summary "Permalink to this headline")
1. 不應過早開始優化，應該關注瓶頸，而且應該從算法開始。
2. 有五個不同的參數控制編譯。它們可以在本地聲明也可以在全局聲明。
3. 優秀的編譯器能夠優化尾遞歸，將一個尾遞歸的函數轉換為一個循環。內聯編譯是另一種避免函數調用的方法。
4. 類型聲明并不是必須的，但它們可以讓一個程序更高效。類型聲明對于處理數值和數組的代碼特別重要。
5. 少的構造可以讓程序更快，特別是在使用著原始的垃圾回收器的實現中。解決方案是使用破壞性函數、預先分配空間塊、以及在棧上分配。
6. 某些情況下，從預先分配的存儲池中提取對象可能是有價值的。
7. Common Lisp 的某些部分是為了速度而設計的，另一些則為了靈活性。
8. 編程必定存在探索的過程。探索和優化應該被分開 ── 有時甚至需要使用不同的語言。
## Chapter 13 練習 (Exercises)[](http://acl.readthedocs.org/en/latest/zhCN/ch13-cn.html#chapter-13-exercises "Permalink to this headline")
1. 檢驗你的編譯器是否支持 (observe)內斂聲明。
2. 將下述函數重寫為尾遞歸形式。它被編譯后能快多少？
~~~
(defun foo (x)
(if (zerop x)
0
(1+ (foo (1- x)))))
注意：你需要增加額外的參數。
~~~
1. 為下述程序增加聲明。你能讓它們變快多少？
~~~
(a) 在 5.7 節中的日期運算代碼。
(b) 在 9.8 節中的光線跟蹤器 (ray-tracer)。
~~~
1. 重寫 3.15 節中的廣度優先搜索的代碼讓它盡可能減少使用構造。
2. 使用存儲池修改 4.7 節中的二叉搜索的代碼。
腳注
[[1]](http://acl.readthedocs.org/en/latest/zhCN/ch13-cn.html#id4) | 較早的實現或許不提供?`declaim`?；需要使用?`proclaim`?并且引用這些參量 (quote the argument)。
[[2]](http://acl.readthedocs.org/en/latest/zhCN/ch13-cn.html#id5) | 為了讓內聯聲明 (inline declaration) 有效，你同時必須設置編譯參數，告訴它你想獲得最快的代碼。
[[3]](http://acl.readthedocs.org/en/latest/zhCN/ch13-cn.html#id6) | 有兩種方法可以描述 Lisp 聲明類型 (typing) 的方式：從類型信息被存放的位置或者從它被使用的時間。顯示類型 (manifest typing) 的意思是類型信息與數據對象 (data objects) 綁定，而運行時類型(run-time typing) 的意思是類型信息在運行時被使用。實際上，兩者是一回事兒。
