What’s that

GC(Garbage Collection)垃圾回收: 寻找程序中不再使用的已占内存空间（非活动对象），予以回收。不同的回收机制衍生出了很多 GC 算法。

Why does that work

并不是所有语言都有 GC，像 C、C++ 是需要自己管理内存的，malloc 申请的内存最后要手动 delete 掉，这有一定的自主可控性，但是对开发人员要求比较高，否则会容易发生内存泄漏（忘记 delete）或者意外删除仍旧使用的内存。

而其他一些主流语言大都带有 GC，就是语言本身帮我们做内存回收管理，GC 减少了我们的工作负担也避免了一些操作失误，可以很大程度上提高生产力。

但是 GC 并不是一本万利，当需要处理的内存对象非常多更新换代非常快时也很容易出现性能问题。如果追求极致的性能的话，首选还是无 GC 的好，比如当下比较火热的 rust 或者传统的 C++，当然这会增加不少使用成本。

Where to use

环境

Java 是 jvm 内存资源紧张的时候，就会自动地去清理无用变量所占用的内存空间，也可以在代码中显示调用 System.gc()；

Golang 是 runtime 时定期或满足条件时并行执行回收器，也可以在代码中显示调用 runtime.GC()，显示调用会阻塞整个程序直到垃圾回收完成；

JS 是 V8 内核中处理 GC。

栈和堆

栈区（stack）— 栈是用来存储函数内部（包括 main 函数）的局部变量和方法调用和函数参数值，是由系统自动分配的，一般速度较快；存储地址是连续且存在有限栈容量，可能存在栈溢出
堆区（heap） — 对象内部的成员变量，局部变量，类变量，他们指向的对象都存储在堆内存中（但指针本身存在栈中），一般速度较栈慢；存储地址通常是链式的，内存较大不会溢出

栈区的内存是系统自行分配回收的，函数出栈时便会释放临时占用的内存；而堆内存则需要我们或者 GC 来处理回收。

下面是 William Kennedy 在 ardanlabs 上关于 go 栈和堆以及内存逃逸的分享，有助于理解。

栈和指针

// https://play.golang.org/p/I4HcCAivEdI
package main

func main() {
   // Declare variable of type int with a value of 10.
   count := 10

   // Display the "value of" and "address of" count.
   println("count:\tValue Of[", count, "]\tAddr Of[", &count, "]")

   // Pass the "value of" the count.
   increment(count)

   println("count:\tValue Of[", count, "]\tAddr Of[", &count, "]")
}

//go:noinline
func increment(inc int) {
   // Increment the "value of" inc.
   inc++
   println("inc:\tValue Of[", inc, "]\tAddr Of[", &inc, "]")
}

输出

count:    Value Of[ 10 ]    Addr Of[ 0x10429fa4 ]
inc:    Value Of[ 11 ]    Addr Of[ 0x10429f98 ]
count:    Value Of[ 10 ]    Addr Of[ 0x10429fa4 ]

当函数返回时，increment 栈帧退出，同时释放内存，用于之后进栈的函数初始化

现在将参数改为传地址:

// https://play.golang.org/p/_2EkPscynM7
package main

func main() {
   // Declare variable of type int with a value of 10.
   count := 10

   // Display the "value of" and "address of" count.
   println("count:\tValue Of[", count, "]\t\tAddr Of[", &count, "]")

   // Pass the "address of" count.
   increment(&count)

   println("count:\tValue Of[", count, "]\t\tAddr Of[", &count, "]")
}

//go:noinline
func increment(inc *int) {
   // Increment the "value of" count that the "pointer points to". (dereferencing)
   *inc++
   println("inc:\tValue Of[", *inc, "]\tAddr Of[", &inc, "]\tValue Points To[", &*inc, "]")
}

输出

count: Value Of[10] Addr Of[0x10429fa4]
inc:   Value Of[11] Addr Of[0x10429f98] Value Points To[0x10429fa4]
count: Value Of[11] Addr Of[0x10429fa4]

共享栈

Go 语言初始化 goroutine 时会默认分配 2k 的空间，当栈空间不足时，函数内部会做溢出检查。现有的栈方案是连续栈（continuous stacks），需要扩容时创建一个两倍于原 stack 大小的新 stack，并将旧栈拷贝到其中；需要缩栈时释放一半即可。

在 Go 语言中，不允许 goroutine 栈中的指针指向另外一个 goroutine 的栈内存。这是因为当栈增长或者收缩时，goroutine 中的栈内存会被一块新的内存替换。如果运行时需要追踪指针指向其他的 goroutine 的栈，就会造成非常多需要管理的内存，以至于更新指向那些栈的指针将使 STW 问题更严重。

这里有一个栈被替换好几次的例子。看输出的第 2 和第 6 行。你会看到 main 函数中的栈的字符串地址值改变了两次。https://play.golang.org/p/pxn5u4EBSI

逃逸分析

逃逸分析是编译器用来决定你的程序中变量对象分配到栈上还是堆上的过程。

package main

type user struct {
    name  string
    email string
}

func main() {
    u1 := createUserV1()
    u2 := createUserV2()
    println("u1", &u1, "u2", &u2)
}

//go:noinline
func createUserV1() user {
    u := user{
        name:  "Bill",
        email: "bill@ardanlabs.com",
    }
    println("V1", &u)
    return u
}

//go:noinline
func createUserV2() *user {
    u := user{
        name:  "Bill",
        email: "bill@ardanlabs.com",
    }

    println("V2", &u)
    return &u
}

createUserV1 函数返回的是值的拷贝

createUserV2 函数返回的是值的地址

可以看到指针指向了栈下的无效地址空间。当 main 函数调用下一个函数，指向的内存将重新映射并将被重新初始化。

这就是逃逸分析发挥作用的地方。在这种情况下，编译器在编译期可以认为在 createUserV2 的（函数）栈中构造 user 值是不安全的，因此，会在选择堆中构造（相应的）值

可以在 build 过程中加上 -gcflags 参数来查看逃逸分析的报告，”-m”可以指定 4 个，越多报告越详细，一般使用一个或两个即可。

$ go build -gcflags "-m -m"
# test
./main.go:16:6: cannot inline createUserV1: marked go:noinline
./main.go:27:6: cannot inline createUserV2: marked go:noinline
./main.go:8:6: cannot inline main: function too complex: cost 179 exceeds budget 80
./main.go:22:16: createUserV1 &u does not escape
./main.go:34:9: &u escapes to heap
./main.go:34:9:         from ~r0 (return) at ./main.go:34:2
./main.go:28:2: moved to heap: u
./main.go:33:16: createUserV2 &u does not escape
./main.go:12:16: main &u1 does not escape
./main.go:12:27: main &u2 does not escape

Go 实现的逃逸分析可以尽可能的把生命周期短的或者作用域有限的内存对象优先分配在栈上，这样可以减少堆的分配，也就间接减轻 GC 的压力。实际开发中如果发现 GC 压力比较大，可以用性能分析工具查一下运行期间分配的堆对象是不是特别多，然后尝试分析内存逃逸优化下代码或者引入临时对象池等。

How does that work

常见 GC 算法

引用计数

较早期出现的、实现较简单的一种算法，大体内容就是每个对象存储的物理空间维护一个计数器，被引用加一解除引用减一，定期清扫计数为零的对象（具体实现具体分析），缺点无法解决循环引用、维护计数影响效能

PHP 的 GC 算法就是一种引用计数 + 局部延时标记的垃圾回收算法，Concurrent Cycle Collection in Reference Counted Systems，对循环引用之类的做了特殊处理。

标记-清除

collector：垃圾收集器。collector 回收不再使用的内存来供 mutator 进行 NEW 操作的使用。

mutator：除了垃圾收集器的其他部分，比如应用程序本身。mutator 的职责一般是 NEW (分配内存), READ (从内存中读取内容), WRITE (将内容写入内存)

mutator root(根对象)：mutator 根对象一般指的是分配在堆内存之外，可以直接被 mutator 直接访问到的对象。

可达对象：mutator 根对象开始进行遍历，可以被访问到的对象都称为是可达对象。这些对象也是 mutator (你的应用程序)正在使用的对象

一种经典的基于追踪的垃圾收集算法，算法分两个部分：标记（mark）和清除（sweep）。标记阶段 collector 从 mutator root 开始进行遍历，将所有访问到的对象都标记为可达对象。清除阶段 collector 对堆内存的所有对象进行线性的遍历，回收没有被标记的对象。

进行上面两个阶段的时候，会停止整个应用程序（stop the world）。等结束后，才会恢复应用程序（start the world）。这个过程俗称 STW，这个时间越短说明 GC 影响越少，性能越好

优点是解决引用计数的缺陷，缺点是需要 STW。

标记清除根据实现又可以分为几类：

1、上述的普通算法，清除阶段扫描整个堆空间回收可用内存，但是这会造成可用内存零碎化，影响 mutator 的分配；

2、在上述算法基础上，清除阶段回收内存时会将保留的对象迁移到连续内存上，也称作标记-压缩算法，这样 mutator 需要申请新内存时直接去尾部找，效率高，但是这种做法会改变已有对象的内存地址，成本高；

3、三色标记算法

白色集合：一组可以回收内存的对象。（也就是最后要清扫的垃圾）

灰色集合：包括所有可以从根对象访问到的，但是还没有扫描引用的”白色“对象的对象。由于这些对象可以从根对象访问到，所以它们不能 collector 收集，并且被扫描后它们移入到黑色集合中

黑色集合：可以显示为没有对白色集合中对象的传出引用并可从根目录访问的对象集合。黑色集合中的对象不被收集。

最初开始的时候，黑色集合中是空的，灰色集合是根对象引用的对象集合，白色集合包含其他所有对象。

1. 从灰色集合中选取一个物体将其自身移至黑色集合
2. 将其引用的每个白色对象移至灰色集合
3. 重复前两个步骤，直到灰色集合为空

灰色设置为空时，扫描完成; 黑色的物体可以从根部到达，而白色的物体不是，可以被 collector 收集。

由于从根不能立即到达的所有对象都添加到白色集合中，并且对象只能从白色移动到灰色，并且从灰色移动到黑色，因此该算法保留了一个重要的不变性 —— 没有黑色对象引用白色对象。这确保了一旦灰色集合为空时，则可以释放白色物体。这被称为三色不变量。

节点复制

也是基于追踪的算法。将整个堆等分为两个半区（semi-space），一个包含现有数据，另一个包含已被废弃的数据。

程序运行所需的存储对象先存储在其中一个分区（假设为“分区 0”）。同样暂停整个程序的全部运行线程后，进行标记后，回收期间将保留的存储对象搬运汇集到另一个分区（假设为“分区 1”），完成回收，程序在本次回收后存活的对象会存储到“分区 1”。在下一次回收时，两个分区的角色对调。

优点是存活的数据对象都缩并地排列在复制分区的底部，这样可以解决内存碎片的问题，缺点是有一半空间得不到有效利用

V8 的 GC 机制是分代回收，其中新生代的回收算法就是这种复制算法，新生代的堆空间为 1M~8M，而且被平分成两份（new-space 和 old-space），通常一个新创建的对象，内存被分配在新生代。当 new-space 满的时候，new-space 和 old-space 交换位置（此时，new 空，old 满），并执行 GC，如果一个对象存活则逃逸次数 +1（如果此时逃逸次数为 2，就移入老生代，否则移入 new-space）。老生代的堆空间大，GC 不适合像新生代那样，用平分成两个 space 这种空间换时间的方式。老生代的垃圾回收使用的是三色标记清除的方式。

分代回收

因为大部分对象的生命周期是短暂的，而生命周期长的对象又是不需要频繁扫描处理的，因此出现了分代回收，也就是根据生命周期长短将堆分为两个或多个分区。

比如分为新生代空间和老生代空间，程序运行所需的存储对象会先分配到新生代分区，新生代分区存在较多的临时对象，会较为频繁且激进地进行垃圾回收行为，每次回收存活的存储对象内的寿命计数器加一。当新生代分区存储对象的寿命计数器达到一定阈值或存储对象的占用空间超过一定阈值时，则被移动到老生代空间，老生代空间会较少运行垃圾回收行为。

优点性能较好，缺点实现复杂。

一种实现就是上述提到的，新生代采用复制算法，老生代采用标记清除算法。Java 就是典型的分代回收（java 还设置了一个永生代）。

至于 GO 并没有实现分代和压缩，原因可见 https://groups.google.com/forum/#!msg/golang-nuts/KJiyv2mV2pU/wdBUH1mHCAAJ

其中主要的观点是因为 Go 基于 tcmalloc 的内存分配管理策略本身可以减少内存碎片的出现，回收压缩的方案并不适用；而逃逸分析可以将很多生命周期短的对象分配到栈上，实现一个新生代的作用并没有那么大。

官方也正在尝试添加分代回收的机制，前段时间刚好看到一篇介绍: https://www.jianshu.com/p/2383743edb7b

Golang GC

Golang 的 GC 一直在改进，早期只是简单的标记-清除，GC pause(STW) 并不理想；v1.5开始引入三色标记，GC 的标记清除可以和程序逻辑并行，但是为解决标记期间用户的引用更改需要有一个 rescan 的过程，此过程仍需要 STW；v1.6~v1.8 引入新的写屏障，特别是 v1.8 实现的混合写屏障可以直接消除 rescan，大大缩短了 STW 的时间。

关于 go gc 的发展史可以看下文末的 The Journey of Go's Garbage Collector

GC 各阶段

• STW : Stop The World Phase
  • 一些初始化准备工作，包括开启 Write Barrier，结束之前未完成的清除任务，清空对象池等
• Mark Phase
  • 刚开始所有对象均为白色
  • Scan Stacks : 找到所有根对象并加进队列
    • 扫描某个 goroutine 的栈时暂停它
    • 所有找到的根对象均标记为灰色
    • 将该栈标记为黑色
  • Mark Phase I : 从队列中取出一个灰色对象
    • 将该对象标记为黑色
    • 如果该对象指向其他白色对象，则把这些白色对象标记为灰色
    • GC 和应用程序是并发进行
    • 在此阶段执行的 Goroutines 的栈会恢复为灰色
  • Mark Phase II - STW : Re-scan 灰色栈
    • Re-scan 所有灰色的栈和根对象
    • 如果有大量活跃的 goroutines 会造成较高的延迟
    • 在黑色集合上调用 finalizers
• Sweep Phase
  • 回收白色集合的内存

STW 有两个过程:
​ - 第一个是 GC 将要开始的时候，这个时候主要是一些准备工作，比如 enable write barrier。
​ - 第二个过程就是上面提到的 re-scan 过程。如果这个时候没有 stw，用户程序反复分配新对象或者修改引用，GC 需要反复 rescan，那 mark 阶段就停不下来了。

v1.5 的时候 STW 主要就耗在这 rescan 上了，后面 v1.8 实现了一种结合了 Yuasa-style deletion write barrier 和 Dijkstra-style insertion write barrier 的 hybrid write barrier，可以消除 rescan，详细介绍在 https://github.com/golang/proposal/blob/master/design/17503-eliminate-rescan.md

write-barrier 写屏障

为什么标记清除需要 STW ?
三色标记有什么好处？
怎么实现并行操作 GC？

三色标记的目的，主要是用于做增量的垃圾回收。如果只有黑色和白色两种颜色，那么回收过程将不能中断，必须一次性完成，期间用户程序是不能运行的。

而使用三色标记，即使在标记过程中对象的引用关系发生了改变，例如分配内存并修改对象属性域的值，只要满足黑色对象不引用白色对象的约束条件，垃圾回收器就可以继续正常工作。于是每次并不需要将回收过程全部执行完，只是处理一部分后停下来，后续会慢慢再次触发的回收过程，实现增量回收。相当于是把垃圾回收过程打散，减少停顿时间

并行问题:

A 是根对象，GC 遍历到 A 时，A 变黑，B 变灰；接着用户程序把 A 到 B 的引用改成了 A 到 C 的引用；然后 GC 接着开始遍历到 B，B 没有引用对象，B 变黑；此时灰色集合已空，标记结束，C 是白色集合所以被清理了。

Obj 是根对象结构体，GC 遍历到 Obj 时，Obj 变黑；接着用户程序在 Obj 中新添加一个变量 C，初始是白色；然后 GC 结束标记后，C 就会被清除。

上述例子的出现说明并行标记会出现黑色对象引用白色对象，为了解决这个问题，需要引入写屏障(Write Barrier)，写屏障相当于程序在写指针操作的地方插入一段代码，当用户程序修改内存引用时，如果有黑色对象引用了白色对象，则把相应白色对象移入灰色集合，如果是新分配的对象则直接放入黑色集合。

触发 GC

触发 GC 的方式有三种:

• 自动检测

  内存分配过程中，当分配的对象大小 >32kb，或是分配小对象时发现 span 已经满了时，会触发 GC。

• 用户调用

  通过调用 runtime.GC() 函数，这是阻塞式的。启用的时候会堵塞调用者直到垃圾回收完成。

  func GC() {
      gcStart(gcForceBlockMode, false)
  }
  

• forcegc

  Golang 本身会对运行状态进行监控，如果超过两分钟没有触发 GC 任务，则强制触发。

// runtime/proc.go
var forcegcperiod int64 = 2*60*1e9 // two minute

// Always runs without a P, so write barriers are not allowed.
//
//go:nowritebarrierrec
func sysmon() {
    ...
    for {
        ...
        // check if we need to force a GC
        if t := (gcTrigger{kind: gcTriggerTime, now: now}); t.test() && atomic.Load(&forcegc.idle) != 0 {
            lock(&forcegc.lock)
            forcegc.idle = 0
            var list gList
            list.push(forcegc.g)
            injectglist(&list)
            unlock(&forcegc.lock)
        }
        ...
    }
}

并不是触发 GC 后就马上执行清理回收，会有一个 test 函数判断是否满足清理条件

// test reports whether the trigger condition is satisfied, meaning that the exit
// condition for the _GCoff phase has been met. The exit condition should be tested when allocating.
func (t gcTrigger) test() bool {
    ...
    switch t.kind {
    case gcTriggerHeap:
        // Non-atomic access to heap_live for performance. If
        // we are going to trigger on this, this thread just
        // atomically wrote heap_live anyway and we'll see our
        // own write.
        return memstats.heap_live >= memstats.gc_trigger
    case gcTriggerTime:
        if gcpercent < 0 {
            return false
        }
        lastgc := int64(atomic.Load64(&memstats.last_gc_nanotime))
        return lastgc != 0 && t.now-lastgc > forcegcperiod
    case gcTriggerCycle:
        // t.n > work.cycles, but accounting for wraparound.
        return int32(t.n-work.cycles) > 0
    }
    return true
}

References

• The Journey of Go’s Garbage Collector
• Language Mechanics On Escape Analysis
• Golang 源码探索(三) GC 的实现原理
• Golang 垃圾回收剖析
• ardanlabs/gotraining
• JVM GC 算法