第十三章：速度

Lisp 實際上是兩種語言：一種能寫出快速執(zhí)行的程序，一種則能讓你快速的寫出程序。 在程序開發(fā)的早期階段，你可以為了開發(fā)上的便捷舍棄程序的執(zhí)行速度。一旦程序的結(jié)構(gòu)開始固化，你就可以精煉其中的關(guān)鍵部分以使得它們執(zhí)行的更快。

由于各個 Common Lisp 實現(xiàn)間的差異，很難針對優(yōu)化給出通用的建議。在一個實現(xiàn)上使程序變快的修改也許在另一個實現(xiàn)上會使得程序變慢。這是難免的事兒。越強大的語言，離機器底層就越遠(yuǎn)，離機器底層越遠(yuǎn)，語言的不同實現(xiàn)沿著不同路徑趨向它的可能性就越大。因此，即便有一些技巧幾乎一定能夠讓程序運行的更快，本章的目的也只是建議而不是規(guī)定。

13.1 瓶頸規(guī)則 (The Bottleneck Rule)

不管是什么實現(xiàn)，關(guān)于優(yōu)化都可以整理出三點規(guī)則：它應(yīng)該關(guān)注瓶頸，它不應(yīng)該開始的太早，它應(yīng)該始于算法。

也許關(guān)于優(yōu)化最重要的事情就是要意識到，程序中的大部分執(zhí)行時間都是被少數(shù)瓶頸所消耗掉的。 正如高德納所說，“在一個與 I/O 無關(guān) (Non-I/O bound) 的程序中，大部分的運行時間集中在大概 3% 的源代碼中?！?λ?優(yōu)化程序的這一部分將會使得它的運行速度明顯的提升；相反，優(yōu)化程序的其他部分則是在浪費時間。

因此，優(yōu)化程序時關(guān)鍵的第一步就是找到瓶頸。許多 Lisp 實現(xiàn)都提供性能分析器 (profiler) 來監(jiān)視程序的運行并報告每一部分所花費的時間量。 為了寫出最為高效的代碼，性能分析器非常重要，甚至是必不可少的。 如果你所使用的 Lisp 實現(xiàn)帶有性能分析器，那么請在進(jìn)行優(yōu)化時使用它。另一方面，如果實現(xiàn)沒有提供性能分析器的話，那么你就不得不通過猜測來尋找瓶頸，而且這種猜測往往都是錯的！

瓶頸規(guī)則的一個推論是，不應(yīng)該在程序的初期花費太多的精力在優(yōu)化上。高德納對此深信不疑：“過早的優(yōu)化是一切 (至少是大多數(shù)) 問題的源頭。”?λ?在剛開始寫程序的時候，通常很難看清真正的瓶頸在哪，如果這個時候進(jìn)行優(yōu)化，你很可能是在浪費時間。優(yōu)化也會使程序的修改變得更加困難，邊寫程序邊優(yōu)化就像是在用風(fēng)干非?？斓念伭蟻懋嫯嬕粯?。

在適當(dāng)?shù)臅r候做適當(dāng)?shù)氖虑椋梢宰屇銓懗龈鼉?yōu)秀的程序。 Lisp 的一個優(yōu)點就是能讓你用兩種不同的工作方式來進(jìn)行開發(fā)：很快地寫出運行較慢的代碼，或者，放慢寫程序的速度，精雕細(xì)琢，從而得出運行得較快的代碼。

在程序開發(fā)的初期階段，工作通常在第一種模式下進(jìn)行，只有當(dāng)性能成為問題的時候，才切換到第二種模式。 對于非常底層的語言，比如匯編，你必須優(yōu)化程序的每一行。但這么做會浪費你大部分的精力，因為瓶頸僅僅是其中很小的那部分代碼。一個更加抽象的語言能夠讓你把主要精力集中在瓶頸上， 達(dá)到事半功倍的效果。

當(dāng)真正開始優(yōu)化的時候，還必須從最頂端入手。 在使用各種低層次的編碼技巧 (low-level coding tricks) 之前，請先確保你已經(jīng)使用了最為高效的算法。 這么做的潛在好處相當(dāng)大 ── 甚至可能大到你都不再需要玩那些奇淫技巧。 當(dāng)然本規(guī)則還是要和前一個規(guī)則保持平衡。 有些時候，關(guān)于算法的決策必須盡早進(jìn)行。

13.2 編譯 (Compilation)

有五個參數(shù)可以控制代碼的編譯方式：?speed?(速度)代表編譯器產(chǎn)生代碼的速度；?compilation-speed?(編譯速度)代表程序被編譯的速度；?safety?(安全) 代表要對目標(biāo)代碼進(jìn)行錯誤檢查的數(shù)量；?space?(空間)代表目標(biāo)代碼的大小和內(nèi)存需求量；最后，?debug?(調(diào)試)代表為了調(diào)試而保留的信息量。

交互與解釋 (INTERACTIVE VS. INTERPRETED)

Lisp 是一種交互式語言 (Interactive Language)，但是交互式的語言不必都是解釋型的。早期的 Lisp 都通過解釋器實現(xiàn)，因此認(rèn)為 Lisp 的特質(zhì)都依賴于它是被解釋的想法就這么產(chǎn)生了。但這種想法是錯誤的：Common Lisp 既是編譯型語言，又是解釋型語言。

至少有兩種 Common Lisp 實現(xiàn)甚至都不包含解釋器。在這些實現(xiàn)中，輸入到頂層的表達(dá)式在求值前會被編譯。因此，把頂層叫做解釋器的這種說法，不僅是落伍的，甚至還是錯誤的。

編譯參數(shù)不是真正的變量。它們在聲明中被分配從?0?(最不重要) 到?3?(最重要) 的權(quán)值。如果一個主要的瓶頸發(fā)生在某個函數(shù)的內(nèi)層循環(huán)中，我們或許可以添加如下的聲明：

(defun bottleneck (...)
  (do (...)
      (...)
    (do (...)
        (...)
      (declare (optimize (speed 3) (safety 0)))
      ...)))

一般情況下，應(yīng)該在代碼寫完并且經(jīng)過完善測試之后，才考慮加上那么一句聲明。

要讓代碼在任何情況下都盡可能地快，可以使用如下聲明：

(declaim (optimize (speed 3)
                   (compilation-speed 0)
                   (safety 0)
                   (debug 0)))

考慮到前面提到的瓶頸規(guī)則?[1]?，這種苛刻的做法可能并沒有什么必要。

另一類特別重要的優(yōu)化就是由 Lisp 編譯器完成的尾遞歸優(yōu)化。當(dāng)?speed?(速度)的權(quán)值最大時，所有支持尾遞歸優(yōu)化的編譯器都將保證對代碼進(jìn)行這種優(yōu)化。

如果在一個調(diào)用返回時調(diào)用者中沒有殘余的計算，該調(diào)用就被稱為尾遞歸。下面的代碼返回列表的長度：

(defun length/r (lst)
  (if (null lst)
      0
      (1+ (length/r (cdr lst)))))

這個遞歸調(diào)用不是尾遞歸，因為當(dāng)它返回以后，它的值必須傳給?1+?。相反，這是一個尾遞歸的版本，

(defun length/rt (lst)
  (labels ((len (lst acc)
             (if (null lst)
                 acc
                 (len (cdr lst) (1+ acc)))))
    (len lst 0)))

更準(zhǔn)確地說，局部函數(shù)?len?是尾遞歸調(diào)用，因為當(dāng)它返回時，調(diào)用函數(shù)已經(jīng)沒什么事情可做了。 和?length/r?不同的是，它不是在遞歸回溯的時候構(gòu)建返回值，而是在遞歸調(diào)用的過程中積累返回值。 在函數(shù)的最后一次遞歸調(diào)用結(jié)束之后，?acc?參數(shù)就可以作為函數(shù)的結(jié)果值被返回。

出色的編譯器能夠?qū)⒁粋€尾遞歸編譯成一個跳轉(zhuǎn) (goto)，因此也能將一個尾遞歸函數(shù)編譯成一個循環(huán)。在典型的機器語言代碼中，當(dāng)?shù)谝淮螆?zhí)行到表示?len?的指令片段時，棧上會有信息指示在返回時要做些什么。由于在遞歸調(diào)用后沒有殘余的計算，該信息對第二層調(diào)用仍然有效：第二層調(diào)用返回后我們要做的僅僅就是從第一層調(diào)用返回。 因此，當(dāng)進(jìn)行第二層調(diào)用時，我們只需給參數(shù)設(shè)置新的值，然后跳轉(zhuǎn)到函數(shù)的起始處繼續(xù)執(zhí)行就可以了，沒有必要進(jìn)行真正的函數(shù)調(diào)用。

另一個利用函數(shù)調(diào)用抽象，卻沒有開銷的方法是使函數(shù)內(nèi)聯(lián)編譯。對于那些調(diào)用開銷比函數(shù)體的執(zhí)行代價還高的小型函數(shù)來說，這種技術(shù)非常有價值。例如，以下代碼用于判斷列表是否僅有一個元素：

(declaim (inline single?))

(defun single? (lst)
  (and (consp lst) (null (cdr lst))))

因為這個函數(shù)是在全局被聲明為內(nèi)聯(lián)的，引用了?single??的函數(shù)在編譯后將不需要真正的函數(shù)調(diào)用。?[2]?如果我們定義一個調(diào)用它的函數(shù)，

(defun foo (x)
  (single? (bar x)))

當(dāng)?foo?被編譯后，?single??函數(shù)體中的代碼將會被編譯進(jìn)?foo?的函數(shù)體，就好像我們直接寫以下代碼一樣：

(defun foo (x)
  (let ((lst (bar x)))
    (and (consp lst) (null (cdr lst)))))

內(nèi)聯(lián)編譯有兩個限制： 首先，遞歸函數(shù)不能內(nèi)聯(lián)。 其次，如果一個內(nèi)聯(lián)函數(shù)被重新定義，我們就必須重新編譯調(diào)用它的任何函數(shù)，否則調(diào)用仍然使用原來的定義。

在一些早期的 Lisp 方言中，有時候會使用宏（ 10.2 節(jié)）來避免函數(shù)調(diào)用。這種做法在 Common Lisp 中通常是沒有必要的。

不同 Lisp 編譯器的優(yōu)化方式千差萬別。 如果你想了解你的編譯器為某個函數(shù)生成的代碼，試著調(diào)用?disassemble?函數(shù)：它接受一個函數(shù)或者函數(shù)名，并顯示該函數(shù)編譯后的形式。 即便你看到的東西是完全無法理解的，你仍然可以使用?disassemble?來判斷聲明是否起效果：編譯函數(shù)的兩個版本，一個使用優(yōu)化聲明，另一個不使用優(yōu)化聲明，然后觀察由?disassemble?顯示的兩組代碼之間是否有差異。 同樣的技巧也可以用于檢驗函數(shù)是否被內(nèi)聯(lián)編譯。 不論情況如何，都請優(yōu)先考慮使用編譯參數(shù)，而不是手動調(diào)優(yōu)的方式來優(yōu)化代碼。

13.3 類型聲明 (Type Declarations)

如果 Lisp 不是你所學(xué)的第一門編程語言，那么你也許會感到困惑，為什么這本書還沒說到類型聲明這件事來？畢竟，在很多流行的編程語言中，類型聲明是必須要做的。

在不少編程語言里，你必須為每個變量聲明類型，并且變量也只可以持有與該類型相一致的值。 這種語言被稱為強類型(strongly typed) 語言。 除了給程序員們徒增了許多負(fù)擔(dān)外，這種方式還限制了你能做的事情。 使用這種語言，很難寫出那些需要多種類型的參數(shù)一起工作的函數(shù)，也很難定義出可以包含不同種類元素的數(shù)據(jù)結(jié)構(gòu)。 當(dāng)然，這種方式也有它的優(yōu)勢，比如無論何時當(dāng)編譯器碰到一個加法運算，它都能夠事先知道這是一個什么類型的加法運算。如果兩個參數(shù)都是整數(shù)類型，編譯器可以直接在目標(biāo)代碼中生成一個固定 (hard-wire) 的整數(shù)加法運算。

正如 2.15 節(jié)所講，Common Lisp 使用一種更加靈活的方式：顯式類型 (manifest typing)?[3]?。有類型的是值而不是變量。變量可以用于任何類型的對象。

當(dāng)然，這種靈活性需要付出一定的速度作為代價。 由于?+?可以接受好幾種不同類型的數(shù)，它不得不在運行時查看每個參數(shù)的類型來決定采用哪種加法運算。

在某些時候，如果我們要執(zhí)行的全都是整數(shù)的加法，那么每次查看參數(shù)類型的這種做法就說不上高效了。 Common Lisp 處理這種問題的方法是：讓程序員盡可能地提示編譯器。 比如說，如果我們提前就能知道某個加法運算的兩個參數(shù)是定長數(shù) (fixnums) ，那么就可以對此進(jìn)行聲明，這樣編譯器就會像 C 語言的那樣為我們生成一個固定的整數(shù)加法運算。

因為顯式類型也可以通過聲明類型來生成高效的代碼，所以強類型和顯式類型兩種方式之間的差別并不在于運行速度。 真正的區(qū)別是，在強類型語言中，類型聲明是強制性的，而顯式類型則不強加這樣的要求。 在 Common Lisp 中，類型聲明完全是可選的。它們可以讓程序運行的更快，但(除非錯誤)不會改變程序的行為。

全局聲明以?declaim?伴隨一個或多個聲明的形式來實現(xiàn)。一個類型聲明是一個列表，包含了符號?type?，后跟一個類型名，以及一個或多個變量組成。舉個例子，要為一個全局變量聲明類型，可以這么寫：

(declaim (type fixnum *count*))

在 ANSI Common Lisp 中，可以省略?type?符號，將聲明簡寫為：

(declaim (fixnum *count*))

局部聲明通過?declare?完成，它接受的參數(shù)和?declaim?的一樣。 聲明可以放在那些創(chuàng)建變量的代碼體之前：如?defun?、?lambda?、let?、?do?，諸如此類。 比如說，要把一個函數(shù)的參數(shù)聲明為定長數(shù)，可以這么寫：

(defun poly (a b x)
  (declare (fixnum a b x))
  (+ (* a (expt x 2)) (* b x)))

在類型聲明中的變量名指的就是該聲明所在的上下文中的那個變量 ── 那個通過賦值可以改變它的值的變量。

你也可以通過?the?為某個表達(dá)式的值聲明類型。 如果我們提前就知道?a?、?b?和?x?是足夠小的定長數(shù)，并且它們的和也是定長數(shù)的話，那么可以進(jìn)行以下聲明：

(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?把你的數(shù)值運算代碼變得散亂不堪。其一是很容易通過宏，來幫你插入這些聲明。其二是某些實現(xiàn)使用了特殊的技巧，即便沒有類型聲明的定長數(shù)運算也能足夠快。

Common Lisp 中有相當(dāng)多的類型 ── 恐怕有無數(shù)種類型那么多，如果考慮到你可以自己定義新的類型的話。 類型聲明只在少數(shù)情況下至關(guān)重要，可以遵照以下兩條規(guī)則來進(jìn)行：

1. 當(dāng)函數(shù)可以接受若干不同類型的參數(shù)(但不是所有類型)時，可以對參數(shù)的類型進(jìn)行聲明。如果你知道一個對?+?的調(diào)用總是接受定長數(shù)類型的參數(shù)，或者一個對?aref?的調(diào)用第一個參數(shù)總是某種特定種類的數(shù)組，那么進(jìn)行類型聲明是值得的。
2. 通常來說，只有對類型層級中接近底層的類型進(jìn)行聲明，才是值得的：將某個東西的類型聲明為?fixnum?或者?simple-array?也許有用，但將某個東西的類型聲明為?integer?或者?sequence?或許就沒用了。

類型聲明對內(nèi)容復(fù)雜的對象特別重要，這包括數(shù)組、結(jié)構(gòu)和對象實例。這些聲明可以在兩個方面提升效率：除了可以讓編譯器來決定函數(shù)參數(shù)的類型以外，它們也使得這些對象可以在內(nèi)存中更高效地表示。

如果對數(shù)組元素的類型一無所知的話，這些元素在內(nèi)存中就不得不用一塊指針來表示。但假如預(yù)先就知道數(shù)組包含的元素僅僅是 ── 比方說 ── 雙精度浮點數(shù) (double-floats)，那么這個數(shù)組就可以用一組實際的雙精度浮點數(shù)來表示。這樣數(shù)組將占用更少的空間，因為我們不再需要額外的指針指向每一個雙精度浮點數(shù)；同時，對數(shù)組元素的訪問也將更快，因為我們不必沿著指針去讀取和寫元素。