JVM 解剖公园(11): 移动 GC 与局部性

2019 Java 开发者跳槽指南.pdf (吐血整理)….>>>

编译: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());
        }
    }
}

可以注意到这个实验有三个自由度:

  1. size:数组大小。通过尝试不同大小来避免命中偶然最佳结果。
  2. shuffle:遍历前是否执行 shuffle。启用 shuffle 可以模拟不按照顺序插入以及插入时数组未排序的情况。
  3. 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 在应用程序的运行中增加了开销,但同时通过为对象进行重新排序增强了局部性从而提高效率,如下图所示:

 

JVM 解剖公园(11): 移动 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 方案可以很好运行时,请格外小心。很有可能他们把局部性问题(不是其他内存管理问题)转移到你的代码中解决。没有什么方案不会带来隐性成本。也许这种方案效果很好,带来的收益会超过已知成本?还是只是你自己忽略了成本,而卖家又巧妙地回避了这个话题?

 

原文始发于微信公众号(ImportNew):JVM 解剖公园(11): 移动 GC 与局部性