logo标签列表

为什么间接增量比直接增量更快？

javaperformancejvm
53

这个问题之前被另一位Stack Overflow的成员提出过，但遗憾的是已经被删除。评论里说这些测量结果存在缺陷，毫无意义。

然而，我利用JMH进行了一个小型基准测试，成功地重现了原始问题：

package bench;

import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.runner.*;
import org.openjdk.jmh.runner.options.*;
import java.util.concurrent.*;

@State(Scope.Benchmark)
public class LoopInc {

    private int getValue() {
        return ThreadLocalRandom.current().nextInt(2);
    }

    @Benchmark
    public int directInc() {
        int result = 0;
        for (int i = 0; i < 1000; i++) {
            switch (getValue()) {
                case 0:
                    break;
                case 1:
                    result++;
                    break;
            }
        }
        return result;
    }

    @Benchmark
    public int indirectInc() {
        int result = 0;
        for (int i = 0; i < 1000; i++) {
            boolean incr = false;
            switch (getValue()) {
                case 0:
                    break;
                case 1:
                    incr = true;
                    break;
            }

            if (incr) {
                result++;
            }
        }
        return result;
    }

    public static void main(String[] args) throws RunnerException {
        Options options = new OptionsBuilder()
                .include("bench.LoopInc.*")
                .warmupIterations(5)
                .measurementIterations(10)
                .forks(3)
                .timeUnit(TimeUnit.MILLISECONDS)
                .build();
        new Runner(options).run();
    }
}

基准测试显示，indirectInc 的速度快了3倍，尽管这种“优化”根本不明显。有人可能会认为 indirectInc 速度应该会比较慢，因为它涉及额外的中间操作。

Benchmark             Mode  Cnt    Score   Error   Units
LoopInc.directInc    thrpt   30  127,301 ± 0,202  ops/ms
LoopInc.indirectInc  thrpt   30  378,147 ± 1,144  ops/ms


java version "1.8.0_51"
Java(TM) SE Runtime Environment (build 1.8.0_51-b16)
Java HotSpot(TM) 64-Bit Server VM (build 25.51-b03, mixed mode)

为什么JIT比较好地编译indirectInc而不是类似的directInc？

5
可能是一个热身问题。尝试颠倒你测试的顺序。 - ControlAltDel
我认为你可以让JMH打印汇编输出，这对此处会很有帮助。同时确保它使用C2进行编译。 - the8472
@PeterLawrey 我知道随机数生成很耗费资源，但这并不重要。即使我将 getValue 更改为返回预生成的序列，indirectInc 仍然会显著更快。 - apangin
@apangin，我建议你看一下使用JITWatch生成的汇编代码。 我预计更快的版本将被更大程度地优化，例如循环展开。 - Peter Lawrey
转储字节码并查看差异。 - Hot Licks
显示剩余11条评论
1个回答
71

好的，这是处理此类问题的方法。

  1. 尝试重现它。好的，它可以重现：

Benchmark             Mode  Cnt    Score   Error   Units
LoopInc.directInc    thrpt   15  175.678 ± 1.118  ops/ms
LoopInc.indirectInc  thrpt   15  641.413 ± 9.722  ops/ms
尝试使用-prof perfasm查看生成的汇编代码。长话短说，它会生成大量的代码，所以我们可能希望限制循环展开。但这可能会影响性能，并且可能是原因之一。因此，让我们重新运行-XX:LoopUnrollLimit=1。好的，得分降低了，但差异仍然存在，非常好。
Benchmark             Mode  Cnt    Score   Error   Units
LoopInc.directInc    thrpt   15  161.147 ± 6.101  ops/ms
LoopInc.indirectInc  thrpt   15  489.430 ± 1.698  ops/ms
再看一下生成的代码，没有什么特别引人注目的地方。嗯，这似乎很有趣。让我们好好研究一下。我们能够描述这个工作负载吗？当然可以，借助于 -prof perfnorm 的帮助，它可以将硬件计数器标准化为基准操作。让我们看看：
Benchmark                                     Mode  Cnt      Score      Error   Units
LoopInc.directInc                            thrpt   15    161.875 ±    3.038  ops/ms
LoopInc.directInc:·CPI                       thrpt    3      0.967 ±    0.196    #/op
LoopInc.directInc:·L1-dcache-load-misses     thrpt    3      0.394 ±    3.663    #/op
LoopInc.directInc:·L1-dcache-loads           thrpt    3   2149.594 ±  228.166    #/op
LoopInc.directInc:·L1-dcache-store-misses    thrpt    3      0.114 ±    1.001    #/op
LoopInc.directInc:·L1-dcache-stores          thrpt    3   1073.666 ±   96.066    #/op
LoopInc.directInc:·L1-icache-load-misses     thrpt    3      0.965 ±   22.984    #/op
LoopInc.directInc:·LLC-loads                 thrpt    3      0.204 ±    2.763    #/op
LoopInc.directInc:·LLC-stores                thrpt    3      0.060 ±    0.633    #/op
LoopInc.directInc:·branch-misses             thrpt    3    536.068 ±   43.293    #/op
LoopInc.directInc:·branches                  thrpt    3   3728.890 ±  220.539    #/op
LoopInc.directInc:·cycles                    thrpt    3  26219.146 ± 6287.590    #/op
LoopInc.directInc:·dTLB-load-misses          thrpt    3      0.063 ±    0.124    #/op
LoopInc.directInc:·dTLB-loads                thrpt    3   2136.942 ±  165.990    #/op
LoopInc.directInc:·dTLB-store-misses         thrpt    3      0.022 ±    0.029    #/op
LoopInc.directInc:·dTLB-stores               thrpt    3   1084.787 ±  417.281    #/op
LoopInc.directInc:·iTLB-load-misses          thrpt    3      0.081 ±    0.333    #/op
LoopInc.directInc:·iTLB-loads                thrpt    3      3.623 ±   19.955    #/op
LoopInc.directInc:·instructions              thrpt    3  27114.052 ± 1843.720    #/op

LoopInc.indirectInc                          thrpt   15    489.164 ±    2.692  ops/ms
LoopInc.indirectInc:·CPI                     thrpt    3      0.281 ±    0.015    #/op
LoopInc.indirectInc:·L1-dcache-load-misses   thrpt    3      0.503 ±    9.071    #/op
LoopInc.indirectInc:·L1-dcache-loads         thrpt    3   2149.806 ±  369.040    #/op
LoopInc.indirectInc:·L1-dcache-store-misses  thrpt    3      0.167 ±    1.370    #/op
LoopInc.indirectInc:·L1-dcache-stores        thrpt    3   1073.895 ±  186.741    #/op
LoopInc.indirectInc:·L1-icache-load-misses   thrpt    3      0.313 ±    1.275    #/op
LoopInc.indirectInc:·branch-misses           thrpt    3      1.102 ±    0.375    #/op
LoopInc.indirectInc:·branches                thrpt    3   2143.670 ±  228.475    #/op
LoopInc.indirectInc:·cycles                  thrpt    3   8701.665 ±  706.183    #/op
LoopInc.indirectInc:·dTLB-load-misses        thrpt    3      0.020 ±    0.301    #/op
LoopInc.indirectInc:·dTLB-loads              thrpt    3   2141.965 ±  135.852    #/op
LoopInc.indirectInc:·dTLB-store-misses       thrpt    3      0.002 ±    0.029    #/op
LoopInc.indirectInc:·dTLB-stores             thrpt    3   1070.376 ±   81.445    #/op
LoopInc.indirectInc:·iTLB-load-misses        thrpt    3      0.007 ±    0.135    #/op
LoopInc.indirectInc:·iTLB-loads              thrpt    3      0.310 ±    5.768    #/op
LoopInc.indirectInc:·instructions            thrpt    3  30968.207 ± 3627.540    #/op

哦，两种基准测试的指令数量相当。速度较慢的需要更多的周期（这就是为什么directInc中CPI也不理想；然而，在indirectInc中，产生了接近理想的CPI）。如果您仔细查看可能的原因：没有太多的缓存未命中，没有太多的TLB未命中，但是慢基准测试有很多分支未命中。啊哈！现在我们知道要在生成的代码中查找什么。

  • 让我们再次查看生成的代码。-prof perfasm方便地突出显示跳转。然后你会看到这个...

    directInc:

                      ╭│      0x00007fa0a82a50ff: jmp    0x00007fa0a82a5116
 11.39%   16.90%  ││ ↗    0x00007fa0a82a5101: inc    %edx               ;*iinc
                  ││ │                                                  ; - org.openjdk.LoopInc::directInc@46 (line 18)
 12.52%   23.11%  ││ │↗↗  0x00007fa0a82a5103: mov    %r10,0xe8(%r11)    ;*invokevirtual putLong
                  ││ │││                                                ; - java.util.concurrent.ThreadLocalRandom::nextSeed@27 (line 241)
 12.00%    8.14%  ││ │││  0x00007fa0a82a510a: inc    %r8d               ;*iinc
                  ││ │││                                                ; - org.openjdk.LoopInc::directInc@46 (line 18)
  0.03%    0.03%  ││ │││  0x00007fa0a82a510d: cmp    $0x3e8,%r8d
                  │╰ │││  0x00007fa0a82a5114: jge    0x00007fa0a82a50c7  ;*aload_0
                  │  │││                                                ; - org.openjdk.LoopInc::directInc@11 (line 19)
  0.80%    0.91%  ↘  │││  0x00007fa0a82a5116: mov    0xf0(%r11),%r10d   ;*invokevirtual getInt
                     │││                                                ; - java.util.concurrent.ThreadLocalRandom::current@9 (line 222)
  4.28%    1.23%     │││  0x00007fa0a82a511d: test   %r10d,%r10d
                    ╭│││  0x00007fa0a82a5120: je     0x00007fa0a82a517b  ;*ifne
                    ││││                                                ; - java.util.concurrent.ThreadLocalRandom::current@12 (line 222)
  2.11%    0.01%    ││││  0x00007fa0a82a5122: movabs $0x9e3779b97f4a7c15,%r10
  0.01%    0.07%    ││││  0x00007fa0a82a512c: add    0xe8(%r11),%r10    ;*ladd
                    ││││                                                ; - java.util.concurrent.ThreadLocalRandom::nextSeed@24 (line 242)
  7.73%    1.89%    ││││  0x00007fa0a82a5133: mov    %r10,%r9
  1.21%    1.84%    ││││  0x00007fa0a82a5136: shr    $0x21,%r9
  1.90%    0.03%    ││││  0x00007fa0a82a513a: xor    %r10,%r9
  2.02%    0.03%    ││││  0x00007fa0a82a513d: movabs $0xff51afd7ed558ccd,%rcx
  0.94%    1.82%    ││││  0x00007fa0a82a5147: imul   %rcx,%r9           ;*lmul
                    ││││                                                ; - java.util.concurrent.ThreadLocalRandom::mix32@9 (line 182)
  7.01%    2.40%    ││││  0x00007fa0a82a514b: mov    %r9,%rcx
                    ││││  0x00007fa0a82a514e: shr    $0x21,%rcx
  1.89%    0.70%    ││││  0x00007fa0a82a5152: xor    %r9,%rcx
  3.11%    2.55%    ││││  0x00007fa0a82a5155: movabs $0xc4ceb9fe1a85ec53,%r9
  0.99%    1.50%    ││││  0x00007fa0a82a515f: imul   %r9,%rcx
  7.66%    2.89%    ││││  0x00007fa0a82a5163: shr    $0x20,%rcx
  3.70%    1.97%    ││││  0x00007fa0a82a5167: mov    %ecx,%r9d
           0.11%    ││││  0x00007fa0a82a516a: and    $0x1,%r9d          ;*iand
                    ││││                                                ; - java.util.concurrent.ThreadLocalRandom::nextInt@34 (line 356)
  3.76%   11.13%    ││││  0x00007fa0a82a516e: cmp    $0x1,%r9d
                    │╰││  0x00007fa0a82a5172: je     0x00007fa0a82a5101
 10.48%   16.62%    │ ││  0x00007fa0a82a5174: test   %r9d,%r9d
                    │ ╰│  0x00007fa0a82a5177: je     0x00007fa0a82a5103  ;*lookupswitch
                    │  │                                                ; - org.openjdk.LoopInc::directInc@15 (line 19)
                    │  ╰  0x00007fa0a82a5179: jmp    0x00007fa0a82a5103  ;*aload_0
                    │                                                   ; - org.openjdk.LoopInc::directInc@11 (line 19)
                    ↘     0x00007fa0a82a517b: mov    $0xffffff5d,%esi

    间接增量:

      0.01%    0.01%  ↗  0x00007f65588d8260: mov    %edx,%r9d
  0.01%           │  0x00007f65588d8263: nopw   0x0(%rax,%rax,1)
 11.99%   11.38%  │  0x00007f65588d826c: data16 data16 xchg %ax,%ax  ;*iconst_0
                  │                                                ; - org.openjdk.LoopInc::indirectInc@11 (line 34)
                  │  0x00007f65588d8270: mov    0xf0(%r8),%r10d    ;*invokevirtual getInt
                  │                                                ; - java.util.concurrent.ThreadLocalRandom::current@9 (line 222)
                  │  0x00007f65588d8277: test   %r10d,%r10d
                  │  0x00007f65588d827a: je     0x00007f65588d8331  ;*ifne
                  │                                                ; - java.util.concurrent.ThreadLocalRandom::current@12 (line 222)
  0.01%           │  0x00007f65588d8280: movabs $0x9e3779b97f4a7c15,%r10
 11.80%   11.49%  │  0x00007f65588d828a: add    0xe8(%r8),%r10     ;*ladd
                  │                                                ; - java.util.concurrent.ThreadLocalRandom::nextSeed@24 (line 242)
  0.01%    0.01%  │  0x00007f65588d8291: mov    %r10,0xe8(%r8)     ;*invokevirtual putLong
                  │                                                ; - java.util.concurrent.ThreadLocalRandom::nextSeed@27 (line 241)
                  │  0x00007f65588d8298: mov    %r9d,%edx
  0.01%    0.01%  │  0x00007f65588d829b: inc    %edx
 11.12%   12.40%  │  0x00007f65588d829d: mov    %r10,%rcx
           0.01%  │  0x00007f65588d82a0: shr    $0x21,%rcx
  0.03%           │  0x00007f65588d82a4: xor    %r10,%rcx
  0.06%    0.03%  │  0x00007f65588d82a7: movabs $0xff51afd7ed558ccd,%r10
 12.38%   13.94%  │  0x00007f65588d82b1: imul   %r10,%rcx          ;*lmul
                  │                                                ; - java.util.concurrent.ThreadLocalRandom::mix32@9 (line 182)
  0.03%    0.01%  │  0x00007f65588d82b5: mov    %rcx,%r10
                  │  0x00007f65588d82b8: shr    $0x21,%r10
           0.03%  │  0x00007f65588d82bc: xor    %rcx,%r10
 11.43%   12.62%  │  0x00007f65588d82bf: movabs $0xc4ceb9fe1a85ec53,%rcx
           0.01%  │  0x00007f65588d82c9: imul   %rcx,%r10
  0.34%    0.30%  │  0x00007f65588d82cd: shr    $0x20,%r10
  0.85%    0.76%  │  0x00007f65588d82d1: mov    %r10d,%r10d
 11.81%   11.51%  │  0x00007f65588d82d4: and    $0x1,%r10d
  2.16%    1.78%  │  0x00007f65588d82d8: cmp    $0x1,%r10d
  3.45%    3.00%  │  0x00007f65588d82dc: cmovne %r9d,%edx         <----- HERE IT IS
 17.55%   15.86%  │  0x00007f65588d82e0: inc    %r11d              ;*iinc
                  │                                                ; - org.openjdk.LoopInc::indirectInc@56 (line 33)
                  │  0x00007f65588d82e3: cmp    $0x3e8,%r11d
                  ╰  0x00007f65588d82ea: jl     0x00007f65588d8260  ;*if_icmpge
                                                           ; - org.openjdk.LoopInc::indirectInc@8 (line 33)

    请注意，这里使用的是cmovne而不是jmp，这就是为什么我们有更多"可预测的"分支。HotSpot对分支进行了剖析，并在分支剖析非常平稳时发出条件移动指令。换句话说，通过支付一点额外的延迟来避免非常可能的分支错误预测。然而，在这种情况下，switch语句是特殊的：它有超过两个选项（0、1和"nothing"）。因此，我猜想result自增不会被合并到cmov中。（一般来说，HotSpot本可以把零存储到"default"中的result中，但它失败了，哎呀）

  • 为了证实这个假设，让我们创建一个directCompleteInc的例子，其中我们仍然使用switch，但现在涵盖了所有情况：

    @Benchmark
public int directCompleteInc() {
    int result = 0;
    for (int i = 0; i < 1000; i++) {
        switch (getValue()) {
            case 1:
                result++;
                break;
            default:
                break;
        }
    }
    return result;
}

    ...并且测量它，这一次不使用任何选项，就像OP所做的那样：

    Benchmark                   Mode  Cnt    Score    Error   Units
LoopInc.directCompleteInc  thrpt    5  644.414 ±  0.371  ops/ms
LoopInc.directInc          thrpt    5  174.974 ±  0.103  ops/ms
LoopInc.indirectInc        thrpt    5  644.015 ±  0.533  ops/ms

    THERE.

  • 确认 directCompleteInc 是否使用了 cmov 并开启了 -prof perfasm。确实是这样。

  • 喝完它。

    • 4
    是的，我也注意到在生成的汇编代码中使用了 cmov 而不是 jmp，并且验证了如果我使用 -XX:ConditionalMoveLimit=0 禁用 cmov，两种情况的速度都一样慢。但仍然不清楚为什么 HotSpot 不能在第一种情况下生成 cmov。我还检查了如果我用可预测的序列替换随机序列，那么两种情况的速度都会一样快，这样 perf 报告的错误分支数量会小得多。总之，这是一个很棒的答案！ - apangin
    1
    顺便问一下，Windows有没有类似于“-prof perfnorm”的模拟器？ - apangin
    @apangin：Windows有“-prof xperfasm”，但没有“perfnorm”。我不知道Windows上是否有“perf stat”的替代方法，所以... - Aleksey Shipilev
    2
    @apangin：我猜测非完整开关生成的IR形状可能会让cmov折叠产生困惑，因为存在超过两个分支。但这只是一种推测，你告诉我吧 ;) - Aleksey Shipilev
    再次感谢您提供的出色答案和方法论课程。我只想补充一点：虽然这在JVM中找到了一个良好的（失败的）微观优化点，但我猜几乎没有真正重要的场合（也许你能够复制错误/正确的优化吗？）。 - eckes
    4
    像JVM这样的复杂环境中，存在许多看似微不足道的问题，可能会使事情不如您所愿。如果那些微小的差异对您很重要（即您认为它们是问题），那么可以使用类似上述方法来避免它们。此外，玩具示例为您提供了在深入研究实际案例之前，在简单案例中学习的机会。 - Aleksey Shipilev
    网页内容由stack overflow 提供, 点击上面的
    可以查看英文原文，
    原文链接