編寫與優化 Go 代碼

1. 編寫不太慢的軟件的 tips

• 入門級計算機知識

3. 編寫快速的軟件的 tips

• 優化時需要了解的 Go 特性

5. 編寫_真正_快速的軟件的進階 tips

• 當你優化後的代碼還是不夠快時怎麼辦

何時何地進行優化

優化都是有成本的。這種成本是以代碼複雜度或認知負擔呈現的 -- 優化後的代碼一般都比原來的版本要更難理解。

但優化往往能帶來經濟效益。作爲一個程序員，時間寶貴。對於你來說，優化也是個機會成本的問題。因爲可能還有項目等着你去做，有 bug 等着你去修，有特性等着你去開發。儘管優化很有意思，但並不一定是當前最應該做的事情。性能是重要的產品特性，但及時地發佈和正確的軟件也是應該做到的。

有時 CPU 優化相比用戶體驗優化優先級沒那麼高，你應該選擇最重要的事情。可能只是增加一個簡單的進度條，或者讓頁面不要在進行計算的時候直接卡住。

這在我們的工作中顯而易見：三小時做的報告有時可能還不如我們幾十分鐘做的更有用。

一個問題很容易優化，並不代表這個問題就值得優化。忽略當下不重要的問題，也是軟件開發的大智慧。

可以把上面的想法當成是在優化_你的_時間。

你需要選擇優化的對象和時機。你可以按照實際情況將優先級在 “快速的軟件” 和“快速的部署”之間來回切換。

人們經常聽別人說，並且自己可能也會無意識地重複 “提前優化是萬惡之源”，但他們忽略了這幾話的上下文。

程序員浪費了大量的時間來考慮或擔心他們程序中非關鍵部分的速度，這些提高效率的嘗試在考慮到調試和維護的時候，實際上產生了很大的負面影響。我們得忽略那些不關鍵的效率提升，也就是說 97% 的時候我們要說：過早的優化是萬惡之源。同時也不放棄那關鍵的 3% 的機會。-- Knuth

Add: https://www.youtube.com/watch?time_continue=429&v=3WBaY61c9sE

• 也不要看不起簡單的優化

• 對數據結構和算法有更多瞭解，會使更多的優化變的 “簡單” 且“顯而易見

你應該優化麼？

是的，只有當優化問題是非常重要的，這個程序確實非常慢，並且用戶除了對程序的正確，穩定和清晰以外，也有對速度的期望時。-- The Practice of Programming, Kernighan and Pike

過早的優化也會傷害你，把你綁在某些決定上。如果需求發生變化，優化後的代碼會更難修改，也更難丟棄（沉沒成本謬論）。

BitFunnel 性能估計 [1] 有一些數字使這種權衡變得明確。想象一下，一個假想的搜索引擎需要在多個數據中心使用 30,000 臺機器。這些機器每臺成本約爲 1,000 美元。如果你能把軟件的速度提高一倍，這可以爲公司每年節省 1500 萬美元。即使是一個開發人員花一整年的時間來提高性能，只需 1% 就可以得到回報。

在絕大多數情況下，程序的大小和速度並不是一個問題。最簡單的優化是不需要這樣做。第二簡單的優化就是購買更快的硬件。

一旦你決定要修改你的程序，請繼續閱讀。

如何優化

優化工作流

在我們討論具體問題之前，讓我們先談談優化的一般過程。

優化是重構的一種形式。只不過這種重構過程不是出於改善源代碼的代碼重複或清晰這些方面，而是爲了改善性能：降低 CPU、內存使用、延遲等。這種改進通常是以可讀性爲代價的。這意味着，除了一套完整且全面的單元測試（以確保你的改動沒有破壞任何邏輯），還需要一套好的基準測試，以確保改動對性能產生預期的影響。必須能夠驗證代碼修改是否真的降低了 CPU。有時候，你認爲會提高性能的改變實際上會變成零或負的改變。在這種情況下，一定要記得撤消你的修改。

What is the best comment in source code you have ever encountered? - Stack Overflow[2]:

//
// Dear maintainer:
//
// Once you are done trying to 'optimize' this routine,
// and have realized what a terrible mistake that was,
// please increment the following counter as a warning
// to the next guy:
//
// total_hours_wasted_here = 42
//

你所使用的基準必須是正確的，並在有代表性的工作負載上提供可重複的數字。如果單個運行的差異太大，會使小的改進更難發現。需要使用 benchstat[3] 或同類的統計測試工具，而不能只靠單次或者肉眼對比。(注意，無論如何，使用統計測試是一個好主意。）運行基準的步驟應該被記錄下來，任何定製的腳本和工具都應該被提交到代碼倉庫裏，並說明如何運行它們。要注意運行時間較長的大型基準套件：這會使你的開發迭代被拖累速度。

還要注意，任何可以測量的指標都可以被優化。請確保你使用的是正確的指標。

下一步是決定你的優化目標是什麼。如果目標是提高 CPU 使用效率，什麼是可接受的速度？你想把當前的性能提高 2 倍？10 倍? 你能把它表述爲 "在少於時間 T 的情況下解決一個大小爲 N 的問題" 嗎？你是想減少內存的使用嗎？減少多少？慢多少是可以接受的？你願意放棄什麼來換取更低的空間需求？

對服務延遲的優化是一個更棘手的問題。關於如何測試網絡服務器的書已經寫了一整本。主要的問題是，對於一個單一的功能，在給定的問題規模下，性能是相當一致的。對於網絡服務，無法用單一的數字表示性能。一個靠譜的網絡服務基準測試套件將爲給定的 reqs/second 壓力提供延遲分佈結果。這個講座對一些問題做了很好的概述。[Gil Tene 的 "如何不測量延遲"](https://youtu.be/lJ8ydIuPFeU "Gil Tene 的" 如何不測量延遲 "")

性能目標必須具體，你一定能夠使一些東西更快。但優化經常是一個收益遞減的遊戲，要知道何時應該停止。你打算投入多少精力來完成最後一點工作。你願意讓代碼變得多難看、多難維護？

Simon Eskildsen 在 SRECon 的演講中更深入地闡述了這個話題。高級餐巾紙數學：從第一原理估算系統性能 [4]

最後，Jon Bentley 的 "Programming Pearls" 中有一章題爲 "The Back of the Envelope"，涉及費米問題。可悲的是，由於在 20 世紀 90 年代和 21 世紀初微軟式的 "智力面試題" 中使用了這些估計技能，這些技能給人的印象很差。

對於零起點開發，不應該把基準測試留到最後再搞。儘管說 "我們以後再解決" 很容易，但如果性能真的很重要，一開始設計階段就應該納入考量。在臨近收工時發現性能問題而需要架構大改，會給項目帶來巨大的風險。請注意，在開發過程中，重點應該放在合理的程序設計、算法和數據結構上。不過較底層的技術棧的優化可以放到項目研發的後期再做，對系統性能有了全面瞭解之後再去做更合適。當系統還不完整時，難以得到正確的全局性能視角。

"過早的劣化是指當你寫的代碼比它需要的速度慢時，通常是在進行不必要的額外工作，而同等複雜的代碼會更快，而且應該自然而然地從你的手指中流出來。"

-- Herb Sutter

在 CI 過程中進行基準測試是比較難的，因爲 CI 過程往往是混部的，這時候你得和同一臺機器上的其它 CI 任務一起跑，所以 CI 結果會受其它任務影響，難以獲得準確的指標。一個折衷是由開發人員在特定的硬件上自己跑 benchmark，並在 commit message 中將性能的變化數據附帶上。如果是普通的功能性的 patch，就需要用肉眼在 code review 過程中捕捉性能衰退情況了。

在大型系統上一般使用 profiling 採樣，局部的獨立組件寫的則是 benchmark。你需要能在性能測試時，啓動合理的上下文環境來模擬真實的情況。

當前系統的性能和你的目標性能之間存在哪些差異，在找到差異之後，就知道該從哪裏着手進行優化了，如果你只需要 10%~20% 的性能提升，可以通過一些實現的調整和較小的修復來達到目標。如果需要 10 倍這樣的係數，那麼只是用左移來替代乘法運算顯然是不可能的。這需要你對代碼進行反覆分析，甚至需要爲了這個性能目標把大部分模塊推翻重做。

性能優化需要了解不同層次的知識，從系統設計、網絡、硬件 (CPU、緩存、存儲)、算法、調整和調試。在時間和資源有限的情況下，要考慮哪個層面帶來的改進最大，這個並不一定總是在調整算法和程序、

通常，優化應該是自頂向下的。系統級的優化肯定比表達式級的優化效果要好。你應該確定自己是在合適的層級解決性能問題。

這本書大部分是討論減少 CPU 的使用，減少內存使用和減少延遲。需要指出的是，這三者比較難兼得。可能 CPU 使用率低了，但內存佔用上升了。可能內存使用下降了，但程序計算要花的時間更長了。

阿姆達爾定律 [5] 告訴我們要關注瓶頸問題。如果你把只佔運行時間 5% 的代碼速度提高一倍，這只是在總時鐘上提高了 2.5%。另一方面，如果將佔用 80% 時間的代碼的速度只提高 10%，將使運行性能提高近 8%。Profile 能夠幫助我們確定時間實際花在哪裏。

進行算法優化也可以減少 CPU 佔用，比如你用 quicksort，肯定比冒泡排序快，因爲它用更少的步驟就可以解決同樣的問題。

程序調整，就像編譯器優化一樣，通常只會對總的運行時間產生小的影響。大幅性能提升幾乎總是來自於算法的改變或數據結構的改變，是你的程序組織方式的根本轉變。編譯器技術的改進是緩慢的。Proebsting's Law[6] 說，編譯器的性能每 18 _年_翻一番，這與摩爾定律的（稍有誤解的解釋）形成鮮明對比，摩爾定律是每 18 _月_將處理器性能翻一番。算法的改進對程序的改進更爲顯著。

混合整數規劃算法在 1991 年和 2008 年之間改進了 30,000 倍 [7]。對於一個更具體的例子，考慮一下這個分解 [8]，將 Uber blog 中描述的蠻力地理空間算法替換爲更適合所提出的任務的更特化的算法。沒有任何編譯器開關可以給你帶來同等的性能提升。

profiler 可能會告訴你，大量的時間花在了某個特定的過程上。這可能是一個昂貴的調用，也可能是一個低消耗的調用，只是被調用了許多次。與其立即嘗試加快那個調用的速度，不如看看你是否能減少它被調用的次數或完全消除它。我們將在下一節中討論更具體的優化策略。

三個優化問題。

• 我們有必要這樣做嗎？最快的代碼是從未運行過的代碼。

• 如果是的話，這是不是最好的算法。

• 如果是的話，這是不是這個算法的_最佳_實現。

具體優化手段

喬恩 - 本特利（Jon Bentley）1982 年的作品《編寫高效程序》（Writing Efficient Programs）將程序優化作爲工程問題來研究：基準測試，分析，改進，驗證，迭代。他的許多建議現在都由編譯器自動完成。程序員的工作是使用編譯器_不能_自動進行的那個轉換優化。

書中有總結：

• http://www.crowl.org/lawrence/programming/Bentley82.html

• http://www.geoffprewett.com/BookReviews/WritingEfficientPrograms.html

程序的 tuning 規則：

當對程序進行修改時，一般有兩個選項：

• 要麼對數據做修改，要麼對代碼做修改

數據修改

改變你的數據意味着修改你的業務數據字段。從性能的角度來看，這些修改會影響後後續業務邏輯處理數據的時間複雜度。這個過程可能包含對你的數據提前進行一些預處理，以降低後續的數據處理負擔。

擴充你的數據結構的一些可能的做法：

• 冗餘字段

  這方面的典型例子是將一個鏈表的長度存儲在頭節點的一個字段中。保持它的更新需要更多的工作，但隨後查詢長度就變成了一個簡單的字段查找，而不是一個 O(n) 的遍歷過程。你的數據結構優化可能是這樣的：在一些操作中增加一次額外的記錄操作，換取高頻使用場景下的更快的性能。

  類似地，存儲指向經常訪問的節點的指針，而不是執行額外的搜索。這涵蓋了像雙鏈接列表中的 "next" 鏈接，以使節點移除變成 O(1) 時間複雜度。一些跳錶 (skiplist) 保留了一個 "search finger"，在這個位置保存了你上一次查詢到的位置。這種優化是假設了下次查詢從這個位置開始更好。

• 冗餘的搜索索引

  大多數數據結構都是爲單一類型的查詢而設計的。如果你需要兩種不同的查詢類型，在你的數據上有一個額外的 "視圖" 可能就有很大的改進。例如，一個數據結構數組可能有一個主鍵 ID（整數），可以被用來在切片中查詢，但還需要用一個次要的 ID（字符串）來查詢。你可以用一個從字符串到 ID 或直接到結構本身的映射來增強你的數據結構，而不是在切片上進行迭代。

• 額外的元素信息

  例如，保留一個你已經插入的所有元素的 Bloomfilter 可以讓你快速返回查詢 "不匹配"。bloomfilter 的設計應該是 “小而快”，不要超過你主要的數據結構的存儲成本。(如果主數據結構中的查找成本較低，bloomfilter 的維護成本可能超過這個查詢成本)。

• 如果查詢成本很高，增加 cache 層

  在應用層，增加進程內、進程外 (如 memcache) 緩存對提升查詢效率有很大幫助。對於單個數據結構來說可能這樣可能有點誇張，下面會詳細講講緩存。

當你需要的數據存儲成本低且容易保持更新時，這類優化就很有用。

這些都是在數據結構層面上 "少做工作" 的明顯例子。它們都要花費空間。大多數時候，如果你對 CPU 進行優化，你的程序會使用更多的內存。這就是典型的 [時空權衡]（https://en.wikipedia.org/wiki/Space%E2%80%93time_tradeoff）。

研究這種權衡如何影響你的解決方案是很重要的 -- 它並不總是簡單明瞭的。有時少量的內存可以帶來顯著的速度，有時權衡是線性的（2 倍的內存使用量 ==2 倍的性能加速），有時沒那麼明顯：大量的內存只帶來很小的速度提升。你需要在這條內存 / 性能曲線上的達到什麼位置，會影響到你需要選擇哪些算法。並不總是能簡單地調調算法參數，有時不同的內存使用目標可能需要完全不一樣的算法實現。

查表法 (lookup tables) 也是一種空間換時間的折衷。表就是我們複雜計算過程計算出的結果的一種緩存。

如果域足夠小，那麼_全部_結果都可以預先計算出來並存儲在表中。popcount 是這種模式的一個很好的例子，其中字節中的設置位數被存儲在一個 256 個條目的表中。一個更大的表可以存儲所有 16 位字所需的比特。在這種情況下，他們存儲的是精確的結果。

一些三角函數的算法使用查表作爲計算的起點。

如果你的程序使用了太多的內存，也可以走另一條路。通過消耗更多 CPU 減少內存空間的使用。與其存儲內容，不如每次都計算它們。可以在內存中存放壓縮後的數據，並在需要時實時解壓。

如果你要處理的數據在磁盤上，你可以爲你需要的數據創建索引，並只在內存中存儲索引，而不是全量數據，也可以將文件拆分成一個一個的 chunk。

小內存軟件 [9] 是一本可在網上獲得的書，涵蓋了減少程序所使用的空間的技術。雖然這本書最初是針對嵌入式開發人員編寫的，但其思想也適用於現代硬件上處理大量數據的程序。

• 重新排列你的數據

  消除結構填充。刪除多餘的字段。使用一個較小的數據類型。

• 改爲較慢的數據結構

  簡單的數據結構經常有較低的內存要求。例如，從一個指針很多的樹形結構轉爲使用切片和線性搜索。

• 爲你的數據定製壓縮格式

  壓縮算法在很大程度上取決於被壓縮的內容。最好選擇一種適合你的數據的算法。如果數據是 byte 數組，像 snappy、gzip、lz4 這樣的東西表現得很好。對於浮點數據，有 go-tsz 用於時間序列，fpc 用於科學數據。圍繞壓縮整數已經做了很多研究，通常是爲了在搜索引擎中進行信息檢索。例子包括 delta 編碼和 varints，以及 Huffman 編碼 xor-differences 等更復雜的方案。你也可以爲你的數據研發特殊的定製壓縮格式。

  數據是否可以壓縮？隨機訪問還是流式訪問？如果你需要訪問單個條目，但又不想解壓整個條目，你可以把數據壓縮成較小的塊，並保留一個索引，表明每個塊中的條目範圍。對單個條目的訪問只需要檢查索引和解壓較小的數據塊。

  如果你的數據不只是處理過程的數據，會被寫入磁盤，那麼數據遷移或添加 / 刪除字段怎麼辦。你現在要處理的是原始的 []byte，而不是漂亮的結構化 Go 類型，所以你需要考慮 unsafe 的序列化選項。

後面會更詳細地討論數據佈局。

現代計算機和內存分層使空間 / 時間的權衡變得不那麼清晰。查表算法中的表很容易在內存中離代碼較遠（因此訪問成本很高），這可能還不如重新計算一次值更快。

這也意味着基準測試中看起來有改進的代碼會經常由於緩存爭用而在生產系統中沒有改進（例如，在基準測試中查找表在處理器緩存中，但在實際系統中使用時總是 "新數據" 刷新緩存。) Google 的 Jump Hash 論文 [10] 實際上直接解決了這個問題，比較了有競爭和無競爭的處理器高速緩存的性能。(參見 Jump Hash 論文中的圖表 4 和 5)

sync.Map 是 Go 語言中針對 cache-contention 場景的解決方案。

另一個需要考慮的方面是數據傳輸時間。一般來說，網絡和磁盤訪問是非常緩慢的，因此能夠加載一個壓縮塊然後解壓也比直接從磁盤上加載完整未壓縮的內容消耗的 CPU 少得多。同樣與往常一樣，要有基準。二進制格式通常會比文本格式更小，解析速度更快，但代價是可讀性降低。

對於數據傳輸來說，可以轉向不那麼冗餘的協議，或者增強 API 以允許局部查詢。例如，可以將 API 實現爲增量查詢，而不是每次都被迫獲取整個數據集。

[1]

BitFunnel 性能估計: http://bitfunnel.org/strangeloop

[2]

What is the best comment in source code you have ever encountered? - Stack Overflow: https://stackoverflow.com/questions/184618/what-is-the-best-comment-in-source-code-you-have-ever-encountered

[3]

benchstat: https://golang.org/x/perf/benchstat

[4]

高級餐巾紙數學：從第一原理估算系統性能: https://www.youtube.com/watch?v=IxkSlnrRFqc

[5]

阿姆達爾定律: https://en.wikipedia.org/wiki/Amdahl%27s_law

[6]

Proebsting's Law: http://proebsting.cs.arizona.edu/law.html

[7]

在 1991 年和 2008 年之間改進了 30,000 倍: https://agtb.wordpress.com/2010/12/23/progress-in-algorithms-beats-moore%E2%80%99s-law/

[8]

這個分解: https://medium.com/@buckhx/unwinding-uber-s-most-efficient-service-406413c5871d

[9]

小內存軟件: http://smallmemory.com/book.html

[10]

Jump Hash 論文: https://arxiv.org/pdf/1406.2294.pdf

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/zv7gjs9w7d5brE-7_e1JOw