關于算法的選擇，我談到其理論上的復雜度，并不直接反映出效率。因為在實際運用時，數據的規模，特征等等都會涉及到算法的實際效果。一個時間復雜度低的算法并不代表任何情況下的效率都高。這是“實際”和“理論”的區別之一。現在我打算來談一下另一個比較“實際”的東西：編譯器對于程序效率的影響。

　　那么我們先來看這樣一段代碼，假設有一個保存著整數的單向鏈表，要求您寫一個函數進行求和，您會怎么寫呢？如果我們用F#，那么最容易實現的自然是遞歸方式：

let rec sum ls = 
    match ls with
    | [] -> 0
    | x :: xs -> x + (sum xs)

　　這段F#代碼使用了模式匹配：如果是一個空鏈表，那么其結果自然等于零，否則就把它第一個元素加上剩余元素之和。這段代碼顯然非常簡單，通過聲明式的方法“表達”了函數的邏輯，沒有任何一句多余的代碼。不過您一定發現了，這個函數的實現中使用了遞歸，因此對于長度為n的鏈表來說，這個函數的時間復雜度為O(n)，空間復雜度也是O(n)——空間的開銷在函數的調用棧上。一般來說，遞歸總是難逃調用棧的累積，因此它的空間復雜度總是難以做到O(1)的常數級別。調用棧的堆積，使得程序在執行訪問的內存地址跨度不斷增大，容易導致程序的局部性（Locality）不佳，性能較差——關于代碼局部性的影響，我們下篇文章中再進行討論。

　　當然，有些朋友可能會說，為什么要用遞歸呢？用普通的一個for或while循環，然后不斷累加不也可以嗎？當然可以，而且這么做的話空間復雜度便是O(1)了，時間復雜度雖然還是O(n)，但是經過上面的描述，我們可以知道它的實際執行效率會比遞歸的方式要好。不過，for/while都是命令式編程的方式，不適合函數式編程的“聲明”風格，因此在實際應用中我們往往會寫這樣的sum函數：

let sum ls = 
    let rec sum' ls acc =
        match ls with
        | [] -> acc
        | x :: xs -> sum' xs (acc + x)

    sum' ls 0

　　這個sum函數中定義了一個輔助函數sum'，這個輔助函數會多一個參數作為“累加器”，其中依舊使用了模式匹配的語法，在遇到空數組時直接返回累加器的值，否則就把鏈表的第一個元素加至累加器中，再遞歸調用sum'輔助函數。沒錯，這里還是用了遞歸。這樣看起來，它的執行效果應該和前一種實現沒有多大差別？

　　那么實際結果又是如何呢？如果您有條件不妨可以自己嘗試一下——我這里貼一下由.NET Reflector反編譯為C#后的sum'函數代碼：

[Serializable]
internal class sum'@9 : OptimizedClosures.FSharpFunc<FSharpList<int>, int, int>
{
    public override int Invoke(FSharpList<int> ls, int acc)
    {
        while (true)
        {
            FSharpList<int> list = ls;
            if (!(list is FSharpList<int>._Cons))
            {
                return acc;
            }
            FSharpList<int>._Cons cons = (FSharpList<int>._Cons)list;
            FSharpList<int> xs = cons.get_Tail();
            int x = cons.get_Head();
            acc += x;
            ls = xs;
        }
    }
}

　　您不用徹底理解這段代碼的結果如何，但您可以輕易察覺到，這并不是一段遞歸代碼——這是一段“循環”，它的效果和我們自己的循環實現相同。為什么會這樣？因為現在的sum'函數已經實現了尾遞歸，它能夠被F#編譯器優化為循環（并不是所有的尾遞歸都能優化為循環）。因此，雖然從高級語言的代碼上，第二種實現方式比第一種要略微復雜一些，而且同樣是遞歸，但最終的執行效果有較大差距。尾遞歸示例可能有些過分典型了，但這正說明了一個問題，我們使用的算法（廣義的算法，即程序的實現方法）會在很多方便影響程序效率，例如體系結構方面（如遞歸性能較低）或是編譯器的優化方面。一個好的算法，在這些方面都要考慮——例如，它可能需要在一定程度上去“迎合”編譯器的優化，個中復雜程度并非“簡短”二字就能概括的。

　　這便是編譯器的威力所在了，它能把一段有特定模式的代碼進行優化成更高效的形式。因此，您所看到的代碼執行方式，并不一定是計算機的真正運行方式。換句話說，高級代碼中表現出的高性能的代碼，并不能把它直接視為機器執行時效果。這句話可能有些過于“理論”，如果您還一時無法立即接受的話，可能它的另一個“變體”會更加現實一些：一段看上去性能較差的代碼，經過編譯器優化之后其性能可能并不比“高效”的代碼要差。而事實上，編譯器最適合優化的一類內容便是所謂“少一些變量”，“少一些判斷”等人工的、機械的優化方式了。

　　編譯技術發展了幾十年，早已形成了許多模式，高級語言的編譯器也早已熟知一些機械的優化方式。例如，C#編譯器會直接幫我們計算出一些常量表達式（包括數值計算和字符串連接），而JIT也會幫我們做一些循環展開、內聯調用等常見優化手段。要比一些傳統的優化，又有誰比的過機械而嚴謹的計算機來的完整呢？編譯器甚至可以在多種可能產生沖突的優化方式中做出選擇最有效的選擇，而這個讓人來完成就很麻煩了，如果在項目中這么做的話，可能會隨著代碼的修改之前的優化都沒有效果了。對于大部分人來說，進行手動的細節優化，即便使用的是C語言，其最后的結果也很難超過編譯器——更何況，C語言的確貼近CPU，但這表示它一定最為高效嗎？

　　在目前的CPU面前，調整兩條指令的順序可能就會在效率方面產生非常顯著的區別（這也是為什么在某些極端性能敏感的地方還是需要直接內嵌匯編代碼），因為它迎合了CPU在執行指令過程中的預測及并行等優化方式。例如，處理器中只有一個乘法元件，那么編譯器可以將兩個乘法操作的依賴性降低，這樣CPU便可以并發執行多條指令——關于這些我們會在以后的文章中進行討論。試想，作為一個普通人類，我們進行此類優化的難度是多少呢？所以，我們應該把精力投入最有效的優化方式上，而程序字面上的“簡短”幾乎不會產生任何效果。

　　編譯器的優化并非在空談。例如Core Java 2中闡述了這樣一個現象，便是JDK中的BitSet集合效率比C++的性能高。當然，文章里承認，這是由于Borland C++編譯器的BitSet模板實現不佳導致的性能底下。不過這篇文章的數據也已經舊了，據某大牛的可靠消息，Core Java 7中表示，BitSet的效率已經打敗了g++的編譯成果，感興趣的朋友們可以翻閱一下，如果我找到了網上的引用資料也會及時更新。這也是編譯器的優化效果，因為對于BitSet這種純算術操作，Java比C/C++這種靜態編譯的語言快很正常，因為JIT可以找到更多在運行時期可以做的特殊優化方式。

　　最后再舉一個例子，便是Google工程師Mark Chu-Carroll在3年多前寫的一篇文章《The “C is Efficient” Language Fallacy》，其中表示C/C++只是“最貼近CPU的語言”，但并非是進行科學計算時最高效的語言——甚至它們幾乎不可能成為最高效的語言。這也是編譯器的緣故，且看Mark列舉了一小段代碼：

for (int i=0; i < 20000) {
   for (int j=0; j < 20000) {
      x[i][j] = y[i-2][j+1] * y[i+1][j-2];
   }
}

　　這段代碼進行的是兩個數組的計算。此時C++編譯器便會遇到一個叫做“別名檢測（alias detection）”的問題，那就是C++編譯器無法得知x和y兩個數組的關系（試想如果它們是一個函數的兩個參數，也就是說沒有任何其他上下文信息），例如它們是不是同一個數組？是不是有重疊？要知道C++的數組訪問只是基于下標地址配合偏移量的計算，因此x和y的內容完全可能出現重疊現象。于是C++編譯器只能老老實實地按照高級代碼的寫法生成機器碼，優化的余地并不大——這里由于語言特性而導致編譯器無法進行更高級的優化，可謂是一個“硬傷”。

　　Mark表示，Fortran-77可以區分x和y兩者是否相同，Fortran-98可以由程序員指名兩者并無重疊（如果我沒有理解錯原文的話），而一個由Lawrence Livermore實驗室發明實驗性語言Sisal比Fortran更有20%的性能提高。此外Mark還提出了他經歷過的一個實際案例：幾年前他要寫一個復雜的算法來求出兩個數組中“最長相同子串”，當時他不知道哪種語言合適，便使用多種語言各實現了一遍。最后他使用兩個長為2000的數組進行測試的結果為：

• C：0.8秒。
• C++：2.3秒。
• OCaml：解釋執行花費0.6秒，完全編譯后執行耗費0.3秒。
• Java：1分20秒。
• Python：超過5分鐘。

　　一年以后它使用最新的Java運行時，改進后的JIT只用了0.7秒便執行完了——當然還有額外的1秒用于啟動JVM。在評論中Mark補充到，他是個嚴肅的C/C++程序員，并且已經盡他最大的努力來對C代碼進行了優化。而當時他從來沒有用過OCaml寫過程序，更別說對OCaml代碼進行一些取巧的優化方式了。至于OCaml高效的原因，他只是簡單的提了一句，我也沒有完全理解，便直接引用，不作翻譯了：

The results were extremely surprising to me, and I did spend some time profiling to try to figure out just why the OCaml was so much faster. The specific reason was that the Caml code did some really clever stuff - it basically did something like local constant propagation that were based on be able to identify relations between subscripts used to access different arrays, and having done that, it could do some dramatic code rewriting that made it possible to merge loops, and hoist some local constants out of the restructured merged loop.

　　事實上，OCaml似乎的確是門了不起的語言，您可以在搜索引擎上使用“C++ OCaml Performance”作為關鍵字進行查找，可以找到很多性能比較的結果，以及OCaml編譯優化方面的資料。自然，這些是題外話，您可以把它們作為擴展閱讀用于“開闊視野”。我列舉這個例子也不是為了說明C/C++的性能不夠好，我這里談的一切都是想說明一個問題：代碼的執行效率并非能從字面上得出結論，更不是“簡短”兩個字能說明問題的。少一些賦值，少一些判斷并非提高性能的正確做法，甚至您的手動優化會讓編譯器無法理解您的意圖，進而無法進行有效的優化。如果您真想在細節上進行優化，還是進行Profiling之后，針對熱點進行有效地優化吧。

　　Profiling，Profiling，Profiling。

　　至此，我們已經談了算法和編譯器對于性能的影響。那么下次，我們就在“算法一致”且“編譯器沒有優化”的前提下，繼續探討影響代碼執行效率的要素之一吧。