編寫和優(yōu)化Go代碼

image

本文檔概述了編寫高性能Go代碼的最佳實踐。

雖然有些討論會提高單個服務的速度（通過緩存等），但設(shè)計高性能的分布式系統(tǒng)已經(jīng)超出了這項工作的范圍。在監(jiān)控和分布式系統(tǒng)設(shè)計方面已經(jīng)有很好的文章，它包含了一套完全不同的研究和設(shè)計權(quán)衡理論。

所有內(nèi)容將根據(jù)CC-BY-SA進行許可。

本書分為不同的部分:

1) 編寫高性能軟件的基本技巧
  * CS 101-level的東西
2) 編寫快速軟件的技巧
  * 關(guān)于如何從Go獲得最佳效果的Go-specific章節(jié)
3) 編寫*真正*快速軟件的高級技巧
  * 當你優(yōu)化的代碼不夠快時

我們可以總結(jié)這三個部分:

• “合理的”
• “慎重的”
• “危險的”

何時何地做優(yōu)化

我先把這個放在第一位，是因為這真的是最重要的一步。你曾經(jīng)也應該這樣做嗎？

每個優(yōu)化都有成本。通常，這個成本是用代碼復雜度或認知負載來表示的 - 優(yōu)化后的代碼很少比未優(yōu)化的版本簡單。

但另一方面，我將稱之為“優(yōu)化經(jīng)濟學”。作為程序員，你的時間是寶貴的。你可以為你的項目工作的機會成本，哪些錯誤需要修復，以及需要添加哪些功能。優(yōu)化的工作是很有趣的，但并不總是正確的選擇。性能是一項功能，但代價和正確性也是如此。

選擇最重要的工作。有時它不是一個實際的CPU優(yōu)化，而是一個用戶體驗。就像添加進度條一樣簡單，或者通過在渲染頁面后在后臺執(zhí)行計算來提高頁面的響應速度。

有時這是顯而易見的:在三小時內(nèi)完成的報告在一小時完成可能不太有用。

僅僅因為容易優(yōu)化并不意味著它是值得優(yōu)化的。忽略low-hang的效果是一種有效的發(fā)展戰(zhàn)略。

把這看作是優(yōu)化你的時間。

選擇要優(yōu)化的內(nèi)容以及何時優(yōu)化，你可以在“軟件質(zhì)量”和“開發(fā)速度”之間移動滑塊。

人們無意識地重復說名言——“過早的優(yōu)化是萬惡之源”，但他們錯過了它的主要內(nèi)容。

“程序員浪費了大量的時間來思考或者擔心程序中非關(guān)鍵部分的速度，而這些效率的嘗試實際上在考慮調(diào)試和維護時會產(chǎn)生很大的負面影響。我們應該忘記為了小的性能使用的97％的時間：過早的優(yōu)化是萬惡之源，但我們不應該在這個關(guān)鍵的3％中放棄我們的優(yōu)化機會。“ - Knuth

附：https : //www.youtube.com/watch?time_continue=429&v=RT46MpK39rQ

• 不要忽視簡單的優(yōu)化
• 更多的算法和數(shù)據(jù)結(jié)構(gòu)知識使得更多的優(yōu)化變得“容易”或“明顯”

“你應該優(yōu)化嗎？”是的，但是只有當問題很重要時，程序真的太慢了，并且能夠在保證正確性，穩(wěn)健性和清晰度的同時變得更快?！?- 編程實踐，Kernighan and Pike

BitFunnel性能評估 有一些數(shù)字可以使這種權(quán)衡更加明確。想象一下假設(shè)搜索引擎需要跨越多個數(shù)據(jù)中心的30,000臺機器，這些機器每年的成本約為1,000美元。如果你可以將軟件的速度提高一倍，這可以為公司節(jié)省每年1500萬美元。即使只有一個開發(fā)人員花費整整一年時間才能將性能提高也只會付出1％的代價。

在絕大多數(shù)情況下，程序的大小和速度不是問題。最簡單的優(yōu)化不必這樣做。第二個最簡單的優(yōu)化就是購買更快的硬件。

如果你決定要改變你的程序，請繼續(xù)閱讀。

如何優(yōu)化

優(yōu)化工作流程

在介紹具體細節(jié)之前，我們先談談優(yōu)化的一般過程。

優(yōu)化是一種重構(gòu)形式。但是，每一步不是改進源代碼的某些方面（代碼重復，清晰度等），而是可以提高性能的某些方面：降低CPU，內(nèi)存使用率，延遲等。這種改進通常以可讀性為代價。這意味著除了一套全面的單元測試（以確保你的更改沒有破壞任何內(nèi)容）之外，你還需要一套很好的基準測試，以確保您的更改對性能產(chǎn)生預期的影響。你必須能夠驗證您的更改是否真的在降低CPU。有時候你認為會改善性能的變化實際上會變成零或負變化。在這些情況下，務必確保撤消修改的程序。

<cite>源代碼中遇到過的最好的評論是什么？- Stack Overflow</cite>

//
//親愛的維護者:
//
//當你完成試圖“優(yōu)化”這個程序，
//并且已經(jīng)意識到了什么可怕的錯誤，這是，
//請增加以下計數(shù)器作為警告
//下一個:
//
//total_hours_wasted_here = 42
//

你使用的基準測試必須正確，并為代表性工作負載提供可重復的數(shù)字。如果單個的運行差異太大，則會使得小的改進更難以發(fā)現(xiàn)。你將需要使用benchstat或等效的統(tǒng)計測試，而不能只是用眼睛去看(請注意，使用統(tǒng)計測試無論如何都是一個好主意)。應該記錄運行基準測試的步驟，并且應該向存儲庫提交任何自定義腳本和工具，并提供如何運行它們的說明。要注意需要很長時間才能運行的大型基準測試套件:它會使開發(fā)迭代變慢。

還要注意，任何可以測量的東西都可以優(yōu)化。確保你正在衡量正確的事情。

下一步是決定你正在優(yōu)化什么。如果目標是改進CPU，那么什么是可接受的速度。你想要將當前的性能提高2倍嗎？10倍？你能否說它是“小于時間T的大小為N的問題”？你想減少內(nèi)存使用量嗎？多少錢？對于內(nèi)存使用情況的變化，可以接受的速度有多慢？你愿意放棄什么來換取較低的空間需求？

優(yōu)化服務延遲是一個棘手的問題。整本書都是關(guān)于如何對Web服務器進行性能測試的。主要問題是：對于單個函數(shù)，對于給定的問題規(guī)模，性能相當一致。對于webservices，你沒有一個單一的性能數(shù)字。一個適當?shù)腤eb服務基準套件將為給定的需求/秒級別提供延遲分布。這篇演講很好地概述了Gil Tene的一些問題："如何不去測量延遲" by Gil Tene

TODO：請參閱后面的關(guān)于優(yōu)化Web服務的部分

績效目標必須具體。你會（幾乎）總是能夠更快地做出一些事情。優(yōu)化往往是一個收益遞減的游戲。你需要知道何時停止。你要付出多少努力才能完成最后一點工作。你愿意做出這樣的代碼是多么難以維護？

Dan Luu之前提到的BitFunnel性能評估的演講顯示了一個使用粗略計算來確定目標性能數(shù)據(jù)是否合理的例子。

TODO：編程珠璣有“Fermi Problems”。從Jeff Dean's 幻燈片可以了解

對于綠地開發(fā)，你不應該把所有的基準和性能數(shù)字都留到最后。很容易說“我們稍后會修復”，但如果性能非常重要，那么從一開始就將是一個設(shè)計考慮因素。在解決性能問題時所需的任何重大體系結(jié)構(gòu)更改在截止日期前將過于冒險。請注意，在開發(fā)過程中，重點應放在合理的程序設(shè)計，算法和數(shù)據(jù)結(jié)構(gòu)上。在更低層次的堆棧優(yōu)化應該等到開發(fā)周期晚些時候才能獲得更完整的系統(tǒng)性能視圖。你在系統(tǒng)不完整時執(zhí)行的任何完整系統(tǒng)配置文件都會對完成系統(tǒng)中瓶頸的位置給出偏斜視圖。

TODO：如何避免/發(fā)現(xiàn)軟件寫得不好的情況下的“凌遲”。

作為CI的一部分，基準測試是很難的，因為嘈雜的因素，甚至不同的CI盒子，那么很難獲取性能指標。一個好的基礎(chǔ)是讓開發(fā)人員運行基準測試（在適當?shù)挠布希┎⑵浒谔峤幌⒅?，專門用于處理性能問題。對于那些只是提普通補丁的人來說，盡量在代碼審查中捕捉性能下降。

TODO：如何跟蹤一段時間的性能表現(xiàn)？

編寫你可以測試的代碼。你可以在較大的系統(tǒng)上執(zhí)行分析。你可以通過基準測試測試孤立的部分。你需要能夠提取并設(shè)置足夠的環(huán)境上下文，以便基準測試足夠并具有代表性。

你的目標是什么和目前的表現(xiàn)之間的差異也會讓你知道從哪里開始。如果你只需要10％-20％的性能改進，那么可以通過一些實施調(diào)整和較小的修復來實現(xiàn)。如果你需要一個10倍或更多的因子，那么用一個左移代替一個乘法不會削減它。這可能會要求你的堆棧上下進行更改。

良好的性能工作需要從系統(tǒng)設(shè)計，網(wǎng)絡(luò)，硬件(CPU，緩存，存儲)，算法，調(diào)整和調(diào)試等多個不同層面的知識。在時間和資源有限的情況下，考慮哪個級別能夠提供最大的改進:它并不總是算法或程序調(diào)優(yōu)。

一般而言，優(yōu)化應該從上到下進行。系統(tǒng)級別的優(yōu)化將比表達級別的影響更大。確保你在適當?shù)乃缴辖鉀Q問題。

本書主要討論如何減少CPU使用率，減少內(nèi)存使用量并減少延遲。很高興指出你很少能做到這三點。也許CPU時間更快，但現(xiàn)在你的程序使用更多的內(nèi)存。也許你需要減少內(nèi)存空間，但現(xiàn)在該程序需要更長的時間。

阿姆達爾定律告訴我們要關(guān)注瓶頸。如果你將運行時間僅占5％的例程速度提高一倍，那么整個掛鐘的速度只有2.5％。另一方面，將80％的時間加速10％的例程將使運行時間提高近8％。配置文件將有助于確定實際花費的時間。

優(yōu)化時，你想減少CPU必須完成的工作量。Quicksort比氣泡排序更快，因為它能以更少的步驟解決相同的問題(排序)。這是一個更高效的算法。你已經(jīng)減少了CPU完成相同任務所需完成的工作。

像編譯器優(yōu)化一樣，程序調(diào)優(yōu)通常只會在整個運行時間中造成一點小小的負擔。大的勝利幾乎總是來自算法改變或數(shù)據(jù)結(jié)構(gòu)的改變，這是你的程序組織方式的根本轉(zhuǎn)變。編譯器技術(shù)有所改進，但速度很慢。Proebsting定律表明，編譯器每18 年的性能翻倍，這與摩爾定律(稍微誤解了解釋)形成鮮明對比，該定律使處理器性能每18 個月翻一番。算法改進在更大的范圍內(nèi)工作。從1991年到2008年，混合器整數(shù)規(guī)劃算法提高了30,000倍 有關(guān)更具體的示例，請考慮此故障取代優(yōu)步博客文章中描述的蠻力地理空間算法，使用更適合于所提交任務的更專業(yè)的算法。沒有編譯器開關(guān)可以提供相同的性能提升。

TODO：在gttse07.pdf中優(yōu)化浮點FFT和MMM算法的差異

分析器可能會告訴你，大量的時間都花在了特定的例程上。這可能是一個昂貴的例程，或者它可能是一個便宜的例程，只是被稱為許多次。而不是立即加快這一過程，看看你是否可以減少被調(diào)用的次數(shù)或完全消除它。我們將在下一節(jié)討論更具體的優(yōu)化策略。

三個優(yōu)化問題:

• 我們必須這樣做嗎？最快的代碼是永遠不會運行的代碼。
• 如果是的話，這是最好的算法。
• 如果是的話，這是這個算法的最佳實現(xiàn)。

具體的優(yōu)化技巧

Jon Bentley在1982年的作品“編寫高效程序”將程序優(yōu)化視為一個工程問題:基準。分析。提高。校驗。迭代。他的一些技巧現(xiàn)在由編譯器自動完成。程序員的工作是使用編譯器無法做到的轉(zhuǎn)換。

本書的摘要如下:

• http://www.crowl.org/lawrence/programming/Bentley82.html
• http://www.geoffprewett.com/BookReviews/WritingEfficientPrograms.html

和程序調(diào)整規(guī)則:
https://web.archive.org/web/20080513070949/http://www.cs.bell-labs.com/cm/cs/pearls/apprules.html

在考慮對程序進行更改時，有兩個基本選項:你可以更改數(shù)據(jù)，也可以更改代碼。

數(shù)據(jù)的更改

改變你的數(shù)據(jù)意味著增加或改變你正在處理的數(shù)據(jù)的表示。從性能角度來看，其中一些最終會改變與數(shù)據(jù)結(jié)構(gòu)的不同方面相關(guān)的O()。

增加數(shù)據(jù)結(jié)構(gòu)的想法:

• 額外字段:例如，存儲鏈接列表的大小，而不是在詢問時迭代?；蛘邔⒔?jīng)常需要的其他節(jié)點的指針存儲到多個搜索中(例如，雙向鏈接列表中的“向后”鏈接以進行刪除O(1))。當你需要的數(shù)據(jù)便于存儲并保持最新時，這些更改很有用。
• 額外的搜索索引:大多數(shù)數(shù)據(jù)結(jié)構(gòu)都是為單一類型的查詢而設(shè)計的。如果你需要兩種不同的查詢類型，對數(shù)據(jù)進行額外的“查看”可能會有很大的改進。例如，[] struct，由ID引用，但有時是string - > map [string] id(或* struct)
• 有關(guān)元素的額外信息:例如布隆過濾器。這些數(shù)據(jù)結(jié)構(gòu)必須小而快，以免壓倒其余的數(shù)據(jù)結(jié)構(gòu)。
• 如果查詢很昂貴，請?zhí)砑右粋€緩存。我們都熟悉memcache，但還有進程內(nèi)緩存。

• 通過網(wǎng)絡(luò)，網(wǎng)絡(luò)+序列化成本將會受到影響
• 進程內(nèi)緩存，但現(xiàn)在你需要擔心到期
• 即使是單個項目也可以幫助(日志文件時間解析示例)

TODO:“緩存”可能不是鍵值對，只是指向你工作的地方。這可以像“搜索手指”一樣簡單

這些都是數(shù)據(jù)結(jié)構(gòu)層面“做更少工作”的明確例子。他們都花費空間。大多數(shù)情況下，如果你針對CPU進行優(yōu)化，程序?qū)⑹褂酶嗟膬?nèi)存。這是經(jīng)典的時空交易

如果你的程序使用太多的內(nèi)存，也可以換個方式。減少空間使用量以換取更多計算。而不是存儲的東西，每次計算它們。你還可以壓縮內(nèi)存中的數(shù)據(jù)，并在需要時隨時對其進行解壓縮。

小內(nèi)存軟件是一本網(wǎng)上可獲取的書籍，涵蓋了減少程序使用內(nèi)存空間的技術(shù)。雖然它最初是針對嵌入式開發(fā)人員編寫的，但這些想法適用于處理大量數(shù)據(jù)的現(xiàn)代硬件的程序。

• 重新排列你的數(shù)據(jù)
  消除結(jié)構(gòu)填充。刪除額外的字段。使用較小的數(shù)據(jù)類型
• 更改為較慢的數(shù)據(jù)結(jié)構(gòu)
  較簡單的數(shù)據(jù)結(jié)構(gòu)通常具有較低的內(nèi)存要求。例如，從一個指針重的樹結(jié)構(gòu)轉(zhuǎn)向使用切片和線性搜索。
• 為你的數(shù)據(jù)定制壓縮格式
  []字節(jié)（snappy，gzip，lz4），浮點數(shù)（go-tsz），整數(shù)（delta，xor + huffman）大量的壓縮資源。你需要檢查數(shù)據(jù)還是可以保持壓縮？你需要隨機訪問還是只有流媒體？壓縮具有額外索引的塊。如果不是在進程中，而是寫入磁盤，那么遷移或添加/刪除字段呢？你現(xiàn)在正在處理raw []字節(jié)而不是很好的結(jié)構(gòu)化Go類型。

我們稍后會詳細討論數(shù)據(jù)布局。

現(xiàn)代計算機和存儲器層次結(jié)構(gòu)使空間/時間的權(quán)衡不太明確。查找表很容易在內(nèi)存中“遠離”(因此訪問成本很高)，使得每次需要時重新計算一次值都會更快。

這也意味著基準測試通常會顯示由于緩存爭用而導致生產(chǎn)系統(tǒng)無法實現(xiàn)的改進(例如，查找表在基準測試期間位于處理器緩存中，但在真實系統(tǒng)中使用時總是會被“真實數(shù)據(jù)”沖刷。哈希表實際上直接解決了這個問題，比較了滿足和無約束的處理器緩存上的性能。參見Jump Hash paper論文中的圖4和圖5。

TODO:如何模擬滿足的緩存，顯示增量成本

另一個要考慮的方面是數(shù)據(jù)傳輸時間。通常，網(wǎng)絡(luò)和磁盤訪問非常緩慢，因此能夠加載壓縮塊的速度將比獲取數(shù)據(jù)后解壓縮數(shù)據(jù)所需的額外CPU時間快得多。一如既往，基準。二進制格式通常比文本格式更小且更快解析，但代價是不再是人類可讀的格式。

對于數(shù)據(jù)傳輸，轉(zhuǎn)移到一個不那么有趣的協(xié)議，或者增加API以允許部分查詢。例如，增量查詢而不是每次都被迫獲取整個數(shù)據(jù)集。

算法的更改

如果你不更改數(shù)據(jù)，另一個主要選項是更改代碼。

最大的改進很可能來自算法變化。這與使用快速排序?qū)馀菖判蛱鎿Q為從O(n ^ 2)排序到O(n log n)或使用映射查找替換通過過去是小O(n)的數(shù)組的線性掃描等效(O (1))。

最大的改進可能來自算法變化。這相當于用quicksort（O(nlogn)）替換O(n^2)的冒泡排序或者通過哈希查找（O(1)）替換數(shù)組（O(n)）的線性掃描。

這就是軟件如何變慢。最初設(shè)計用于一種用途的結(jié)構(gòu)被重新用于未設(shè)計的東西。這是逐漸發(fā)生的。

直觀地掌握不同的大O級別是很重要的。為你的問題選擇正確的數(shù)據(jù)結(jié)構(gòu)。你不必一直刮刮胡須，但是這樣做可以防止很久以后才會發(fā)現(xiàn)的愚蠢的性能問題。

基本的復雜類別是:

• O（1）：字段訪問，數(shù)組或地圖查找
  建議：不要擔心
• O（log n）：二進制搜索
  建議：如果處于循環(huán)狀態(tài)，則只是一個問題
• O（n）：簡單循環(huán)
  建議：你一直在這樣做
• O（n log n）：分而治之，排序
  建議：還是相當快的
• O（n * m）：嵌套循環(huán)/二次方
  建議：小心并限制你的大小
• 二次和次指數(shù)之間的任何其他內(nèi)容
  建議：不要在一百萬行上運行
• O（b ^ n），O（n！）：指數(shù)上升
  建議：如果你有十幾個或兩個數(shù)據(jù)點，祝您好運

鏈接:http://bigocheatsheet.com

假設(shè)你需要搜索未分類的數(shù)據(jù)集?！拔覒撚枚炙阉鳌?，你知道一個二分搜索O(log n)比O(n)線性掃描快。但是，二分查找需要對數(shù)據(jù)進行排序，這意味著你需要先對它進行排序，這將花費O(n log n)時間。如果你正在進行大量搜索，那么分類的前期成本將會得到回報。另一方面，如果你主要做查詢，也許有一個數(shù)組是錯誤的選擇，你最好支付O(1)查找地圖的代價。

選擇最簡單的合理數(shù)據(jù)結(jié)構(gòu)并繼續(xù)。這是用于編寫“非慢速軟件”的CS 101。這應該是您的默認開發(fā)模式。如果您知道需要隨機訪問，請不要選擇鏈接列表。如果您知道需要按順序遍歷，請不要使用地圖。需求變化，你不能總是猜測未來。對工作量做出合理的猜測。

http://daslab.seas.harvard.edu/rum-conjecture/

類似問題的數(shù)據(jù)結(jié)構(gòu)在做一件工作時會有所不同。隨著插入的發(fā)生，二叉樹每次排序一次。未排序的數(shù)組插入速度更快但未排序:最后，“敲定”你需要一次完成排序。

當編寫一個供其他人使用的包時，避免每個用例都要優(yōu)先考慮的誘惑。這將導致代碼不可讀。按設(shè)計的數(shù)據(jù)結(jié)構(gòu)實際上是單一用途的。你既不能讀懂頭腦，也不能預測未來。如果用戶說“你的軟件包對于這個用例太慢”，一個合理的答案可能是“然后在這里使用這個軟件包”。一攬子計劃應該“做得很好”。

有時混合數(shù)據(jù)結(jié)構(gòu)將提供你需要的性能改進。例如，通過分段數(shù)據(jù)，你可以將搜索范圍限制在一個存儲桶中。這仍然支付O(n)的理論成本，但常數(shù)會更小。當我們進行編程調(diào)整時，我們將重新審視這些調(diào)整。

在討論大O符號時，人們忘記了兩件事

其一，涉及到一個不變的因素。具有相同算法復雜度的兩種算法可以具有不同的常數(shù)因子。想象一下，循環(huán)遍歷一個列表100次，而僅循環(huán)一次。即使兩者都是O（n），也有一個恒定的因子是100倍。

這些常數(shù)因素是為什么即使合并排序，快速排序和排列所有O(n log n)，每個人都使用快速排序，因為它是最快的。它具有最小的常數(shù)因子。

第二件事是大O只說“隨著n增長到無窮大”。它談到了增長趨勢，“隨著數(shù)字變大，這是主導運行時間的增長因素?！?它沒有提到實際的表現(xiàn)，也沒有說明它如何表現(xiàn)小n。

經(jīng)常有一個分界點，在這個分界點以下，木材算法更快。Go標準庫sort包的一個很好的例子。大多數(shù)時候它使用快速排序，但是當分區(qū)大小降到12個元素以下時，它會進行shell排序傳遞，然后進行插入排序。

對于某些算法，常數(shù)因子可能非常大，以致此截點可能比所有合理的輸入都大。也就是說，O（n ^ 2）算法對于所有可能處理的輸入都比O（n）算法快。

這也是另一種方式：例如，即使小輸入的基準變慢，選擇使用更復雜的數(shù)據(jù)結(jié)構(gòu)來給出O（n）縮放而不是O（n ^ 2）。這也適用于大多數(shù)無鎖數(shù)據(jù)結(jié)構(gòu)。它們通常在單線程情況下較慢，但在多線程使用它時更具可擴展性。

現(xiàn)代計算機中的存儲器層次結(jié)構(gòu)將問題混淆了一點，因為高速緩存更喜歡將片段掃描到追蹤指針的有效隨機訪問的可預測訪問。不過，最好從一個好的算法開始。我們將在硬件特定部分討論這個問題。

“這場斗爭可能并不總是最強，也不是最快的比賽，但這是打賭的方式?！?- 吉卜林。

有時，針對特定問題的最佳算法不是單一的算法，而是專門針對稍微不同的輸入類的算法集合。這個“polyalgorithm”可以快速檢測出需要處理的輸入類型，然后發(fā)送到相應的代碼路徑。這就是上面提到的排序包所做的：確定問題的大小并選擇不同的算法。除了結(jié)合quicksort，shell排序和插入排序之外，它還會跟蹤快速排序的遞歸深度并在必要時調(diào)用堆排序。在string與bytes包做類似的事情，檢測和專門處理不同的情況。與數(shù)據(jù)壓縮一樣，您對輸入內(nèi)容的了解越多，定制解決方案就越好。即使優(yōu)化并不總是適用，通過確定使用和執(zhí)行不同的邏輯是安全的，使代碼復雜化可能是值得的。

這也適用于你的算法需要解決的子問題。例如，能夠使用基數(shù)排序可以對性能產(chǎn)生重大影響，如果只需要部分排序，則可以使用快速選擇。

有時候，而不是專門針對您的特定任務，最好的方法是將其抽象為研究人員已經(jīng)充分研究的更一般的問題空間。然后，您可以將更一般的解決方案應用于您的特定問題。將你的問題映射到已經(jīng)有很好研究實現(xiàn)的領(lǐng)域可能是一個重大的勝利。

基準輸入

了解你的每種輸入尺寸可能在生產(chǎn)中有多大。

你的基準測試必須使用適當大小的輸入。正如我們所看到的，不同的算法在不同的輸入大小下都有意義。如果你的預期輸入范圍<100，那么你的基準應該反映這一點。否則，選擇最適合n = 10 ^ 6的算法可能不是最快的。

能夠生成有代表性的測試數(shù)據(jù)。不同的數(shù)據(jù)分布會在你的算法中引發(fā)不同的行為:想想經(jīng)典的“數(shù)據(jù)排序時快速排序為O(n ^ 2)”示例。類似地，對于均勻的隨機數(shù)據(jù)，插值搜索是O(log log n)，但是O(n)最差的情況。知道你的輸入是什么樣子是代表性基準和選擇最佳算法的關(guān)鍵。如果你用來測試的數(shù)據(jù)不能代表實際工作負載，那么你可以輕松完成針對某個特定數(shù)據(jù)集的優(yōu)化，“過度配置”你的代碼以便使用一組特定的輸入進行最佳工作。

這也意味著你的基準數(shù)據(jù)需要代表真實世界。如果重復的請求非常少見，保留它們比重新計算它們更昂貴。如果你的基準數(shù)據(jù)僅包含相同的重復請求，則緩存將提供不準確的性能視圖。

另請注意，一旦部署到生產(chǎn)環(huán)境并且在40核心服務器上達到25萬次/秒，筆記本電腦上可能看不到的一些問題就可以看到。

編寫好的基準測試可能很困難。
TODO：microbenchmarks顯示速度減慢但宏觀（現(xiàn)實世界）性能提高的情況。

• https://timharris.uk/misc/five-ways.pdf

程序調(diào)整

程序調(diào)優(yōu)曾經(jīng)是一種藝術(shù)形式，但編譯器變得更好。所以現(xiàn)在事實證明，編譯器可以比復雜的代碼更好地直接優(yōu)化代碼。Go編譯器在匹配gcc和clang方面還有很長的路要走，但這確實意味著在調(diào)整時需要小心，特別是在升級Go版本時不要變得更糟。一旦編譯器得到改進，肯定會出現(xiàn)一些針對缺少特定編譯器優(yōu)化工作的調(diào)整。

TODO：https : //github.com/golang/go/commit/9eb219480e8de08d380ee052b7bff293856955f8）

如果你正在解決特定的運行時或編譯器代碼生成問題，請始終使用指向上游問題的鏈接記錄你的更改。這可以讓你在bug修復后快速重新訪問你的優(yōu)化。

打擊基于民間傳說的崇拜“性能提示”的誘惑，甚至是從你自己的經(jīng)驗中過度概括。每個性能缺陷都需要根據(jù)自身的優(yōu)點加以處理。即使之前已經(jīng)有效，確保配置文件確保修復仍然適用。你以前的工作可以指導你，但不要盲目應用以前的優(yōu)化。

程序調(diào)優(yōu)是一個迭代過程。繼續(xù)重新訪問你的代碼并查看可以進行哪些更改。確保你在每一步都取得進展。經(jīng)常有一項改進可以使其他人獲得成功。(現(xiàn)在我沒有做A，我可以通過做C來簡化B)。這意味著你需要繼續(xù)觀察整個圖片，而不是沉迷于一小組線。

一旦你確定了正確的算法，程序調(diào)優(yōu)就是改進算法實現(xiàn)的過程。在Big-O表示法中，這是減少與程序相關(guān)的常量的過程。

所有的節(jié)目調(diào)整都要么讓速度變慢，要么減慢速度。算法變化也屬于這些類別，但我們將看到較小的變化。你的具體做法隨技術(shù)變化而變化。

做一個緩慢的事情可能會用更快的散列函數(shù)替換SHA1或者hash/fnv1。少做一次緩慢的事情可能會節(jié)省一個大文件的哈希計算結(jié)果，因此你不必多次執(zhí)行該操作。

保留意見。如果不需要做什么，請解釋原因。通常，在優(yōu)化算法時，你會發(fā)現(xiàn)在某些情況下不需要執(zhí)行的步驟。記錄它們。其他人可能會認為這是一個錯誤，需要放回去。

空程序立刻給出了錯誤的答案。
如果你不必是正確的，那么很快就會很快。

“正確性”可以取決于問題。啟發(fā)式算法大多數(shù)情況下是正確的，大部分時間都可以很快，而且猜測和改進的算法可以讓您在達到可接受的限制時停下來。

緩存常見情況：

• 你的緩存甚至不需要很大。
• 參見下面的 time.Parse（）例子; 只有一個價值觀產(chǎn)生了影響
• 但要注意緩存失效，線程問題等。
• 隨機緩存驅(qū)逐是快速且足夠有效的。
• 隨機緩存插入可以用最少的邏輯將緩存限制為流行的項目。
• 將緩存邏輯的成本與重新獲取數(shù)據(jù)的成本進行比較。
• 大容量緩存可能會增加GC壓力并不斷吹動處理器緩存。
• 在極端情況下（很少或沒有驅(qū)逐，將所有請求緩存到一個昂貴的函數(shù)），這可以變成記憶

我已經(jīng)完成了一個網(wǎng)絡(luò)跟蹤實驗，表明即使是最佳的緩存也不值得。你的預期命中率很重要。你需要將比率導出到你的監(jiān)控堆棧。不斷變化的比例將顯示流量的變化。然后是重新訪問緩存大小或過期策略的時候了。

程序調(diào)優(yōu)：

程序調(diào)優(yōu)是以小步驟迭代改進程序的藝術(shù)。Egon Elbre列出了他的程序：

• 提出一個假設(shè)，為什么你的程序很慢。
• 拿出N個解決方案來解決它
• 嘗試一切，并保持最快。
• 以防萬一。
• 重復。

調(diào)整可以采取多種形式。

• 如果可能，請保留舊的實現(xiàn)以進行測試。
• 如果不可能，則生成足夠的黃金測試用例來比較輸出。
  “足夠”意味著包括邊緣案例，因為這些可能會受到調(diào)優(yōu)的影響，因為您旨在提高一般情況下的性能。
• 利用數(shù)學身份：https://github.com/golang/go/commit/ed6c6c9c11496ed8e458f6e0731103126ce60223 https://gist.github.com/dgryski/67e6a7ff94c3a1add30eb26ec0ad8b0f
  • 與加法相乘
  • 使用WolframAlpha，Maxima，sympy和類似工具來專門化，優(yōu)化或創(chuàng)建查找表
    （另外，https://users.ece.cmu.edu/~franzf/papers/gttse07.pdf）
  • “只為你使用的東西付費，而不是你可以使用的東西”
  • 零只是數(shù)組的一部分，而不是整個事物
  • 最好以微小的步驟完成，一次只做幾個陳述
  • 從浮點數(shù)學到整數(shù)數(shù)學
  • 或者mandelbrot刪除sqrt，或者lttb刪除abs， a < b/c=>a * c < b
  • 在更昂貴的支票前進行廉價支票
  • 例如，在正則表達式之前的strcmp，（qv，在查詢之前的布隆過濾器）“少花費更多時間”
  • 在罕見情況之前的常見情況，即避免總是失敗的額外測試
  • 展開仍然有效：https：//play.golang.org/p/6tnySwNxG6O
  • 代碼大小。vs分支測試開銷
  • 使用偏移而不是切片分配可以幫助進行邊界檢查，數(shù)據(jù)依賴性和代碼生成（少于在內(nèi)部循環(huán)中復制）。
  • 這就是Hacker's Delight的一部分
  • 考慮不同的數(shù)字表示法：定點，浮點，（?。┱麛?shù)，
  • 愛好者：帶誤差累加器的整數(shù)（如Bresenham的線和圓），多基數(shù)/冗余數(shù)字系統(tǒng)

許多針對調(diào)優(yōu)的民間傳說性能提示依賴于對編譯器的優(yōu)化不足，并鼓勵程序員手動完成這些轉(zhuǎn)換。編譯器一直在使用更新，而不是用15年的時間乘以或除以2的冪 - 現(xiàn)在沒有人應該親自去做。類似地，提升循環(huán)中的不變計算，基本循環(huán)展開，常見子表達式消除等等都是由gcc和clang等自動完成的。Go的編譯器完成了其中的許多工作，并繼續(xù)改進。一如往常，在提交新版本之前進行基準測試。

編譯器無法做到的轉(zhuǎn)換依賴于你了解有關(guān)算法，輸入數(shù)據(jù)，系統(tǒng)中的不變量以及可以做出的其他假設(shè)等事情，并將該隱式知識分解為刪除或更改數(shù)據(jù)結(jié)構(gòu)中的步驟。

每個優(yōu)化都會對你的數(shù)據(jù)進行假設(shè)。這些必須記錄下來，甚至更好地進行測試。這些假設(shè)將會在你的程序崩潰，放慢速度，或隨著系統(tǒng)發(fā)展而開始返回錯誤數(shù)據(jù)的地方。

程序調(diào)整改進是累積的。5倍3％的改善是15％的改善。進行優(yōu)化時，值得考慮預期的性能改進。用更快的替換哈希函數(shù)是一個不斷改進的因素。

了解你的要求和可以改變的地方可以提高性能。在#performance Gophers Slack頻道中呈現(xiàn)的一個問題是用于為字符串鍵/值對映射創(chuàng)建唯一標識的花的數(shù)量。最初的解決方案是提取鍵，對它們進行排序，并將結(jié)果字符串傳遞給散列函數(shù)。我們提出的改進解決方案是在鍵/值添加到地圖時對其進行單獨散列處理，然后將所有這些散列在一起以創(chuàng)建標識符。

這是一個專業(yè)化的例子。

假設(shè)我們正在處理一天中的大量日志文件，并且每行都以時間戳開始。

Sun 4 Mar 2018 14:35:09 PST <...........................>
對于每行，我們調(diào)用time.Parse()把它變成一個格式。如果性能分析顯示我們time.Parse()是瓶頸，那么我們有幾種方法可以加快速度。

最簡單的方法是保留先前看到的時間戳和相關(guān)歷元的單項緩存。只要我們的日志文件在一秒鐘內(nèi)有多行，這將是一場勝利。對于1000萬行日志文件的情況，這種策略將昂貴的呼叫數(shù)量time.Parse()從10,000,000減少到86400 - 每個獨立的秒鐘一個。

TODO：單項緩存的代碼示例

我們可以做更多嗎？因為我們確切知道時間戳的格式， 并且它們都在一天內(nèi)完成，所以我們可以編寫自定義時間解析邏輯，將其考慮在內(nèi)。我們可以計算午夜的時代，然后從時間戳字符串中提取小時，分鐘和秒 - 它們都將在字符串中處于固定偏移量 - 并執(zhí)行一些整數(shù)運算。

TODO：字符串偏移版本的代碼示例

在我的基準測試中，這將解析時間從275ns / op減少到5ns / op。（當然，即使在275 ns / op下，你也更有可能在I / O上被阻塞，而不是在時間解析上被CPU阻塞。）

一般算法很慢，因為它必須處理更多的案例。你的算法可以更快，因為你更了解你的問題。但是代碼與您需要的密切關(guān)系更緊密。如果時間格式發(fā)生變化，更新更加困難。

優(yōu)化是專業(yè)化的，專用代碼比通用代碼更易于改變。

對于大多數(shù)情況，標準庫實現(xiàn)需要“足夠快”。如果你有更高的性能需求，你可能需要專門的實現(xiàn)。

定期進行配置文件以確保跟蹤系統(tǒng)的性能特征，并準備隨著流量變化重新優(yōu)化。了解你的系統(tǒng)的極限，并有好的指標，讓你預測什么時候你會達到這些限制。

當你的應用程序的使用發(fā)生更改時，不同的部分可能會成為熱點。重溫先前的優(yōu)化并決定它們是否仍然值得，并在可能的情況下恢復為更易讀的代碼。我有一個系統(tǒng)，我使用一組復雜的mmap優(yōu)化了啟動時間，反映了不安全性。一旦我們改變了系統(tǒng)的部署方式，這個代碼就不再需要了，我用更可讀的常規(guī)文件操作取代了它。

優(yōu)化工作流程摘要
所有優(yōu)化都應遵循以下步驟：

1. 確定你的表現(xiàn)目標，并確認你沒有達到他們的目標
2. 配置文件來識別要改進的區(qū)域。
3. 這可以是CPU，堆分配或goroutine阻塞。
4. 基準來確定您的解決方案使用內(nèi)置基準測試框架提供的加速http://golang.org/pkg/testing/
5. 確保您在目標操作系統(tǒng)和體系結(jié)構(gòu)上進行正確的基準測試。
6. 之后再次進行配置以驗證問題已消失
7. 使用https://godoc.org/golang.org/x/perf/benchstat或https://github.com/codahale/tinystat來驗證一組時間“充分”不同，以便優(yōu)化值得添加代碼復雜性。
8. 使用https://github.com/tsenart/vegeta負載測試http服務（+其他花哨的：k6，fortio，...）
9. 確保你的延遲數(shù)字是有意義的
10. 第一步很重要。它會告訴您何時何地開始優(yōu)化。更重要的是，它還會告訴你何時停止。幾乎所有優(yōu)化都會增加代碼的復雜性以換取速度。而且你總是可以更快地編寫代碼。這是一個平衡的行為。

工具

介紹性分析

一般適用于源代碼的技術(shù)

1. 介紹pprof
   • Go工具pprof(https://github.com/google/pprof)
2. 編寫和運行(微)基準
   • 簡介，將hot code提取到基準，優(yōu)化基準，配置文件。
   • -cpuprofile/-memprofile/-benchmem
   • 0.5 ns/op意味著它被優(yōu)化了 ->如何避免
   • 編寫好的基準測試的技巧(刪除不必要的工作，但增加基準)
3. 如何讀取它的pprof輸出
4. 顯示的運行系統(tǒng)有哪些不同的部分
5. 宏觀基準(生產(chǎn)剖析)
   • net/HTTP/pprof
6. 使用-base查看差異
7. 內(nèi)存選項：-inuse_space，-inuse_objects，-alloc_space，-alloc_objects
8. 生產(chǎn)分析; localhost + ssh隧道，auth頭文件，使用curl。

追蹤

• 一些更有趣的/先進的工具
• /x/perf中的其他工具
• perf（perf2pprof）
• 英特爾vtune/amd codexl/instruments
  https://godoc.org/github.com/aclements/go-perf

垃圾收集

你不止一次支付內(nèi)存分配。第一個顯然是你分配它的時候。但是，每次垃圾收集運行時，你也要付出代價。

減少回收再利用。 - @bboreham

• 堆棧與堆分配
• 什么導致堆分配？
• 了解逃逸分析(和當前的限制)
• /debug/pprof/heap和-base
• API設(shè)計限制分配:允許傳入緩沖區(qū)，因此調(diào)用者可以重用而不是強制分配
• 你甚至可以在掃描時仔細修改切片
• 減少指針以減少gc掃描時間
• 無指針的map鍵
• GOGC
• 緩沖區(qū)重用(sync.Pool vs或通過go-slab等自定義)
• 切片與偏移量：當GC運行時指針寫入需要writebarrier：https : //github.com/golang/go/commit/b85433975aedc2be2971093b6bbb0a7dc264c8fd
• 使用錯誤變量而不是errors.New（）/ fmt.Errorf（）在呼叫站點（性能或風格？接口需要指針，所以它轉(zhuǎn)義為堆）
• 使用結(jié)構(gòu)化的錯誤來減少分配（傳遞結(jié)構(gòu)值），在錯誤打印時創(chuàng)建字符串
• 大小端

運行時和編譯器

• 通過接口調(diào)用的成本(在CPU級別上的間接調(diào)用)
• runtime.convT2E/runtime.convT2I
• 類型斷言與類型切換
• 延緩
• 用于整數(shù)，字符串的特殊映射實現(xiàn)
  • byte/uint16的映射未優(yōu)化; 改用切片。
  • 你可以使用math.Float{32,64}{from,}bits優(yōu)化float64-optimized ，但要注意浮動平等問題
  • https://github.com/dgryski/go-gk/blob/master/exact.go 據(jù)說快100倍; 需要基準測試
• 邊界檢查消除
• []字節(jié)<->字符串副本，Map優(yōu)化
• 雙值的range將復制一個數(shù)組，使用sclice替代：
  • https://play.golang.org/p/4b181zkB1O
  • https://github.com/mdempsky/rangerdanger
• 盡可能使用字符串連接而不是fmt.Sprintf; 運行時為它已經(jīng)優(yōu)化了例程

Unsafe

• 它所有的危險項
• unsafe的常見用途
• mmap數(shù)據(jù)文件
  • 結(jié)構(gòu)填充
  • 但并不總是足夠快以證明復雜性/安全成本
  • 但是“off-heap”，所以被gc忽略（但是沒有指針的slice）
• 快速反序列化
• string <-> slice 轉(zhuǎn)換，[]byte <-> []uint32，...
• int到bool是不安全的hack (但 != 0是可以的)
• 填充：
  • https://dave.cheney.net/2015/10/09/padding-is-hard
  • http://www.catb.org/esr/structure-packing/#_go_and_rust
  • https://golang.org/ref/spec#Size_and_alignment_guarantees
  • https://github.com/dominikh/go-tools 結(jié)構(gòu)布局，結(jié)構(gòu)布局優(yōu)化
  • 通過Offsetof對結(jié)構(gòu)布局進行編碼以發(fā)現(xiàn)unsafe和asm破損

與標準庫共同陷阱

• time.After()泄漏，直到它被觸發(fā)
• 重用HTTP連接...
• rand.Int()和朋友是1)互斥體保護和2)創(chuàng)建昂貴
• 考慮交替隨機數(shù)生成(go-pcgr，xorshift)
• binary.Read和binary.Write使用反射并且很慢; 手動做
• 如果可能，請使用strconv而不是fmt
• ....

替代實現(xiàn)

• 標準庫軟件包的普遍替代品:
  • encoding/json -> ffjson
  • net/http -> fasthttp(但不兼容的API)
  • regexp -> ragel(或其他正則表達式包)
• 系列化
  • encoding/gob - > https://github.com/alecthomas/go_serialization_benchmarks
  • protobuf - > https://github.com/gogo/protobuf
  • 所有格式都有權(quán)衡:選擇一種符合你需要的編碼空間，解碼速度，語言/工具兼容性......
• database/sql - > jackx/pgx，...
• gccgo
• container/list：使用切片（幾乎總是）

CGO

• cgo調(diào)用的性能特征
• 降低成本的技巧:配料
• Go和C之間傳遞指針的規(guī)則
• syso文件

高級技術(shù)

特定于運行代碼的體系結(jié)構(gòu)的技術(shù)

• CPU緩存介紹

  • 性能的懸崖
  • 圍繞緩存行構(gòu)建直覺:大小，填充，對齊
  • 共享假
  • 真正的共享 ->分片
  • OS工具來查看緩存未命中
  • Mao與切片
  • SOA vs AOS布局
  • 減少指針追逐

• 分支預測
  從內(nèi)部循環(huán)中刪除分支：
  if a { for { } } else { for { } }
  代替
  for { if a { } else { } }

  避免

  if i % 2 == 0 {
  evens++
  } else {
  odds++
  }

  counts[i & 1] ++并不總是更快，但通常更難以閱讀
  TODO：ASCII類計數(shù)示例和基準

• 排序數(shù)據(jù)可以通過緩存局部性和分支預測來幫助提高性能，即使考慮到排序所花費的時間

• 函數(shù)調(diào)用開銷

• 關(guān)于Jeff Dean的2002年數(shù)字(加上更新)的評論

  • cpus變得更快了，但是內(nèi)存沒有跟上

并發(fā)

• 找出哪些部分可以并行完成，哪部分必須是順序的
• goroutines很便宜，但不免費。
• 優(yōu)化多線程代碼
  • 共享false -> 填充緩存行大小
  • 共享true -> 分片
• 與上一節(jié)關(guān)于緩存和虛假/真實共享重疊
• 延遲同步; 它很貴，所以復制工作可能會更便宜
• 你可以控制的東西：worker的數(shù)量，批量大小

你需要一個互斥體來保護共享的可變狀態(tài)。如果你有很多的互斥量爭用，你需要減少共享，或者減少mutable。減少共享的兩種方法是1）分割鎖或2）獨立處理，然后合并。為了減少mutable：好吧，讓你的數(shù)據(jù)結(jié)構(gòu)是只讀的。你還可以通過減少關(guān)鍵部分來縮短數(shù)據(jù)共享的時間 - 盡可能少地鎖定鎖定。有時候RWMutex就足夠了，但是請注意，它們比較慢，但是它們允許多個讀者進入。

如果你正在分解鎖，請注意共享緩存行。您需要填充以避免緩存行擁有權(quán)在處理器之間彈跳。

var stripe [8]struct{ sync.Mutex; _ [7]uint64 } //互斥量為64位; 填充填充緩存行的其余部分

部件

• 關(guān)于為Go編寫匯編代碼
• 編譯器改進; bar很高
• 盡可能少地替換以產(chǎn)生影響
• 很好的理由：SIMD指令或者Go和編譯器可以提供的其他東西
• 非常重要的基準:改進可能是巨大的(高速公路的10倍)零(小點)，或甚至更慢(不內(nèi)聯(lián))
• 用新版本重新標記以查看是否可以刪除代碼
• TODO：鏈接到1.11補丁刪除匯編代碼
• 總是有純粹的Go版本(noasm build tag):測試，arm，gccgo
• 簡要介紹語法
• 調(diào)用的約定
• 使用不受asm支持的操作碼
• 關(guān)于為什么內(nèi)聯(lián)很難
• 使這更容易工具:asmfmt，peachpy，c2goasm，...

優(yōu)化整個服務

大多數(shù)情況下，你不會看到一個CPU限制的例程。這是一個簡單的例子。如果你有優(yōu)化服務，則需要查看整個系統(tǒng)。監(jiān)測。指標。隨著時間的推移記錄很多事情，這樣你可以看到它們變得更糟，所以你可以看到你的更改對生產(chǎn)的影響。

tip.golang.org/doc/diagnostics.html

• 系統(tǒng)設(shè)計參考:SRE Book，實用的分布式系統(tǒng)設(shè)計
• 額外的工具:更多日志記錄+分析
• 兩條基本規(guī)則:加速緩慢的事情或減少頻率。
• 分布式跟蹤以追蹤更高級別的瓶頸
• 用于查詢單個服務器而不是批量查詢模式
• 你的性能問題可能不是你的代碼，但是你仍然需要解決它們

附錄:實施研究論文

實施論文的提示:( algorithm另請參閱data structure）

• 別。從明顯的解決方案和合理的數(shù)據(jù)結(jié)構(gòu)開始。
  “現(xiàn)代”算法往往具有較低的理論復雜性，但具有較高的常數(shù)因子和很多實施復雜性。其中一個經(jīng)典例子是斐波那契堆。他們很難得到正確的，并有一個巨大的不變因素。已經(jīng)發(fā)表了多篇論文，比較了不同工作負載下堆的實現(xiàn)方式，總體而言，4或8元的隱含堆總是排在前列。即使在Fibonacci堆應該更快（由于O（1）“減少鍵”）的情況下，使用Dijkstra的深度優(yōu)先搜索算法的實驗表明，當他們使用直接堆去除和加法時，它的速度更快。

類似地，對比更復雜的紅黑或AVL樹也可以找到對照或者跳過列表。在現(xiàn)代硬件上，“較慢”的算法可能足夠快，甚至更快。

最快的算法經(jīng)常可以被幾乎一樣快速且容易理解的算法取代。

道格拉斯W.瓊斯，愛荷華大學

增加的復雜性必須足以使得回報實際上值得。另一個例子是緩存驅(qū)逐算法。不同的算法可以具有高得多的復雜度，僅命中率的小改進。當然，您可能無法在測試之前進行測試，直到您有一個可行的實施并將其整合到您的程序中。

有時候這篇論文會有圖表，但很像只發(fā)布正面結(jié)果的趨勢，但這些傾向往往會偏向于表示新算法的優(yōu)點。

• 選擇正確的紙張。
• 尋找他們的算法聲稱擊敗和實施的論文。

通常，早期的論文會更容易理解，并且必須具有更簡單的算法。

并非所有的文件都很好。

查看論文寫入的上下文。確定有關(guān)硬件的假設(shè)：磁盤空間，內(nèi)存使用情況等。一些較舊的論文在70年代或80年代進行了合理的不同折衷，但不一定適用于您的使用案例。例如，他們認為什么是“合理的”內(nèi)存與磁盤使用的權(quán)衡。內(nèi)存大小現(xiàn)在增加了數(shù)量級，并且SSD改變了使用磁盤的延遲懲罰。同樣，一些流媒體算法是為路由器硬件而設(shè)計的，這可能會使轉(zhuǎn)換成軟件變得非常痛苦。

確保算法對數(shù)據(jù)保持的假設(shè)。

這將需要一些挖掘。你可能不想實現(xiàn)你找到的第一篇論文。

• 確保你了解算法。這聽起來很明顯，但是否則無法進行調(diào)試。
  https://blizzard.cs.uwaterloo.ca/keshav/home/Papers/data/07/paper-reading.pdf
  一個良好的理解可能會讓你從論文中提取關(guān)鍵的想法，并且可能將這個想法應用于你的問題，這可能比重新實現(xiàn)整個事情更簡單。
• 數(shù)據(jù)結(jié)構(gòu)或算法的原始文件并不總是最好的。后來的論文可能會有更好的解釋。
• 一些論文發(fā)布了可以與之比較的參考源代碼，但是
  1. 學術(shù)代碼幾乎普遍可怕
  2. 謹防許可限制（僅限“研究目的”）
  3. 提防錯誤; 邊緣情況，錯誤檢查，性能等。

還要注意GitHub上的其他實現(xiàn)：它們可能與您的bug相同（或不同）。

有關(guān)此主題的其他資源：

• https://www.youtube.com/watch?v=8eRx5Wo3xYA
• http://codecapsule.com/2012/01/18/how-to-implement-a-paper/

image