Google工程师教你编写垃圾回收器

伯乐在线补充:本文作者 Bob Nystrom 是 Google Dart 团队的一名工程师,所以下文中”处理一些工作上的事情“中的链接是指向了 Dart 官网。Bob 之前(曾在 EA 公司)做过游戏开发,UI 设计。更多信息,请看他的简历


每当我倍感压力以及有很多事情要做的时候,我总是有这样一种反常的反应,那就是希望做一些其他的事情来摆脱这种状况。通常情况下,这些事情都是些我能够编写并实现的独立的小程序。

一天早上,我几乎要被一堆事情给整疯了——我得写我那本《游戏编程模式》、处理一些工作上的事情、还要准备一场Strange Loop的演讲,然后这时我突然想到:“我该写一个垃圾回收器了”。

是的,我知道那一刻让我看上去有多疯狂。不过我的神经故障却是你实现一段基础的程序语言设计的免费教程!在100行左右毫无新意的 C 代码中,我设法实现一个基本的标记和扫描模块。

有人认为,垃圾回收好比是有更多鲨鱼出没的危险水域,但在这篇文章中,我会给你一个漂亮的儿童游泳池去玩耍。可能这里面仍然会有一些坑,但至少这是一个浅水区。

 

精简、复用、再复用

垃圾回收背后有这样一个基本的观念:编程语言(大多数的)似乎总能访问无限的内存。而开发者可以一直分配、分配再分配——像魔法一样,取之不尽用之不竭。

当然,我们从来都没有无限的内存。所以计算机实现回收的方式就是当机器需要分配一些内存,而内存又不足时,让它回收垃圾

“垃圾(Garbage)”在这里表示那些事先分配过但后来不再被使用的内存。而基于对无限内存的幻想,我们需要确保“不再被使用”对于编程语言来说是非常安全的。要知道在你的程序试图访问一些随机的对象时它们却刚好正在得到回收,这可不是一件好玩的事情。

为了实现回收,编程语言需要确保程序不再使用那个对象。如果该程序不能得到一个对象的引用,那么显然它也不会再去使用它。所以关于”in use”的定义事实上非常简单:

  1. 任何被一个变量引用的对象,仍然在作用域内,就属于”in use”状态。
  2. 任何被另一个对象引用的对象,仍在使用中,就是”in use”状态。

如果对象A被一个变量引用,而它又有一些地方引用了对象B,那么B就是在使用中(“in use”),因为你能够通过A来访问到它。

这样到最后的结果就是得到一张可访问的对象图——以一个变量为起点并能够遍历到的所有对象。任何不在图中的对象对于程序来说都是死的,而它的内存也是时候被回收了。

 

标记并清理

有很多不同的方法可以实现关于查找和回收所有未被使用的对象的操作,但是最简单也是第一个被提出的算法就是”标记-清除”算法。它由John McCarthy——Lisp(列表处理语言)的发明者提出,所以你现在做的事情就像是与一个古老的神在交流,但希望你别用一些洛夫克拉夫特式的方法——最后以你的大脑和视网膜的完全枯萎而结束。

该算法的工作原理几乎与我们对”可访问性(reachability)”的定义完全一样:

  1. 从根节点开始,依次遍历整个对象图。每当你访问到一个对象,在上面设置一个”标记(mark)”位,置为true。
  2. 一旦搞定,找出所有标记位为”not”的对象集,然后删除它们。

对,就是这样。我猜你可能已经想到了,对吧?如果是,那你可能就成为了一位被引用了数百次的文章的作者。所以这件事情的教训就是,想要在CS(计算机科学)领域中出名,你不必开始就搞出一个很牛的东西,你只需要第一个整出来即可,哪怕这玩意看上去很搓。

 

对象对

在我们落实这两个步骤之前,让我们先做些不相关的准备工作。我们不会为一种语言真正实现一个解释器——没有分析器,字节码、或任何这种愚蠢的东西。但我们确实需要一些少量的代码来创建一些垃圾去回收。

让我们假装我们正在为一种简单的语言编写一个解释器。它是动态类型,并且有两种类型的变量:int 和 pair。 下面是用枚举来标示一个对象的类型:

其中,pair可以是任何一对东西,两个int、一个int和另一个pair,什么都可以。随你怎么想都行。因为一个对象在虚拟机中可以是这两个当中的任意一种类型,所以在c中实现对象的典型方法是时用一个标记联合体(tagged union)。

这个Object结构拥有一个type字段表示它是哪种类型的值——要么是int要么是pair。接下来用一个union来持有这个int或是pair的数据。如果你对c语言很生疏,一个union就是一个结构体,它将字段重叠在内存中。由于一个给定的对象只能是int或是pair,我们没有任何理在一个单独的对象中同时为所有这3个字段分配内存。一个union就搞定。帅吧。

 

小虚拟机

现在我们可以将其包装在一个小的虚拟机结构中了。它(指虚拟机)在这里的角色是用一个栈来存储在当前作用域内的变量。大多数语言虚拟机要么是基于栈(如JVM和CLR)的,要么是基于寄存器(如Lua)的。但是不管哪种情况,实际上仍然存在这样一个栈。它用来存放在一个表达式中间需要用到的临时变量和局部变量。

我们来简洁明了地建立这个模型,如下:

现在我们得到了一个合适的基本数据结构,接下来我们一起敲些代码来创建些东西。首先,我们来写一个方法创建并初始化一个虚拟机:

一旦我们得到了虚拟机,我们需要能够操作它的堆栈:

好了,现在我们能敲些玩意到”变量”中了,我们需要能够实际的创建对象。首先来一些辅助函数:

它实现了内存的分配和设置类型标记。我们一会儿会重温它的。利用它,我们可以编写方法将每种类型的对象压到虚拟机的栈上:

这就是我们的小小虚拟机。如果我们有调用这些方法的解析器和解释器,那我们手上就有了一种对上帝都诚实的语言。而且,如果我们有无限的内存,它甚至能够运行真正的程序。可惜咱们没有,所以让我们来回收些垃圾吧。

 

标记

第一个阶段就是标记(marking)。我们需要扫遍所有可以访问到的对象,并设置其标志位。现在我们需要做的第一件事就是为对象添加一个标志位(mark bit):

一旦我们创建了一个新的对象,我们将修改newObject()方法初始化marked为0。为了标记所有可访问的对象,我们从内存中的变量入手,这样就意味着要扫一遍堆栈。看上去就像这样:

里面又调用了mark。我们来分几步搭建它。第一:

毫无疑问,这是最重要的一点。我们标记了这个对象自身是可访问的,但记住,我们还需要处理对象中的引用:可访问性是递归的。如果该对象是一个pair,它的两个字段也是可访问的。操作很简单:

但是这里有一个bug。你看到了吗?我们正在递归,但我们没有检查循环。如果你有一堆pair在一个循环中相互指向对方,这就会造成栈溢出并崩溃。

为了解决这个情况,我们仅需要做的是在访问到了一个已经处理过的对象时,退出即可。所以完整的mark()方法应该是:

现在我们可以调用markAll()方法了,它会准确的标记内存中所有可访问的对象。我们已经成功一半了!

 

清理

下一个阶段就是清理一遍所有我们已经分配过(内存)的对象并释放那些没有被标记过的(对象)。但这里有一个问题:所有未被标记的对象——我们所定义的——都不可达!我们都不能访问到它们!

虚拟机已经实现了对象引用的语义:所以我们只在变量和pair元素中储存指向对象的指针。当一个对象不再被任何指针指向时,那我们就完全失去它了,而这也实际上造成了内存泄露。

解决这个问题的诀窍是:虚拟机可以有它自己的对象引用,而这不同于对语言使用者可读的那种语义。换句话说,我们自己可以保留它们的痕迹。

这么做最简单的方法是仅维持一张由所有分配过(内存)的对象(组成)的链表。我们在这个链表中将对象自身扩展为一个节点:

虚拟机会保留这个链表头的痕迹:

在newVM()方法中我们确保将firstObject初始化为NULL。无论何时创建一个对象,我们都将其添加到链表中:

这样一来,即便是语言找不到一个对像,它还是可以被实现。想要清理并删除那些未被标记的对象,我们只需要遍历该链表:

这段代码读起来有点棘手,因为那个指针(指object)指向的是一个指针,但是通过它的工作你会发现它还是非常简单的。它只是扫遍了整张链表。只要它碰到了一个未被标记的对象,它就会释放该对象的内存并将其从链表中移除。最后,我们将会删除所有不可访问的对象。

祝贺你!我们已经有了一个垃圾回收器!现在只剩下一点工作了:实际调用它!首先我们将这两个阶段整合在一起:

没有比这更明显的”标记-清除”算法了。现在最棘手的是搞清楚什么时候来实际调用它。”内存不足(low on memory)”是个什么意思?尤其是对于现在的计算机,它们几乎拥有无限的虚拟内存!

事实证明,我们没有完全正确或错误的答案。这真的取决于你使用虚拟机的目的以及让它运行在什么样的硬件上。为了让这个例子看上去很简单,我们仅在进行了一定数量的内存分配之后开始回收。事实上一些语言的实现就是这么做的,而这也很容易。

我们将邀请虚拟机来追踪我们到底创建了多少(对象):

接下来,初始化:

其中,INITIAL_GC_THRESHOLD为你启动第一个GC(垃圾回收器)的对象数量。较小的值会更节省内存,而较大的值则更省时。自己看着办吧。

每当我们创建一个对象,我们增加numObjects,如果它达到最大值就启动一次回收:

我不会费心的显示它(指numObjects),但是我们也会稍微调整sweep()方法,每释放一次就递减numObjects。最后,我们修改了gc()方法来更新最大值:

每次回收之后,我们更新maxObjects——以进行回收后仍在活动的对象为基准。乘法器让我们的堆随着活动中的对象数量的增加而增加。同样,也会随着一些对象最终被释放掉而自动减少。

 

最后

你成功了!如果你全部照做了,那你现在已经理解了一个简单的垃圾回收算法。如果你想看完整的代码,在这里。我再强调一点,尽管这个回收器很简单,但它可不是一个玩具。

你可以在这上面做一大堆的优化(像在GC和程序设计语言这些事情中,90%的努力都在优化上),但它的核心代码可是真正的GC。它与目前Ruby和Lua中的回收器非常的相似。你可以使用一些类似的代码到你的项目中。去做些很酷的事情吧!

1 9 收藏 29 评论

关于作者:deathmonkey

(新浪微博:@deathmonkey) 个人主页 · 我的文章 · 2

相关文章

可能感兴趣的话题



直接登录
最新评论
  • kewei   2013/12/19

    高手! 獲益良多,給跪了

  • 应该是所有 html的左右括号转义都没处理好

  • fh   2013/12/19

    希望向大家请教两个问题:
    1. pair类型在C中可参照的类型是什么啊?
    2.sweep()函数中第10行:*object = unreached->next;与第object = &(*object)->next;行两种写法的目的有什么本质不同吗?

    • yan   2013/12/21

      关于第二个问题:
      *object = unreached->next; 是修改当前节点的值,此时*object是开头节点或者上一个节点的next字段。因为要释放*object了,所以要提前把节点指向当前的下一个。
      object = &(*object)->next; 这个只是把指针指向下一个,不修改链表。

      这个是链表操作中经常用到的。如果回答错误,联系我。我一直这么认为的。

    • zzl   2013/12/21

      1. C语言中没有内置的pair类型,pair类型主要是在Lisp类语言中,就是文中说的John McCarthy发明的语言。

      2. 你最好画个图看看,
      *object = unreached->next; 是改变了object指针指向的值,文中就相当于从链表中删除了一个未标记结点。

      object = &(*object)->next; 相当于 object = &((*object)->next); 是改变object变量的值,文中意思就是object遍历到下一个结点。

      • susershine   2013/12/22

        *object = unreached->next;不代表从链表中删除了一个未标记节点吧。它应该是表示下个循环是从unreached->next开始的。如果是删除节点还需要用当前*object的前一个节点的next指针指向当前*object的next指针指向的节点,才是删除链表中的节点。如文中所写的方法,在一次遍历链表后,下次再遍历链表时就会出现状况了。

        而且Object** object = &vm->firstObject;为什么要用指向指针的指针呢?换做普通的指针,Object* object = vm->firstObject;然后对下面的代码稍作修改,也能实现链表的遍历和删除节点的,一般的链表貌似都是这样做的。

  • pandes   2013/12/21

    谢谢分享

  • 吸收了,谢谢!

  • zhenghuiwin   2013/12/21

    翻译上需要纠正的地方:
    "我得看一本书",原文是:“ the book I’m working on”,作者想表述的是他正在写一本书,不是在看书,此文中那个“书”的超链接内容正是作者正在写的书。

  • lsccl   2013/12/22

    不明觉厉

  • 叶敏   2013/12/22

    不是很明白,这个pushPair()函数是什么时候调用呢?

    • crawlman   2013/12/24

      按照作者的意思,应该是先push这个Pair的两个域,再执行这个push方法,push这个Pair。

  • 很不错 收藏了

  • zkx928   2013/12/24

    mark !~

  • keg   2013/12/26

    Garbage collection is considered one of the more shark-infested waters of programming, but in this post, I’ll give you a nice kiddie pool to paddle around in. (There may still be sharks in it, but at least it will be shallower.) -> 垃圾收集被认为是有更多编程牛人出没的水域之一,但在这里,我会给你一个漂亮的儿童游泳池去玩耍。可能这里面仍然会有一些能手,但至少这会是一个浅水区。 ???
    这里 Shark 就是鲨鱼,意译的话比较接近于 “坑” 。

    • 黄利民 站长 2013/12/27

      谢谢建议,已修改。

      > 有人认为,垃圾收集好比是有更多鲨鱼出没的危险水域,但在这篇文章中,我会给你一个漂亮的儿童游泳池去玩耍。可能这里面仍然会有一些坑,但至少这是一个浅水区。

  • object->tail = pop(vm);
    object->head = pop(vm);
    pushPair函数中这两句话是干嘛的?

    • niannian   2014/01/07

      把之前的两个int型的object放到pair里,没学过lisp, 估计是lisp的思想。

  • hshqcn   2014/01/08

    翻译的比较生硬,举个例子:

    If you followed all of this, you’ve now got a handle on a simple garbage collection algorithm.
    如果你全部照做了,那你现在已经得到了一个简单的垃圾收集算法的句柄。
    =》
    读着不顺,查了下词典,get a handle on是个短语,”理解、掌握、上手“。

    I won’t bother showing it, but we’ll also tweak sweep() to decrement numObjects every time it frees one.
    我不会费心的显示它(指numObjects),但是我们也会稍微调整sweep()方法,每释放一次就递减numObjects。
    =》
    it应该是指tweak后的sweep函数,你的看法不通。

  • 弱弱的问一句,这种垃圾回收的方式难道不是建立在分配内存的人自己失误的前提下吗?是因为这是给动态语言用的?

    • Pynix   2014/06/20

      有了gc,你的对象就只管创建,不用管释放,比如c++没有gc,你要new 要delete,new了没有del的话就是内存泄漏。java只管new,不管del。

  • 这东西还要push之后自己pop?那和malloc之后free有啥区别?

跳到底部
返回顶部