|
|
關(guān)于算法的選擇，我談到其理論上的復(fù)雜度，并不直接反映出效率。因?yàn)樵趯?shí)際運(yùn)用時(shí)，數(shù)據(jù)的規(guī)模，特征等等都會涉及到算法的實(shí)際效果。一個(gè)時(shí)間復(fù)雜度低的算法并不代表任何情況下的效率都高。這是“實(shí)際”和“理論”的區(qū)別之一?，F(xiàn)在我打算來談一下另一個(gè)比較“實(shí)際”的東西：編譯器對于程序效率的影響。
那么我們先來看這樣一段代碼，假設(shè)有一個(gè)保存著整數(shù)的單向鏈表，要求您寫一個(gè)函數(shù)進(jìn)行求和，您會怎么寫呢？如果我們用F#，那么最容易實(shí)現(xiàn)的自然是遞歸方式：
let rec sum ls = match ls with | [] -> 0 | x :: xs -> x + (sum xs)
這段F#代碼使用了模式匹配：如果是一個(gè)空鏈表，那么其結(jié)果自然等于零，否則就把它第一個(gè)元素加上剩余元素之和。這段代碼顯然非常簡單，通過聲明式的方法“表達(dá)”了函數(shù)的邏輯，沒有任何一句多余的代碼。不過您一定發(fā)現(xiàn)了，這個(gè)函數(shù)的實(shí)現(xiàn)中使用了遞歸，因此對于長度為n的鏈表來說，這個(gè)函數(shù)的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度也是O(n)——空間的開銷在函數(shù)的調(diào)用棧上。一般來說，遞歸總是難逃調(diào)用棧的累積，因此它的空間復(fù)雜度總是難以做到O(1)的常數(shù)級別。調(diào)用棧的堆積，使得程序在執(zhí)行訪問的內(nèi)存地址跨度不斷增大，容易導(dǎo)致程序的局部性（Locality）不佳，性能較差——關(guān)于代碼局部性的影響，我們下篇文章中再進(jìn)行討論。
當(dāng)然，有些朋友可能會說，為什么要用遞歸呢？用普通的一個(gè)for或while循環(huán)，然后不斷累加不也可以嗎？當(dāng)然可以，而且這么做的話空間復(fù)雜度便是O(1)了，時(shí)間復(fù)雜度雖然還是O(n)，但是經(jīng)過上面的描述，我們可以知道它的實(shí)際執(zhí)行效率會比遞歸的方式要好。不過，for/while都是命令式編程的方式，不適合函數(shù)式編程的“聲明”風(fēng)格，因此在實(shí)際應(yīng)用中我們往往會寫這樣的sum函數(shù)：
let sum ls = let rec sum' ls acc = match ls with | [] -> acc | x :: xs -> sum' xs (acc + x) sum' ls 0
這個(gè)sum函數(shù)中定義了一個(gè)輔助函數(shù)sum'，這個(gè)輔助函數(shù)會多一個(gè)參數(shù)作為“累加器”，其中依舊使用了模式匹配的語法，在遇到空數(shù)組時(shí)直接返回累加器的值，否則就把鏈表的第一個(gè)元素加至累加器中，再遞歸調(diào)用sum'輔助函數(shù)。沒錯(cuò)，這里還是用了遞歸。這樣看起來，它的執(zhí)行效果應(yīng)該和前一種實(shí)現(xiàn)沒有多大差別？
那么實(shí)際結(jié)果又是如何呢？如果您有條件不妨可以自己嘗試一下——我這里貼一下由.NET Reflector反編譯為C#后的sum'函數(shù)代碼：
[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; } }}
您不用徹底理解這段代碼的結(jié)果如何，但您可以輕易察覺到，這并不是一段遞歸代碼——這是一段“循環(huán)”，它的效果和我們自己的循環(huán)實(shí)現(xiàn)相同。為什么會這樣？因?yàn)楝F(xiàn)在的sum'函數(shù)已經(jīng)實(shí)現(xiàn)了尾遞歸，它能夠被F#編譯器優(yōu)化為循環(huán)（并不是所有的尾遞歸都能優(yōu)化為循環(huán)）。因此，雖然從高級語言的代碼上，第二種實(shí)現(xiàn)方式比第一種要略微復(fù)雜一些，而且同樣是遞歸，但最終的執(zhí)行效果有較大差距。尾遞歸示例可能有些過分典型了，但這正說明了一個(gè)問題，我們使用的算法（廣義的算法，即程序的實(shí)現(xiàn)方法）會在很多方便影響程序效率，例如體系結(jié)構(gòu)方面（如遞歸性能較低）或是編譯器的優(yōu)化方面。一個(gè)好的算法，在這些方面都要考慮——例如，它可能需要在一定程度上去“迎合”編譯器的優(yōu)化，個(gè)中復(fù)雜程度并非“簡短”二字就能概括的。
這便是編譯器的威力所在了，它能把一段有特定模式的代碼進(jìn)行優(yōu)化成更高效的形式。因此，您所看到的代碼執(zhí)行方式，并不一定是計(jì)算機(jī)的真正運(yùn)行方式。換句話說，高級代碼中表現(xiàn)出的高性能的代碼，并不能把它直接視為機(jī)器執(zhí)行時(shí)效果。這句話可能有些過于“理論”，如果您還一時(shí)無法立即接受的話，可能它的另一個(gè)“變體”會更加現(xiàn)實(shí)一些：一段看上去性能較差的代碼，經(jīng)過編譯器優(yōu)化之后其性能可能并不比“高效”的代碼要差。而事實(shí)上，編譯器最適合優(yōu)化的一類內(nèi)容便是所謂“少一些變量”，“少一些判斷”等人工的、機(jī)械的優(yōu)化方式了。
編譯技術(shù)發(fā)展了幾十年，早已形成了許多模式，高級語言的編譯器也早已熟知一些機(jī)械的優(yōu)化方式。例如，C#編譯器會直接幫我們計(jì)算出一些常量表達(dá)式（包括數(shù)值計(jì)算和字符串連接），而JIT也會幫我們做一些循環(huán)展開、內(nèi)聯(lián)調(diào)用等常見優(yōu)化手段。要比一些傳統(tǒng)的優(yōu)化，又有誰比的過機(jī)械而嚴(yán)謹(jǐn)?shù)挠?jì)算機(jī)來的完整呢？編譯器甚至可以在多種可能產(chǎn)生沖突的優(yōu)化方式中做出選擇最有效的選擇，而這個(gè)讓人來完成就很麻煩了，如果在項(xiàng)目中這么做的話，可能會隨著代碼的修改之前的優(yōu)化都沒有效果了。對于大部分人來說，進(jìn)行手動的細(xì)節(jié)優(yōu)化，即便使用的是C語言，其最后的結(jié)果也很難超過編譯器——更何況，C語言的確貼近CPU，但這表示它一定最為高效嗎？
在目前的CPU面前，調(diào)整兩條指令的順序可能就會在效率方面產(chǎn)生非常顯著的區(qū)別（這也是為什么在某些極端性能敏感的地方還是需要直接內(nèi)嵌匯編代碼），因?yàn)樗狭薈PU在執(zhí)行指令過程中的預(yù)測及并行等優(yōu)化方式。例如，處理器中只有一個(gè)乘法元件，那么編譯器可以將兩個(gè)乘法操作的依賴性降低，這樣CPU便可以并發(fā)執(zhí)行多條指令——關(guān)于這些我們會在以后的文章中進(jìn)行討論。試想，作為一個(gè)普通人類，我們進(jìn)行此類優(yōu)化的難度是多少呢？所以，我們應(yīng)該把精力投入最有效的優(yōu)化方式上，而程序字面上的“簡短”幾乎不會產(chǎn)生任何效果。
編譯器的優(yōu)化并非在空談。例如Core Java 2中闡述了這樣一個(gè)現(xiàn)象，便是JDK中的BitSet集合效率比C++的性能高。當(dāng)然，文章里承認(rèn)，這是由于Borland C++編譯器的BitSet模板實(shí)現(xiàn)不佳導(dǎo)致的性能底下。不過這篇文章的數(shù)據(jù)也已經(jīng)舊了，據(jù)某大牛的可靠消息，Core Java 7中表示，BitSet的效率已經(jīng)打敗了g++的編譯成果，感興趣的朋友們可以翻閱一下，如果我找到了網(wǎng)上的引用資料也會及時(shí)更新。這也是編譯器的優(yōu)化效果，因?yàn)閷τ贐itSet這種純算術(shù)操作，Java比C/C++這種靜態(tài)編譯的語言快很正常，因?yàn)镴IT可以找到更多在運(yùn)行時(shí)期可以做的特殊優(yōu)化方式。
最后再舉一個(gè)例子，便是Google工程師Mark Chu-Carroll在3年多前寫的一篇文章《The “C is Efficient” Language Fallacy》，其中表示C/C++只是“最貼近CPU的語言”，但并非是進(jìn)行科學(xué)計(jì)算時(shí)最高效的語言——甚至它們幾乎不可能成為最高效的語言。這也是編譯器的緣故，且看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]; }}這段代碼進(jìn)行的是兩個(gè)數(shù)組的計(jì)算。此時(shí)C++編譯器便會遇到一個(gè)叫做“別名檢測（alias detection）”的問題，那就是C++編譯器無法得知x和y兩個(gè)數(shù)組的關(guān)系（試想如果它們是一個(gè)函數(shù)的兩個(gè)參數(shù)，也就是說沒有任何其他上下文信息），例如它們是不是同一個(gè)數(shù)組？是不是有重疊？要知道C++的數(shù)組訪問只是基于下標(biāo)地址配合偏移量的計(jì)算，因此x和y的內(nèi)容完全可能出現(xiàn)重疊現(xiàn)象。于是C++編譯器只能老老實(shí)實(shí)地按照高級代碼的寫法生成機(jī)器碼，優(yōu)化的余地并不大——這里由于語言特性而導(dǎo)致編譯器無法進(jìn)行更高級的優(yōu)化，可謂是一個(gè)“硬傷”。
Mark表示，F(xiàn)ortran-77可以區(qū)分x和y兩者是否相同，F(xiàn)ortran-98可以由程序員指名兩者并無重疊（如果我沒有理解錯(cuò)原文的話），而一個(gè)由Lawrence Livermore實(shí)驗(yàn)室發(fā)明實(shí)驗(yàn)性語言Sisal比Fortran更有20%的性能提高。此外Mark還提出了他經(jīng)歷過的一個(gè)實(shí)際案例：幾年前他要寫一個(gè)復(fù)雜的算法來求出兩個(gè)數(shù)組中“最長相同子串”，當(dāng)時(shí)他不知道哪種語言合適，便使用多種語言各實(shí)現(xiàn)了一遍。最后他使用兩個(gè)長為2000的數(shù)組進(jìn)行測試的結(jié)果為：
一年以后它使用最新的Java運(yùn)行時(shí)，改進(jìn)后的JIT只用了0.7秒便執(zhí)行完了——當(dāng)然還有額外的1秒用于啟動JVM。在評論中Mark補(bǔ)充到，他是個(gè)嚴(yán)肅的C/C++程序員，并且已經(jīng)盡他最大的努力來對C代碼進(jìn)行了優(yōu)化。而當(dāng)時(shí)他從來沒有用過OCaml寫過程序，更別說對OCaml代碼進(jìn)行一些取巧的優(yōu)化方式了。至于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.
事實(shí)上，OCaml似乎的確是門了不起的語言，您可以在搜索引擎上使用“C++ OCaml Performance”作為關(guān)鍵字進(jìn)行查找，可以找到很多性能比較的結(jié)果，以及OCaml編譯優(yōu)化方面的資料。自然，這些是題外話，您可以把它們作為擴(kuò)展閱讀用于“開闊視野”。我列舉這個(gè)例子也不是為了說明C/C++的性能不夠好，我這里談的一切都是想說明一個(gè)問題：代碼的執(zhí)行效率并非能從字面上得出結(jié)論，更不是“簡短”兩個(gè)字能說明問題的。少一些賦值，少一些判斷并非提高性能的正確做法，甚至您的手動優(yōu)化會讓編譯器無法理解您的意圖，進(jìn)而無法進(jìn)行有效的優(yōu)化。如果您真想在細(xì)節(jié)上進(jìn)行優(yōu)化，還是進(jìn)行Profiling之后，針對熱點(diǎn)進(jìn)行有效地優(yōu)化吧。
Profiling，Profiling，Profiling。
至此，我們已經(jīng)談了算法和編譯器對于性能的影響。那么下次，我們就在“算法一致”且“編譯器沒有優(yōu)化”的前提下，繼續(xù)探討影響代碼執(zhí)行效率的要素之一吧。
it知識庫：淺談代碼的執(zhí)行效率（2）：編譯器的威力，轉(zhuǎn)載需保留來源！
鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請第一時(shí)間聯(lián)系我們修改或刪除，多謝。
