一、年轻代和老年代的性格完全不一样先说结论年轻代回收得又快又勤老年代回收得又慢又贵。年轻代一般用疏散evacuation来管理说白了就是把活下来的对象搬到别的地方去可能是搬到同一代的另一块空白空间也可能直接搬去老年代。为什么年轻代能做到又快又勤因为大部分刚创建的对象活不了多久一次年轻代回收能存活下来的对象非常少需要追踪的东西自然也就很少所以速度快。老年代就完全反过来了。老年代回收次数很少但一旦触发就很贵因为通常要连带把所有比它年轻的代也一起回收掉——除非你愿意付出维护双向写屏障的代价也就是既要记录老指向新也要记录新指向老这个开销通常划不来。对应图1有个规律要记住当你回收最老的那一代时往往会顺带把堆里除了不朽空间immortal space和启动镜像boot image之外的所有空间都收一遍。不朽空间和启动镜像里的对象不会死但它们持有的引用指向普通堆里对象的指针依然要当作根来处理而且如果发生了对象移动这些引用也得跟着更新。还有一点很微妙做全堆回收的时候压根不需要用记忆集remembered set唯一的例外是记录了不朽空间/启动镜像里有哪些位置指向普通堆的那部分记忆集——而这部分记忆集如果你干脆把这两块空间整体扫描一遍那也可以不需要了。二、老年代怎么管三种候选方案管理最老的那一代可选的策略挺多下面逐个说说各自的账怎么算。方案A半空间复制semispace copying这个方案最大的问题是太浪费空间——它需要预留相当于整个分代堆一半大小的复制保留区copy reserve。这一预留直接挤占了老年代自己来源区fromspace以及年轻代能用的空间堆变小了各级回收自然就更频繁了等于是拆东墙补西墙。而且半空间复制还有个副作用长期存活的数据会被反复搬来搬去每次复制都要付出拷贝的代价这些数据明明活得好好的却要一遍遍挪窝纯属浪费。方案B标记-清除mark-sweep这个方案的优点是内存利用率更高尤其是在小堆的场景下表现更好。也许有人会说标记清除慢因为它要用空闲链表分配不像顺序分配那么快局部性也没那么好——但这个说法主要是针对对象创建这个场景的因为创建对象时分配频率非常高需要顺序分配才能给年轻对象提供良好的空间局部性。可老年代的对象根本不是这种高频创建的场景所以这个缺点在老年代身上并不致命。标记-清除真正的硬伤是它不移动对象non-moving用久了老年代会出现碎片化性能慢慢往下掉。解决办法是隔一段时间跑一次额外的压缩compactingpass不需要每次回收都压缩只要碎片化开始影响性能了再压缩就行。压缩的时候还可以对特别长寿的数据做特殊处理——这些数据往往会被压实成老年代最底部的一块稠密前缀dense prefix。HotSpot 的标记压缩回收器就是这么干的它不去搬动这层沉淀物代价是允许一定程度用户可指定的碎片化。三、几乎所有分代回收器都靠物理隔离区分代际这里有个前提要说清楚几乎所有分代式回收器都是靠物理上把不同代分开放来区分代际的而这就要求年轻代必须用复制式回收来管理。像 Appel 提出的那种复制回收器为了保守起见需要预留一块和被回收的这一代大小相等的复制保留区——因为最坏情况下这一代里所有对象都可能存活下来。不过实际情况没那么惨大多数对象根本活不过一次年轻代回收所以这个最坏情况的预留其实是有富余的。但也不是所有回收器都要物理隔离各代。比如 Android RuntimeART和 WebKit 的 Riptide 回收器就是原地管理所有对象用标记-清除来做不做物理隔离。更省空间的思路小复制保留区 动态切换McGachey 和 Hosking 提出了一个更聪明的办法用一块更小的复制保留区一旦发现保留区不够用了就从复制模式切换到压缩模式。这里的难点在于回收器必须能够边回收边切换因为保留区到底够不够用这件事只有在真正回收的过程中才会暴露出来没法提前预知。对应图2图9.7本文重点讲解的图这张图分两步图9.7(a)对象被复制或标记——这时候复制保留区已经满了。年轻代里黑色的对象是已经被复制搬进老年代的那些“灰色的对象是被标记了、但还没来得及复制的剩下所有没被标记也没被复制的新对象都是死的可以直接当垃圾扔掉。图9.7(b)标记的对象被压缩——压缩这一步会把灰色对象滑动”slide挪到老年代那一头去跟黑色对象紧挨在一起。像通常的压缩算法一样这个滑动过程要分好几趟才能做完。这里有个坑压缩会把黑色对象里留着的转发地址forwarding address给破坏掉。转发地址是干什么用的简单说当一个对象被复制走了原来的位置上会留一个指路牌告诉别的指针这个对象已经搬到哪儿去了这样别的对象还引用着旧地址时才能顺着指路牌找到新地址。可如果压缩把这块内存直接覆盖掉了这个指路牌就没了。McGachey 和 Hosking 的解决办法分两步第一遍扫描灰色的年轻代对象时先把所有指向已复制对象的引用给修正好相当于赶在指路牌被抹掉之前把该改的地址先改完。然后再用Jonkers 的滑动压缩算法在第3章讲过去搬动那些被标记的对象——之所以选这个算法是因为它是穿线式threaded的不需要在对象头里额外占空间来存转发信息。作者还提到其实还有更好的备选方案Compressor 算法第3章也讲过它既不用在对象头里占额外空间也不会覆写活对象的任何部分可能比 Jonkers 算法更合适拿来做这件事。最后说效果用相当于堆大小 10% 的复制保留区这个方案平均能带来4%的性能提升——个别情况下最高能到20%——对比的是那些老年代要么用纯复制、要么用纯标记-清除的 MMTk 回收器。小结文字版老年代回收贵是因为往往要连带回收所有更年轻的代。全堆回收基本不需要记忆集。老年代管理方案对比半空间复制简单但浪费空间、长寿对象被反复搬。标记-清除省空间但会碎片化需要不定期压缩。复制动态切换到压缩兼顾两者优点McGachey/Hosking 方案实测提速 4%~20%。图9.7 展示的正是复制保留区用满后切换成标记压缩这个动态切换过程的两个阶段。图1、图2见配套 PDF9.10 老对象优先回收Older-first Garbage Collection一、先想清楚分代回收到底在回收谁分代回收有个基本套路每次只处理堆里最年轻的一段前缀其余对象一律不碰。这段前缀具体多大取决于这次回收是只收 nursery最年轻的那一小块还是收几个中间代如果你的系统用了两代以上还是干脆收整个堆。那些自适应晋升的技术本质上就是在动态调整年轻前缀的边界目的是让年轻对象能多活一会儿给它们更多机会自然死亡减少无谓的复制开销。但分代回收只是避免每次都扫全堆的其中一种设计思路并不是唯一思路。如果我们把视角从分代换成更广义的按年龄分段其实还能想出好几种玩法按对象年龄分段可以有的几种策略只收最年轻的也就是标准分代回收只处理堆里最新的那批对象。只收最老的听起来对称但实际上不靠谱——因为这样会一遍又一遍地反复检查那些几乎不朽或者极长寿的对象纯属做无用功。前面章节提到过有些回收器干脆故意跳过这层古老沉积物就是因为这个原因。优先收中年对象也就是本节的主角older-first既不碰最年轻的让它们有充分时间自然死亡也不去反复折腾最老的减少无谓开销专挑中间年龄段下手。二、Older-first 面临的两大难题想让老对象优先这个思路真正落地要解决两个麻烦事难题一怎么界定老堆里对象年龄是个连续的谱系具体从哪个点开始算老对象用什么机制去标记和追踪这个边界本身就不简单。难题二指针管理更复杂了被回收的这批对象术语叫被判定/condemned的对象可能同时被比它更老的对象指着也可能被比它更年轻的对象指着——也就是说指向这批对象的指针可能来自两个方向老指向它或者新指向它这跟传统分代回收里只有老指向新这一种情况完全不同写屏障要处理的场景一下子变复杂了。下面介绍两种具体方案分别用不同思路解决这两个难题。三、方案一Renewal-Older-First更新式老对象优先回收核心想法这个方案对年龄的定义很朴素一个对象的年龄就是从它被创建、或者上一次被回收如果活下来了到现在经过的时间取二者中更新的那个时间点算起。Renewal-Older-First 每次都固定回收堆里最老的那一段前缀。具体怎么实现对应图1为了让记忆集remembered set好管理整个堆被切成k kk个大小相等的步进段step编号从老到新排列。规则很简单分配规则新对象永远分配到编号最小的那个空着的 step里也就是当前最年轻可用的那一段。回收触发条件堆满了。回收对象最老的k − j k-jk−j个 step图里灰色的那个窗口 window被判定为本次回收目标。存活对象去哪凡是在这次回收里活下来的对象会被疏散evacuate到堆的最年轻端新开的一块复制保留区里图里黑色的区域。这样一来存活对象相当于被更新了一次年龄——原本最年轻的 step从j jj到1 11现在变成了最老的那批堆里的年龄排序整体往前推进了一轮。图中堆是向右在虚拟地址空间里不断推进的。这个设计对写屏障的简化在哪因为堆总是往右变新的方向推进所以写屏障只需要盯住一种指针从右往左指的指针也就是从地址更大、也就是更年轻的对象指向地址更小、也就是编号≤ j \le j≤j的更老对象的那些指针——只有这种指针的来源地址比j jj大才需要被 mutator用户程序记录下来。这个方案的两个缺点缺点一地址空间会被耗尽上面这套堆一直往右推进的做法在 64 位地址空间下也许还撑得住但放到 32 位地址空间里很快地址就用光了。这时候 Renewal-Older-First 必须给所有 step 重新编号为下一轮回收做准备。而且写屏障也不能再简单地比较地址大小了得改成比较来源和目标各自属于哪个 step 编号——这需要查表而不是简单的地址比大小开销更高了。缺点二对象在堆里的真实年龄顺序被打乱了Renewal-Older-First 不保留对象在堆里按真实年龄排列的顺序而是把不同真实年龄的对象不可逆地混在一起。这里还提了个实践细节Hansen 在 Scheme 语言的 Larceny 实现里通过加一个标准的分代式 nursery过滤掉了很多不必要记录的指针也就是只用 Renewal-Older-First 来管理老年代年轻代还是走传统分代那一套。但即便这样他的记忆集依然很大。四、方案二Deferred-Older-First延迟式老对象优先回收核心想法这个方案的最大卖点是它保留了对象在堆里的真实年龄顺序不会像方案一那样把年龄搞乱。具体怎么实现对应图2想象堆是一条从最老左边到最新右边排列的长条有一个固定大小的回收窗口灰色区域像滑块一样在堆上从老的一端往新的一端滑动。触发回收堆满了的时候只回收这个窗口里的对象窗口两侧更老的、更年轻的的对象一律不碰图里的白色区域。存活对象去哪窗口里活下来的对象图里的黑色区域会被搬到堆里最老区域的紧挨着的后面。腾出来的空间怎么用回收后腾出来的空闲空间会被加到堆的最年轻最右端供后续分配使用。下一个窗口在哪紧挨着这次存活对象的右边也就是更年轻的方向。这个方案巧妙在哪自动寻找甜蜜点这个设计背后的直觉是随着窗口不断往右滑回收器会自己摸索到堆里的一个甜蜜点sweet spot——在这个区域窗口里的对象存活率特别低。一旦找到这个甜蜜点回收器的mark/cons 比率也就是每次回收标记的存活对象数量相对于分配总量的比值会变得很低窗口移动速度也会变得非常慢就像图里下面几行画的那样窗口移动的距离越来越小。不过总有一天窗口会滑到堆的最年轻端这时候回收器就必须把窗口重置回堆的最老端重新开始一轮。写屏障这里反而更复杂了虽然 Deferred-Older-First 保留了真实年龄顺序但代价是写屏障要记录的情况变多了mutator用户程序侧的写屏障必须记录所有从最老区域指向回收窗口或者最年轻区域的指针所有年轻指向老的指针但如果这个指针的来源本身就在被判定回收的窗口里就不用记。回收器collector自己在复制过程中的写屏障也必须记录所有从存活对象指向其他区域的指针所有年轻的存活对象指向老的存活对象的指针。同样Deferred-Older-First 的实现通常也会把堆切分成一个个 block给每个 block 关联一个死亡时间保证越老的 block死亡时间数值越大比年轻 block 的死亡时间大。写屏障就可以靠比较两个 block 的死亡时间来实现不过要小心处理死亡时间数值溢出这种边界情况。效果怎么样Deferred-Older-First 在最大暂停时间这个指标上确实比其他分代方案表现更好。但和 Renewal-Older-First 一样它也需要追踪更多的指针写屏障更复杂。一个现实的结论在较小的地址空间里older-first 这类算法很难跟其他优秀方案竞争因为它们那套更复杂的写屏障记录机制开销不小。但是在更大的地址空间比如 64 位里写屏障可以大幅简化这类算法反而可能更有竞争力。小结文字版分代回收本质上是只收最年轻前缀这一种按年龄分段回收的特例还可以有别的分法。Older-first 想专挑中年对象下手年轻的给时间自然死老的不反复折腾。两大难题怎么界定老对象、以及指针可能双向指向被回收对象导致写屏障复杂。Renewal-Older-First靠固定切成k kk个 step回收最老一批存活者搬到最年轻端重新计龄。优点是写屏障相对简单只需比较地址缺点是 32 位地址空间会耗尽需要重编号而且打乱了对象真实年龄顺序。Deferred-Older-First用一个固定大小窗口从老向新滑动回收窗口内对象存活者放到最老区域后面。优点是保留真实年龄顺序并能自动找到存活率低、窗口移动慢的甜蜜点缺点是写屏障要记录的指针种类更多更复杂。两种方案都在小地址空间里因写屏障开销竞争力不足但在 64 位这种大地址空间下更有前途。图1、图2见配套 PDF