Golang——垃圾回收GC(2)

1 垃圾回收中的重要概念

1.1 定義

In computer science, garbage collection (GC) is a form of automatic memory management. The garbage collector, or just collector, attempts to reclaim garbage, or memory occupied by objects that are no longer in use by the program. Garbage collection was invented by John McCarthy around 1959 to simplify manual memory management in Lisp. （引用自維基百科)）

1.2 GC性能的評價標準

吞吐量：是指單位時間內是有多少時間是用來運行user application的。GC占用的時間過多，就會導致吞吐量較低。
最大暫停時間：基本上所有的垃圾回收算法，都會在執行GC的過程中，暫停user application。如果暫停時間過長，必然會影響用戶體驗，尤其是那些交互性較強的應用。
堆使用效率：影響堆使用效率的主要有兩個因素，一個是對象頭部大小，一個是堆的用法。一般來說，堆的頭部越大，存儲的信息越多，那么GC的效率就會越高，吞吐量什么的也會有更佳的表現。但是，我們必須明白，對象頭越小越好。另外，不同的算法對于堆的不同用法，也會導致堆使用效率差距非常大。比如復制算法，用戶應用只能使用一般的堆大小。GC是自動管理內存的，如果因為GC導致過量占用堆，那么就是本末倒置了。
訪問的局部性：具有引用關系的對象之間很可能存在連續訪問的情況。因此，把具有引用關系的對象安排在堆中較勁的位置，可以充分利用內存訪問局部性。有的GC算法會根據引用關系重排對象，比如復制算法。
等等等等

設計垃圾回收算法時，折中無處不在。較大的吞吐量和較短的最大暫停時間往往不可兼得。

2 常見的GC算法

2.1 標記-清除算法 STW

mark_sweep(){????mark()sweep()}

分兩個階段，整個過程需要STW：

mark phase：時間復雜度跟活動對象數量成正比
sweep phase：時間復雜度跟堆的大小成正比

sweep階段回收的空間會連接到空閑鏈表上，分配空間時從空閑鏈表分配，因此分配空間時間復雜度可能會有點高，即需要遍歷整個空閑鏈表。

優點是實現簡單，并且與保守式GC兼容（即沒有移動對象）

缺點也非常明顯：

存在內存碎片
分配速度較慢：使用多個空閑鏈表
與寫時復制技術不兼容：位圖標記法
sweep操作時間復雜度同堆大小成正比：延遲清除法

延遲清除法：沒有空閑鏈表。定義一個全局變量sweeping，從sweeping開始遍歷分配新空間，遍歷的開始位置處于上一次lazy_sweep操作發現的分塊的右邊。如果當前分塊mark=true，則取消標記。如果mark=false并且分開大小大于申請空間，則分配給他。當遍歷到堆末尾時，需要將sweeping設置為heap_start，并且需要重新標記。

2.2 引用計數法

在標記-清除等GC算法中，沒有分塊可用時，mutator會調用下面的函數啟動GC回收空間，以便進行分配：

garbage_collect(){...
}

然而引用計數法是沒有啟動GC的語句的，它與mutator的執行密切相關，它在mutator的執行過程中通過增減引用計數器的值來實現實時的內存管理和垃圾回收。

引用計數器的更新主要有兩個場景：

分配新對象時
更新指針時

如果引用計數值變為0，則會立即連接到空閑鏈表上去。分配空間時，從空閑鏈表分配，分配失敗，則直接失敗返回。

優點是：

最大暫停時間短
可即刻回收垃圾

缺點是：

引用計數值的增減處理繁重，吞吐量低
循環引用
計數器占用很多位

2.3 復制算法 STW

GC復制算法將堆空間分成大小相等的兩塊：from空間和to空間。新對象只能從from空間分配。

當from空間沒有可用空間時，則會啟動GC，將from空間的活動對象復制到to空間，同時將from和to的身份互換。因此其時間復雜度，與活動對象的數量成正比，而與堆的大小無關。

復制時，是從根對象遞歸遍歷復制過去的。因此，我們定義了一個free變量記錄下從這個位置分配可用空間，分配空間的時間復雜度為常數。

優點：

因為時間復雜度與活動對象數量成正比，而與堆大小無關。所以，吞吐量優秀。
分配速度快
不會發生碎片化
訪問的局部性原理

缺點是：

堆的使用效率低下
移動對象，與保守式GC不兼容

2.4 標記-壓縮算法 STW

標記-壓縮算法時將標記-清除和復制算法相結合的產物。

標記階段跟標記-清除算法一樣，從根引用的活動變量開始遍歷。時間復雜度同活動對象的數量成正比。

而壓縮階段則需要遍歷整個堆，按照之前的排列順序壓縮到堆的一側去。

壓縮階段需要遍歷三次堆：

第一次遍歷，需要找出計算出所有的活動對象需要移動到哪個位置去
第二次遍歷，需要重寫根指針，重寫活動對象的指針
第三次遍歷，移動對象到目標位置

優點是堆的利用率很高，沒有碎片。缺點也是灰常的明顯，壓縮的時間復雜度太高，而且與堆的大小成正比。

2.5 分代垃圾回收

分代垃圾回收在對象中引入了“年齡”的概念，通過優先回收容易成為垃圾的對象，提高GC的效率。

我們把剛生成的對象稱為新生代對象，到達一定年齡的對象稱為老年代對象。

在新生代空間執行的GC，稱為minor GC。在老年代空間執行的GC，稱為major GC。

堆的結構：

新生成對象分配的空間都是從Eden區分配的。當Eden區滿了的時候，就會觸發minor GC，將Eden區和From區的活動對象都復制到To，然后交互To和From的身份。

復制的時候如果超過一定的年齡或者To空間不足（即Eden和From的活動對象占用的空間超過了To），那么直接復制到老年代空間。如果老年代空間不足則會觸發major GC。

那些大于Eden空間的對象，一般也不會直接失敗，而是直接分配到老年代空間。實際的實現，一般是超過一定大小，則會將其分配到老年代空間。

新生代空間和老年代空間采用不同的GC算法。新生代采用復制算法，老年代采用標記-壓縮算法或者標記-清除算法。

3 Golang的垃圾回收算法

3.1 三色標記法

golang采用的是并發的三色標記清除算法（Tri-color marking）。

白色：還沒搜索的對象
灰色：正在搜索的對象
黑色：搜索完成的對象

GC開始前所有的對象都是白色對象。GC開始時，會將從根能夠直接引用的對象標記為灰色，并且放到堆棧里。

然后，灰色對象會被依次彈出棧，其子對象也被涂成灰色，壓入棧。當其所有的子對象都變成灰色后，就會把這個對象涂成黑色。

當GC結束時，活動對象全部為黑色對象，垃圾則為白色對象，回收白色對象即可。

主要分為四個階段：

root_scan：STW
mark...mark...mark...mark...
mark termination：STW
sweep...sweep...sweep...

接下來分別介紹一下上述的四個不同階段。

3.1.1 root scan

根查找階段需要STW。找出能夠從根直接引用的對象，標記為灰色，壓入棧。

root_scan_phase(){????for(r?:?$roots){mark(*r)}????$gc_phase?=?GC_MARK
}mark(obj){????if(obj.mark?==?false){obj.mark?=?truepush(obj,$mark_stack)}
}

當我們把所有直接從根引用的對象涂成了灰色時，root scan階段就結束了，mutator（即user application）會繼續執行。

3.1.2 mark 和 mark termination

mark是分多次運行的，即增量式的mark，不需要STW，它和mutator交替運行。它主要是彈出棧里面的對象，將其子對象涂成灰色，壓入棧，然后把這個對象涂成黑色。重復這個過程，直到棧為空。

mark termination則是需要STW的。它會root_rescan，然后重新執行mark。

然而，mark階段與mutator并發運行存在一個問題，可能誤把活動對象當做垃圾對象回收。

比如下面的情況：

第二張圖，創建了從黑色對象到白色對象的引用。第三張圖，刪除了從灰色對象到白色對象的引用。這個時候就會導致C被誤認為垃圾而回收。

為了避免這種情況的發生，需要引入write barrier。

最常用的write barrier是由Dijkstra提出的insertion style write barrier。

write_barrier(obj,field,newobj){????if(newobj.mark?==?false){newobj.mark?=?truepush(newobj,$mark_stack)}*field?=?newobj
}

即如果新引用的對象是白色對象，則直接把它涂為灰色：

mark和mark termination的偽代碼為：

incremental_mark_phase(){????for(i?:?1...MARK_MAX){????????//?分多次mark，不需要STWif(is_empty($mark_stack)?==?false){obj?=?pop($mark_stack)????????????for(child?:?children(obj)){mark(*child)}}else{????????????//?mark?termination，需要STWfor(r?:?roots){mark(*r)}????????????while(is_empty($mark_stack)?==?false){obj?=?pop($mark_stack)????????????????for(child?:?children(obj)){mark(*child)}}????????????$gc_phase?=?GC_SWEEP$sweeping?=?$heap_startreturn}}
}

3.1.3 sweep

sweep也是分多次的，增量式的回收垃圾，跟mutator交替運行。跟標記-清除算法的實現基本一致，也是需要遍歷整個堆，將白色對象掛到空閑鏈表上，黑色對象取消mark標記。

3.1.4 分配新對象

從空閑鏈表分配。

3.2 golang為什么沒有采用壓縮算法和分代算法

有點高深，想深入了解的可以參考golang-nuts上面的討論。

4 Golang垃圾回收的相關參數

4.1 觸發GC

gc觸發的時機：2分鐘或者內存占用達到一個閾值（當前堆內存占用是上次gc后對內存占用的兩倍，當GOGC=100時）

?#?表示當前應用占用的內存是上次GC時占用內存的兩倍時，觸發GCexport?GOGC=100

4.2 查看GC信息

export?GODEBUG=gctrace=1

可以查看gctrace信息。

舉例：

gc?1?@0.008s?6%:?0.071+2.0+0.080?ms?clock,?0.21+0.22/1.9/1.9+0.24?ms?cpu,?4->4->3?MB,?5?MB?goal,?4?P#?command-line-argumentsgc?1?@0.001s?16%:?0.071+3.3+0.060?ms?clock,?0.21+0.17/2.9/0.36+0.18?ms?cpu,?4->4->4?MB,?5?MB?goal,?4?Pgc?2?@0.016s?8%:?0.020+6.0+0.070?ms?clock,?0.082+0.094/3.9/2.2+0.28?ms?cpu,?8->9->8?MB,?9?MB?goal,?4?Pgc?3?@0.046s?7%:?0.019+7.3+0.062?ms?clock,?0.076+0.089/7.1/7.0+0.24?ms?cpu,?14->16->14?MB,?17?MB?goal,?4?Pgc?4?@0.092s?8%:?0.015+24+0.10?ms?clock,?0.060+0.10/24/0.75+0.42?ms?cpu,?25->27->24?MB,?28?MB?goal,?4?P

每個字段表示什么信息可以參考?golang doc

5 如何提高GC的性能

Golang的GC算法是固定的，用戶無法去配置采用什么算法，也沒法像Java一樣配置年輕代、老年代的空間比例等。golang的GC相關的配置參數只有一個，即GOGC，用來表示觸發GC的條件。

目前來看，提高GC效率我們唯一能做的就是減少垃圾的產生。所以說，這一章稱為提高GC的性能也不太合適。下面我們就主要討論一下，在golang中如何減少垃圾的產生，有哪些需要注意的方面。

5.1 golang中的內存分配

參考官網Frequently Asked Questions (FAQ)

How do I know whether a variable is allocated on the heap or the stack?

From a correctness standpoint, you don't need to know. Each variable in Go exists as long as there are references to it. The storage location chosen by the implementation is irrelevant to the semantics of the language.

The storage location does have an effect on writing efficient programs. When possible, the Go compilers will allocate variables that are local to a function in that function's stack frame. However, if the compiler cannot prove that the variable is not referenced after the function returns, then the compiler must allocate the variable on the garbage-collected heap to avoid dangling pointer errors. Also, if a local variable is very large, it might make more sense to store it on the heap rather than the stack.

In the current compilers, if a variable has its address taken, that variable is a candidate for allocation on the heap. However, a basic escape analysis recognizes some cases when such variables will not live past the return from the function and can reside on the stack.

我們看一個例子有個直觀的認識：

1?package?main2?3?import?()4?5?func?foo()?*int?{6?????var?x?int7?????return?&x8?}9?10?func?bar()?int?{11?????x?:=?new(int)12?????*x?=?113?????return?*x14?}15?16?func?big()?{17?????x?:=?make([]int,0,20)18?????y?:=?make([]int,0,20000)19?20?????len?:=?1021?????z?:=?make([]int,0,len)22?}23?24?func?main()?{25??26?}

#?go?build?-gcflags='-m?-l'?test.go./test.go:7:12:?&x?escapes?to?heap
./test.go:6:9:?moved?to?heap:?x
./test.go:11:13:?bar?new(int)?does?not?escape
./test.go:18:14:?make([]int,?0,?20000)?escapes?to?heap
./test.go:21:14:?make([]int,?0,?len)?escapes?to?heap
./test.go:17:14:?big?make([]int,?0,?20)?does?not?escape
./test.go:17:23:?x?declared?and?not?used
./test.go:18:23:?y?declared?and?not?used
./test.go:21:23:?z?declared?and?not?used

5.2 sync.Pool對象池

sync.Pool主要是為了重用對象，一方面縮短了申請空間的時間，另一方面，還減輕了GC的壓力。不過它是一個臨時對象池，為什么這么說呢？因為對象池中的對象會被GC回收。所以說，有狀態的對象，比如數據庫連接是不能夠用sync.Pool來實現的。

use sync.Pool if you frequently allocate many objects of the same type and you want to save some allocation and garbage collection overhead. However, in the current implementation, any unreferenced sync.Pool objects are removed at each garbage collection cycle, so you can't use this as a long-lived free-list of objects. If you want a free-list that maintains objects between GC runs, you'll still have to build that yourself. This is only to reuse allocated objects between garbage collection cycles. ?

sync.Pool主要有兩個方法：

func?(p?*Pool)?Get()?interface{}?{...
}func?(p?*Pool)?Put(x?interface{})?{...
}

Get方法是指從臨時對象池中申請對象，put是指把不再使用的對象返回對象池，以便后續重用。如果我們在使用Get申請新對象時pool中沒有可用的對象，那么就會返回nil，除非設置了sync.Pool的New func：

type?Pool?struct?{...????//?New?optionally?specifies?a?function?to?generate//?a?value?when?Get?would?otherwise?return?nil.//?It?may?not?be?changed?concurrently?with?calls?to?Get.New?func()?interface{}
}

另外，我們不能對從對象池申請到的對象值做任何假設，可能是New新生成的，可能是被某個協程修改過放回來的。

一個比較好的使用sync.Pool的例子：

var?DEFAULT_SYNC_POOL?*SyncPoolfunc?NewPool()?*SyncPool?{DEFAULT_SYNC_POOL?=?NewSyncPool(5,?????30000,?2,?????)return?DEFAULT_SYNC_POOL
}func?Alloc(size?int)?[]int64?{return?DEFAULT_SYNC_POOL.Alloc(size)
}func?Free(mem?[]int64)?{DEFAULT_SYNC_POOL.Free(mem)
}//?SyncPool?is?a?sync.Pool?base?slab?allocation?memory?pool
type?SyncPool?struct?{classes?????[]sync.PoolclassesSize?[]intminSize?????intmaxSize?????int
}func?NewSyncPool(minSize,?maxSize,?factor?int)?*SyncPool?{n?:=?0for?chunkSize?:=?minSize;?chunkSize?<=?maxSize;?chunkSize?*=?factor?{n++}pool?:=?&SyncPool{make([]sync.Pool,?n),make([]int,?n),minSize,?maxSize,}n?=?0for?chunkSize?:=?minSize;?chunkSize?<=?maxSize;?chunkSize?*=?factor?{pool.classesSize[n]?=?chunkSizepool.classes[n].New?=?func(size?int)?func()?interface{}?{return?func()?interface{}?{buf?:=?make([]int64,?size)return?&buf}}(chunkSize)n++}return?pool
}func?(pool?*SyncPool)?Alloc(size?int)?[]int64?{if?size?<=?pool.maxSize?{for?i?:=?0;?i?<?len(pool.classesSize);?i++?{if?pool.classesSize[i]?>=?size?{mem?:=?pool.classes[i].Get().(*[]int64)//?return?(*mem)[:size]return?(*mem)[:0]}}}return?make([]int64,?0,?size)
}func?(pool?*SyncPool)?Free(mem?[]int64)?{if?size?:=?cap(mem);?size?<=?pool.maxSize?{for?i?:=?0;?i?<?len(pool.classesSize);?i++?{if?pool.classesSize[i]?>=?size?{pool.classes[i].Put(&mem)return}}}
}

有一個開源的通用golang對象池實現，有興趣的可以研究一下：Go Commons Pool，在此不再贅述。