算法|漫画 | 垃圾回收实在是太垃圾了！
1960年，人工智能之父 John McCarthy 在麻省理工大学做了一次重要演示
文章图片
文章图片
Lisp的担心很快就变成了现实
文章图片
垃圾回收虽然在卖力工作，可是系统还是恢复不了。
文章图片
【算法|漫画 | 垃圾回收实在是太垃圾了！】
文章图片
在编程的世界中，内存分配每时每刻都在发生，从底层来讲，可以分为三类。
文章图片
而Lisp中所有的数据都是“表”（List），都是在堆中动态分配的，如果它不支持GC，程序员管理表（List）估计就会疯掉。
为此， John McCarthy于1960年发表了一篇论文，提出了标记-清除算法。
算法分为两个阶段， 第一个阶段是标记， 从一个GC root集合出发，沿着“指针”找到所有活动对象
文章图片
到了清除阶段，只需要把那些没有被标记的对象删除，释放空间就行。
文章图片
标记-清除算法非常简单，容易实现，现在垃圾收集算法都是它的思想的延续。
仅此一点，McCarthy就可以成为GC算法之父。
文章图片
可是标记-清除算法也有两个要命的缺点：分配速度慢，容易产生碎片。
文章图片
为了解决这个问题， 1963年， 另外一位人工智能之父”的Marvin L. Minsky提出了著名的复制算法。
文章图片
Minsky 的复制算法需要把整个空间平均分成两部分， 先在From空间进行分配，当From空间被占满，GC将活动对象复制到To空间， 复制完成后， From和To进行互换。
文章图片
复制算法的第一步也是标记，但是找到活动对象以后，直接复制到另一半空间，所以能在较短时间内完成GC。
并且每次复制的时候，对象都会集中，避免碎片。
文章图片
标记-清除算法和复制算法优缺点都非常明显。
1960年， George E. Collins独辟蹊径，提出了一个新的GC算法：引用计数
文章图片
当时Collins可能没有注意到，引用计数法有个缺点，就是它不能回收“循环引用”
文章图片
至此， 垃圾收集技术的三大算法已经集齐，GC根本性的内容已经完成。后人只是在GC大厦上修修补补罢了。
文章图片
三位GC大佬说得没错，1970年出现的标记-压缩算法就是标记-清除和复制算法结合的产物。
文章图片
标记压缩算法工作起来是这样的：
文章图片
标记-压缩看起来和复制算法很像，但是算法实现要复杂得多
文章图片
后来人们又发现：大部分对象的生存期限很短，生下来不久就变成垃圾
文章图片
于是把对象进行分代，对不同的分代实施不同的垃圾收集算法
文章图片
几十年过去了， 垃圾回收技术不断完善， 计算机的性能也越来越高。
Lisp曾经遭遇的GC尴尬不会再出现了，GC逐渐成了编程语言的标配。
文章图片
文章图片
当然， 还有些编程语言在坚守，因为他们承担着更重要的使命。
文章图片
GC把程序员从内存管理中解放出来，世界上没有免费的午餐，付出的代价就是多了虚拟机/解释器这一层额外的开销。
也许有这么一天，程序员既不需要操心内存空间的管理，又可以充分发挥硬件的效率，期望这一天能够来临。
嗯， 这一天其实已经来了，它就是Z语言， 参见《Z语言传奇》
（完）
点击下方图片，查看更多文章吧 ！
文章图片
文章图片
文章图片
文章图片
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 漫画初学者如何学习漫画背景的透视画法（这篇教程请收藏好了！）
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- 随笔（二）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列