资讯频道 → 编程语言
阅读更多

2顶
0踩

编程语言

转载新闻 Google工程师教你编写垃圾回收器

2015-08-12 16:16 by 正式记者 黑客不黑 评论(2) 有6833人浏览
Google Java 虚拟机
本文由伯乐在线 - deathmonkey翻译
英文出处：Bob Nystrom

本文作者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。 下面是用枚举来标示一个对象的类型： 
typedef enum {
  OBJ_INT,
  OBJ_PAIR
} ObjectType;

其中，pair可以是任何一对东西，两个int、一个int和另一个pair，什么都可以。随你怎么想都行。因为一个对象在虚拟机中可以是这两个当中的任意一种类型，所以在c中实现对象的典型方法是时用一个标记联合体(tagged union)。 
typedef struct sObject {
  ObjectType type;
 
  union {
    
/* OBJ_INT */
    int value;
 
    
/* OBJ_PAIR */
    struct {
      struct sObject* head;
      struct sObject* tail;
    };
  };
} Object;

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

小虚拟机

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

我们来简洁明了地建立这个模型，如下： 
#define STACK_MAX 256
 
typedef struct {
  Object* stack[STACK_MAX];
  int stackSize;
} VM;

现在我们得到了一个合适的基本数据结构，接下来我们一起敲些代码来创建些东西。首先，我们来写一个方法创建并初始化一个虚拟机： 
VM* newVM() {
  VM* vm = malloc(sizeof(VM));
  vm->stackSize = 0;
  return vm;
}

一旦我们得到了虚拟机，我们需要能够操作它的堆栈： 
void push(VM* vm, Object* value) {
  assert(vm->stackSize < STACK_MAX, "Stack overflow!");
  vm->stack[vm->stackSize++] = value;
}
 
Object* pop(VM* vm) {
  assert(vm->stackSize > 0, "Stack underflow!");
  return vm->stack[--vm->stackSize];
}

好了，现在我们能敲些玩意到”变量”中了，我们需要能够实际的创建对象。首先来一些辅助函数： 
Object* newObject(VM* vm, ObjectType type) {
  Object* object = malloc(sizeof(Object));
  object->type = type;
  return object;
}

它实现了内存的分配和设置类型标记。我们一会儿会重温它的。利用它，我们可以编写方法将每种类型的对象压到虚拟机的栈上： 
void pushInt(VM* vm, int intValue) {
  Object* object = newObject(vm, OBJ_INT);
  object->value = intValue;
  push(vm, object);
}
 
Object* pushPair(VM* vm) {
  Object* object = newObject(vm, OBJ_PAIR);
  object->tail = pop(vm);
  object->head = pop(vm);
 
  push(vm, object);
  return object;
}

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

标记

第一个阶段就是标记(marking)。我们需要扫遍所有可以访问到的对象，并设置其标志位。现在我们需要做的第一件事就是为对象添加一个标志位(mark bit)： 
typedef struct sObject {
  unsigned char marked;
  
/* Previous stuff... */
} Object;

一旦我们创建了一个新的对象，我们将修改newObject()方法初始化marked为0。为了标记所有可访问的对象，我们从内存中的变量入手，这样就意味着要扫一遍堆栈。看上去就像这样： 
void markAll(VM* vm)
{
  for (int i = 0; i < vm->stackSize; i++) {
    mark(vm->stack[i]);
  }
}

里面又调用了mark。我们来分几步搭建它。第一： 
void mark(Object* object) {
  object->marked = 1;
}

毫无疑问，这是最重要的一点。我们标记了这个对象自身是可访问的，但记住，我们还需要处理对象中的引用：可访问性是递归的。如果该对象是一个pair，它的两个字段也是可访问的。操作很简单： 
void mark(Object* object) {
  object->marked = 1;
 
  if (object->type == OBJ_PAIR) {
    mark(object->head);
    mark(object->tail);
  }
}

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

为了解决这个情况，我们仅需要做的是在访问到了一个已经处理过的对象时，退出即可。所以完整的mark()方法应该是： 
void mark(Object* object) {
  
/* If already marked, we're done. Check this first
     
to avoid recursing on cycles in the object graph. */
  if (object->marked) return;
 
  object->marked = 1;
 
  if (object->type == OBJ_PAIR) {
    mark(object->head);
    mark(object->tail);
  }
}

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

清理

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

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

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

这么做最简单的方法是仅维持一张由所有分配过(内存)的对象(组成)的链表。我们在这个链表中将对象自身扩展为一个节点： 
typedef struct sObject {
  
/* The next object in the list of all objects. */
  struct sObject* next;
 
  
/* Previous stuff... */
} Object;

虚拟机会保留这个链表头的痕迹： 
typedef struct {
  
/* The first object in the list of all objects. */
  Object* firstObject;
 
  
/* Previous stuff... */
} VM;

在newVM()方法中我们确保将firstObject初始化为NULL。无论何时创建一个对象，我们都将其添加到链表中： 
Object* newObject(VM* vm, ObjectType type) {
  Object* object = malloc(sizeof(Object));
  object->type = type;
  object->marked = 0;
 
  
/* Insert it into the list of allocated objects. */
  object->next = vm->firstObject;
  vm->firstObject = object;
 
  return object;
}

这样一来，即便是语言找不到一个对像，它还是可以被实现。想要清理并删除那些未被标记的对象，我们只需要遍历该链表： 
void sweep(VM* vm)
{
  Object** object = &vm->firstObject;
  while (*object) {
    if (!(*object)->marked) {
      
/* This object wasn't reached, so remove it from the list
         
and free it. */
      Object* unreached = *object;
 
      *object = unreached->next;
      free(unreached);
    } else {
      
/* This object was reached, so unmark it (for the next GC)
         
and move on to the next. */
      (*object)->marked = 0;
      object = &(*object)->next;
    }
  }
}

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

祝贺你！我们已经有了一个垃圾回收器！现在只剩下一点工作了：实际调用它！首先我们将这两个阶段整合在一起： 
void gc(VM* vm) {
  markAll(vm);
  sweep(vm);
}

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

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

我们将邀请虚拟机来追踪我们到底创建了多少(对象)： 
typedef struct {
  
/* The total number of currently allocated objects. */
  int numObjects;
 
  
/* The number of objects required to trigger a GC. */
  int maxObjects;
 
  
/* Previous stuff... */
} VM;

接下来，初始化： 
VM* newVM() {
  
/* Previous stuff... */
 
  vm->numObjects = 0;
  vm->maxObjects = INITIAL_GC_THRESHOLD;
  return vm;
}

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

每当我们创建一个对象，我们增加numObjects，如果它达到最大值就启动一次回收： 
Object* newObject(VM* vm, ObjectType type) {
  if (vm->numObjects == vm->maxObjects) gc(vm);
 
  
/* Create object... */
 
  vm->numObjects++;
  return object;
}

我不会费心的显示它(指numObjects)，但是我们也会稍微调整sweep()方法，每释放一次就递减numObjects。最后，我们修改了gc()方法来更新最大值： 
void gc(VM* vm) {
  int numObjects = vm->numObjects;
 
  markAll(vm);
  sweep(vm);
 
  vm->maxObjects = vm->numObjects * 2;
}

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

最后

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

你可以在这上面做一大堆的优化（像在GC和程序设计语言这些事情中，90%的努力都在优化上），但它的核心代码可是真正的GC。它与目前Ruby和Lua中的回收器非常的相似。你可以使用一些类似的代码到你的项目中。去做些很酷的事情吧！
来自: 伯乐在线
2
顶
0
踩
评论 共 2 条 请登录后发表评论
2 楼 沙舟狼客 2015-08-13 18:28
看不懂....
1 楼 xlaohe1 2015-08-12 21:58
      mark.

发表评论

您还没有登录,请您登录后再发表评论

相关推荐

  • [转] Google工程师教你编写垃圾回收器

    Google工程师教你编写垃圾回收器 [url]http://www.iteye.com/news/30842[/url]

  • JVM垃圾收集器基准报告 – Ionuț Baloșin 如何选择适合你的垃圾回收器

    本文使用一组不同的模式描述了一系列Java虚拟机（JVM）垃圾收集器（GC）微基准及其结果。对于当前问题，我包括了AdoptOpenJDK 64位服务器VM版本13（内部版本13 + 33）中的所有垃圾收集器： 串行GC Parallel / ...

  • JVM内存与垃圾回收篇

    作为Java工程师的你曾被伤害过吗？你是否也遇到过这些问题？ 运行着的线上系统突然卡死，系统无法访问，甚至直接OOM 想解决线上JVM GC问题，但却无从下手 新项目上线，对各种JVM参数设置一脸茫然，直接默认吧...

  • [翻译]Go与C#的比较，第二篇：垃圾回收

    Go vs C#, part 2: Garbage Collection | by Alex Yakunin | ServiceTitan — Titan Tech | Medium 目录 译者注 什么是垃圾回收？ 什么是GCBurn？ 峰值分配吞吐量（"速度测试"） GCBurn 测试 GC Burn测试结果 结论...

  • 编写你的第一个垃圾收集器

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

  • 编写你的第一个垃圾收集器（转载）

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

  • 如何成为一名Google工程师

    [译] Google Interview University 一套完整的学习手册帮助自己准备 Google 的面试 原文地址：Google Interview University 原文作者：John Washam 译文出自：掘金翻译计划 译者：Aleen，Newton，bobmayuze，...

  • 超干货！彻底搞懂Golang内存管理和垃圾回收

    而Java和Go等语言使用自动的内存管理系统，由内存分配器和垃圾收集器来代为分配和回收内存，开发者只需关注业务代码而无需关注底层内存分配和回收，虽然语言帮我们处理了这部分，但是还是有必要去了解一下底层的架构...

  • Java进阶 JVM 内存与垃圾回收篇（一）

    自动内存管理，垃圾回收功能 数据下标越界越界检查 多态 比较 Jvm vs Jre vs JDK 1.2 学习路线 本文主要讲解的是HotSpot VM HotSpot VM 是目前市面上高性能虚拟机的代表作之一，采用解释器与即时编译器并存...

  • ＜JVM上篇：内存与垃圾回收篇＞01-JVM与Java体系结构

    上篇：内存与垃圾回收篇＞01-JVM与Java体系结构

  • [ZZ] 编写你的第一个垃圾收集器

    编写你的第一个垃圾收集器 本文由 伯乐在线 - deathmonkey 翻译自 Bob Nystrom 。欢迎加入技术翻译小组 。转载请参见文章末尾处的要求。 伯乐在线补充：本文作者 Bob Nystrom 是 Google Dart 团队的一名...

  • 外加热强制循环蒸发器装配图（CAD).rar

    外加热强制循环蒸发器装配图（CAD).rar

  • 数控车床纵向进给系统设计.zip

    数控车床纵向进给系统设计.zip

  • vault_side_off_ominous.png

    j

  • 爬虫 bangumi名称和评论数

    爬虫 bangumi名称和评论数

  • 基于SpringBoot的垃圾分类回收系统(源码+数据库+万字文档)526

    基于SpringBoot的垃圾分类回收系统，系统包含两种角色：管理员、用户主要功能如下。 【用户功能】 首页：浏览垃圾分类回收系统信息。 个人中心：管理个人信息，查看历史记录和订单状态。 运输管理：查看运输信息，垃圾回收的时间和地点。 公告管理：阅读系统发布的相关通知和公告。 垃圾回收管理：查看垃圾回收的信息，回收类型和进度。 垃圾出库申请管理：提交和查看垃圾出库申请的状态。 【管理员功能】 首页：查看垃圾分类回收系统。 个人中心：管理个人信息。 管理员管理：审核和管理注册管理员用户的信息。 用户管理：审核和管理注册用户的信息。 运输管理：监管和管理系统中的运输信息。 公告管理：发布、编辑和删除系统的通知和公告。 垃圾回收管理：监管和管理垃圾回收的信息。 垃圾出库申请管理：审批和管理用户提交的垃圾出库申请。 基础数据管理：管理系统的基础数据，运输类型、公告类型和垃圾回收类型。 二、项目技术 编程语言：Java 数据库：MySQL 项目管理工具：Maven 前端技术：Vue 后端技术：SpringBoot 三、运行环境 操作系统：Windows、macOS都可以 JDK版本：JDK1.8以上都可以 开发工具：IDEA、Ecplise、Myecplise都可以 数据库: MySQL5.7以上都可以 Maven：任意版本都可以

  • 这篇文章是台湾大学（NTU）计算机科学与信息工程系（CSIE）2021年秋季学期算法设计与分析课程的第一份作业（Homework#1）的具体要求和题目描述 以下是主要内容的总结：

    内容概要：本文档是台湾大学计算机科学与信息工程系2021年秋季学期《算法设计与分析》课程的第一次作业（Homework#1）。作业包含四道编程题和三道手写题，旨在考察学生对算法设计和分析的理解与应用能力。编程题涉及汉诺塔、数组计算、矩形点对、糖果分配等问题；手写题涵盖渐近符号证明、递归方程求解、幽灵腿游戏优化、不公平的卢卡斯问题等。文档详细描述了每个问题的具体要求、输入输出格式、测试用例以及评分标准。此外，还提供了编程技巧和注意事项，如避免延迟提交、正确引用资料、处理大输入文件等。 适合人群：具备一定编程基础的本科生或研究生，特别是修读过或正在修读算法设计与分析相关课程的学生。 使用场景及目标：①帮助学生巩固课堂所学的算法理论知识；②通过实际编程练习提高解决复杂问题的能力；③为后续更深入的学习和研究打下坚实的基础。 其他说明：此作业强调团队合作和个人独立思考相结合的重要性，鼓励学生在讨论后用自己的语言表达解决方案，并注明参考资料。对于编程题，特别提醒学生注意输入文件可能较大，建议采取适当的优化措施以确保程序运行效率。

  • 基于SpringBoot的铁路订票管理系统(源码+数据库+万字文档+ppt)528

    基于SpringBoot的铁路订票管理系统，系统包含两种角色：管理员、用户主要功能如下。 【用户功能】 首页：浏览铁路订票管理系统的主要信息。 火车信息：查看火车的相关信息，包括车次、出发地、目的地和票价等。 公告资讯：阅读系统发布的相关通知和资讯。 后台管理：进行系统首页、个人中心、车票预订管理、车票退票管理等操作。 个人中心：管理个人信息，查看订单历史记录等。 【管理员功能】 首页：查看铁路订票管理系统。 个人中心：修改密码、管理个人信息。 用户管理：审核和管理注册用户的信息。 火车类型管理：管理系统中的火车类型信息。 火车信息管理：监管和管理系统中的火车信息，添加、编辑、删除等。 车票预订管理：处理用户的车票预订请求。 车票退票管理：处理用户的车票退票请求。 系统管理：管理系统的基本设置，公告资讯、关于我们、系统简介和轮播图管理。 二、项目技术 编程语言：Java 数据库：MySQL 项目管理工具：Maven 前端技术：Vue 后端技术：SpringBoot 三、运行环境 操作系统：Windows、macOS都可以 JDK版本：JDK1.8以上都可以 开发工具：IDEA、Ecplise、Myecplise都可以 数据库: MySQL5.7以上都可以 Maven：任意版本都可以

  • 塑料架注射模具设计.rar

    塑料架注射模具设计.rar

  • 基于json文件数据驱动的的接口测试框架.zip

    基于json文件数据驱动的的接口测试框架

Global site tag (gtag.js) - Google Analytics