00:00
那说完了标记清除算法和复制算法之后啊,咱们来看第三个算法,叫做标记压缩算法啊,也称为呢叫标记整理算法,对应的这个英文的话呢,叫做mark comp啊这个comp的话呢,就翻译成叫压缩或者叫整理都可以啊,压缩的话呢,我觉得更像是这个单词的一个解释,这个整理的话呢,也可以理解成就是我们这个算法的一个实现过程是吧?诶我们实际上呢,实现了一个内存碎片化的一个整理,所以呢,也称为呢叫标记整理算法,OK,这是两个不同的叫法而已,行,那首先呢,我们来看一下这个背景说呢,这个复制算法它的高效性啊,是建立在存活对象比较少,垃圾呢对象比较多的前提下,这个咱们刚才呢,是不是已经强调过这个点。对吧?哎,你要说这个存货对象非常多的话呢,我们再去复制这个就非常悲壮了,那这个复制算法的这个效率呢,一下子就下来了,优势呢荡然无存,对吧,那这种情况呢,我们就非常适合于在这个新生代当中去使用。那对于说咱们这个老年代的话呢,咱们说大部分这个对象呢,可能都是存活的,咱们就不适合在这个老年代当中去使用这个叫复制算法,那下边我们就要考虑说,那老年代这个基于它的这个特点,我们应该使用什么样的算法呢?啊,那这里边儿我们就提到了,说如果呢,咱们要是使用这个标记清楚算法在老年代中的话呢,行不行呢?呃,也行。
01:14
啊,首先说呢是可以的,呃,但是呢,这个算法呢,说执行效率比较低啊,执行完以后的话呢,这个回收啊,接下来我们还需要呢,专门进行一个碎片整理,所以这里边儿呢,其实主要呢,想谈到的问题就是这个碎片整理。啊,大家知道咱们这个老年代这个空间呢,相对来说也是比较大的,对吧,那我们呢,如果使用这个标记侵除算法之后,我们这个堆空间的这个老年代里边呢,它这个碎片化呢,是比较严重的,我们需要呢,专门的来进行这个碎片的一个整理,那否则的话呢,我们是没有办法呢放这个大对象的,对吧?因为我说这个新生带当中啊,因为这个内存空间相对比较小,而且呢,又分割成这个叫伊甸园区和两个survivor区,那我们说这个大对象呢,是不是直接进入老年代啊,那如果这个老年代呢,你在进行完这个GC之后呢,发现里边的碎片化很严重,那这个大对象呢,很有可能也放不下。啊,就是说我们这个标记清楚算法呢,呃能用在老年代码能用,但是呢,就是你要考虑到啊,你还得专门在整个整理一个这个,呃,专门进行这个碎片的一个整理的问题啊,那这时候呢,我们在这个标记清除的基础之上啊,就进行了一个优化,这个优化呢,咱们就称为呢叫标记压缩算法。
02:17
啊,那这呢是在1970年前后,所以呢,我们讲的这三个算法呢,大家会发现实际上呢,也是按照这个时间先后顺序来的,对吧,1900年,1963年和1970年前后,在1970年前后的话呢,这样几个人他们呢,就发明了一个叫标记压缩算法,哎,在很多咱们说现在的垃圾收集器当中使用的都是标压缩算法,或者是他的一个改进版本,下下章咱们就讲这个具体的垃圾回收器了,到时候呢,大家就知道我们使用的这样的一些算法,当然呢,也有算法呢,还在使用这个叫标记清除算法。啊,这个咱们讲到这的时候呢,再说好,首先的话呢,我们来看一下这个执行过程,这个执行过程呢,它叫标记压缩,其实呢,也是算是两个主要环节,第一个环节呢,叫做标记,那这个环节呢,跟咱们前面讲的标记清除算法的这个环节呢,其实是一样子的,我们从这个根据点出发,便利一下所有的可达的这些对象,然后做一个header,就是在这个对象的对象头当中进行一个标记,就是我们这里边这个绿色的,就好比是进行了标记,OK,那么第二个环节呢,我们是将所有的这个叫存活对象呢,压缩到内存的一端,按顺序排放。
03:18
那下边的话呢,清除并不是说像我们标记清除的时候那么简单了,把这个没有这个便利到的这个对象呢,我们给他这个直接干掉是吧?诶而这呢,不是这样子的,这呢是我们把你这个啊,比如说这块呢,已经是在这个开头的这个位置了,像这个呢,是前面会有一些空闲区域,我们就把它呢在呃标记完以后呢,下一个阶段呢,直接去做一个复制过来啊,直接呢就移动到这。那那移动到这儿的时候呢,我们此时呢,其实就相当于进行了一个碎片的整理,那剩下这个区域呢,我们就直接呢,就挂掉了,就不要了。那就不要了,行,这呢,就是我们所谓的叫压缩,或者呢,大家也可以称为呢,叫一个叫标记整理,因为整理的话呢,涉及到这个碎片整理的问题嘛,那我们得到的这个新的这个空间的话呢,你会发现呢,它都是连续存储的。
04:04
那整个呢,整片的这个空间呢,空闲呢,都在下面。那就在下边,那还是呢,举咱们说这个机器人的一个例子,那是成什么情况呢?咱们现在的话呢,还是整个这个餐厅啊,大家呢都可以用餐,不用呢说就砍一半空间了,对吧?那像我们刚才提到说这个老年代呢,说不适合于用这个复制算法,其实还有一个原因,一个呢是因为它这个大部分对象呢,其实它都是存活的啊,这个复制算法呢,就不太合适,另外一个呢,就是咱们这个老年代的话呢,虽然说它这个区域比较大,是因为咱们要存放的东西比较多,你现在呢,如果用复制算法整个把这空间砍一半,是不是这个呢,也显得浪费的就有点也过多是吧,就跟说大家你吃一口米饭,然后你吐一半,感觉说哎心里边还可以接受一下,因为这一碗米饭呢,你扔了一半,你是不是感觉要这个浪费很多呀。能理解这个概念对吧,就是你这块呢堆空间,呃,这个老年代本身的空间比较大,然后你再砍掉一半。那这个时候呢,感觉浪费的有点太多了,太奢侈了,对吧,所以从这个角度来讲,我们也不太适合用这种,哎复制算法啊行,那咱们用这个叫标记压缩算法的话呢,这个仍然是这个餐厅所有的人呢,诶都可以考虑吃饭,不用分成两个区域了,东区西区啥的,那现在的话呢,就是这些人呢,手里边儿还拿着他使用的这个餐巾纸,那我们第一个环节呢,还是一个标记环节,大家呢,就把你这个餐巾纸上画一个圈圈,就是如果说你这个餐巾纸还用是吧,我们就画个小圈圈,然后没有画的这些呢,就是我们这个黑色的部分,接下来的话呢,这个机器人说说所有的人啊,就是凡是这个餐巾纸上画圈圈的,你呢,就是回到你去我们这个餐厅的这个一端,比如咱们上边这个叫北北端是吧。
05:41
嗯,所以呢,这个餐巾纸上画圈圈的,呃,这个客人呢,你到这个北端啊,大家呢,就都跑到北端,就依次呢这样去放,然后呢,这个呃没有画圈的这个你就在下边,接下来的话呢,这个或者说你没有画圈的,你可以理解成就是这个散落的那些餐巾纸对吧?然后呢,大家诶这个机器人呢,就直接呢去针对这个没有画圈的下边这些呃进行回收就行,那上边呢,就是呃使用的这个餐巾纸的这些人呢,他们就都放在一起。
06:08
啊,是一个紧密排列的情况。啊,举个这样的生活中的例子啊,咱们几个呢,算法呢,都是使用这个机器人跟这个回收餐厅这个餐巾纸的这个例子呢来说的,哎,大家呢,能够基本上有个对应就行,如果你说我举了这个例子之后呢,你反而更迷糊了,那就别看这个例子了,是吧?呃,因为本身这个算法呢,其实这几个诶大家应该说都还是比较好理解的啊嗯,行,然后下边呢来描述说,哎,标记压缩算法的最终效果呀,就等同于咱们呢,标记最终呢,你看把那个垃圾是不是也清除掉了,对吧,相当于呢,是在这个标记清除的基础上,咱们进行了一次碎片整理,所以有的时候呢,诶,咱们也会把这个标记压缩算法呢,称为叫标记清除压缩算法。就是中间又加了个清除,毕竟的话呢,你把这些所谓的不用的对象是不是也进行了一个清除啊,哎,这样的一个例子啊。那么二者这个主要区别是什么呢?区别的话呢,就是咱们这个标记清楚算法。
07:03
标记清楚算法呢,咱们只是把那个垃圾给清除掉,它没有涉及到这个呃,存活的那个对象的空间位置的一个移动,所以呢,它属于叫非移动式的,而我们这个呃标记压缩算法呢,因为你涉及到内存的一个碎片整理了,所以呢它是一个移动式的。哎,主要呢,就是这个点。啊,那是否需要移动呢?是一个优缺点并存的一个风险决策啊,能理解这个话吗?优缺点并存就是既有好处又有风险,对吧?那好处的话呢,就是我们没有这个碎片的一个问题了,来进行这个碎片整理,当然呢,这个效率呢也会比较低一些,另外的话呢,你想想我们这个对象,比如说呢,被其他的引用呢,引用着呢,那现在你把这个对呢放在这儿了,那这块的话呢,我们首先这个对像修改了这个位置了,那你这时候呢,那个引用呢,也要需要改,以及呢,还有很多其他的这个位置对象当中有可能都还要用到它,那用到它的位置呢,所有的那个引用都需要做一些修改,那这时候你在这个程序呢,编写过程当中都需要考虑到这些问题啊,所以呢,他也会有一定的风险啊。
08:04
行,那么可以看到就是标记的存活对象呢,被整理了,然后按照内存地址呢依次排列了,还是没有呢,呃,这个而没有标记呢,就被清理掉了,我们呢,还都放在一起,对吧?说这样呢,我们就不用使用这个叫空间列表了,言外之意呢,就是现在我们这个内存呢,你看属于这样的一个场景,那么此时咱们如果说你再去。啊,分配新的对象的话呢,咱们是不是就用不着使用这个空间列表了。对吧,诶这个呢,针对的是咱们说叫标记啊标记清除算法,咱们呢需要呢,用空间列表来维护,然后呢,对于咱们说的这个复制算法呢,咱可以使用呢,叫指针碰撞。哎,复制算法可以这样,然后咱们的这个标记,诶是不是这个压缩算法也可以使用,这个叫指针碰撞了。没问题啊,这个大家记住它啊,这呢跟咱们前面讲的这个对象实例化的这个内容咱就连到一起了,那么这个词呢,大家也都得能明白啊,是什么意思,那PPT里边我还放了一个说这个关于这个呃,指针碰撞的一个描述,这呢我们就就不看了,前面咱们已经讲过啊。
09:08
好,那么总结一下,咱们关于这个标记压缩算法它的一个优点,还有它的一个缺点,那首先呢,咱们来看这个优点啊,那优点呢,简单来说啊,简单来说就是解决了咱们说的那个标记清除算法和复制算法的缺点。啊,就是把他们两个缺点呢给干掉了,你看这样说大家,那那是不是这个算法就挺完美的,也不是是吧,也不是,就是你解决人家缺点,但是人家是优点的,可能你这块就变成你的缺点了,是吧。哎,看一下啊,那对于这个标记清除算法,咱们前面说了,前面说的话呢,就是它是不是有这个叫内存是不是碎片化的一个问题,对吧,那这时候呢,我们标记压缩呢,就是把它整理整理了一下啊,这个它呢,这时候这个内存空间呢,就比较规整一些,诶只保留一个内存的一个起始地址就行,就是那个指针的位置,你在加对象的时候,指针碰撞是吧,往后移啊就可以了啊,这是相当于这个标记清除算法的一个,呃,一个好处是吧,那下边呢,相当于这个复制算法的话呢,我们这个内存呢,就不用减半了,咱们直接呢,就使用一整块这个内存就可以啊,用不着用不着呢,P2半不用去考虑这个两个区域,OK,这是优点啊,那么缺点话呢,也有。
10:18
就是你把人家的缺点给改了,但是呢,你对应的这块呢,也会附带着有一些缺点。行,那首先说呢,从这个效率上来讲呢,它比我们这个复制算法呢,要低一些。或者换句话说呢,跟我们标记清除算法比呢,是不是要更低一些啊?啊,因为呢,你这块还涉及到碎片的整理嘛,是吧,比我们这个标记清楚算法其实效率还是要还还要低一些,然后同时的话呢,我们在移动这个对象的同时啊,你移动对象同时呢,这个对象被其他引用,如果所引用的话呢,也需要调整这些地址啊,需要调整的地方呢,比较多一些啊这是一个,另外呢,在整个移动的过程当中,咱们需要呢,Stop the word啊其实这个呢,其他的这个算法的话呢,也有这个问题。
11:00
啊,有这个问题,OK,只不过呢,因为这块我们还涉及到这个复制这个环节,所以呢,我们这个stop the word这个时长呢,会稍微的长一点。OK,这呢就是我们涉及到叫哎标记压缩算法它的一个描述,哎,那咱们呢,就说到这儿。
我来说两句