JVM 解剖公园(11): 移动 GC 与局部性
（给ImportNew加星标，提高Java技能）
编译：ImportNew/唐尤华
shipilev.net/jvm/anatomy-quarks/11-moving-gc-locality/
1. 写在前面
“JVM 解剖公园”是一个持续更新的系列迷你博客，阅读每篇文章一般需要5到10分钟。限于篇幅，仅对某个主题按照问题、测试、基准程序、观察结果深入讲解。因此，这里的数据和讨论可以当轶事看，不做写作风格、句法和语义错误、重复或一致性检查。如果选择采信文中内容，风险自负。
Aleksey Shipilёv，JVM 性能极客
推特 @shipilev
问题、评论、建议发送到 aleksey@shipilev.net"">aleksey@shipilev.net
2. 问题
据说如果并不关心分配速度与内存碎片，垃圾回收器也可以不移动。是不是还有其他方案？
3. 理论
打开 GC 手册，有一个小节讨论“压缩是否必要? ”，最后的结论是：
标记-压缩回收器可以保持堆中对象的分配顺序，也可以对其任意重排。虽然任意顺序能够比其他标记-压缩回收器速度更快，也不会带来空间开销，但是会破坏 Mutator（应用线程）的局部性。
— GC 手册
3.5. 需要考虑的问题，局部性
真的很重要吗？
4. 实验
下面是我们设计的一个简单的实验，试图揭开背后的工作机制。在测试用例首先初始化数组，接着进行 shuffle 操作或者不做任何操作，然后遍历数组。JMH 执行测试如下：
import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.infra.*;
@State(Scope.Thread)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Fork(value = 1, jvmArgsAppend = {"-Xms8g", "-Xmx8g", "-Xmn7g" })
public class ArrayWalkBench {
@Param({"16", "256", "4096", "65536", "1048576", "16777216"})
int size;
@Param({"false", "true"})
boolean shuffle;
@Param({"false", "true"})
boolean gc;
String[] arr;
@Setup
public void setup() throws IOException, InterruptedException {
arr = new String[size];
for (int c = 0; c < size; c++) {
arr[c] = "Value" + c;
}
if (shuffle) {
Collections.shuffle(Arrays.asList(arr), new Random(0xBAD_BEE));
}
if (gc) {
for (int c = 0; c < 5; c++) {
System.gc();
TimeUnit.SECONDS.sleep(1);
}
}
}
@Benchmark
public void walk(Blackhole bh) {
for (String val : arr) {
bh.consume(val.hashCode());
}
}
}可以注意到这个实验有三个自由度：
size：数组大小。通过尝试不同大小来避免命中偶然最佳结果。
shuffle：遍历前是否执行 shuffle。启用 shuffle 可以模拟不按照顺序插入以及插入时数组未排序的情况。
gc：准备好数据集后强制 GC。由于没有在 payload 代码中分配，因此需要显式调用强制 GC，否则可能永远不会运行。
让我们通过 -XX:+UseParallelGC 选项观察不同设置条件下运行的结果：
Benchmark (gc) (shuffle) (size) Mode Cnt Score Error Units
ArrayWalkBench.walk false false 16 avgt 5 0.051 ± 0.001 us/op
ArrayWalkBench.walk false false 256 avgt 5 0.821 ± 0.001 us/op
ArrayWalkBench.walk false false 4096 avgt 5 14.516 ± 0.026 us/op
ArrayWalkBench.walk false false 65536 avgt 5 307.210 ± 4.789 us/op
ArrayWalkBench.walk false false 1048576 avgt 5 4306.660 ± 7.950 us/op
ArrayWalkBench.walk false false 16777216 avgt 5 60561.476 ± 925.685 us/op
ArrayWalkBench.walk false true 16 avgt 5 0.051 ± 0.001 us/op
ArrayWalkBench.walk false true 256 avgt 5 0.823 ± 0.003 us/op
ArrayWalkBench.walk false true 4096 avgt 5 18.646 ± 0.044 us/op
ArrayWalkBench.walk false true 65536 avgt 5 461.187 ± 31.183 us/op
ArrayWalkBench.walk false true 1048576 avgt 5 16350.706 ± 75.757 us/op
ArrayWalkBench.walk false true 16777216 avgt 5 312296.960 ± 632.552 us/op
ArrayWalkBench.walk true false 16 avgt 5 0.051 ± 0.001 us/op
ArrayWalkBench.walk true false 256 avgt 5 0.820 ± 0.004 us/op
ArrayWalkBench.walk true false 4096 avgt 5 13.639 ± 0.063 us/op
ArrayWalkBench.walk true false 65536 avgt 5 174.475 ± 0.771 us/op
ArrayWalkBench.walk true false 1048576 avgt 5 4345.980 ± 15.230 us/op
ArrayWalkBench.walk true false 16777216 avgt 5 68687.192 ± 1375.171 us/op
ArrayWalkBench.walk true true 16 avgt 5 0.051 ± 0.001 us/op
ArrayWalkBench.walk true true 256 avgt 5 0.828 ± 0.010 us/op
ArrayWalkBench.walk true true 4096 avgt 5 13.749 ± 0.088 us/op
ArrayWalkBench.walk true true 65536 avgt 5 174.230 ± 0.655 us/op
ArrayWalkBench.walk true true 1048576 avgt 5 4365.162 ± 88.927 us/op
ArrayWalkBench.walk true true 16777216 avgt 5 70631.288 ± 1144.980 us/op从上面的结果中可以了解到什么？
可以看到，遍历打乱后的数组确实比遍历初始化排序的数组慢得多，花费时间大约是后者的4倍！这告诉我们对象的内存布局很重要！在初始化过程中可以通过代码进行控制，但外部客户端（随机）放置对象时就无法做到这一点。
此外还可以看到，GC 发生后两种情况都得到了改善。因为 GC 压缩了临时对象中数组占据的空间，并且可能的话会移动内存中的对象按照数组排序。执行 shuffle 与不进行 shuffle 的差异基本消失了。这里得到另外的启示：GC 在应用程序的运行中增加了开销，但同时通过为对象进行重新排序增强了局部性从而提高效率，如下图所示：
如果垃圾回收器不移动对象，那么只付出了 GC 开销却没有享受到它带来的好处。实际上，这就是为什么像 Epsilon 这样的 GC 比使用压缩的 GC 运行更慢的原因。Epsilon 运行相同负载后的结果（gc = true 在这里不起作用）：
译注：Epsilon 是一个试验性 GC。处理内存分配，但不进行任何实际的内存回收机制。一旦 Java 堆耗尽 JVM 就会关闭。
Benchmark (gc) (shuffle) (size) Mode Cnt Score Error Units
ArrayWalkBench.walk false false 16 avgt 5 0.051 ± 0.001 us/op
ArrayWalkBench.walk false false 256 avgt 5 0.826 ± 0.006 us/op
ArrayWalkBench.walk false false 4096 avgt 5 14.556 ± 0.049 us/op
ArrayWalkBench.walk false false 65536 avgt 5 274.073 ± 37.163 us/op
ArrayWalkBench.walk false false 1048576 avgt 5 4383.223 ± 997.953 us/op
ArrayWalkBench.walk false false 16777216 avgt 5 60322.171 ± 266.683 us/op
ArrayWalkBench.walk false true 16 avgt 5 0.051 ± 0.001 us/op
ArrayWalkBench.walk false true 256 avgt 5 0.826 ± 0.007 us/op
ArrayWalkBench.walk false true 4096 avgt 5 18.169 ± 0.165 us/op
ArrayWalkBench.walk false true 65536 avgt 5 312.345 ± 26.149 us/op
ArrayWalkBench.walk false true 1048576 avgt 5 16445.739 ± 54.241 us/op
ArrayWalkBench.walk false true 16777216 avgt 5 311573.643 ± 3650.280 us/op是的，你没有看错，Epsilon 比 Parallel 运行慢。作为 no-op GC，Epsilon 不会引起 GC 开销，但也没有带来任何好处。
造成性能差异的原因很简单，用 -prof perfnorm 就能看出来（用 -opi 1048576 除以元素个数)：
Benchmark (gc) (shuffle) (size) Mode Cnt Score Error Units
walk true true 1048576 avgt 25 4.247 ± 0.090 ns/op
walk:CPI true true 1048576 avgt 5 0.498 ± 0.050 #/op
walk:L1-dcache-load-misses true true 1048576 avgt 5 0.955 ± 0.025 #/op
walk:L1-dcache-loads true true 1048576 avgt 5 12.149 ± 0.432 #/op
walk:L1-dcache-stores true true 1048576 avgt 5 7.027 ± 0.176 #/op
walk:LLC-load-misses true true 1048576 avgt 5 0.156 ± 0.029 #/op
walk:LLC-loads true true 1048576 avgt 5 0.514 ± 0.014 #/op
walk:cycles true true 1048576 avgt 5 17.056 ± 1.673 #/op
walk:instructions true true 1048576 avgt 5 34.223 ± 0.860 #/op
walk false true 1048576 avgt 25 16.155 ± 0.101 ns/op
walk:CPI false true 1048576 avgt 5 1.885 ± 0.069 #/op
walk:L1-dcache-load-misses false true 1048576 avgt 5 1.922 ± 0.076 #/op
walk:L1-dcache-loads false true 1048576 avgt 5 12.128 ± 0.326 #/op
walk:L1-dcache-stores false true 1048576 avgt 5 7.032 ± 0.212 #/op
walk:LLC-load-misses false true 1048576 avgt 5 1.031 ± 0.032 #/op
walk:LLC-loads false true 1048576 avgt 5 1.365 ± 0.101 #/op
walk:cycles false true 1048576 avgt 5 64.700 ± 2.613 #/op
walk:instructions false true 1048576 avgt 5 34.335 ± 1.564 #/op对于 shuffle 版本，每条指令大约需要2个时钟周期，并且最后一级缓存几乎每次都没有命中。这就解释了为什么会运行得更慢：遍历随机数组会带来很大开销。
5. 观察
有关 GC 讨论的讽刺之处在于，有了 GC 某些时候会痛苦，但是没有 GC 有时也会痛苦！
对与不移动对象的 GC 非常容易低估增强局部性带来的效果。
我认为 CMS 运行良好其中一个原因，在把特定对象提交到“老年代”之前，对“年轻代”对象集合进行压缩而不是直接放入“老年代”。像 Serial 和 Parallel 这样的 STW 回收器都能从中受益。像 G1 和 Shenandoah 这样的区域化回收器可以而且也应该利用这个优势，尽管由于堆遍历与清空操作是分离需要更多的工作。声称局部性没有用是很武断的。在 NUMA 架构下，局部性带来的性能惩罚会飙升，把整体性能彻底搞砸。
宣称地点无关紧要将是大胆的。进入 NUMA，其地区罚款飙升，并准备得到皇家螺丝。
译注：NUMA（Non-uniform memory access 非统一内存访问架构）是一种用于多处理器的计算机存储设计，内存访问时间取决于处理器的内存位置。
值得注意的是，这里的局部性属性指对象图而非对象本身的布局。即使某种语言提供了控制对象的内存布局的能力，但据我所知也只包括对象内部结构（比如结构数组、对象集合等）而非对象图。一旦把常规对象放到非稠密数组以外的内存中，比如链表、链式队列、concurrent skiplist、链式 HashTable 等，除非内存管理器可以移动对象，否则只能用这种特定的方式线性化对象图。
译注：对象图（object graph），在面向对象程序中，一组对象通过对象之间关系、对象间引用或一系列中间引用形成一个网络，这些对象组称为对象图。
还要注意，这种局部性属性是动态的。换句话说，它依赖于应用程序特定会话的实际运行情况，因为在运行时应用程序会改变对象图。重新分配数据结构可以教会应用程序如何恰当地进行反馈，但随着工作的进行你会发现自己实现了移动动态内存管理器或者移动 GC。
局部性与分配比率无关。可以注意到，上面的示例工作负载几乎完全是静态的，这也是现实中大多数垃圾回收的情况。这些大块空间代表了内存中频繁更改的数据块。在变更频繁发生的情况下，让 GC 适应新的布局后运行一段时间直到再次改变是很有意义的。除非精心设计，否则寄希望应用本身按照顺序排列从局部性中受益只可能是一厢情愿。
当有人告诉你使用非移动 GC 或者无 GC 方案可以很好运行时，请格外小心。很有可能他们把局部性问题（不是其他内存管理问题）转移到你的代码中解决。没有什么方案不会带来隐性成本。也许这种方案效果很好，带来的收益会超过已知成本？还是只是你自己忽略了成本，而卖家又巧妙地回避了这个话题？
推荐阅读
（点击标题可跳转阅读）
成为 Java GC 专家（ 3 ）: 如何优化 Java 垃圾回收机制
看完本文有收获？请转发分享给更多人
关注「ImportNew」，提升Java技能
好文章，我在看❤️