TCMalloc 內存分配器如何減少內存碎片？

前言

前文說過 TCMalloc 的基本原理，ThreadCache、PageHeap、PageMap 之類的，有了這些組件，基本算的上一個現代化的內存分配器了。但對於 TCMalloc 來說，這些只是萬里長征第一步，實現一個高性能的內存分配器還有很長的路要走。

本文圍繞着如何減少內存碎片這一問題，來看看 TCMalloc 對這方面的考量。

什麼是內存碎片？

這基本上是一個地球人都知道的問題。。不過我還需要再嘮叨一遍。所謂內存碎片，就是有一部分內存不能夠分配給程序使用，因爲它們以碎片的方式存在。內存碎片可以分兩種，內部碎片和外部碎片，內部碎片是分配器分配的內存大於程序申請的內存，外部碎片是內存塊太小，無法分配給程序使用。

那麼，內存碎片來自於哪裏呢？這個問題的答案取決於具體的內存分配算法，所以我們先來回顧一下經典的內存分配算法。

內存碎片 - Freelist

首先是 free-list，通過鏈表，把內存中空閒塊連接起來。分配的時候，找到大小合適的 Block，把它切分成兩塊，一塊是待分配的大小，另一塊放回 free-list；釋放的時候，插入到鏈表中，並且合併一下前後的內存塊方便下次分配。

分配的時候，選擇哪塊內存進行分裂？第一個滿足大小的？還是大小最合適的？通常有 First-Fit、Next-Fit、Best-Fit 這幾種策略。

放回的時候，也有多種策略，可以直接放回鏈表頭部（Last In First Out），最省事；或者按照地址順序放回（Address-Ordered），使得鏈表中的空閒塊都按照地址順序排列。

free-list 的內部碎片來自於固定大小的頭部和尾部，用來記錄內存塊的大小以及這塊內存的空閒與否，否則無從得知一個內存塊的大小，以及前一個內存塊的地址，後一個內存塊的地址，也就無從進行內存合併了。

free-list 的外部碎片則取決於分配和釋放策略。通常來說，First-Fit 策略會使得鏈表前面的大塊內存被頻繁分裂，從而造成較多的內存碎片；Best-Fit 的內存碎片較少；放回時，採用 Address-Ordered 順序能夠增加內存合併的機會，相比於 LIFO 的碎片會更少。

這裏有一個很有意思的策略是 Address-Ordered。先看一下 LIFO 的情況：

首先這些內存塊都是按地址排序的，3 和 5 是空閒的，4 是已分配的，3 指向 5。現在分別申請了 3 和 5 的內存，然後又釋放了 3 和 5，得到第二幅圖的情況，指針變成了 5 指向 3，因爲直接把 3 和 5 插入到鏈表頭部，LIFO 策略。接下來再申請 3 字節內存，按照 First-Fit 策略，就會把 5 的內存進行分裂。

如果採用 Address-Ordered 策略，放回 3 和 5 時，指針順序還是從 3 指向 5。那麼再次申請 3 字節內存時，直接分配原有的 3，而不需要分裂 5 的內存。

一些研究表明，採用 Address-Ordered 策略能夠顯著降低內存碎片，不過其實現較爲複雜，釋放內存的複雜度較高。

內存碎片 - Segregated-Freelist

上面的 Freelist 都可以申請和釋放任意大小的內存塊，而將大的內存塊和小的內存塊放在一起很容易帶來內存碎片，因此就有了 Segregated-Freelist，每個 Freelist 存儲不同大小的內存塊。

在 Seglist 中，就無需 Boundary-Tag 去存儲內存塊的大小信息了，只需要實現從地址到 Seglist 的映射即可，例如 TCMalloc 中使用的 PageMap 就是一種方式。

看起來可以減少內部碎片，但是問題隨之而來，每個 Freelist 都存儲固定大小的內存塊，如果申請 9 字節數據，可能就要分配 16 字節，帶來的內存碎片反而更多了！因此，雖然按照 2 的冪級數去分配是一種很簡單的策略，但是它並不高效。解決方案也有不少，例如分配 2^N 和 3*2^N 的內存塊。

至於外部碎片的問題，Seglist 也同樣存在，不過不是那麼明顯。因爲在分配 Freelist 的時候，通常按照內存 Page 爲單位，如果塊大小不是 Page 的約數，就會有外部碎片了。

Segregated-Freelist 還有一個變種，稱之爲 Segregated-Fit。每個 Freelist 不再是存儲固定大小的內存塊，而是存儲一定範圍的內存塊。大名鼎鼎的 Doug Lea 內存分配其（dlmalloc）就使用了這種策略。

內存碎片 - Buddy-System

夥伴系統也是一種很經典的分配算法。

按照一分爲二，二分爲四的原則，直到分裂出一個滿足大小的內存塊；合併的時候看看它的 Buddy 是否也爲空閒，如果是就可以合併，可以一直向上合併。

夥伴系統的優勢在於地址計算很快，對於一個內存塊的地址，可以通過位運算直接算出它的 Buddy，Buddy 的 Buddy，因此速度很不錯。

不過考慮內存碎片，它並沒有什麼優勢，像圖中的這種經典的 Binary Buddy，全部都是 2 的冪級數，內部碎片還是會達到 50%。當然也有一些其他的優化，塊大小可以是 3 的倍數之類的。

內存分配算法的比較

對於以上的幾種算法，實際會產生的內存碎片會有多少呢，有人專門做過測試比較：

Frag#3 和 Frag#4 分別是兩種不同的度量方法，一個是分配器申請內存最大時，程序分配的內存和分配器申請的內存，另一個是程序最大申請的內存和分配器最大申請的內存。測試時使用了實際的程序進行模擬，例如 GCC 之類內存開銷較大的程序。

這裏有幾個比較誇張的值，例如 simple seg 的 1468%，這是因爲碎片率的度量僅僅考慮分配器申請的內存和程序分配的內存，存在一定誤差。不過對於 best fit AO 來說，其內存碎片顯然是相當少的，而一些在我們看來比較樸素的算法，first fit，其內存碎片率其實也相當低，反而是 buddy system 和 segregated list 比較尷尬。

不過這篇文章說明的核心觀點是，只要選擇了合適的策略，其內存碎片就完全不用擔心，只要關心實現的性能就可以了，程序員也不用再手寫內存分配器什麼的了。

TCMalloc 的內存碎片

TCMalloc 採用了 Segregated-Freelist 的算法，提前分配好多種 size-class，在 64 位系統中，通常就是 88 種，那麼問題來了，這個怎麼計算？

首先看一下結果：8， 16， 32， 48， 64， 80， 96， 112， 128， 144， 160， 176......

TCMalloc 的目標是最多 12.5% 的內存碎片，按照上面的 size-class 算一下，例如 [112, 128)，碎片率最大是 (128-112-1)/128 = 11.7%，(1152-1024-1)/1151 = 11.02%。當然結果是滿足 12.5% 這一目標的。

要生成一批滿足碎片率的 size-class 其實也有多種方法，比如，[x, y) 區間內，只要滿足 (y-x-1)/y <= 0.125 即可，即 y <= 8/7*(x+1)，從前往後遞推一下就可以得到這些結果了，另外再考慮一下字節對齊什麼的，就可以得到不錯的結果。

不過 TCMalloc 從另一個角度來考慮這個問題的：從 size 到 size-class，需要進行一次向上對齊（round-up），例如 17 對齊到 32；其實也是進行了一次字節對齊（Alignment），把 17 以 16 字節進行對齊，(17 + 15) / 16 * 16 = 32。

那麼，內存碎片率其實就是 (Alignment-1) / SizeClass。那麼我們只需要保證每個 SizeClass 它的 Alignment 滿足 (Alignment-1)/SizeClass <= 0.125 就能滿足需求了。

例如，對於 size-class 1024，下一個 size-class 就是 1024 + 1024 / 8 = 1152，其中 Alignment 是 1024/8=128；那麼 1152，我們是按照 1152/8=144，還是按照 128 計算 Alignment 呢，我們選一個比較好看的數字 128 計算出下一個 size-class。好吧，爲什麼是 128 呢，因爲是把 1152 向下對齊到了 2 的冪級數 1024，（這裏的原因我就不是那麼清楚了）。得到的代碼如下：

func InitSizeClass() []int {
	alignment := 8
	classToSize := make([]int, 0, 88)
	for size := alignment; size <= 256*1024; size += alignment {
		alignment = align(size)
		classToSize = append(classToSize, size)
	}
	return classToSize
}

代碼非常簡單，不過省略了 align 這個函數的實現：

func align(size int) int {
	aligment := 8
	if size > 256*1024 {
		aligment = PageSize
	} else if size >= 128 {
		aligment = (1 << uint32(lgfloor(size))) / 8
	} else if size >= 16 {
		aligment = 16
	}
	if aligment > PageSize {
		aligment = PageSize
	}
	return aligment
}

計算 Alignment 的時候，大於 256 × 1024 就按照 Page 進行對齊；最小對齊是 8；在 128 到 256×1024 之間的，按照 1<<lgfloor(size) / 8 進行對齊。等等，說好的向下取整到 2 的冪級數然後除以 8 呢？

其實 lgfloor 就是用二分查找，向下對齊到 2 的冪級數的：

func lgfloor(size int) int {
	n := 0
	for i := 4; i >= 0; i-- {
		shift := uint32(1 << uint32(i))
		if (size >> shift) != 0 {
			size >>= shift
			n += int(shift)
		}
	}
	return n
}

先看左邊 16 位，有數字的話就搜左邊，否則搜右邊。。。

到這裏，基本上完成了 size-class 的計算（TCMalloc 還有一個優化）。

TCMalloc 的外部碎片

上面的 size-class 保證了內部碎片基本在 12.5% 以下，但是外部碎片呢？

外部碎片是因爲 CentralCache 在向 PageHeap 申請內存的時候，以 Page 爲單位進行申請。舉個例子，對於 size-class 1024，以一個 Page（8192）申請，完全沒有外部碎片；但是對於 size-class 1152，就有 8192 % 1152 = 128 的碎片。爲了保證外部碎片也小於 12.5%，可以一次多申請幾個 Page，但是又不能太多造成浪費。

func numMoveSize(size int) int {
	if size == 0 {
		return 0
	}
	num := 64 * 1024 / size
	return minInt(32768, maxInt(2, num))
}
 
func InitPages(classToSize []int) []int {
	classToPage := make([]int, 0, NumClass)
	for _, size := range classToSize {
		blocksToMove := numMoveSize(size) / 4
		psize := 0
		for {
			psize += PageSize
			for (psize % size) > (psize >> 3) {
				psize += PageSize
			}
			if (psize / size) >= blocksToMove {
				break
			}
		}
		classToPage = append(classToPage, psize>>PageShift)
	}
	return classToPage
}

這裏計算出來的結果，就是每個 size-class 每次申請的 Page 數量，保證 12.5% 以下的外部碎片。

到這裏基本能夠保證內部碎片和外部碎片都在 12.5% 以下了，但 TCMalloc 還沒有就此止步。。

size-class 的合併

在我們上面計算出來的 size-class 中存在一些冗餘，比如 1664，1792。它們都是一次申請 2 個 Page，1664 可以分配出 8 * 1024 * 2 / 1664 = 9 個對象，1792 也是可以分配出 8 * 1024 * 2 / 1792 = 9 個對象，那麼，區分這兩個 size-class 有意義嗎？1664 浪費的內存是 810242%1664=1408, 1792 浪費的內存是 810242%1792=256，1792 浪費的內存反而更少一點。因此都保留並不能讓這 2 個 Page 發揮更大的價值，所以，我們乾脆把這兩個合併了，僅僅保留 1792，結果並不會更差。

不過還有一個問題，如果我們計算一下 [1536, 1792) 的碎片，會發現 （1792-1536+1) / 1792 = 14.28% ，怎麼大於 12.5 % 了？略尷尬。這也意味着，申請 1537 字節，它的實際碎片率是 (81922 - (81922/1792*1537)) / (8192 * 2) = 15.57%，還是大於了 12.5% 的承諾。。

這裏會發現，雖然內部碎片小於 12.5%，外部碎片也小於 12.5%，但是它們加在一起就大於 12.5% 了，很悲傷的故事。。不知道 Sanjay 是有意爲之，還是無心之過。

size 到 size-class

還有一個小的問題，如何從 size 計算出 size-class。最簡單的最大是二分查找，用 std::upper_bound 就可以搞定，不過對於 88 個 size-class，O（LogN）需要 7 次查找，還是有些多，隨之帶來的 cache miss 可能又會加劇問題。

另一個方法是打表，因爲所有 size-class 都是至少 8 字節對齊的，我們把 256×1024 所有 8 字節對齊的數都打表，就能用 O（1）的複雜度查找到 size-class，不過這種方法略廢內存，cache locality 可能也不會太好；觀察一下發現，大於 1024 的 size-class 其實都以 128 對齊，那麼這個表就可以分兩段，小於 1024 和大於 1024，省了很多內存。具體的計算就不再贅述。

總結

其實在代碼中，關於 size-class 的計算真的就那麼幾行，以至於很多文章都沒有仔細考慮這段代碼的含義。不過 size-class 關係到內存碎片的多少，顯然又是相當重要的，所以還是花了不少心思研究了一下這幾行代碼的意思。而我又比較弱，其實花了好多時間才搞明白。雖然只是幾個參數，但是相信 Sanjay 還是仔細設計的，否則直接用 magic number 寫在裏面，後來人更是不知所云了。

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