牽著老婆滿街逛

原文

動機

TCMalloc要比glibc 2.3的malloc（可以從一個叫作ptmalloc2的獨立庫獲得）和其他我測試過的malloc都快。ptmalloc在一臺2.8GHz的P4機器上（對于小對象）執行一次malloc及free大約需要300納秒。而TCMalloc的版本同樣的操作大約只需要50納秒。malloc版本的速度是至關重要的，因為如果malloc不夠快，應用程序的作者就很有可能在malloc之上寫一個自己的自由列表。這就可能導致額外的代碼復雜度，以及更多的內存占用――除非作者本身非常仔細地劃分自由列表的大小并經常從自由列表中清除空閑的對象。

TCMalloc也減少了多線程程序中的鎖爭用情況。對于小對象，幾乎已經達到了零爭用。對于大對象，TCMalloc嘗試使用粒度較好和有效的自旋鎖。ptmalloc同樣是通過使用每線程各自的場地來減少鎖爭用，但是ptmalloc2使用每線程場地有一個很大的問題。在ptmalloc2中，內存可能會從一個場地移動到另一個。這有可能導致大量空間被浪費。例如，在一個Google的應用中，第一階段可能會為其URL標準化的數據結構分配大約300MB內存。當第一階段結束后，第二階段將從同樣的地址空間開始。如果第二個階段被安排到了一個與第一階段什?用的場地不同的場地，這個階段不會復用任何第一階段留下的的內存，并會給地址空間添加另外一個300MB。類似的內存爆炸問題也可以在其他的應用中看到。

TCMalloc的另一個好處是小對象的空間最優表現形式。例如，分配N個8字節對象可能要使用大約8N * 1.01字節的空間。即，多用百分之一的空間。而ptmalloc2中每個對象都使用了一個四字節的頭，（我認為）并將最終的尺寸規整為8字節的倍數，最后使用了16N字節。

使用

要使用TCMalloc，只要將tcmalloc通過“-ltcmalloc”鏈接器標志接入你的應用即可。

你也可以通過使用LD_PRELOAD在不是你自己編譯的應用中使用tcmalloc：

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

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

TCMalloc還包含了一個堆檢查器以及一個堆測量器。

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

概覽

TCMalloc給每個線程分配了一個線程局部緩存。小分配可以直接由線程局部緩存來滿足。需要的話，會將對象從中央數據結構移動到線程局部緩存中，同時定期的垃圾收集將用于把內存從線程局部緩存遷移回中央數據結構中。

TCMalloc將尺寸小于<=
32K的對象（“小”對象）和大對象區分開來。大對象直接使用頁級分配器（一個頁是一個4K的對齊內存區域）從中央堆直接分配。即，一個大對象總是頁對齊的并占據了整數個數的頁。

連續的一些頁面可以被分割為一系列小對象，而他們的大小都相同。例如，一個連續的頁面（4K）可以被劃分為32個128字節的對象。

小對象的分配

每個小對象的大小都會被映射到170個可分配的尺寸類別中的一個。例如，在分配961到1024字節時，都會歸整為1024字節。尺寸類別這樣隔開：較小的尺寸相差8字節，較大的尺寸相差16字節，再大一點的尺寸差32字節，如此類推。最大的間隔（對于尺寸 >= ~2K的）是256字節。

一個線程緩存對每個尺寸類都包含了一個自由對象的單向鏈表。

當分配一個小對象時：

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

如果自由列表為空：

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

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

大對象的分配

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

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

如果k個頁面的一次分配行為由連續的長度> k的頁面滿足了，剩下的連續頁面將被重新插回到頁面堆的對應的自由列表中。

跨度（Span）

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

由頁面號索引的中央數組可以用于找到某個頁面所屬的跨度。例如，下面的跨度a占據了2個頁面，跨度b占據了1個頁面，跨度c占據了5個頁面最后跨度d占據了3個頁面。

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

在64位機器上，我們將使用一個3層的基數樹。

解除分配

當一個對象被解除分配時，我們先計算他的頁面號并在中央陣列中查找對應的跨度對象。該跨度會告訴我們該對象是大是小，如果它是小對象的話尺寸類別是什么。如果是小對象的話，我們將其插入到當前線程的線程緩存中對應的自由列表中。如果線程緩存現在超過了某個預定的大小（默認為2MB），我們便運行垃圾收集器將未使用的對象從線程緩存中移入中央自由列表。

如果該對象是大對象的話，跨度會告訴我們該對象覆蓋的頁面的范圍。假設該范圍是[p,q]。我們還會查找頁面p-1和頁面q+1對應的跨度。如果這兩個相鄰的跨度中有任何一個是自由的，我們將他們和[p,q]的跨度接合起來。最后跨度會被插入到頁面堆中合適的自由列表中。

小對象的中央自由列表

就像前面提過的一樣，我們為每一個尺寸類別設置了一個中央自由列表。每個中央自由列表由兩層數據結構來組成：一系列跨度和每個跨度一個自由對象的鏈表。

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

一個對象可以通過將其添加到他包含的跨度的鏈表中來返回到中央自由列表中。如果鏈表長度現在等于跨度中所有小對象的數量，那么該跨度就是完全自由的了，就會被返回到頁面堆中。

線程緩存的垃圾收集

某個線程緩存當緩存中所有對象的總共大小超過2MB的時候，會對他進行垃圾收集。垃圾收集閾值會自動根據線程數量的增加而減少，這樣就不會因為程序有大量線程而過度浪費內存。

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

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

性能備注

PTMalloc2單元測試

PTMalloc2包（現在已經是glibc的一部分了）包含了一個單元測試程序t-test1.c。它會產生一定數量的線程并在每個線程中進行一系列分配和解除分配；線程之間沒有任何通信除了在內存分配器中同步。

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

下面的圖像顯示了TCMalloc對比PTMalloc2在不同的衡量指標下的性能。首先，現實每秒全部操作（百萬）以及最大分配尺寸，針對不同數量的線程。用來生產這些圖像的原始數據（time工具的輸出）可以在t-test1.times.txt中找到。

• TCMalloc要比PTMalloc2更具有一致地伸縮性——對于所有線程數量>1的測試，小分配達到了約7～9百萬操作每秒，大分配降到了約2百萬操作每秒。單線程的案例則明顯是要被剔除的，因為他只能保持單個處理器繁忙因此只能獲得較少的每秒操作數。PTMalloc2在每秒操作數上有更高的方差——某些地方峰值可以在小分配上達到4百萬操作每秒，而在大分配上降到了<1百萬操作每秒。
• TCMalloc在絕大多數情況下要比PTMalloc2快，并且特別是小分配上。線程間的爭用在TCMalloc中問題不大。
• TCMalloc的性能隨著分配尺寸的增加而降低。這是因為每線程緩存當它達到了閾值（默認是2MB）的時候會被垃圾收集。對于更大的分配尺寸，在垃圾收集之前只能在緩存中存儲更少的對象。
• TCMalloc性能在約32K最大分配尺寸附件有一個明顯的下降。這是因為在每線程緩存中的32K對象的最大尺寸；對于大于這個值得對象TCMalloc會從中央頁面堆中進行分配。

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

這次我們再一次看到TCMalloc要比PTMalloc2更連續也更高效。對于<32K的最大分配尺寸，TCMalloc在大線程數的情況下典型地達到了CPU時間每秒約0.5～1百萬操作，同時PTMalloc通常達到了CPU時間每秒約0.5～1百萬，還有很多情況下要比這個數字小很多。在32K最大分配尺寸之上，TCMalloc下降到了每CPU時間秒1～1.5百萬操作，同時PTMalloc對于大線程數降到幾乎只有零（也就是，使用PTMalloc，在高度多線程的情況下，很多CPU時間被浪費在輪流等待鎖定上了）。

注意

對于某些系統，TCMalloc可能無法與沒有鏈接libpthread.so（或者你的系統上同等的東西）的應用程序正常工作。它應該能正常工作于使用glibc 2.3的Linux上，但是其他OS/libc的組合方式尚未經過任何測試。

TCMalloc可能要比其他malloc版本在某種程度上更吃內存，（但是傾向于不會有其他malloc版本中可能出現的爆發性增長。）尤其是在啟動時TCMalloc會分配大約240KB的內部內存。

不要試圖將TCMalloc載入到一個運行中的二進制程序中（例如，在Java中使用JNI）。二進制程序已經使用系統malloc分配了一些對象，并會嘗試將它們傳遞到TCMalloc進行解除分配。TCMalloc是無法處理這種對象的。