原文

動(dòng)機(jī)

TCMalloc要比glibc 2.3的malloc（可以從一個(gè)叫作ptmalloc2的獨(dú)立庫(kù)獲得）和其他我測(cè)試過(guò)的malloc都快。ptmalloc在一臺(tái)2.8GHz的P4機(jī)器上（對(duì)于小對(duì)象）執(zhí)行一次malloc及free大約需要300納秒。而TCMalloc的版本同樣的操作大約只需要50納秒。malloc版本的速度是至關(guān)重要的，因?yàn)槿绻?code style="PADDING-BOTTOM: 0px; MARGIN: 1.5em 0px; PADDING-LEFT: 0px; PADDING-RIGHT: 0px; FONT: 1em 'andale mono', 'monotype.com', 'lucida console', monospace; WHITE-SPACE: pre; PADDING-TOP: 0px">malloc不夠快，應(yīng)用程序的作者就很有可能在malloc之上寫(xiě)一個(gè)自己的自由列表。這就可能導(dǎo)致額外的代碼復(fù)雜度，以及更多的內(nèi)存占用――除非作者本身非常仔細(xì)地劃分自由列表的大小并經(jīng)常從自由列表中清除空閑的對(duì)象。

TCMalloc也減少了多線程程序中的鎖爭(zhēng)用情況。對(duì)于小對(duì)象，幾乎已經(jīng)達(dá)到了零爭(zhēng)用。對(duì)于大對(duì)象，TCMalloc嘗試使用粒度較好和有效的自旋鎖。ptmalloc同樣是通過(guò)使用每線程各自的場(chǎng)地來(lái)減少鎖爭(zhēng)用，但是ptmalloc2使用每線程場(chǎng)地有一個(gè)很大的問(wèn)題。在ptmalloc2中，內(nèi)存可能會(huì)從一個(gè)場(chǎng)地移動(dòng)到另一個(gè)。這有可能導(dǎo)致大量空間被浪費(fèi)。例如，在一個(gè)Google的應(yīng)用中，第一階段可能會(huì)為其URL標(biāo)準(zhǔn)化的數(shù)據(jù)結(jié)構(gòu)分配大約300MB內(nèi)存。當(dāng)?shù)谝浑A段結(jié)束后，第二階段將從同樣的地址空間開(kāi)始。如果第二個(gè)階段被安排到了一個(gè)與第一階段什?用的場(chǎng)地不同的場(chǎng)地，這個(gè)階段不會(huì)復(fù)用任何第一階段留下的的內(nèi)存，并會(huì)給地址空間添加另外一個(gè)300MB。類(lèi)似的內(nèi)存爆炸問(wèn)題也可以在其他的應(yīng)用中看到。

TCMalloc的另一個(gè)好處是小對(duì)象的空間最優(yōu)表現(xiàn)形式。例如，分配N(xiāo)個(gè)8字節(jié)對(duì)象可能要使用大約8N * 1.01字節(jié)的空間。即，多用百分之一的空間。而ptmalloc2中每個(gè)對(duì)象都使用了一個(gè)四字節(jié)的頭，（我認(rèn)為）并將最終的尺寸規(guī)整為8字節(jié)的倍數(shù)，最后使用了16N字節(jié)。

使用

要使用TCMalloc，只要將tcmalloc通過(guò)“-ltcmalloc”鏈接器標(biāo)志接入你的應(yīng)用即可。

你也可以通過(guò)使用LD_PRELOAD在不是你自己編譯的應(yīng)用中使用tcmalloc：

   $ LD_PRELOAD="/usr/lib/libtcmalloc.so"

LD_PRELOAD比較討巧，我們也不十分推薦這種用法。

TCMalloc還包含了一個(gè)堆檢查器以及一個(gè)堆測(cè)量器。

如果你更想鏈接不包含堆測(cè)量器和檢查器的TCMalloc版本（比如可能為了減少靜態(tài)二進(jìn)制文件的大小），你可以接入libtcmalloc_minimal。

概覽

TCMalloc給每個(gè)線程分配了一個(gè)線程局部緩存。小分配可以直接由線程局部緩存來(lái)滿(mǎn)足。需要的話，會(huì)將對(duì)象從中央數(shù)據(jù)結(jié)構(gòu)移動(dòng)到線程局部緩存中，同時(shí)定期的垃圾收集將用于把內(nèi)存從線程局部緩存遷移回中央數(shù)據(jù)結(jié)構(gòu)中。

TCMalloc將尺寸小于<=
32K的對(duì)象（“小”對(duì)象）和大對(duì)象區(qū)分開(kāi)來(lái)。大對(duì)象直接使用頁(yè)級(jí)分配器（一個(gè)頁(yè)是一個(gè)4K的對(duì)齊內(nèi)存區(qū)域）從中央堆直接分配。即，一個(gè)大對(duì)象總是頁(yè)對(duì)齊的并占據(jù)了整數(shù)個(gè)數(shù)的頁(yè)。

連續(xù)的一些頁(yè)面可以被分割為一系列小對(duì)象，而他們的大小都相同。例如，一個(gè)連續(xù)的頁(yè)面（4K）可以被劃分為32個(gè)128字節(jié)的對(duì)象。

小對(duì)象的分配

每個(gè)小對(duì)象的大小都會(huì)被映射到170個(gè)可分配的尺寸類(lèi)別中的一個(gè)。例如，在分配961到1024字節(jié)時(shí)，都會(huì)歸整為1024字節(jié)。尺寸類(lèi)別這樣隔開(kāi)：較小的尺寸相差8字節(jié)，較大的尺寸相差16字節(jié)，再大一點(diǎn)的尺寸差32字節(jié)，如此類(lèi)推。最大的間隔（對(duì)于尺寸 >= ~2K的）是256字節(jié)。

一個(gè)線程緩存對(duì)每個(gè)尺寸類(lèi)都包含了一個(gè)自由對(duì)象的單向鏈表。

當(dāng)分配一個(gè)小對(duì)象時(shí)：

1. 我們將其大小映射到對(duì)應(yīng)的尺寸類(lèi)中。
2. 查找當(dāng)前線程的線程緩存中相應(yīng)的自由列表。
3. 如果自由列表不空，那么從移除列表的第一個(gè)對(duì)象并返回它。當(dāng)按照這個(gè)快速通道時(shí)，TCMalloc不會(huì)獲取任何鎖。這就可以極大提高分配的速度，因?yàn)殒i/解鎖操作在一個(gè)2.8GHz Xeon上大約需要100納秒的時(shí)間。

如果自由列表為空：

1. 從該尺寸類(lèi)別的中央自由列表（中央自由列表是被所有線程共享的）取得一連串對(duì)象。
2. 將他們放入線程局部的自由列表。
3. 將新獲取的對(duì)象中的一個(gè)返回給應(yīng)用程序。

如果中央自由列表也為空：(1) 我們從中央頁(yè)分配器分配了一連串頁(yè)面。(2) 將他們分割成該尺寸類(lèi)的一系列對(duì)象。(4) 像前面一樣，將部分對(duì)象移入線程局部的自由列表中。

大對(duì)象的分配

一個(gè)大對(duì)象的尺寸(> 32K)會(huì)被除以一個(gè)頁(yè)面尺寸（4K）并取整（大于結(jié)果的最小整數(shù)），同時(shí)是由中央頁(yè)面堆來(lái)處理的。中央頁(yè)面堆又是一個(gè)自由列表的陣列。對(duì)于i < 256而言，第k個(gè)條目是一個(gè)由k個(gè)頁(yè)面組成的自由列表。第256個(gè)條目則是一個(gè)包含了長(zhǎng)度>= 256個(gè)頁(yè)面的自由列表：

k個(gè)頁(yè)面的一次分配通過(guò)在第k個(gè)自由列表中查找來(lái)完成。如果該自由列表為空，那么我們則在下一個(gè)自由列表中查找，如此繼續(xù)。最終，如果必要的話，我們將在最后一個(gè)自由列表中查找。如果這個(gè)動(dòng)作也失敗了，我們將向系統(tǒng)獲取內(nèi)存（使用sbrk、mmap或者通過(guò)在/dev/mem中進(jìn)行映射）。

如果k個(gè)頁(yè)面的一次分配行為由連續(xù)的長(zhǎng)度> k的頁(yè)面滿(mǎn)足了，剩下的連續(xù)頁(yè)面將被重新插回到頁(yè)面堆的對(duì)應(yīng)的自由列表中。

跨度（Span）

TCMalloc管理的堆由一系列頁(yè)面組成。連續(xù)的頁(yè)面由一個(gè)“跨度”（Span）對(duì)象來(lái)表示。一個(gè)跨度可以是已被分配或者是自由的。如果是自由的，跨度則會(huì)是一個(gè)頁(yè)面堆鏈表中的一個(gè)條目。如果已被分配，它會(huì)是一個(gè)已經(jīng)被傳遞給應(yīng)用程序的大對(duì)象，或者是一個(gè)已經(jīng)被分割成一系列小對(duì)象的一個(gè)頁(yè)面。如果是被分割成小對(duì)象的，對(duì)象的尺寸類(lèi)別會(huì)被記錄在跨度中。

由頁(yè)面號(hào)索引的中央數(shù)組可以用于找到某個(gè)頁(yè)面所屬的跨度。例如，下面的跨度a占據(jù)了2個(gè)頁(yè)面，跨度b占據(jù)了1個(gè)頁(yè)面，跨度c占據(jù)了5個(gè)頁(yè)面最后跨度d占據(jù)了3個(gè)頁(yè)面。

在一個(gè)32位的地址空間中，中央陣列由一個(gè)2層的基數(shù)樹(shù)來(lái)表示，其中根包含了32個(gè)條目，每個(gè)葉包含了 2¹⁵個(gè)條目（一個(gè)32為地址空間包含了 2²⁰個(gè) 4K 頁(yè)面，所以這里樹(shù)的第一層則是用2⁵整除2²⁰個(gè)頁(yè)面）。這就導(dǎo)致了中央陣列的初始內(nèi)存使用需要128KB空間（2¹⁵*4字節(jié)），看上去還是可以接受的。

在64位機(jī)器上，我們將使用一個(gè)3層的基數(shù)樹(shù)。

解除分配

當(dāng)一個(gè)對(duì)象被解除分配時(shí)，我們先計(jì)算他的頁(yè)面號(hào)并在中央陣列中查找對(duì)應(yīng)的跨度對(duì)象。該跨度會(huì)告訴我們?cè)搶?duì)象是大是小，如果它是小對(duì)象的話尺寸類(lèi)別是什么。如果是小對(duì)象的話，我們將其插入到當(dāng)前線程的線程緩存中對(duì)應(yīng)的自由列表中。如果線程緩存現(xiàn)在超過(guò)了某個(gè)預(yù)定的大小（默認(rèn)為2MB），我們便運(yùn)行垃圾收集器將未使用的對(duì)象從線程緩存中移入中央自由列表。

如果該對(duì)象是大對(duì)象的話，跨度會(huì)告訴我們?cè)搶?duì)象覆蓋的頁(yè)面的范圍。假設(shè)該范圍是[p,q]。我們還會(huì)查找頁(yè)面p-1和頁(yè)面q+1對(duì)應(yīng)的跨度。如果這兩個(gè)相鄰的跨度中有任何一個(gè)是自由的，我們將他們和[p,q]的跨度接合起來(lái)。最后跨度會(huì)被插入到頁(yè)面堆中合適的自由列表中。

小對(duì)象的中央自由列表

就像前面提過(guò)的一樣，我們?yōu)槊恳粋€(gè)尺寸類(lèi)別設(shè)置了一個(gè)中央自由列表。每個(gè)中央自由列表由兩層數(shù)據(jù)結(jié)構(gòu)來(lái)組成：一系列跨度和每個(gè)跨度一個(gè)自由對(duì)象的鏈表。

通過(guò)從某個(gè)跨度中移除第一個(gè)條目來(lái)從中央自由列表分配一個(gè)對(duì)象。（如果所有的跨度里只有空鏈表，那么首先從中央頁(yè)面堆中分配一個(gè)尺寸合適的跨度。）

一個(gè)對(duì)象可以通過(guò)將其添加到他包含的跨度的鏈表中來(lái)返回到中央自由列表中。如果鏈表長(zhǎng)度現(xiàn)在等于跨度中所有小對(duì)象的數(shù)量，那么該跨度就是完全自由的了，就會(huì)被返回到頁(yè)面堆中。

線程緩存的垃圾收集

某個(gè)線程緩存當(dāng)緩存中所有對(duì)象的總共大小超過(guò)2MB的時(shí)候，會(huì)對(duì)他進(jìn)行垃圾收集。垃圾收集閾值會(huì)自動(dòng)根據(jù)線程數(shù)量的增加而減少，這樣就不會(huì)因?yàn)槌绦蛴写罅烤€程而過(guò)度浪費(fèi)內(nèi)存。

我們會(huì)遍歷緩存中所有的自由列表并且將一定數(shù)量的對(duì)象從自由列表移到對(duì)于得中央列表中。

從某個(gè)自由列表中移除的對(duì)象的數(shù)量是通過(guò)使用一個(gè)每列表的低水位線L來(lái)確定的。L記錄了自上一次垃圾收集以來(lái)列表最短的長(zhǎng)度。注意，在上一次的垃圾收集中我們可能只是將列表縮短了L個(gè)對(duì)象而沒(méi)有對(duì)中央列表進(jìn)行任何額外訪問(wèn)。我們利用這個(gè)過(guò)去的歷史作為對(duì)未來(lái)訪問(wèn)的預(yù)測(cè)器并將L/2個(gè)對(duì)象從線程緩存自由列表中移到相應(yīng)的中央自由列表中。這個(gè)算法有個(gè)很好的特性是，如果某個(gè)線程不再使用某個(gè)特定的尺寸時(shí)，該尺寸的所有對(duì)象都會(huì)很快從線程緩存被移到中央自由列表，然后可以被其他緩存利用。

性能備注

PTMalloc2單元測(cè)試

PTMalloc2包（現(xiàn)在已經(jīng)是glibc的一部分了）包含了一個(gè)單元測(cè)試程序t-test1.c。它會(huì)產(chǎn)生一定數(shù)量的線程并在每個(gè)線程中進(jìn)行一系列分配和解除分配；線程之間沒(méi)有任何通信除了在內(nèi)存分配器中同步。

t-test1（放在tests/tcmalloc/中，編譯為ptmalloc_unittest1）用一系列不同的線程數(shù)量（1～20）和最大分配尺寸（64B～32KB）運(yùn)行。這些測(cè)試運(yùn)行在一個(gè)2.4GHz 雙核心Xeon的RedHat 9系統(tǒng)上，并啟用了超線程技術(shù)， 使用了Linux glibc-2.3.2，每個(gè)測(cè)試中進(jìn)行一百萬(wàn)次操作。在每個(gè)案例中，一次正常運(yùn)行，一次使用LD_PRELOAD=libtcmalloc.so。

下面的圖像顯示了TCMalloc對(duì)比PTMalloc2在不同的衡量指標(biāo)下的性能。首先，現(xiàn)實(shí)每秒全部操作（百萬(wàn)）以及最大分配尺寸，針對(duì)不同數(shù)量的線程。用來(lái)生產(chǎn)這些圖像的原始數(shù)據(jù)（time工具的輸出）可以在t-test1.times.txt中找到。

• TCMalloc要比PTMalloc2更具有一致地伸縮性——對(duì)于所有線程數(shù)量>1的測(cè)試，小分配達(dá)到了約7～9百萬(wàn)操作每秒，大分配降到了約2百萬(wàn)操作每秒。單線程的案例則明顯是要被剔除的，因?yàn)樗荒鼙３謫蝹€(gè)處理器繁忙因此只能獲得較少的每秒操作數(shù)。PTMalloc2在每秒操作數(shù)上有更高的方差——某些地方峰值可以在小分配上達(dá)到4百萬(wàn)操作每秒，而在大分配上降到了<1百萬(wàn)操作每秒。
• TCMalloc在絕大多數(shù)情況下要比PTMalloc2快，并且特別是小分配上。線程間的爭(zhēng)用在TCMalloc中問(wèn)題不大。
• TCMalloc的性能隨著分配尺寸的增加而降低。這是因?yàn)槊烤€程緩存當(dāng)它達(dá)到了閾值（默認(rèn)是2MB）的時(shí)候會(huì)被垃圾收集。對(duì)于更大的分配尺寸，在垃圾收集之前只能在緩存中存儲(chǔ)更少的對(duì)象。
• TCMalloc性能在約32K最大分配尺寸附件有一個(gè)明顯的下降。這是因?yàn)樵诿烤€程緩存中的32K對(duì)象的最大尺寸；對(duì)于大于這個(gè)值得對(duì)象TCMalloc會(huì)從中央頁(yè)面堆中進(jìn)行分配。

下面，CPU時(shí)間的每秒操作數(shù)（百萬(wàn)）以及線程數(shù)量的圖像，最大分配尺寸64B～128KB。

這次我們?cè)僖淮慰吹絋CMalloc要比PTMalloc2更連續(xù)也更高效。對(duì)于<32K的最大分配尺寸，TCMalloc在大線程數(shù)的情況下典型地達(dá)到了CPU時(shí)間每秒約0.5～1百萬(wàn)操作，同時(shí)PTMalloc通常達(dá)到了CPU時(shí)間每秒約0.5～1百萬(wàn)，還有很多情況下要比這個(gè)數(shù)字小很多。在32K最大分配尺寸之上，TCMalloc下降到了每CPU時(shí)間秒1～1.5百萬(wàn)操作，同時(shí)PTMalloc對(duì)于大線程數(shù)降到幾乎只有零（也就是，使用PTMalloc，在高度多線程的情況下，很多CPU時(shí)間被浪費(fèi)在輪流等待鎖定上了）。

注意

對(duì)于某些系統(tǒng)，TCMalloc可能無(wú)法與沒(méi)有鏈接libpthread.so（或者你的系統(tǒng)上同等的東西）的應(yīng)用程序正常工作。它應(yīng)該能正常工作于使用glibc 2.3的Linux上，但是其他OS/libc的組合方式尚未經(jīng)過(guò)任何測(cè)試。

TCMalloc可能要比其他malloc版本在某種程度上更吃?xún)?nèi)存，（但是傾向于不會(huì)有其他malloc版本中可能出現(xiàn)的爆發(fā)性增長(zhǎng)。）尤其是在啟動(dòng)時(shí)TCMalloc會(huì)分配大約240KB的內(nèi)部?jī)?nèi)存。

不要試圖將TCMalloc載入到一個(gè)運(yùn)行中的二進(jìn)制程序中（例如，在Java中使用JNI）。二進(jìn)制程序已經(jīng)使用系統(tǒng)malloc分配了一些對(duì)象，并會(huì)嘗試將它們傳遞到TCMalloc進(jìn)行解除分配。TCMalloc是無(wú)法處理這種對(duì)象的。