這是 go-perfbook 翻譯的第一部分，這本書(shū)雖然沒(méi)有寫(xiě)完，但里面的內(nèi)容還是很有價(jià)值的，建議每一個(gè) gopher 都看一看~

編寫(xiě)與優(yōu)化 Go 代碼

本文檔概述了編寫(xiě)高性能 Go 代碼的最佳實(shí)踐。

雖然會(huì)有一些使用緩存來(lái)提升服務(wù)速度的案例，但設(shè)計(jì)高性能的分布式系統(tǒng)超出了本文的范圍。因?yàn)樵诒O(jiān)控和分布式系統(tǒng)設(shè)計(jì)方面已經(jīng)有了足夠多的優(yōu)秀材料，且優(yōu)化分布式系統(tǒng)是完全不同的一系列的研究與設(shè)計(jì)權(quán)衡。所以本書(shū)內(nèi)容主要還是聚集在單一服務(wù)層面。

這本書(shū)被分成了不同的小節(jié):

1. 編寫(xiě)不太慢的軟件的 tips
• 入門(mén)級(jí)計(jì)算機(jī)知識(shí)
2. 編寫(xiě)快速的軟件的 tips
• 優(yōu)化時(shí)需要了解的 Go 特性
3. 編寫(xiě)真正快速的軟件的進(jìn)階 tips
• 當(dāng)你優(yōu)化后的代碼還是不夠快時(shí)怎么辦

何時(shí)何地進(jìn)行優(yōu)化

這個(gè)放在第一位，因?yàn)槭亲钪匾囊徊?。先要確定到底應(yīng)不應(yīng)該優(yōu)化。

優(yōu)化都是有成本的。這種成本是以代碼復(fù)雜度或認(rèn)知負(fù)擔(dān)呈現(xiàn)的 -- 優(yōu)化后的代碼一般都比原來(lái)的版本要更難理解。

但優(yōu)化往往能帶來(lái)經(jīng)濟(jì)效益。作為一個(gè)程序員，時(shí)間寶貴。對(duì)于你來(lái)說(shuō)，優(yōu)化也是個(gè)機(jī)會(huì)成本的問(wèn)題。因?yàn)榭赡苓€有項(xiàng)目等著你去做，有 bug 等著你去修，有特性等著你去開(kāi)發(fā)。盡管優(yōu)化很有意思，但并不一定是當(dāng)前最應(yīng)該做的事情。性能是重要的產(chǎn)品特性，但及時(shí)地發(fā)布和正確的軟件也是應(yīng)該做到的。

有時(shí) CPU 優(yōu)化相比用戶(hù)體驗(yàn)優(yōu)化優(yōu)先級(jí)沒(méi)那么高，你應(yīng)該選擇最重要的事情。可能只是增加一個(gè)簡(jiǎn)單的進(jìn)度條，或者讓頁(yè)面不要在進(jìn)行計(jì)算的時(shí)候直接卡住。

這在我們的工作中顯而易見(jiàn)：三小時(shí)做的報(bào)告有時(shí)可能還不如我們幾十分鐘做的更有用。

一個(gè)問(wèn)題很容易優(yōu)化，并不代表這個(gè)問(wèn)題就值得優(yōu)化。忽略當(dāng)下不重要的問(wèn)題，也是軟件開(kāi)發(fā)的大智慧。

可以把上面的想法當(dāng)成是在優(yōu)化你的時(shí)間。

你需要選擇優(yōu)化的對(duì)象和時(shí)機(jī)。你可以按照實(shí)際情況將優(yōu)先級(jí)在“快速的軟件”和“快速的部署”之間來(lái)回切換。

人們經(jīng)常聽(tīng)別人說(shuō)，并且自己可能也會(huì)無(wú)意識(shí)地重復(fù)“提前優(yōu)化是萬(wàn)惡之源”，但他們忽略了這幾話的上下文。

程序員浪費(fèi)了大量的時(shí)間來(lái)考慮或擔(dān)心他們程序中非關(guān)鍵部分的速度，這些提高效率的嘗試在考慮到調(diào)試和維護(hù)的時(shí)候，實(shí)際上產(chǎn)生了很大的負(fù)面影響。我們得忽略那些不關(guān)鍵的效率提升，也就是說(shuō) 97% 的時(shí)候我們要說(shuō)：過(guò)早的優(yōu)化是萬(wàn)惡之源。同時(shí)也不放棄那關(guān)鍵的 3% 的機(jī)會(huì)。-- Knuth

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

• 也不要看不起簡(jiǎn)單的優(yōu)化
• 對(duì)數(shù)據(jù)結(jié)構(gòu)和算法有更多了解，會(huì)使更多的優(yōu)化變的“簡(jiǎn)單”且“顯而易見(jiàn)

你應(yīng)該優(yōu)化么？

是的，只有當(dāng)優(yōu)化問(wèn)題是非常重要的，這個(gè)程序確實(shí)非常慢，并且用戶(hù)除了對(duì)程序的正確，穩(wěn)定和清晰以外，也有對(duì)速度的期望時(shí)。-- The Practice of Programming, Kernighan and Pike

過(guò)早的優(yōu)化也會(huì)傷害你，把你綁在某些決定上。如果需求發(fā)生變化，優(yōu)化后的代碼會(huì)更難修改，也更難丟棄（沉沒(méi)成本謬論）。

BitFunnel性能估計(jì)[1]有一些數(shù)字使這種權(quán)衡變得明確。想象一下，一個(gè)假想的搜索引擎需要在多個(gè)數(shù)據(jù)中心使用 30,000 臺(tái)機(jī)器。這些機(jī)器每臺(tái)成本約為 1,000 美元。如果你能把軟件的速度提高一倍，這可以為公司每年節(jié)省 1500 萬(wàn)美元。即使是一個(gè)開(kāi)發(fā)人員花一整年的時(shí)間來(lái)提高性能，只需 1% 就可以得到回報(bào)。

在絕大多數(shù)情況下，程序的大小和速度并不是一個(gè)問(wèn)題。最簡(jiǎn)單的優(yōu)化是不需要這樣做。第二簡(jiǎn)單的優(yōu)化就是購(gòu)買(mǎi)更快的硬件。

一旦你決定要修改你的程序，請(qǐng)繼續(xù)閱讀。

如何優(yōu)化

優(yōu)化工作流

在我們討論具體問(wèn)題之前，讓我們先談?wù)剝?yōu)化的一般過(guò)程。

優(yōu)化是重構(gòu)的一種形式。只不過(guò)這種重構(gòu)過(guò)程不是出于改善源代碼的代碼重復(fù)或清晰這些方面，而是為了改善性能：降低 CPU、內(nèi)存使用、延遲等。這種改進(jìn)通常是以可讀性為代價(jià)的。這意味著，除了一套完整且全面的單元測(cè)試（以確保你的改動(dòng)沒(méi)有破壞任何邏輯），還需要一套好的基準(zhǔn)測(cè)試，以確保改動(dòng)對(duì)性能產(chǎn)生預(yù)期的影響。必須能夠驗(yàn)證代碼修改是否真的降低了CPU。有時(shí)候，你認(rèn)為會(huì)提高性能的改變實(shí)際上會(huì)變成零或負(fù)的改變。在這種情況下，一定要記得撤消你的修改。

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
//

你所使用的基準(zhǔn)必須是正確的，并在有代表性的工作負(fù)載上提供可重復(fù)的數(shù)字。如果單個(gè)運(yùn)行的差異太大，會(huì)使小的改進(jìn)更難發(fā)現(xiàn)。需要使用benchstat[3]或同類(lèi)的統(tǒng)計(jì)測(cè)試工具，而不能只靠單次或者肉眼對(duì)比。(注意，無(wú)論如何，使用統(tǒng)計(jì)測(cè)試是一個(gè)好主意。）運(yùn)行基準(zhǔn)的步驟應(yīng)該被記錄下來(lái)，任何定制的腳本和工具都應(yīng)該被提交到代碼倉(cāng)庫(kù)里，并說(shuō)明如何運(yùn)行它們。要注意運(yùn)行時(shí)間較長(zhǎng)的大型基準(zhǔn)套件：這會(huì)使你的開(kāi)發(fā)迭代被拖累速度。

還要注意，任何可以測(cè)量的指標(biāo)都可以被優(yōu)化。請(qǐng)確保你使用的是正確的指標(biāo)。

下一步是決定你的優(yōu)化目標(biāo)是什么。如果目標(biāo)是提高 CPU 使用效率，什么是可接受的速度？你想把當(dāng)前的性能提高 2 倍？10 倍? 你能把它表述為 "在少于時(shí)間 T 的情況下解決一個(gè)大小為 N 的問(wèn)題 "嗎？你是想減少內(nèi)存的使用嗎？減少多少？慢多少是可以接受的？你愿意放棄什么來(lái)?yè)Q取更低的空間需求？

對(duì)服務(wù)延遲的優(yōu)化是一個(gè)更棘手的問(wèn)題。關(guān)于如何測(cè)試網(wǎng)絡(luò)服務(wù)器的書(shū)已經(jīng)寫(xiě)了一整本。主要的問(wèn)題是，對(duì)于一個(gè)單一的功能，在給定的問(wèn)題規(guī)模下，性能是相當(dāng)一致的。對(duì)于網(wǎng)絡(luò)服務(wù)，無(wú)法用單一的數(shù)字表示性能。一個(gè)靠譜的網(wǎng)絡(luò)服務(wù)基準(zhǔn)測(cè)試套件將為給定的 reqs/second 壓力提供延遲分布結(jié)果。這個(gè)講座對(duì)一些問(wèn)題做了很好的概述。[Gil Tene的"如何不測(cè)量延遲"](https://youtu.be/lJ8ydIuPFeU "Gil Tene的 "如何不測(cè)量延遲"")

性能目標(biāo)必須具體，你一定能夠使一些東西更快。但優(yōu)化經(jīng)常是一個(gè)收益遞減的游戲，要知道何時(shí)應(yīng)該停止。你打算投入多少精力來(lái)完成最后一點(diǎn)工作。你愿意讓代碼變得多難看、多難維護(hù)？

Dan Luu之前提到的關(guān)于[BitFunnel性能估計(jì)]的講座（http://bitfunnel.org/strangeloop）展示了一個(gè)使用粗略計(jì)算來(lái)確定你的目標(biāo)性能數(shù)字是否合理的例子。

Simon Eskildsen在SRECon的演講中更深入地闡述了這個(gè)話題。高級(jí)餐巾紙數(shù)學(xué)：從第一原理估算系統(tǒng)性能[4]

最后，Jon Bentley 的 "Programming Pearls" 中有一章題為 "The Back of the Envelope"，涉及費(fèi)米問(wèn)題?？杀氖?，由于在 20 世紀(jì) 90 年代和 21 世紀(jì)初微軟式的"智力面試題"中使用了這些估計(jì)技能，這些技能給人的印象很差。

對(duì)于零起點(diǎn)開(kāi)發(fā)，不應(yīng)該把基準(zhǔn)測(cè)試留到最后再搞。盡管說(shuō)"我們以后再解決"很容易，但如果性能真的很重要，一開(kāi)始設(shè)計(jì)階段就應(yīng)該納入考量。在臨近收工時(shí)發(fā)現(xiàn)性能問(wèn)題而需要架構(gòu)大改，會(huì)給項(xiàng)目帶來(lái)巨大的風(fēng)險(xiǎn)。請(qǐng)注意，在開(kāi)發(fā)過(guò)程中，重點(diǎn)應(yīng)該放在合理的程序設(shè)計(jì)、算法和數(shù)據(jù)結(jié)構(gòu)上。不過(guò)較底層的技術(shù)棧的優(yōu)化可以放到項(xiàng)目研發(fā)的后期再做，對(duì)系統(tǒng)性能有了全面了解之后再去做更合適。當(dāng)系統(tǒng)還不完整時(shí)，難以得到正確的全局性能視角。

"過(guò)早的劣化是指當(dāng)你寫(xiě)的代碼比它需要的速度慢時(shí)，通常是在進(jìn)行不必要的額外工作，而同等復(fù)雜的代碼會(huì)更快，而且應(yīng)該自然而然地從你的手指中流出來(lái)。"

-- Herb Sutter

在 CI 過(guò)程中進(jìn)行基準(zhǔn)測(cè)試是比較難的，因?yàn)?CI 過(guò)程往往是混部的，這時(shí)候你得和同一臺(tái)機(jī)器上的其它 CI 任務(wù)一起跑，所以 CI 結(jié)果會(huì)受其它任務(wù)影響，難以獲得準(zhǔn)確的指標(biāo)。一個(gè)折衷是由開(kāi)發(fā)人員在特定的硬件上自己跑 benchmark，并在 commit message 中將性能的變化數(shù)據(jù)附帶上。如果是普通的功能性的 patch，就需要用肉眼在 code review 過(guò)程中捕捉性能衰退情況了。

在大型系統(tǒng)上一般使用 profiling 采樣，局部的獨(dú)立組件寫(xiě)的則是 benchmark。你需要能在性能測(cè)試時(shí)，啟動(dòng)合理的上下文環(huán)境來(lái)模擬真實(shí)的情況。

當(dāng)前系統(tǒng)的性能和你的目標(biāo)性能之間存在哪些差異，在找到差異之后，就知道該從哪里著手進(jìn)行優(yōu)化了，如果你只需要 10%~20% 的性能提升，可以通過(guò)一些實(shí)現(xiàn)的調(diào)整和較小的修復(fù)來(lái)達(dá)到目標(biāo)。如果需要 10 倍這樣的系數(shù)，那么只是用左移來(lái)替代乘法運(yùn)算顯然是不可能的。這需要你對(duì)代碼進(jìn)行反復(fù)分析，甚至需要為了這個(gè)性能目標(biāo)把大部分模塊推翻重做。

性能優(yōu)化需要了解不同層次的知識(shí)，從系統(tǒng)設(shè)計(jì)、網(wǎng)絡(luò)、硬件(CPU、緩存、存儲(chǔ))、算法、調(diào)整和調(diào)試。在時(shí)間和資源有限的情況下，要考慮哪個(gè)層面帶來(lái)的改進(jìn)最大，這個(gè)并不一定總是在調(diào)整算法和程序、

通常，優(yōu)化應(yīng)該是自頂向下的。系統(tǒng)級(jí)的優(yōu)化肯定比表達(dá)式級(jí)的優(yōu)化效果要好。你應(yīng)該確定自己是在合適的層級(jí)解決性能問(wèn)題。

這本書(shū)大部分是討論減少 CPU 的使用，減少內(nèi)存使用和減少延遲。需要指出的是，這三者比較難兼得?？赡?CPU 使用率低了，但內(nèi)存占用上升了?？赡軆?nèi)存使用下降了，但程序計(jì)算要花的時(shí)間更長(zhǎng)了。

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

進(jìn)行算法優(yōu)化也可以減少 CPU 占用，比如你用 quicksort，肯定比冒泡排序快，因?yàn)樗酶俚牟襟E就可以解決同樣的問(wèn)題。

程序調(diào)整，就像編譯器優(yōu)化一樣，通常只會(huì)對(duì)總的運(yùn)行時(shí)間產(chǎn)生小的影響。大幅性能提升幾乎總是來(lái)自于算法的改變或數(shù)據(jù)結(jié)構(gòu)的改變，是你的程序組織方式的根本轉(zhuǎn)變。編譯器技術(shù)的改進(jìn)是緩慢的。Proebsting's Law[6]說(shuō)，編譯器的性能每18年翻一番，這與摩爾定律的（稍有誤解的解釋?zhuān)┬纬甚r明對(duì)比，摩爾定律是每18月將處理器性能翻一番。算法的改進(jìn)對(duì)程序的改進(jìn)更為顯著。

混合整數(shù)規(guī)劃算法在1991年和2008年之間改進(jìn)了30,000倍[7]。對(duì)于一個(gè)更具體的例子，考慮一下這個(gè)分解[8]，將 Uber blog 中描述的蠻力地理空間算法替換為更適合所提出的任務(wù)的更特化的算法。沒(méi)有任何編譯器開(kāi)關(guān)可以給你帶來(lái)同等的性能提升。

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

三個(gè)優(yōu)化問(wèn)題。

• 我們有必要這樣做嗎？最快的代碼是從未運(yùn)行過(guò)的代碼。
• 如果是的話，這是不是最好的算法。
• 如果是的話，這是不是這個(gè)算法的最佳實(shí)現(xiàn)。

具體優(yōu)化手段

喬恩-本特利（Jon Bentley）1982年的作品《編寫(xiě)高效程序》（Writing Efficient Programs）將程序優(yōu)化作為工程問(wèn)題來(lái)研究：基準(zhǔn)測(cè)試，分析，改進(jìn)，驗(yàn)證，迭代。他的許多建議現(xiàn)在都由編譯器自動(dòng)完成。程序員的工作是使用編譯器不能自動(dòng)進(jìn)行的那個(gè)轉(zhuǎn)換優(yōu)化。

書(shū)中有總結(jié)：

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

程序的 tuning 規(guī)則：

• https://web.archive.org/web/20080513070949/http://www.cs.bell-labs.com/cm/cs/pearls/apprules.html

當(dāng)對(duì)程序進(jìn)行修改時(shí)，一般有兩個(gè)選項(xiàng)：

• 要么對(duì)數(shù)據(jù)做修改，要么對(duì)代碼做修改

數(shù)據(jù)修改

改變你的數(shù)據(jù)意味著修改你的業(yè)務(wù)數(shù)據(jù)字段。從性能的角度來(lái)看，這些修改會(huì)影響后后續(xù)業(yè)務(wù)邏輯處理數(shù)據(jù)的時(shí)間復(fù)雜度。這個(gè)過(guò)程可能包含對(duì)你的數(shù)據(jù)提前進(jìn)行一些預(yù)處理，以降低后續(xù)的數(shù)據(jù)處理負(fù)擔(dān)。

擴(kuò)充你的數(shù)據(jù)結(jié)構(gòu)的一些可能的做法：

• 冗余字段

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

  類(lèi)似地，存儲(chǔ)指向經(jīng)常訪問(wèn)的節(jié)點(diǎn)的指針，而不是執(zhí)行額外的搜索。這涵蓋了像雙鏈接列表中的 "next" 鏈接，以使節(jié)點(diǎn)移除變成 O(1) 時(shí)間復(fù)雜度。一些跳表(skiplist)保留了一個(gè)"search finger"，在這個(gè)位置保存了你上一次查詢(xún)到的位置。這種優(yōu)化是假設(shè)了下次查詢(xún)從這個(gè)位置開(kāi)始更好。

• 冗余的搜索索引

  大多數(shù)數(shù)據(jù)結(jié)構(gòu)都是為單一類(lèi)型的查詢(xún)而設(shè)計(jì)的。如果你需要兩種不同的查詢(xún)類(lèi)型，在你的數(shù)據(jù)上有一個(gè)額外的 "視圖" 可能就有很大的改進(jìn)。例如，一個(gè)數(shù)據(jù)結(jié)構(gòu)數(shù)組可能有一個(gè)主鍵 ID（整數(shù)），可以被用來(lái)在切片中查詢(xún)，但還需要用一個(gè)次要的 ID（字符串）來(lái)查詢(xún)。你可以用一個(gè)從字符串到 ID 或直接到結(jié)構(gòu)本身的映射來(lái)增強(qiáng)你的數(shù)據(jù)結(jié)構(gòu)，而不是在切片上進(jìn)行迭代。

• 額外的元素信息

  例如，保留一個(gè)你已經(jīng)插入的所有元素的 Bloomfilter 可以讓你快速返回查詢(xún) "不匹配"。bloomfilter 的設(shè)計(jì)應(yīng)該是“小而快”，不要超過(guò)你主要的數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)成本。(如果主數(shù)據(jù)結(jié)構(gòu)中的查找成本較低，bloomfilter 的維護(hù)成本可能超過(guò)這個(gè)查詢(xún)成本)。

• 如果查詢(xún)成本很高，增加 cache 層

  在應(yīng)用層，增加進(jìn)程內(nèi)、進(jìn)程外(如 memcache) 緩存對(duì)提升查詢(xún)效率有很大幫助。對(duì)于單個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)說(shuō)可能這樣可能有點(diǎn)夸張，下面會(huì)詳細(xì)講講緩存。

當(dāng)你需要的數(shù)據(jù)存儲(chǔ)成本低且容易保持更新時(shí)，這類(lèi)優(yōu)化就很有用。

這些都是在數(shù)據(jù)結(jié)構(gòu)層面上 "少做工作" 的明顯例子。它們都要花費(fèi)空間。大多數(shù)時(shí)候，如果你對(duì) CPU 進(jìn)行優(yōu)化，你的程序會(huì)使用更多的內(nèi)存。這就是典型的[時(shí)空權(quán)衡]（https://en.wikipedia.org/wiki/Space%E2%80%93time_tradeoff）。

研究這種權(quán)衡如何影響你的解決方案是很重要的--它并不總是簡(jiǎn)單明了的。有時(shí)少量的內(nèi)存可以帶來(lái)顯著的速度，有時(shí)權(quán)衡是線性的（2 倍的內(nèi)存使用量==2 倍的性能加速），有時(shí)沒(méi)那么明顯：大量的內(nèi)存只帶來(lái)很小的速度提升。你需要在這條內(nèi)存/性能曲線上的達(dá)到什么位置，會(huì)影響到你需要選擇哪些算法。并不總是能簡(jiǎn)單地調(diào)調(diào)算法參數(shù)，有時(shí)不同的內(nèi)存使用目標(biāo)可能需要完全不一樣的算法實(shí)現(xiàn)。

查表法(lookup tables)也是一種空間換時(shí)間的折衷。表就是我們復(fù)雜計(jì)算過(guò)程計(jì)算出的結(jié)果的一種緩存。

如果域足夠小，那么全部結(jié)果都可以預(yù)先計(jì)算出來(lái)并存儲(chǔ)在表中。popcount 是這種模式的一個(gè)很好的例子，其中字節(jié)中的設(shè)置位數(shù)被存儲(chǔ)在一個(gè) 256 個(gè)條目的表中。一個(gè)更大的表可以存儲(chǔ)所有 16 位字所需的比特。在這種情況下，他們存儲(chǔ)的是精確的結(jié)果。

一些三角函數(shù)的算法使用查表作為計(jì)算的起點(diǎn)。

如果你的程序使用了太多的內(nèi)存，也可以走另一條路。通過(guò)消耗更多 CPU 減少內(nèi)存空間的使用。與其存儲(chǔ)內(nèi)容，不如每次都計(jì)算它們?？梢栽趦?nèi)存中存放壓縮后的數(shù)據(jù)，并在需要時(shí)實(shí)時(shí)解壓。

如果你要處理的數(shù)據(jù)在磁盤(pán)上，你可以為你需要的數(shù)據(jù)創(chuàng)建索引，并只在內(nèi)存中存儲(chǔ)索引，而不是全量數(shù)據(jù)，也可以將文件拆分成一個(gè)一個(gè)的 chunk。

小內(nèi)存軟件[9]是一本可在網(wǎng)上獲得的書(shū)，涵蓋了減少程序所使用的空間的技術(shù)。雖然這本書(shū)最初是針對(duì)嵌入式開(kāi)發(fā)人員編寫(xiě)的，但其思想也適用于現(xiàn)代硬件上處理大量數(shù)據(jù)的程序。

• 重新排列你的數(shù)據(jù)

  消除結(jié)構(gòu)填充。刪除多余的字段。使用一個(gè)較小的數(shù)據(jù)類(lèi)型。

• 改為較慢的數(shù)據(jù)結(jié)構(gòu)

  簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)經(jīng)常有較低的內(nèi)存要求。例如，從一個(gè)指針很多的樹(shù)形結(jié)構(gòu)轉(zhuǎn)為使用切片和線性搜索。

• 為你的數(shù)據(jù)定制壓縮格式

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

  數(shù)據(jù)是否可以壓縮？隨機(jī)訪問(wèn)還是流式訪問(wèn)？如果你需要訪問(wèn)單個(gè)條目，但又不想解壓整個(gè)條目，你可以把數(shù)據(jù)壓縮成較小的塊，并保留一個(gè)索引，表明每個(gè)塊中的條目范圍。對(duì)單個(gè)條目的訪問(wèn)只需要檢查索引和解壓較小的數(shù)據(jù)塊。

  如果你的數(shù)據(jù)不只是處理過(guò)程的數(shù)據(jù)，會(huì)被寫(xiě)入磁盤(pán)，那么數(shù)據(jù)遷移或添加/刪除字段怎么辦。你現(xiàn)在要處理的是原始的 []byte，而不是漂亮的結(jié)構(gòu)化 Go 類(lèi)型，所以你需要考慮 unsafe 的序列化選項(xiàng)。

后面會(huì)更詳細(xì)地討論數(shù)據(jù)布局。

現(xiàn)代計(jì)算機(jī)和內(nèi)存分層使空間/時(shí)間的權(quán)衡變得不那么清晰。查表算法中的表很容易在內(nèi)存中離代碼較遠(yuǎn)（因此訪問(wèn)成本很高），這可能還不如重新計(jì)算一次值更快。

這也意味著基準(zhǔn)測(cè)試中看起來(lái)有改進(jìn)的代碼會(huì)經(jīng)常由于緩存爭(zhēng)用而在生產(chǎn)系統(tǒng)中沒(méi)有改進(jìn)（例如，在基準(zhǔn)測(cè)試中查找表在處理器緩存中，但在實(shí)際系統(tǒng)中使用時(shí)總是 "新數(shù)據(jù) "刷新緩存。) Google的Jump Hash論文[10]實(shí)際上直接解決了這個(gè)問(wèn)題，比較了有競(jìng)爭(zhēng)和無(wú)競(jìng)爭(zhēng)的處理器高速緩存的性能。(參見(jiàn)Jump Hash論文中的圖表4和5)

sync.Map 是 Go 語(yǔ)言中針對(duì) cache-contention 場(chǎng)景的解決方案。

另一個(gè)需要考慮的方面是數(shù)據(jù)傳輸時(shí)間。一般來(lái)說(shuō)，網(wǎng)絡(luò)和磁盤(pán)訪問(wèn)是非常緩慢的，因此能夠加載一個(gè)壓縮塊然后解壓也比直接從磁盤(pán)上加載完整未壓縮的內(nèi)容消耗的 CPU 少得多。同樣與往常一樣，要有基準(zhǔn)。二進(jìn)制格式通常會(huì)比文本格式更小，解析速度更快，但代價(jià)是可讀性降低。

對(duì)于數(shù)據(jù)傳輸來(lái)說(shuō)，可以轉(zhuǎn)向不那么冗余的協(xié)議，或者增強(qiáng) API 以允許局部查詢(xún)。例如，可以將 API 實(shí)現(xiàn)為增量查詢(xún)，而不是每次都被迫獲取整個(gè)數(shù)據(jù)集。

歡迎關(guān)注 TechPaper 和碼農(nóng)桃花源