垃圾回收算法笔记
一、标记清除：
分为两个阶段：标记阶段和清除阶段；从根节点标记所有未被引用的垃圾对象，然后清除阶段删除。
优点：
- 存活对象较多的情况下高效
- 适用于年老代
- 实现简单， 容易和其他算法组合
缺点：
- 容易产生内存碎片
- 分配速度不理想，每次分配都需要遍历空闲列表找到足够大的分块
- 与写时复制技术不兼容，因为每次都会在活动对象上打上标记
- 大量的内存碎片会导致大对象分配时可能失败，从而提前触发了另一次垃圾回收动作
- 具有引用关系的对象可能会被分配在堆中较远的位置，这会增加程序访问所需的时间，即「访问的局部性（Locality）」较差。
二、复制算法：
从根节点扫描，标记所有存活对象，并且复制到新的内存，回收旧内存。现在的商业虚拟机都采用这种收集算法来回收新生代。
优点：
- 存活对象比较少的情况下高效
- 良好的局部性
- 不会发生碎片化
- 适用于年轻代（即新生代）：基本98%的对象都是“朝生夕死”
缺点：
- 最多只能使用一半的堆空间，因此堆的使用率不高；
- 需要一块空的内存空间；需要复制移动对象；
三、标记压缩
标记压缩算法是一种老年代的回收算法，它在标记清除算法的基础上做了一些优化。从根节点对所有可达对象做一次标记，然后将存活的对象压缩到内存的一段，之后清理边界空间。
优点：
- 这种算法避免了碎片产生
- 也不需要两块相同的内存空间
缺点：
- 压缩的过程需要多次搜索
四、分代收集算法
分代收集算法是目前JVM虚拟机使用的回收算法。它将内存分为各个年代。一般情况下将堆区划分为老年代和新生代，在堆区之外还有一个代就是永久代。
在不同的代使用不同的算法，从而使用最适合的算法。
- 新生代 = 生成空间 + 2 * 幸存区 复制算法
- 老年代 标记-清除算法
五、引用计数
引用计数，就是记录每个对象被引用的次数，每次新建对象、赋值引用和删除引用的同时更新计数器，如果计数器值为0则直接回收内存。
优点：
- 可即可回收垃圾
- 最大暂停时间短
缺点：
- 计数器的增删处理重，除了数量多，而且在删除容器的时候，需要遍历所有的对象修改引用计数。
- 计数器需要占用很多空间
- 循环引用无法回收
六、增量式GC
将GC的阻塞任务拆分成少量多次，减少暂停用户程序的执行。
三色标计算法：
- 白色：还未搜索过的对象
- 灰色：正在搜索的对象
- 黑色：搜索完成的对象
三色过程：
- 根查找阶段：对能直接引用的对象打上标记，堆放到标记栈里
- 标记阶段：从标记栈中取出对象，将其子对象涂成灰色；这个阶段不是一下子处理所有的灰色对象；
- 清除阶段：将没被标记的白色连接到空闲链表，并重置已标记的对象标记。
读屏障和写屏障
原因：
- 多标：在对象被标记为灰色之后，父节点解除了引用关系，那本来应该被删除的对象就会被延迟删除；
- 漏标：在对象被标记之后，对象断开子节点A同时A被父节点引用，但父节点已经被标记为黑色，不会再重新访问，因此A节点会被标记成白色删除，这是不可接受的。
漏标的充分必要条件是：
- 应用线程插入了一个从黑色对象（A）到白色对象（E）的新引用。
- 应用线程删除了从灰色对象（C）到白色对象（E）的直接或者间接引用。
避免漏标打破上述任何一个条件即可：
- 这里在第一个条件触发时增加写屏障，修改黑色或者白色为灰色；并且在渐进式GC里对白色对象触发度屏障。
- 第二个条件触发写屏障，当删除关系时触发写屏障，将这些关系都记录下来，最后重新扫一次。
优点：缩短最大暂停时间
缺点：降低了吞吐量
JVM垃圾回收有两种类型：Minor GC和Full GC。
Minor GC
只回收新生代，这里非常频繁且对象大多数死亡频繁，所以选择速度快效率高的算法。
Full GC
对整个堆进行回收，包括新生代和老年代，所以比Minor GC要慢，应该尽可能减少Full GC的次数。
python垃圾回收
python分配<512btype的内存时使用内存池，释放时不会还给系统；分配>512字节的对象时会直接使用C的allocate分配和管理。
标准CPython实现的垃圾收集器有两部分组件构成，一部分为引用计数模块(reference counting collector), 另一部分为分代垃圾回收器(generational garbage collector)。
引用计数是本意，但是无法处理循环引用，所以补充了分代垃圾回收器。
有三种情况会触发垃圾回收：
- 调用gc.collect(),需要先导入gc模块。
- 当gc模块的计数器达到阀值的时候。
- 程序退出的时候。
当循环引用的两个对象都有del时，python不知道先调用哪个导致不会释放，把它们标记为：uncollectable。
这个方法涉及到之前说过的分代回收的策略。python中默认把所有对象分成三代。第0代包含了最新的对象，第2代则是最早的一些对象。在一次垃圾回收中，所有未被回收的对象会被移到高一代的地方。
gc.get_threshold()
这个方法返回的是(700,10,10)，这也是gc的默认值。这个值的意思是说，在第0代对象数量达到700个之前，不把未被回收的对象放入第一代；而在第一代对象数量达到10个之前也不把未被回收的对象移到第二代。可以是使用gc.set_threshold(threashold0,threshold1,threshold2)来手动设置这组阈值。
Unreal GC
虚幻的GC挺复杂的，因为虚幻本身提供了一套非常复杂且自由的系统。
只看UObject类的话就会简单一些，它是Unreal的基础类，它使用的是标记-清除算法，而不是传统类似于shared_ptr这样的引用计数。
学习文档：
https://aijishu.com/a/1060000000080557
https://www.jianshu.com/p/a8a04fd00c3c
https://developer.aliyun.com/article/777750
https://zhuanlan.zhihu.com/p/83251959
https://dreamgoing.github.io/Python%E5%9E%83%E5%9C%BE%E5%9B%9E%E6%94%B6.html