Java Math.abs(int) 优化,为什么这段代码要慢6倍?

18

你可能知道,Math.abs(Integer.MIN_VALUE) == Integer.MIN_VALUE,为了避免出现负数,我的项目中实现了safeAbs方法:

    public static int safeAbs(int i) {
        i = Math.abs(i);

        return i < 0 ? 0 : i;
    }

我将以下内容进行了性能比较:
    public static int safeAbs(int i) {
        return i == Integer.MIN_VALUE ? 0 : Math.abs(i);
    }

第一个版本比第二个版本慢了近6倍(第二个版本的性能几乎与“纯”Math.abs(int)相同)。从我的角度来看,字节码没有显著的差异,但我猜差异存在于JIT“汇编”代码中:

“慢”版本:

  0x00007f0149119720: mov     %eax,0xfffffffffffec000(%rsp)
  0x00007f0149119727: push    %rbp
  0x00007f0149119728: sub     $0x20,%rsp
  0x00007f014911972c: test    %esi,%esi
  0x00007f014911972e: jl      0x7f0149119734
  0x00007f0149119730: mov     %esi,%eax
  0x00007f0149119732: jmp     0x7f014911973c
  0x00007f0149119734: neg     %esi
  0x00007f0149119736: test    %esi,%esi
  0x00007f0149119738: jl      0x7f0149119748
  0x00007f014911973a: mov     %esi,%eax
  0x00007f014911973c: add     $0x20,%rsp
  0x00007f0149119740: pop     %rbp
  0x00007f0149119741: test    %eax,0x1772e8b9(%rip)  ;   {poll_return}
  0x00007f0149119747: retq
  0x00007f0149119748: mov     %esi,(%rsp)
  0x00007f014911974b: mov     $0xffffff65,%esi
  0x00007f0149119750: nop
  0x00007f0149119753: callq   0x7f01490051a0    ; OopMap{off=56}
                                                ;*ifge
                                                ; - math.FastAbs::safeAbsSlow@6 (line 16)
                                                ;   {runtime_call}
  0x00007f0149119758: callq   0x7f015f521d20    ;   {runtime_call}

"普通"版本:

  # {method} {0x00007f31acf28cd8} 'safeAbsFast' '(I)I' in 'math/FastAbs'
  # parm0:    rsi       = int
  #           [sp+0x30]  (sp of caller)
  0x00007f31b08c7360: mov     %eax,0xfffffffffffec000(%rsp)
  0x00007f31b08c7367: push    %rbp
  0x00007f31b08c7368: sub     $0x20,%rsp
  0x00007f31b08c736c: cmp     $0x80000000,%esi
  0x00007f31b08c7372: je      0x7f31b08c738e
  0x00007f31b08c7374: mov     %esi,%r10d
  0x00007f31b08c7377: neg     %r10d
  0x00007f31b08c737a: test    %esi,%esi
  0x00007f31b08c737c: mov     %esi,%eax
  0x00007f31b08c737e: cmovl   %r10d,%eax
  0x00007f31b08c7382: add     $0x20,%rsp
  0x00007f31b08c7386: pop     %rbp
  0x00007f31b08c7387: test    %eax,0x162c2c73(%rip)  ;   {poll_return}
  0x00007f31b08c738d: retq
  0x00007f31b08c738e: mov     %esi,(%rsp)
  0x00007f31b08c7391: mov     $0xffffff65,%esi
  0x00007f31b08c7396: nop
  0x00007f31b08c7397: callq   0x7f31b07b11a0    ; OopMap{off=60}
                                                ;*if_icmpne
                                                ; - math.FastAbs::safeAbsFast@3 (line 17)
                                                ;   {runtime_call}
  0x00007f31b08c739c: callq   0x7f31c5863d20    ;   {runtime_call}

基准测试代码:

@BenchmarkMode(Mode.AverageTime)
@Fork(value = 1, jvmArgsAppend = {"-Xms3g", "-Xmx3g", "-server"})
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@State(Scope.Benchmark)
@Threads(1)
@Warmup(iterations = 10)
@Measurement(iterations = 10)
public class SafeAbsMicroBench {

    @State(Scope.Benchmark)
    public static class Data {
        final int len = 10_000_000; 

        final int[] values = new int[len];

        @Setup(Level.Trial)
        public void setup() {
            // preparing 10 million random integers without MIN_VALUE
            for (int i = 0; i < len; i++) {
                int val;

                do {
                    val = ThreadLocalRandom.current().nextInt();
                } while (val == Integer.MIN_VALUE);

                values[i] = val;
            }
        }
    }

    @Benchmark
    public int safeAbsSlow(Data data) {
        int sum = 0;

        for (int i = 0; i < data.len; i++)
            sum += safeAbsSlow(data.values[i]);

        return sum;
    }

    @Benchmark
    public int safeAbsFast(Data data) {
        int sum = 0;

        for (int i = 0; i < data.len; i++)
            sum += safeAbsFast(data.values[i]);

        return sum;
    }

    private int safeAbsSlow(int i) {
        i = Math.abs(i);

        return i < 0 ? 0 : i;
    }

    private int safeAbsFast(int i) {
        return i == Integer.MIN_VALUE ? 0 : Math.abs(i);
    }

    public static void main(String[] args) throws RunnerException {
        final Options options = new OptionsBuilder()
            .include(SafeAbsMicroBench.class.getSimpleName())
            .build();

        new Runner(options).run();
    }
}

结果(Linux x86-64,7820HQ,在oracle jdk 8和11上进行了测试,结果非常相似)。

Benchmark                      Mode  Cnt         Score        Error  Units
SafeAbsMicroBench.safeAbsFast  avgt   10   6435155.516 ±  47130.767  ns/op
SafeAbsMicroBench.safeAbsSlow  avgt   10  35646411.744 ± 776173.621  ns/op

有人能解释一下为什么第一段代码比第二段代码慢得多吗?

2
“正常”版本有一个cmov,而“慢速”版本则分支,但它们都在返回下面有一些神秘的分支,这是怎么回事? - harold
感谢您指出CMOV,但我并不完全理解您的问题,我不是汇编语言专家,为了简单起见,我只复制了编译方法中看起来不同的部分 - 如果需要,我可以展开它,但我认为每个人都可以“打印汇编代码”。 - xtern
5
不相关,但是Integer.MAX_VALUE是否比abs(Integer.MIN_VALUE)更好的替代品?当然,它会偏差一个,但这仍然比偏差2147483648好。 - tobias_k
1
@tobias_k 嗯,0是你可以得到的最小绝对值。从语义上讲,0似乎是一个不错的选择... - dpr
2
“天真”的答案是:1. 在“慢速”情况下,abs函数总是被调用,汇编包含“更多”的跳转指令(对于abs本身和后续的比较)。2. 在“快速”情况下,只有一个跳转,并且这个跳转检查一个精确值,而且在测试中从未执行过(呀啊-分支预测-也许...?)。因此,在快速情况下,它只是遍历一系列指令,在慢速情况下,它必须跳转得更多。将500万个MIN_VALUE添加到测试中可能会很有趣... - Marco13
显示剩余3条评论
1个回答

7

对于safeAbsSlowsafeAbsFast方法,生成的本机代码存在差异。

safeAbsSlow(C2,级别4):

0x0000023d12ec4b14: add     eax,ecx
0x0000023d12ec4b16: inc     ebx

0x0000023d12ec4b18: cmp     ebx,989680h
0x0000023d12ec4b1e: jnl     23d12ec4b4eh ; jump if `ebx` was not less than `10_000_000`

0x0000023d12ec4b20: mov     ecx,dword ptr [r9+rbx*4+10h]

0x0000023d12ec4b25: test    ecx,ecx
0x0000023d12ec4b27: jnl     23d12ec4b14h ; jump if `ecx` was not less-than `0`

0x0000023d12ec4b29: neg     ecx

0x0000023d12ec4b2b: test    ecx,ecx
0x0000023d12ec4b2d: jnl     23d12ec4b14h ; jump if `ecx` was not less-than `0`

safeAbsFast (C2, level 4):

0x000001d89e8a4b20: mov     ecx,dword ptr [r9+rdi*4+10h]

0x000001d89e8a4b25: cmp     ecx,80000000h
0x000001d89e8a4b2b: je      1d89e8a4b66h ; jump if `ecx` was equal to `2147483648`

0x000001d89e8a4b2d: mov     r11d,ecx
0x000001d89e8a4b30: neg     r11d
0x000001d89e8a4b33: test    ecx,ecx
0x000001d89e8a4b35: cmovl   ecx,r11d

0x000001d89e8a4b39: add     eax,ecx
0x000001d89e8a4b3b: inc     edi

0x000001d89e8a4b3d: cmp     edi,989680h
0x000001d89e8a4b43: jl      1d89e8a4b20h ; jump if `edi` was less than `10_000_000`

从上面可以看出,safeAbsSlowsafeAbsFast 有更多的条件跳转。
这是因为内联到 safeAbsFast 中的 Math.abs 实现没有条件跳转:
0x000001d89e8a4b2d: mov     r11d,ecx
0x000001d89e8a4b30: neg     r11d
0x000001d89e8a4b33: test    ecx,ecx
0x000001d89e8a4b35: cmovl   ecx,r11d

因此,当数据集中存在正数和负数并分散在一个数组中时,与“normal”版本相比,“slow”版本中的分支错误(branch-misses)会更多。以下是使用“perf” Linux profiler所收集到的相应统计数据:
Benchmark                          Mode  Cnt          Score         Error  Units
safeAbsFast                        avgt   10    9611659.726 ± 1429082.431  ns/op
safeAbsFast:branch-misses          avgt            2869.853                 #/op
safeAbsFast:branches               avgt        12492918.020                 #/op
safeAbsFast:cycles                 avgt        28212203.936                 #/op
safeAbsFast:instructions           avgt        92352048.153                 #/op
safeAbsSlow                        avgt   10   44524180.366 ± 6324887.086  ns/op
safeAbsSlow:branch-misses          avgt         5006493.144                 #/op
safeAbsSlow:branches               avgt        17496069.911                 #/op
safeAbsSlow:cycles                 avgt       126413171.674                 #/op
safeAbsSlow:instructions           avgt        67549877.558                 #/op

相比之下,这是已排序数据集的结果:
Benchmark                          Mode  Cnt         Score         Error  Units
safeAbsFast                        avgt   10   9026800.584 ±  528992.157  ns/op
safeAbsFast:branch-misses          avgt           2785.463                 #/op
safeAbsFast:branches               avgt       12474751.905                 #/op
safeAbsFast:cycles                 avgt       27379727.603                 #/op
safeAbsFast:instructions           avgt       92418075.715                 #/op
safeAbsSlow                        avgt   10   6981828.374 ± 2375480.834  ns/op
safeAbsSlow:branch-misses          avgt           2801.022                 #/op
safeAbsSlow:branches               avgt       17496585.992                 #/op
safeAbsSlow:cycles                 avgt       19478382.113                 #/op
safeAbsSlow:instructions           avgt       67589946.278                 #/op

之前的版本在数据集排序后变得更快(这种情况下,昂贵的分支错过被最小化)。


环境:

openjdk version "12-internal" 2019-03-19
OpenJDK Runtime Environment (slowdebug build 12-internal+0-adhoc.jdk12)
OpenJDK 64-Bit Server VM (slowdebug build 12-internal+0-adhoc.jdk12, mixed mode)

1
这基本上与我之前的评论猜测相符。一方面,我想知道如果测试数据包含“许多”(100万... 900万)MIN_VALUE条目,事情是否会发生变化。另一方面,这可能是相当学术性的问题,因为在现实中不太可能发生这种情况... - Marco13
1
cmp ebx,989680hsafeAbsSlowrepeat-loop的一部分。请注意它之前的inc ebx(因此EBX是一个循环计数器),并且分支目标不是你反汇编的一部分。实际上,它是对数组索引进行边界检查,但无法优化掉。我猜它没有证明数组大小>=循环界限。也许这只是第一次JIT,还没有完全优化?此外,“Fast”版本包括do{}while()asm循环结构底部的循环分支(cmp edl/jl)。那不是循环体的一部分。但它确实优化掉了数组边界检查。 - Peter Cordes
1
重点不仅在于条件跳转的数量,而在于它们是否基于不可预测的条件。关键是分支与无分支 Math.abs 的主要工作。一个永远不会被执行的 test/jnl 和快速版本中的 cmp ecx,80000000h/je 一样便宜。这两个都会在除了 INT_MIN 之外的所有输入上跳过。(在原始输入上进行检查可以更早地检测到错误预测,因此如果您从数组中加载 80000000h,则可能会减少一些丢失的工作。) 正如 @Marco13 所说,大量的 MIN_VALUE 也会使这个版本变慢。(而且慢版本会更慢) - Peter Cordes
1
包含测试排序输入情况是个好主意。是的,由于易于预测的分支,分支版本更快:即使cmov只有1个uop(Broadwell及更高版本或AMD),也会减少uops。在现代AMD和Intel CPU上,test/jcccmp/jcc可以解码为测试和分支uop。 - Peter Cordes

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接