从golang的垃圾回收说起（上篇）(代码片段)

关键词：

本文来自网易云社区

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 = true
        push(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 = true
        push(newobj,$mark_stack)
    
    *field = newobj

即如果新引用的对象是白色对象，则直接把它涂为灰色：

mark和mark termination的伪代码为：

incremental_mark_phase()    for(i : 1...MARK_MAX)        // 分多次mark，不需要STW
        if(is_empty($mark_stack) == false)
            obj = pop($mark_stack)            for(child : children(obj))
                mark(*child)
            
        else            // mark termination，需要STW
            for(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_start
            return
        
    

3.1.3 sweep

sweep也是分多次的，增量式的回收垃圾，跟mutator交替运行。跟标记-清除算法的实现基本一致，也是需要遍历整个堆，将白色对象挂到空闲链表上，黑色对象取消mark标记。

3.1.4 分配新对象

从空闲链表分配。

3.2 golang为什么没有采用压缩算法和分代算法

有点高深，想深入了解的可以参考golang-nuts上面的讨论。

 

原文：从golang的垃圾回收说起（上篇）

网易云新用户大礼包：https://www.163yun.com/gift

本文来自网易云社区，经作者李岚清授权发布。

相关文章：
【推荐】 移动端推广APP防作弊机制之依我见
【推荐】 谈谈分布式Aggregation

从golang的垃圾回收说起（下篇）(代码片段)

文章来自网易云社区4Golang垃圾回收的相关参数4.1触发GCgc触发的时机：2分钟或者内存占用达到一个阈值（当前堆内存占用是上次gc后对内存占用的两倍，当GOGC=100时） # 表示当前应用占用的内存是上次GC时占用内存的两倍... 查看详情

从golang的垃圾回收说起（下篇）(代码片段)

文章来自网易云社区 4Golang垃圾回收的相关参数 4.1触发GC gc触发的时机：2分钟或者内存占用达到一个阈值（当前堆内存占用是上次gc后对内存占用的两倍，当GOGC=100时）  # 表示当前应用占用的内存是上次GC... 查看详情

golang垃圾回收器与标记清除算法(代码片段)

go垃圾回收器的主要关注点是低延迟，也就是说为了进行实时操作它会有短暂的暂停。另一方面，创建新对象然后使用指针操作存活对象是程序始终在做的事情，这个过程可能最终会创建出不会再被访问到的对象，... 查看详情

jvm技术专题垃圾回收认知和调优的“思南（司南）“「上篇」(代码片段)

优化目标与策略(Ergonomics)垃圾回收器、堆和运行时编译器默认选择G1(GarbageFirst)收集器GC线程的最大值受限于堆大小和可用的CPU资源初始堆空间（Xms）为物理内存的1/64最大堆空间（Xmx）为物理内存的1/4分层编译器&#x... 查看详情

聊聊javascript垃圾回收机制-v8引擎下的垃圾回收机制(代码片段)

引子从修真故事说起上文大概介绍了垃圾回收的机制和标记清除法的核心思路，接下来准备深入介绍下v8引擎里的垃圾回收算法。既然是算法类的介绍，那自然是比较枯燥的，如果想完全弄懂，可以收藏下来，多看几遍（!·_·!）... 查看详情

jvm技术专题性能调优之cms垃圾回收器「上篇」(代码片段)

...f1b;如果没有偶尔的不幸，幸运不会如此受人欢迎。CMS垃圾回收的6个重要阶段initial-mark初始标记（CMS的第一个STW阶段），标记GCRoot直接引用的对象，GCRoot直接引用的对象不多，所以很快。concurrent-mark并发标... 查看详情

golang垃圾回收和setfinalizer(代码片段)

golang自带内存回收机制--GC。GC通过独立的进程执行，它会搜索不再使用的变量，并释放。需要注意的是，进行GC会占用机器资源。GC是自动进行的。如果要手动进行GC，可以调用runtime.GC()函数，进行显式GC。SetFinalizer一个对象object... 查看详情

从c和c++内存管理来谈谈jvm的垃圾回收算法设计-下(代码片段)

从C和C++内存管理来谈谈JVM的垃圾回收算法设计-下引言基本概念对象GCROOTS垃圾回收常见算法标记清除优缺点引用计数优缺点部分标记清除算法优缺点复制算法优缺点多空间复制算法标记整理(标记压缩)优缺点分代设计HotSpot... 查看详情

从c和c++内存管理来谈谈jvm的垃圾回收算法设计-上(代码片段)

从C和C++内存管理来谈谈JVM的垃圾回收算法设计-上引言C内存模型malloc堆内存分配过程malloc为什么结合使用brk和mmapmalloc如何通过内存池管理Heap区域垃圾收集器引言本文想和大家来探讨一下JVM是如何对堆内存进行管理和垃圾... 查看详情

go语言入门——数组切片和映射(代码片段)

...loWorld太简单了。  1、简介 Go是什么？Go（又称Golang）是Google开发的一种静态强类型、编译型、并发型，并具有垃圾回收功能的编程 查看详情

从c和c++内存管理来谈谈jvm的垃圾回收算法设计-下(代码片段)

从C和C++内存管理来谈谈JVM的垃圾回收算法设计-下引言基本概念对象GCROOTS垃圾回收常见算法标记清除优缺点引用计数优缺点部分标记清除算法优缺点复制算法优缺点多空间复制算法标记整理(标记压缩)优缺点分代设计HotSpot... 查看详情

golang——垃圾回收gc

Go垃圾回收原理Golang源码探索(三)GC的实现原理引用计数：对每个对象维护一个引用计数，当引用该对象的对象被销毁时，引用计数减1，当引用计数器为0是回收该对象。优点：对象可以很快的被回收，不会出现内存耗尽或达到某... 查看详情

<jvm上篇：内存与垃圾回收篇;11-垃圾回收概述及算法

垃圾回收概述及算法笔记来源：尚硅谷JVM全套教程，百万播放，全网巅峰（宋红康详解java虚拟机）同步更新：https://gitee.com/vectorx/NOTE_JVMhttps://codechina.csdn.net/qq_35925558/NOTE_JVMhttps://github.com/uxiahnan/NOTE_JVM目录11.垃圾回收概述及算法11... 查看详情

java垃圾回收机制详解(代码片段)

前言Java相比C/C++最显著的特点便是引入了自动垃圾回收(下文统一用GC指代自动垃圾回收)，它解决了C/C++最令人头疼的内存管理问题，让程序员专注于程序本身，不用关心内存回收这些恼人的问题，这也是Java能大行其道的重要原... 查看详情

自动的内存管理系统实操手册——golang垃圾回收篇

导语 | 现代高级编程语言管理内存的方式分自动和手动两种。手动管理内存的典型代表是C和C++，编写代码过程中需要主动申请或者释放内存；而PHP、Java和Go等语言使用自动的内存管理系统，由内存分配器和垃... 查看详情

详解python的垃圾回收机制(代码片段)

python的垃圾回收机制一、引子我们定义变量会申请内存空间来存放变量的值，而内存的容量是有限的，当一个变量值没有用了（简称垃圾）就应该将其占用的内存空间给回收掉，而变量名是访问到变量值的唯一方式，所以当一个... 查看详情

垃圾回收与对象的引用(代码片段)

垃圾回收当程序创建对象、数组等引用类型实体时，系统就会在对内存中为之分配一块内存区，对象就保存在这块内存区中，当这块内存不再被任何引用变量引用时，这块内存就变成垃圾，等待垃圾回收机制进行回收。垃圾回收... 查看详情

jvm之垃圾回收器(代码片段)

1、GC分类与性能指标1.1、垃圾回收器概述垃圾收集器没有在规范中进行过多的规定，可以由不同的厂商、不同版本的JVM来实现。由于JDK的版本处于高速迭代过程中，因此Java发展至今已经衍生了众多的GC版本。从不同角度... 查看详情