记忆集与卡表

为什么需要记忆集？

跨代引用假说(IntergenerationalReferenceHypothesis):跨代引用相对于同代引用来说仅占极少数。

存在互相引用关系的两个对象，是应该倾向于同时生存或者同时消亡的。举个例子，如果某个新生代对象存在跨代引用，由于老年代对象难以消亡，该引用会使得新生代对象在收集时同样得以存活，进而在年龄增长之后晋升到老年代中，这时跨代引用也随即被消除了。

这时候便引出了记忆集(RememberedSet)概念。用以避免把整个老年代加进GCRoots扫描范围。事实上并不只是新生代、老年代之间才有跨代引用的问题，所有涉及部分区域收集(PartialGC)行为的垃圾收集器，典型的如G1、ZGC和Shenandoah收集器，都会面临相同的问题。

实际上就是一种备忘录思想，空间换时间。

什么是记忆集

记忆集是一种用于记录从非收集区域指向收集区域的指针集合的抽象数据结构。

卡表

卡表（CardTable）是记忆集一种粗粒度的实现方式。来节省存储和维护成本。(由AntonyHosking在1993年发表的论文《Rememberedsetscanalsoplaycards》中提出)。

一种简单的数组结构。字节数组CARD_TABLE的每一个元素都对应着其标识的内存区域中一块特定大小的内存块，这个内存块被称作“卡页”(CardPage)。一般来说，卡页大小都是以2的N次幂的字节数，通过上面代码可以看出HotSpot中使用的卡页是2的9次幂，即512字节(地址右移9位，相当于用地址除以512)。那如果卡表标识内存区域的起始地址是0x0000的话，数组CARD_TABLE的第0、1、2号元素，分别对应了地址范围为0x0000_{0x01FF、0x0200}0x03FF、0x0400~0x05FF的卡页内存块。

一个卡页的内存中通常包含不止一个对象，只要卡页内有一个(或更多)对象的字段存在着跨代指针，那就将对应卡表的数组元素的值标识为1，称为这个元素变脏(Dirty)，没有则标识为0。在垃圾收集发生时，只要筛选出卡表中变脏的元素，就能轻易得出哪些卡页内存块中包含跨代指针，把它们加入GCRoots中一并扫描。

案例：CMS中的卡表。

浅谈G1中记忆集中的实现

使用记忆集避免全堆作为GCRoots扫描，但在G1收集器上记忆集的应用其实要复杂很多，它的每个Region都维护有自己的记忆集，这些记忆集会记录下别的Region指向自己的指针，并标记这些指针分别在哪些卡页的范围之内。G1的记忆集在存储结构的本质上是一种哈希表，Key是别的Region的起始地址，Value是一个集合，里面存储的元素是卡表的索引号。这种“双向”的卡表结构(卡表是“我指向谁”，这种结构还记录了“谁指向我”)比原来的卡表实现起来更复杂，同时由于Region数量比传统收集器的分代数量明显要多得多，因此G1收集器要比其他的传统垃圾收集器有着更高的内存占用负担。根据经验，G1至少要耗费大约相当于Java堆容量10%至20%的额外内存来维持收集器工作。

深入理解JVM第三版，原文说的比较模糊。请注意这是在一个region维持其他region引用该region对象的信息（point out）。实际实现还是CardTable，只不过多了一个哈希表（稀疏表）。

key为其他region的起始地址，Value为该region的卡表索引号的集合。

背景

上一篇文章（浅谈JVM垃圾收集）提到了，当JVM进行垃圾收集时，它是怎么判断对象是否跨代引用的呢？

记忆集与卡表

为解决扫描GC ROOT时遇到对象跨代引用所带来的问题，收集器在新生代上建立一个全局的称为记忆集（Remembered Set）的数据结构

这个结构把老年代划分为若干个小块，标识出老年代哪一块内存会存在跨代引用。当发生 Minor GC 时，只有包含了跨代引用的小块内存中的老年代对象才会加入到 GC Roots 扫描中，避免整个老年代加入到 GC Roots 中。

事实上并不只是新生代、老年代之间才有跨代引用的问题，所有涉及部分区域收集（Partial GC）行为的 垃圾收集器，典型的如G1、ZGC和Shenandoah收集器，都会面临相同的问题。

记忆集是一种用于记录从非收集区域指向收集区域的指针集合的抽象数据结构。在垃圾收集的场景中，收集器只需要通过记忆集判断出某一块非收集区域是否存在有指向了收集区域的指针就可以了，并不需要了解这些跨代指针的全部细节。那设计者在实现记忆集的时候，便可以选择更为粗犷的记录粒度来节省记忆集的存储和维护成本，下面列举了一些可供选择（当然也可以选择这个范 围以外的）的记录精度：

• 字长精度：每个记录精确到一个机器字长（就是处理器的寻址位数，如常见的32位或64位，这个精度决定了机器访问物理内存地址的指针长度），该字包含跨代指针。
• 对象精度：每个记录精确到一个对象，该对象里有字段含有跨代指针。
• 卡精度：每个记录精确到一块内存区域，该区域内有对象含有跨代指针。

第三种“卡精度”所指的是用一种称为“卡表”（Card Table）的方式去实现记忆集，这也是 目前最常用的一种记忆集实现形式。

记忆集其实是一种“抽象”的数据结构，抽象的意思是只定义了记忆集的行为意图，并没有定义其行为的 具体实现。卡表就是记忆集的一种具体实现，它定义了记忆集的记录精度、与堆内存的映射关系等。 关于卡表与记忆集的关系，读者不妨按照Java语言中HashMap与Map。

HotSpot虚拟机定义的卡表只是一个字节数组。以下这行代码是HotSpot默认的卡表标记逻辑：

CARD_TABLE [this address >> 9] = 0;

字节数组CARD_TABLE的每一个元素都对应着其标识的内存区域中一块特定大小的内存块，这个 内存块被称作“卡页”（Card Page）。一般来说，卡页大小都是以2的N次幂的字节数，通过上面代码可 以看出HotSpot中使用的卡页是2的9次幂，即512字节（地址右移9位，相当于用地址除以512）。那如 果卡表标识内存区域的起始地址是0x0000的话，数组CARD_TABLE的第0、1、2号元素，分别对应了 地址范围为0x0000～0x01FF、0x0200～0x03FF、0x0400～0x05FF的卡页内存块，如下图所示：

一个卡页的内存中通常包含不止一个对象，只要卡页内有一个（或更多）对象的字段存在着跨代指针，那就将对应卡表的数组元素的值标识为1，称为这个元素变脏（Dirty），没有则标识为0。在垃圾收集发生时，只要筛选出卡表中变脏的元素，就能轻易得出哪些卡页内存块中包含跨代指针，把它们加入GC Roots中一并扫描。那虚拟机是何时让卡表元素变脏呢？它是如何维护卡表元素的呢？

写屏障

卡表元素何时变脏的答案是很明确的——有其他分代区域中对象引用了本区域对象时，其对应的卡表元素就应该变脏，变脏时间点原则上应该发生在引用类型字段赋值的那一刻，把维护卡表的动作放到每一 个赋值操作之中。

在HotSpot虚拟机里是通过写屏障（Write Barrier）技术维护卡表状态的。写屏障可以看作在虚拟机层面对“引用类型字段赋值”这个动作的AOP切 面，在引用对象赋值时会产生一个环形（Around）通知，也就是说赋值的前后都在写屏障的覆盖范畴内。在赋值前的部分的写屏障叫作写前屏障（Pre-Write Barrier），在赋值 后的则叫作写后屏障（Post-Write Barrier）。下面是简化的代码逻辑：

void oop_field_store(oop* field, oop new_value) {
 // 引用字段赋值操作 
 *field = new_value; 
 // 写后屏障，在这里完成卡表状态更新 
 post_write_barrier(field, new_value); 
 }

应用写屏障后，虚拟机就会为所有赋值操作生成相应的指令，一旦收集器在写屏障中增加了更新卡表操作，无论更新的是不是老年代对新生代对象的引用，每次只要对引用进行更新，就会产生额外的开销，不过这个开销与Minor GC时扫描整个老年代的代价相比还是低得多的。

“伪共享”问题

卡表在高并发场景下还面临着“伪共享”（False Sharing）问题。

伪共享是处理并发底层细节时一种经常需要考虑的问题，现代中央处理器的缓存系统中是以缓存行（Cache Line） 为单位存储的，当多线程修改互相独立的变量时，如果这些变量恰好共享同一个缓存行，就会彼此影响（写回、无效化或者同步）而导致性能降低，这就是伪共享问题。关于伪共享问题的更多内容看这篇文章——并发中的伪共享问题

假设处理器的缓存行大小为64字节，由于一个卡表元素占1个字节，64个卡表元素将共享同一个缓存行。这64个卡表元素对应的卡页总的内存为32KB（64×512字节），也就是说如果不同线程更新的对象正好处于这32KB的内存区域内，就会导致更新卡表时正好写入同一个缓存行而影响性能。

简单的说就是卡表内处于同一缓存行中的元素，若对应的不同卡页的内存中的对象的引用关系发生了变化，部分对象发生了跨代引用，那么对应的卡表数组元素就要从0变为1。但是它们由于处于同一缓存行，导致了CPU并行执行变为串行执行，降低了效率。
伪共享问题是卡表元素更改时处于同一缓存行导致的，诱发的因素是不同卡页内的对象发生了跨代引用。

为了避免伪共享问题，一种简单的解决方案是不采用无条件的写屏障，而是先检查卡表标记，只有当该卡表元素未被标记过时才将其标记为变脏，即将卡表更新的逻辑变为以下代码所示：

if (CARD_TABLE [this address >> 9] != 0) 
CARD_TABLE [this address >> 9] = 0;

在JDK 7之后，HotSpot虚拟机增加了一个新的参数-XX：+UseCondCardMark，用来决定是否开启卡表更新的条件判断。开启会增加一次额外判断的开销，但能够避免伪共享问题，两者各有性能损耗，是否打开要根据应用实际运行情况来进行测试权衡。

总结

记忆集与卡表

HotSpot虚拟机是用记忆集来记录某块内存区域是否包含跨代引用的对象。记忆集是抽象概念，而卡表是记忆集的实现。

卡表是用字节数组实现的，卡表数组的每个元素都是代表某块具体内存区域，这个内存区域叫卡页。

卡页的大小是512字节，代表一块特定大小的内存块，若在这块内存块中有一个或多个的跨代指针，则将对应的卡表元素标为1，代表“变脏”，否则为0。当虚拟机扫描卡表元素为1时，便将对应的卡页内存区域加入到GC ROOT中一并扫描。

写屏障

使用写屏障来实现卡表元素变脏。写屏障分为写前屏障和写后屏障，大多数垃圾收集器都是使用写后屏障（G1使用写前屏障）。写后屏障具体表现在对引用对象赋值时，如果是跨代引用，则通过写后屏障将对应的卡表元素变脏。

伪共享问题（美团面试）

由于CPU集成的多级缓存中是以缓存行来读取数据的，通过MESI协议保证多个CPU之间的缓存一致性。
伪共享问题是卡表元素更改时处于同一缓存行导致的，诱发的因素是不同卡页内的对象发生了跨代引用，从而使CPU并行执行变为串行执行，降低了并发性能。

举例： 若a、b位于同一缓存行，当CPU1修改a后，若CPU2想修改b，必须先提交CPU1的缓存，然后CPU2再去主存中读取数据。

伪共享问题解决方案：JAVA中的解决方案有填充法 和 Contended 注解。

• 填充法：就是 扩大对象的大小，这样，就可以一个缓冲行中，只存在一个对象！这样，就不会导致结果是串行执行了！
• Contended 注解法：Java1.8 中提供了Contended注解，使用这个注解，VM必须设置 -XX:-RestrictContended。
  ConcurrentHashMap的内部类CounterCell有用到这个注解
  

记忆集与OopMap的联系与区别
共同点：他们都是用于获取GC ROOT
不同点：OopMap记录的是准确的GC ROOT。而记忆集记录的是 包含跨代引用的GC ROOT 的一块内存，还要再扫描这块内存以得到GC ROOT。

问题讨论
前面说记忆集的时候有说到，老年代中的对象也存在跨代引用。目前只针对老年代进行回收的只有CMS收集器，但是在CMS中，对于老年代存在的跨代引用的对象，CMS并没有在老年代维护一个记忆集，而是把整个新生代加入到GC ROOT扫描？

问题回答
《深入理解Java虚拟机》的第3.5.7节中讲G1垃圾收集器的时候有提到CMS中的卡表，下面是书中的一段话：

相比起来CMS的卡表就相当简单， 只有唯一一份，而且只需要处理老年代到新生代的引用，反过来则不需要，由于新生代的对象具有朝 生夕灭的不稳定性，引用变化频繁，能省下这个区域的维护开销是很划算的。
代价就是当CMS发生Old GC时（所有收集器中只有CMS有针对老年代的Old GC），要把整个新生代作为GC Roots来进行扫描。（[6]注释中的话）

可知CMS中只会在新生代建立记忆集，老年代中是没有建立记忆集的。
记忆集：用于记录从非收集区域指向收集区域的指针集合。
所以回收新生代时是有老年代（非收集区域）指向新生代（收集区域）的记忆集，而老年代则需要把整个新生代加入到GC ROOT扫描

🥂在说记忆集和卡表之前，先给大家介绍一下跨代引用的问题。

👩🏻‍🏫假如要现在进行一次只局限于新生代区域内的收集(Minor GC)，但新生代的实例对象1在老年代中被引用，为了找出该区域(新生代)中所有的存活对象，不得不在固定的GC Roots之外，再额外遍历整个老年代中所有对象来确保可达性分析结果的正确性，反过来也是一样。遍历整个老年代所有对象的方案虽然理论上可行，但无疑会为内存回收带来很大的性能负担。

👉🏻事实上并不只是新生代、老年代之间才有跨代引用的问题，所有涉及部分区域收集（Partial GC)行为的垃圾收集器，典型的如G1、ZGC和Shenandoah收集器，都会面临相同的问题。

🍬那么如何才能解决跨代引用呢？

首先，跨代引用相对于同代引用来说仅占极少数。原因是跨代引用的对象应该倾向于同时生存或者同时死亡的（举个🌰：如果某个新生代对象存在跨代引用，由于老年代对象难以消亡，该引用会使得新生代对象在收集时同样得以存活，进而在年龄增长之后晋升到老年代中，这时跨代引用也随即被消除了）。

🌴🌴依据上面说所，就不应再为了少量的跨代引用去扫描整个老年代，也不必浪费空间专门记录每一个对象是否存在及存在哪些跨代引用，只需在新生代上建立一个全局的数据结构（该结构被称为“记忆集”，Remembered Set)，这个结构把老年代划分成若干小块，标识出老年代的哪一块内存会存在跨代引用。此后当发生Minor GC时，只有包含了跨代引用的小块内存里的对象才会被加入到GCRoots进行扫描。虽然这种方法需要在对象改变引用关系(如将自己或者某个属性赋值)时维护记录数据的正确性，会增加一些运行时的开销，但比起收集时扫描整个老年代来说仍然是划算的。

下面就来介绍一下这个全局的数据结构记忆集。

记忆集✨✨

🍺记忆集是一种用于记录从非收集区域指向收集区域的指针集合的抽象数据结构。如果我们不考虑效率和成本的话，最简单的实现可以用非收集区域中所有含跨代引用的对象数组来实现这个数据结构，如下面代码所示:

//以对象指针来实现记忆集的伪代码
Class RememberedSet {
	Object[] set[OBJECT_INTERGENERATIONAL_REFERENCE_SIZE]; 
}

🎈这种记录全部含跨代引用对象的实现方案，无论是空间占用还是维护成本都相当高昂。而在垃圾收集的场景中，收集器只需要通过记忆集判断出某一块非收集区域是否存在有指向了收集区域的指针就可以了，并不需要了解这些跨代指针的全部细节。那设计者在实现记忆集的时候，便可以选择更为粗犷的记录粒度来节省记忆集的存储和维护成本。下面列举了一些可供选择（当然也可以选择这个范围以外的）的记录精度：

• 字长精度：每个记录精确到一个机器字长（就是处理器的寻址位数，如常见的32位或64位，这个 精度决定了机器访问物理内存地址的指针长度），该字包含跨代指针。
• 对象精度：每个记录精确到一个对象，该对象里有字段含有跨代指针。
• 卡精度：每个记录精确到一块内存区域，该区域内有对象含有跨代指针。

🍍🍍上面的，第三种“卡精度”所指的是用一种称为“卡表”(Card Table)的方式去实现记忆集，这也是目前最常用的记忆集的实现形式。

👀卡表和记忆集又有什么关系呢？

前面介绍记忆集的时候提到 记忆集其实是一种"抽象”的数据结构，抽象的意思是只定义了记忆集的行为意图，并没有定义其行为的具体实现。卡表就是记忆集的一种具体实现，它定义了记忆集的记录精度、与堆内存的映射关系等。关于记忆集与卡表的关系，可以按照Java中Map与HashMap的关系来类比理解（即接口和实现类来的关系）。

🍋下面来详细说一下记忆集的具体实现卡表

卡表✨✨

卡表是使用一个字节数组CARD_TABLE[] 实现，每个元素对应其标识的内存区域一块特定大小的内存块，每个内存块称为卡页，hotspot使用的卡页是2^9大小 即512字节。如下图所示

🍦这样我们就可以把某个区域按照卡页进行划分，假如我们现在要对新生代区域进行垃圾回收，那么就可以把老年代区域看成是一个卡页一个卡页划分好的，如下图所示。

如图所示🍹，因为cardpage1中存在指向新生代的跨代引用，所以对应卡表的第一个位置为1，表明该page区域存在跨代应用的对象。

📍卡表角度：因为page1中存在跨代饮用的对象，所以卡表对应的第一个位置记为1，表明page1这个元素变脏。

📍内存回收角度：因为卡表的第一个位置为1，表明该page区域存在跨代应用的对象，垃圾回收的时候需要扫描该区域。

😎一个卡页的内存中通常包含不止一个对象，只要卡页内有一个(或更多）对象的字段存在着跨代指针，那就将对应卡表的数组元素的值标识为1，称为这个元素变脏（Dirty)，没有则标识为0。在垃圾收集发生时，只要筛选出卡表中变脏的元素，就能轻易得出哪些卡页内存块中包含跨代指针，把它们加入GC Roots中一并扫描。这样就不需要扫描整个老年代大大减少GC Roots的扫描范围。