通常来说，在整个程序的运行过程中，垃圾回收只会占用很小一部分工夫，赋值器的执行会占用更多的工夫，因而，内存调配速度的快慢将间接决定整个程序的性能。很显著，后面提到的标记-清理算法并不是一个很好的范例，尽管它的算法简略且实现容易，但存在很重大的内存碎片化问题，会重大影响内存的调配速度。

标记-整顿算法能够铲除碎片问题，而且调配速度也很快，但在垃圾回收过程中会进行屡次堆遍历，进而显著减少了回收工夫。

本文将介绍第三种根本的垃圾回收算法：半区复制算法。回收器在整个过程中通过复制的形式来进行堆整顿，从而晋升内存调配速度，且回收过程中只需对存活对象便当一次，其最大的毛病是堆的可用空间升高了一半。

复制算法是一种典型的以空间换工夫的算法。

实现原理

在复制算法中，回收器将堆空间划分为两个大小相等的半区 (semispace)，别离是 起源空间(fromspace) 和 指标空间(tospace) 。在进行垃圾回收时，回收器将存活对象从起源空间复制到指标空间，复制完结后，所有存活对象严密排布在指标空间一端，最初将起源空间和指标空间调换。半区复制算法的概要如下图所示。

接下来看下代码如何实现？次要流程很简略，有一个 free 指针指向TOSPACE的终点，从根节点开始遍历，将根节点及其援用的子节点全副复制到TOSPACE，每复制一个对象，就把 free 指针向后挪动相应大小的地位，最初替换FROMSPACE和TOSPACE，大抵可用如下代码形容：

collect() {// 变量后面加*示意指针// free指向TOSPACE半区的起始地位*free = *to_start;for(root in Roots) {copy(*free, root);}// 替换FROMSPACE和TOSPACEswap(*from_start,*to_start);}复制代码

外围函数 copy 的实现如下所示：

copy(*free,obj) {// 查看obj是否曾经复制实现// 这里的tag仅是一个逻辑上的域if(obj.tag != COPIED) {// 将obj真正的复制到free指向的空间copy_data(*free,obj);// 给obj.tag贴上COPIED这个标签// 即便有多个指向obj的指针，obj也不会被复制屡次obj.tag = COPIED;// 复制实现后把对象的新地址寄存在老对象的forwarding域中obj.forwarding = *free;// 依照obj的长度将free指针向前挪动*free += obj.size;// 递归调用copy函数复制其关联的子对象for(child ingetRefNode(obj.forwarding)){*child = copy(*free,child);}}returnobj.forwarding;}复制代码

在这段代码中须要留神两个问题，其一是 tag=COPIED 只是一个逻辑上的概念，用来辨别对象是否曾经实现复制，以确保即便这个对象被屡次援用，也仅会复制一次；另外一个问题则是 forwarding 域， forwarding指针 在后面曾经屡次提到过，次要是用来保留对象挪动后的新地址，比方在标记整顿算法中，对象挪动后须要遍历更新对象的援用关系，就须要应用 forwarding指针 来查找其挪动后的地址，而在复制算法中，其作用相似，如果遇到已复制实现的对象，间接通过forwarding域把对象的新地址返回即可。整个复制算法的根本致流程如下图所示。

接下来用一个具体的示例看看复制算法的大抵流程。堆中对象的关系如下图所示，其中free指针指向TOSPACE的终点地位。

首先，从根节点登程，找到它间接援用的对象B和E，其中对象B首先被复制到TOSPACE。B被复制后的堆的关系如下图所示。

这里将B被复制后生成的对象成为B'，而原来的对象B中 tag 域曾经打上复制实现的标签，而 forwarding指针 也寄存着B'的地址。

对象B复制实现后，它援用的对象A还在FROMSPACE里，接下来就会把对象A复制到TOSPACE中。

接下来复制从根援用的对象E，以及其援用对象B，不过因为B曾经复制实现，所以只须要把从E指向B的指针换成指向B'的指针即可。

最初只有把FROMSPACE和TOSPACE调换，GC就完结了。GC完结时堆的状态如下图所示。

在这儿，程序的搜寻程序是按B、A、E的顺序搜索对象的，即以深度优先算法来搜寻的。

算法评估

复制算法次要有如下劣势：

  • 吞吐量高：整个GC算法只搜寻并复制存活对象，尤其是堆越大，差距越显著，毕竟它耗费的工夫只是与流动对象数量成正比。
  • 可实现高速调配：因为GC实现后闲暇空间是一个间断的内存块，在内存调配时，只有申请空间小于闲暇内存块，只须要挪动free指针即可。相较于标记-清理算法应用闲暇链表的调配形式，复制算法显著快得多，毕竟要在闲暇链表中找到适合大小的内存怎么都得遍历这个链表。
  • 无碎片：没啥好说的。
  • 与缓存兼容：能够回顾一下后面说的局部性原理，因为所有存活对象都严密的排布在内存里，十分有利于CPU的高速缓存。

相较于后面的两种GC算法，其劣势次要有亮点：

  • 堆空间利用率低：复制算法把堆一分为二，只有一半能被应用，内存利用率极低，这也是复制算法的最大缺点。
  • 递归调用函数：复制某个对象时要递归复制它援用的对象，相较于迭代算法，递归的效率更低，而且有栈空间溢出的危险。

Cheney 复制算法

Cheney算法是用来解决如何遍历援用关系图并将存活对象挪动到TOSPACE的算法，它应用迭代算法来代替递归。

还是以一个简略的例子来看看Cheney算法的执行过程，首先还是初始状态，在后面的例子上做了一点改变，同时有两个指针指向TOSPACE的终点地位。

首先复制所有从根节点间接援用的对象，在这儿就是复制B和E。

这时，与根节点间接援用的对象都曾经复制结束，scan 依然指向TOSPACE的终点，free 从终点向前挪动了B和E个长度。

接下来，scan 和 free 持续向前挪动，scan 的每次挪动都意味着对已实现复制对象的搜寻，而 free 的向前挪动则意味着新的对象复制实现。

还是以例子来说，在B和E实现复制当前，接着开始复制与B关联的所有对象，这里是A和C。

在复制A和C时，free 向前挪动，等A和C复制实现当前，scan向前挪动B个长度到E。接着，持续扫描E援用的对象B，发现B曾经实现复制，则 scan 向前挪动E个长度，free 放弃不动。因为对象A没有援用任何对象，还是 scan 向前挪动A个长度，free 放弃不动。

接下来，持续复制C的关联对象D，实现D的复制当前，发现 scan 和 free 相遇了，则完结复制。

最初依然是FROMSPACE和TOSPACE调换，GC完结。

代码实现只须要在之前的代码上稍做批改，即可：

collect() {// free指向TOSPACE半区的起始地位*scan = *free = *to_start;// 复制根节点间接援用的对象for(root in Roots) {copy(*free, root);}// scan开始向前挪动// 首先获取scan地位处对象所援用的对象// 所有援用对象复制实现后，向前挪动scanwhile(*scan != *free) {for(child ingetRefObject(scan)){copy(*free, child);}*scan += scan.size;}swap(*from_start,*to_start);}复制代码

而 copy 函数也不再蕴含递归调用，仅仅是实现复制性能：

copy(*free,obj) {if(!is_pointer_to_heap(obj.forwarding,*to_start)) {// 将obj真正的复制到free指向的空间copy_data(*free,obj);// 复制实现后把对象的新地址寄存在老对象的forwarding域中obj.forwarding = *free;// 依照obj的长度将free指针向前挪动*free += obj.size;}returnobj.forwarding;}复制代码

对于 is_pointer_to_heap(obj.forwarding,*to_start) ，如果 obj.forwarding 是指向TOSPACE的指针，则返回TRUE，否则返回FALSE。这里没有应用 tag 来辨别对象是否曾经实现复制，而是直接判断 obj.forwarding 指针，如果 obj.forwarding 不是指针或者没有指向TOSPACE，那么就认为它没有实现复制，否则就阐明曾经实现复制。

通过代码能够看出，Cheney算法采纳的是广度优先算法。相熟算法的同学可能晓得，广度优先搜索算法是须要一个先进先出的队列来辅助的，但这儿并没有队列。实际上 scan 和 free 之间的堆变成了一个队列，scan右边是曾经搜寻完的对象，左边是待搜寻对象。free 向前挪动，队列就会追加对象，scan 向前挪动，都会有对象被取出并进行搜寻，这样一来，就满足了先入先出队列的条件。

上面是一个广度优先遍历算法的典型实现，大家能够用作比照，加深了解。

voidBFS(List<Node> roots){// 曾经被拜访过的元素List<Node> visited =newArrayList<Node>();// 用队列寄存顺次要遍历的元素Queue<GraphNode> queue =newLinkedList<GraphNode>();for(node in roots) {visited.add(node);process(node);queue.offer(node);}while(!queue.isEmpty()) {Node currentNode = queue.poll();if(!visited.contains(currNode)) {visited.add(currentNode);process(node);for(child ingetChildren(node)){queue.offer(node);}}}}复制代码

比照之前的算法，Cheney算法的长处是应用迭代算法代替递归，防止了栈的耗费和可能的栈溢出危险，特地是拿堆空间用作队列来实现广度优先遍历，十分奇妙。而毛病则是，互相援用的对象并不是相邻的，就没方法充分利用缓存。留神，这里不是说，Cheney算法无奈兼容缓存，只是相较于前一种算法来说，没有那么好而已。

最初

复制算法还有挺多变种的，这里没方法一一列举，更多内容能够浏览参考资料中的两本书籍。（也能够关注公众号【Java斗帝】收费获取pdf版）

垃圾回收算法手册：主动内存治理的艺术

垃圾回收的算法与实现

复制算法的最大缺点就是堆空间利用率低，因而大多数场景下，都是与其余算法搭配应用；并且咱们也不是真的会把堆空间一分为二，而是依据理论状况，正当的划分。就比方，能够把堆空间分成10份，拿出2份空间别离作为From空间和To空间，用来执行复制算法，而剩下的8分则搭配应用标记-清理算法。

是不是又想到了JVM的新生代和老年代的区域划分，嗯，起因就是咱们所讲的内容。

看完三件事❤️

如果你感觉这篇内容对你还蛮有帮忙，我想邀请你帮我三个小忙：

  1. 点赞，转发，有你们的 『点赞和评论』，才是我发明的能源。
  2. 关注公众号 『 Java斗帝 』，不定期分享原创常识。
  3. 同时能够期待后续文章ing????