Golang GC 三色标记
v1.3以前：STW
在Go语言1.3之前，Go的垃圾回收过程采用了一个称为STW（Stop-The-World）的方法。这意味着在进行垃圾回收时，所有的Go协程都会被停止，直到垃圾回收完成。这种方式可能会导致程序在垃圾回收期间出现短暂的停顿，影响了程序的响应性能。
垃圾回收的过程主要包括以下几个步骤：
标记（Marking）：从根对象（如全局变量、活动栈、寄存器等）开始，通过一种深度优先搜索算法，标记所有可以访问到的对象为活动对象（live objects）。
清扫（Sweeping）：遍历堆内存，将未被标记的对象回收，释放它们所占用的内存。
压缩（Compaction）：对堆内存进行压缩，使得已回收的内存空间连续起来，以便后续的内存分配能够更加高效。
这个垃圾回收过程在1.3版本之前主要是通过暂停整个应用程序来执行的，因此在大型应用程序中可能会导致较长的停顿时间，对于对实时性要求较高的应用程序可能会有影响。
v1.3：Mark STW & Sweep
1.3版本中，go runtime分离了mark和sweep操作，和以前一样，也是先暂停所有任务执行并启动mark，mark完成后马上就重新启动被暂停的任务了，而是让sweep任务和普通协程任务一样并行的和其他任务一起执行。如果运行在多核处理器上，go会试图将gc任务放到单独的核心上运行而尽量不影响业务代码的执行。go team自己的说法是减少了50%-70%的暂停时间。
v1.5：三色标记算法
三色标记算法（也称为Tri-Color Marking Algorithm）是一种用于垃圾回收的算法，通常用于实现并发标记-清除垃圾回收器。该算法通过将对象标记为三种颜色（通常是白色、灰色和黑色）来跟踪对象的可达性，并在标记过程中处理引用的变化。
它将对象分为三种颜色表示，分别是白色、灰色和黑色。 白色（White）：表示对象尚未被访问或标记。在初始标记之前，所有的对象通常都是白色的。在初始标记后，白色对象可能被标记为灰色或黑色。
灰色（Gray）：表示对象已经被发现，但其引用的其他对象尚未被遍历。换句话说，灰色对象的引用链路尚未完全探索。在追踪阶段，会从灰色对象开始继续探索其引用的其他对象，并将这些对象标记为灰色。一旦所有引用的对象都被遍历，灰色对象就会被标记为黑色。
黑色（Black）：表示对象已经被完全探索，即其引用的所有其他对象都已经被遍历过，并且它们的可达性已经确定。黑色对象是被保证是可达的，不会被垃圾回收器回收。一旦对象变为黑色，它就会保持这种状态，直到下一次垃圾回收过程。
- 初始化: 算法开始前，将所有的对象标记为白色（表示未访问）。
- 根节点标记: 从程序的根节点开始，例如全局变量、活跃线程的栈、寄存器等，将这些根节点指向的对象标记为灰色（表示待访问）。
- 标记阶段: 不断地从灰色对象集合中取出一个对象进行标记，然后遍历该对象引用的其他对象。对于每个被引用的对象：
- 如果该对象是白色的，则将其标记为灰色，并将其加入灰色对象集合。
- 如果该对象已经是灰色或黑色的，则不需要做任何操作。
- 标记结束: 当灰色对象集合为空时，标记阶段结束。
- 清除阶段: 遍历所有对象，将未标记的对象（即白色的对象）视为垃圾，进行回收或其他处理。同时，将所有标记为灰色的对象重新标记为黑色（表示已访问）。
- 结束: 清除阶段完成后，垃圾回收器的工作完成，可以继续应用程序的执行。
三色标记算法（Three-color marking algorithm）通常用于垃圾回收（Garbage Collection）中，特别是在分代垃圾回收中。该算法使用三种不同的颜色来标记内存中的对象，以区分它们的状态。通常情况下，这三种颜色是白色（White）、灰色（Gray）和黑色（Black）。以下是三色标记算法的一般步骤：
初始标记（Initial Marking）：
- 从根对象开始，遍历对象图，将根对象及其直接可达的对象标记为灰色。这些根对象通常是程序中已经被直接引用的对象。
- 将已标记的对象从灰色变为黑色。
追踪（Tracing）：
- 从灰色对象的集合中取出一个对象，并遍历该对象引用的其他对象。
- 对于每个被引用的对象，检查其颜色：
- 如果对象为白色，则将其标记为灰色，并加入灰色集合中。
- 如果对象为黑色，则忽略，因为它已经被完全探索过了。
- 如果对象为灰色，则说明已经被标记过，无需重复操作。
并发标记（Concurrent Marking）：
- 在程序运行的同时，可能会有新的对象被创建或引用关系发生变化，因此需要在追踪的同时保证对象的一致性标记。这通常需要一些并发标记的技术来实现。
终止标记（Termination Marking）：
- 等待并发标记结束后，执行终止标记操作，确保所有的对象都被正确标记。
- 此阶段通常需要停止程序的执行，以确保所有对象都被正确地标记。
清除（Sweeping）：
- 遍历整个堆，将未被标记的对象视为垃圾，进行回收或重用。
- 将被标记的对象重新变回白色，以便下一次垃圾回收。
通过以上步骤，三色标记算法可以在进行垃圾回收时有效地标记和识别可达对象，并将未使用的对象回收，从而释放内存空间，提高程序的性能和效率。
最开始所有对象都是白色的，然后把其中全局变量和函数栈里的对象置为灰色。 第二步把灰色的对象全部置为黑色，然后把原先灰色对象指向的变量都置为灰色，以此类推。等发现没有对象可以被置为灰色时，所有的白色变量就一定是需要被清理的垃圾了。
三色标记法因为多了一个白色的状态来存放不确定的对象，所以可以异步地执行。当然异步执行的代价是可能会造成一些遗漏，因为那些早先被标记为黑色的对象可能目前已经是不可达的了。所以三色标记法是一个 false negative（假阴性）的算法。
在过去几年里，Go语言的垃圾收集器（GC）确实经历了一些重大变化，但是我的前述回答可能并未全面涵盖所有的演变。实际上，对于每个版本的Go语言，GC都可能经历了一些微调和改进。以下是对Go语言GC发展历程的更全面描述：
Go 1.0 - 1.4：标记-清除（Mark and Sweep）GC
- Go语言最初的版本使用了标记-清除的垃圾收集算法。
Go 1.5：引入并发标记（Concurrent Marking）
- Go 1.5引入了并发标记，这是一项重大改进，它允许垃圾收集器在程序继续运行的同时进行标记，以减少停顿时间。
Go 1.6 - 1.7：调整和优化
- 在这些版本中，GC经历了一些调整和优化，以提高性能和稳定性。例如，在Go 1.6中，引入了“shrinkstack”机制来减少栈的大小，从而减少了垃圾收集的负担。
Go 1.8：引入并发清理（Concurrent Sweeping）
- Go 1.8进一步改进了GC，引入了并发清理，以减少垃圾收集的停顿时间。
Go 1.9 - 1.10：性能和稳定性改进
- 在这些版本中，GC的性能和稳定性得到了改进，包括更好的内存回收和更低的停顿时间。
Go 1.11：引入基于写屏障的垃圾收集（GC with Write Barriers）
- 引入了基于写屏障的垃圾收集，通过这一技术，GC能够更准确地跟踪指针的写入操作，提高了GC的效率。
Go 1.12：引入增量标记（Incremental Marking）
- Go 1.12中引入了增量标记，以进一步降低GC的停顿时间。
Go 1.13：引入并行标记（Parallel Marking）
- 引入了并行标记，允许在多个CPU核心上并行进行标记过程，提高了GC的性能。
Go 1.14 - 1.16：继续优化和改进
- 在这些版本中，GC持续进行了优化和改进，包括引入了堆拆分、并行清理、调整单元大小的GC等技术，以进一步提高性能、降低延迟并减少内存占用。
综上所述，Go语言的GC在过去几年里经历了多次重大改进和优化，以提高性能、降低延迟，并更好地适应不同类型的工作负载。
