gpt4 book ai didi

java - 在Java中,&可以比&&更快吗?

转载 作者:行者123 更新时间:2023-12-02 07:36:55 26 4
gpt4 key购买 nike

在这段代码中:

if (value >= x && value <= y) {

value >= xvalue <= y在没有特定模式的情况下,可能真假,将使用 &运算符比使用 && 更快?

具体来说,我在想如何 &&懒惰地计算右侧表达式(即仅当 LHS 为真时),这意味着一个条件,而在 Java 中 &在这种情况下,保证对两个( boolean )子表达式的严格评估。无论哪种方式,值结果都是相同的。

但同时一个 >=<=运算符将使用一个简单的比较指令, &&必须涉及一个分支,并且该分支容易受到分支预测失败的影响 - 根据这个非常著名的问题: Why is it faster to process a sorted array than an unsorted array?

因此,强制表达式没有惰性组件肯定会更具确定性,并且不容易受到预测失败的影响。对吗?

笔记:
  • 显然,如果代码如下所示,我的问题的答案是否定的:if(value >= x && verySlowFunction()) .我专注于“足够简单”的 RHS 表达式。
  • 无论如何,那里有一个条件分支(if 语句)。我无法向自己证明这是无关紧要的,替代公式可能是更好的例子,例如 boolean b = value >= x && value <= y;
  • 这一切都属于可怕的微观优化世界。是的,我知道 :-) ... 有趣吗?

  • 更新
    只是为了解释我为什么感兴趣:我一直在盯着 Martin Thompson 在他的 Mechanical Sympathy blog 上写的系统。 ,他来了之后 did a talk关于爱伦。关键信息之一是我们的硬件中包含所有这些神奇的东西,而我们软件开发人员却不幸地未能利用它。别担心,我不会在我所有的代码上使用 s/&&/\&/:-) ...但是这个站点上有很多关于通过删除分支来改进分支预测的问题,它发生了对我来说,条件 boolean 运算符是测试条件的核心。

    当然,@StephenC 提出了一个奇妙的观点,即将您的代码弯曲成奇怪的形状可以使 JIT 更不容易发现常见的优化——如果不是现在,那么在 future 。并且上面提到的非常著名的问题很特别,因为它使预测复杂性远远超出了实际优化。

    我非常清楚,在大多数(或几乎所有)情况下, &&是最清晰、最简单、最快、最好的方法——尽管我非常感谢发布答案的人来证明这一点!我真的很想知道在任何人的经验中是否真的有任何案例可以回答“ & 可以更快吗?”可能是...

    更新 2 :
    (提出问题过于宽泛的建议。我不想对这个问题进行重大更改,因为它可能会影响下面的一些答案,这些答案的质量非常好!)也许需要一个野外的例子;这是来自 Guava LongMath类(非常感谢@maaartinus 找到了这个):
    public static boolean isPowerOfTwo(long x) {
    return x > 0 & (x & (x - 1)) == 0;
    }

    先看 & ?如果你检查链接,下一个方法被称为 lessThanBranchFree(...) ,这暗示我们处于分支回避领域 - Guava 确实被广泛使用:保存的每个周期都会导致海平面明显下降。所以让我们这样提出问题:这是 & 的用法吗? (其中 && 会更正常)真正的优化?

    最佳答案

    好的,所以你想知道它在较低级别的行为......然后让我们看看字节码!
    编辑:最后为 AMD64 添加了生成的汇编代码。看看一些有趣的笔记。
    编辑 2(重新:OP 的“更新 2”):为 Guava's isPowerOfTwo method 添加了 asm 代码以及。
    Java源代码
    我写了这两个快速方法:

    public boolean AndSC(int x, int value, int y) {
    return value >= x && value <= y;
    }

    public boolean AndNonSC(int x, int value, int y) {
    return value >= x & value <= y;
    }
    如您所见,除了 AND 运算符的类型外,它们完全相同。
    Java字节码
    这是生成的字节码:
      public AndSC(III)Z
    L0
    LINENUMBER 8 L0
    ILOAD 2
    ILOAD 1
    IF_ICMPLT L1
    ILOAD 2
    ILOAD 3
    IF_ICMPGT L1
    L2
    LINENUMBER 9 L2
    ICONST_1
    IRETURN
    L1
    LINENUMBER 11 L1
    FRAME SAME
    ICONST_0
    IRETURN
    L3
    LOCALVARIABLE this Ltest/lsoto/AndTest; L0 L3 0
    LOCALVARIABLE x I L0 L3 1
    LOCALVARIABLE value I L0 L3 2
    LOCALVARIABLE y I L0 L3 3
    MAXSTACK = 2
    MAXLOCALS = 4

    // access flags 0x1
    public AndNonSC(III)Z
    L0
    LINENUMBER 15 L0
    ILOAD 2
    ILOAD 1
    IF_ICMPLT L1
    ICONST_1
    GOTO L2
    L1
    FRAME SAME
    ICONST_0
    L2
    FRAME SAME1 I
    ILOAD 2
    ILOAD 3
    IF_ICMPGT L3
    ICONST_1
    GOTO L4
    L3
    FRAME SAME1 I
    ICONST_0
    L4
    FRAME FULL [test/lsoto/AndTest I I I] [I I]
    IAND
    IFEQ L5
    L6
    LINENUMBER 16 L6
    ICONST_1
    IRETURN
    L5
    LINENUMBER 18 L5
    FRAME SAME
    ICONST_0
    IRETURN
    L7
    LOCALVARIABLE this Ltest/lsoto/AndTest; L0 L7 0
    LOCALVARIABLE x I L0 L7 1
    LOCALVARIABLE value I L0 L7 2
    LOCALVARIABLE y I L0 L7 3
    MAXSTACK = 3
    MAXLOCALS = 4
    AndSC ( && ) 方法生成 两个条件跳转,如预期:
  • 它加载 valuex如果value,则跳到L1较低。否则它会继续运行下一行。
  • 它加载 valuey如果value,也跳到L1更伟大。否则它会继续运行下一行。
  • 这恰好是一个 return true如果没有进行两次跳跃。
  • 然后我们将标记为 L1 的行是 return false .
  • AndNonSC ( & ) 方法,然而,生成 条件跳转!
  • 它加载 valuex如果 value 进入堆栈并跳转到 L1较低。因为现在它需要保存结果与AND的其他部分进行比较,所以它必须执行“save true”或“save false”,它不能用相同的指令同时执行。
  • 它加载 valuey如果 value 进入堆栈并跳转到 L1更伟大。再次需要保存truefalse这是两条不同的线,具体取决于比较结果。
  • 现在两个比较都完成了,代码实际上执行了 AND 操作——如果两者都为真,它会跳转(第三次)返回真;否则它会继续执行到下一行以返回 false。

  • (初步)结论
    虽然我对 Java 字节码的经验不是很丰富,而且我可能忽略了一些东西,但在我看来 &实际上会比 && 表现更差在每种情况下:它生成更多要执行的指令,包括更多条件跳转来预测和可能失败。
    正如其他人提出的那样,重写代码以用算术运算替换比较可能是一种方式 &一个更好的选择,但代价是让代码变得不那么清晰。
    恕我直言,对于 99% 的场景来说,麻烦是不值得的(不过,对于需要极度优化的 1% 循环来说,这可能是非常值得的)。
    编辑:AMD64 程序集
    正如评论中所指出的,相同的 Java 字节码可能会导致不同系统中的机器码不同,因此虽然 Java 字节码可能会提示我们哪个 AND 版本性能更好,但获取编译器生成的实际 ASM 是唯一的方法真正找出答案。
    我打印了两种方法的 AMD64 ASM 指令;下面是相关的行(剥离的入口点等)。
    注意:除非另有说明,否则所有方法都是用 java 1.8.0_91 编译的。
    方法AndSC使用默认选项
      # {method} {0x0000000016da0810} 'AndSC' '(III)Z' in 'AndTest'
    ...
    0x0000000002923e3e: cmp %r8d,%r9d
    0x0000000002923e41: movabs $0x16da0a08,%rax ; {metadata(method data for {method} {0x0000000016da0810} 'AndSC' '(III)Z' in 'AndTest')}
    0x0000000002923e4b: movabs $0x108,%rsi
    0x0000000002923e55: jl 0x0000000002923e65
    0x0000000002923e5b: movabs $0x118,%rsi
    0x0000000002923e65: mov (%rax,%rsi,1),%rbx
    0x0000000002923e69: lea 0x1(%rbx),%rbx
    0x0000000002923e6d: mov %rbx,(%rax,%rsi,1)
    0x0000000002923e71: jl 0x0000000002923eb0 ;*if_icmplt
    ; - AndTest::AndSC@2 (line 22)

    0x0000000002923e77: cmp %edi,%r9d
    0x0000000002923e7a: movabs $0x16da0a08,%rax ; {metadata(method data for {method} {0x0000000016da0810} 'AndSC' '(III)Z' in 'AndTest')}
    0x0000000002923e84: movabs $0x128,%rsi
    0x0000000002923e8e: jg 0x0000000002923e9e
    0x0000000002923e94: movabs $0x138,%rsi
    0x0000000002923e9e: mov (%rax,%rsi,1),%rdi
    0x0000000002923ea2: lea 0x1(%rdi),%rdi
    0x0000000002923ea6: mov %rdi,(%rax,%rsi,1)
    0x0000000002923eaa: jle 0x0000000002923ec1 ;*if_icmpgt
    ; - AndTest::AndSC@7 (line 22)

    0x0000000002923eb0: mov $0x0,%eax
    0x0000000002923eb5: add $0x30,%rsp
    0x0000000002923eb9: pop %rbp
    0x0000000002923eba: test %eax,-0x1c73dc0(%rip) # 0x0000000000cb0100
    ; {poll_return}
    0x0000000002923ec0: retq ;*ireturn
    ; - AndTest::AndSC@13 (line 25)

    0x0000000002923ec1: mov $0x1,%eax
    0x0000000002923ec6: add $0x30,%rsp
    0x0000000002923eca: pop %rbp
    0x0000000002923ecb: test %eax,-0x1c73dd1(%rip) # 0x0000000000cb0100
    ; {poll_return}
    0x0000000002923ed1: retq
    方法AndSC-XX:PrintAssemblyOptions=intel选项
      # {method} {0x00000000170a0810} 'AndSC' '(III)Z' in 'AndTest'
    ...
    0x0000000002c26e2c: cmp r9d,r8d
    0x0000000002c26e2f: jl 0x0000000002c26e36 ;*if_icmplt
    0x0000000002c26e31: cmp r9d,edi
    0x0000000002c26e34: jle 0x0000000002c26e44 ;*iconst_0
    0x0000000002c26e36: xor eax,eax ;*synchronization entry
    0x0000000002c26e38: add rsp,0x10
    0x0000000002c26e3c: pop rbp
    0x0000000002c26e3d: test DWORD PTR [rip+0xffffffffffce91bd],eax # 0x0000000002910000
    0x0000000002c26e43: ret
    0x0000000002c26e44: mov eax,0x1
    0x0000000002c26e49: jmp 0x0000000002c26e38

    方法AndNonSC使用默认选项
      # {method} {0x0000000016da0908} 'AndNonSC' '(III)Z' in 'AndTest'
    ...
    0x0000000002923a78: cmp %r8d,%r9d
    0x0000000002923a7b: mov $0x0,%eax
    0x0000000002923a80: jl 0x0000000002923a8b
    0x0000000002923a86: mov $0x1,%eax
    0x0000000002923a8b: cmp %edi,%r9d
    0x0000000002923a8e: mov $0x0,%esi
    0x0000000002923a93: jg 0x0000000002923a9e
    0x0000000002923a99: mov $0x1,%esi
    0x0000000002923a9e: and %rsi,%rax
    0x0000000002923aa1: cmp $0x0,%eax
    0x0000000002923aa4: je 0x0000000002923abb ;*ifeq
    ; - AndTest::AndNonSC@21 (line 29)

    0x0000000002923aaa: mov $0x1,%eax
    0x0000000002923aaf: add $0x30,%rsp
    0x0000000002923ab3: pop %rbp
    0x0000000002923ab4: test %eax,-0x1c739ba(%rip) # 0x0000000000cb0100
    ; {poll_return}
    0x0000000002923aba: retq ;*ireturn
    ; - AndTest::AndNonSC@25 (line 30)

    0x0000000002923abb: mov $0x0,%eax
    0x0000000002923ac0: add $0x30,%rsp
    0x0000000002923ac4: pop %rbp
    0x0000000002923ac5: test %eax,-0x1c739cb(%rip) # 0x0000000000cb0100
    ; {poll_return}
    0x0000000002923acb: retq
    方法AndNonSC-XX:PrintAssemblyOptions=intel选项
      # {method} {0x00000000170a0908} 'AndNonSC' '(III)Z' in 'AndTest'
    ...
    0x0000000002c270b5: cmp r9d,r8d
    0x0000000002c270b8: jl 0x0000000002c270df ;*if_icmplt
    0x0000000002c270ba: mov r8d,0x1 ;*iload_2
    0x0000000002c270c0: cmp r9d,edi
    0x0000000002c270c3: cmovg r11d,r10d
    0x0000000002c270c7: and r8d,r11d
    0x0000000002c270ca: test r8d,r8d
    0x0000000002c270cd: setne al
    0x0000000002c270d0: movzx eax,al
    0x0000000002c270d3: add rsp,0x10
    0x0000000002c270d7: pop rbp
    0x0000000002c270d8: test DWORD PTR [rip+0xffffffffffce8f22],eax # 0x0000000002910000
    0x0000000002c270de: ret
    0x0000000002c270df: xor r8d,r8d
    0x0000000002c270e2: jmp 0x0000000002c270c0
  • 首先,根据我们选择默认的 AT&T 语法还是 Intel 语法,生成的 ASM 代码会有所不同。
  • 使用 AT&T 语法:
  • AndSC的ASM代码实际上更长方法,每个字节码 IF_ICMP*转换为两条汇编跳转指令,总共有 4 条条件跳转。
  • 同时,对于AndNonSC方法编译器生成更直接的代码,其中每个字节码IF_ICMP*被转换为仅一条汇编跳转指令,保持 3 次条件跳转的原始计数。

  • 使用英特尔语法:
  • AndSC 的 ASM 代码更短,只有 2 个条件跳转(不包括最后的非条件 jmp)。实际上它只是两个 CMP、两个 JL/E 和一个 XOR/MOV,具体取决于结果。
  • AndNonSC 的 ASM 代码现在比 AndSC 更长一! 然而 ,它只有 1 次条件跳转(用于第一次比较),使用寄存器直接将第一个结果与第二个结果进行比较,无需更多跳转。


  • ASM 代码分析后的结论
  • 在 AMD64 机器语言级别,&运算符似乎生成具有较少条件跳转的 ASM 代码,这对于高预测失败率可能更好(例如随机 value s)。
  • 另一方面,&&运算符似乎生成具有较少指令的 ASM 代码(无论如何使用 -XX:PrintAssemblyOptions=intel 选项),这对于具有预测友好输入的真正长循环可能更好,其中每次比较的 CPU 周期数越少可以在长循环中产生差异跑。

  • 正如我在一些评论中所说的,这在系统之间会有很大差异,所以如果我们谈论分支预测优化,唯一真正的答案是: 这取决于您的 JVM 实现、您的编译器、您的 CPU 和您的输入数据 .

    附录: Guava 的 isPowerOfTwo方法
    在这里,Guava 的开发人员提出了一种计算给定数字是否为 2 的幂的巧妙方法:
    public static boolean isPowerOfTwo(long x) {
    return x > 0 & (x & (x - 1)) == 0;
    }
    引用 OP:

    is this use of & (where && would be more normal) a real optimization?


    为了确定它是否是,我在我的测试类中添加了两个类似的方法:
    public boolean isPowerOfTwoAND(long x) {
    return x > 0 & (x & (x - 1)) == 0;
    }

    public boolean isPowerOfTwoANDAND(long x) {
    return x > 0 && (x & (x - 1)) == 0;
    }
    Intel Guava 版本的 ASM 代码
      # {method} {0x0000000017580af0} 'isPowerOfTwoAND' '(J)Z' in 'AndTest'
    # this: rdx:rdx = 'AndTest'
    # parm0: r8:r8 = long
    ...
    0x0000000003103bbe: movabs rax,0x0
    0x0000000003103bc8: cmp rax,r8
    0x0000000003103bcb: movabs rax,0x175811f0 ; {metadata(method data for {method} {0x0000000017580af0} 'isPowerOfTwoAND' '(J)Z' in 'AndTest')}
    0x0000000003103bd5: movabs rsi,0x108
    0x0000000003103bdf: jge 0x0000000003103bef
    0x0000000003103be5: movabs rsi,0x118
    0x0000000003103bef: mov rdi,QWORD PTR [rax+rsi*1]
    0x0000000003103bf3: lea rdi,[rdi+0x1]
    0x0000000003103bf7: mov QWORD PTR [rax+rsi*1],rdi
    0x0000000003103bfb: jge 0x0000000003103c1b ;*lcmp
    0x0000000003103c01: movabs rax,0x175811f0 ; {metadata(method data for {method} {0x0000000017580af0} 'isPowerOfTwoAND' '(J)Z' in 'AndTest')}
    0x0000000003103c0b: inc DWORD PTR [rax+0x128]
    0x0000000003103c11: mov eax,0x1
    0x0000000003103c16: jmp 0x0000000003103c20 ;*goto
    0x0000000003103c1b: mov eax,0x0 ;*lload_1
    0x0000000003103c20: mov rsi,r8
    0x0000000003103c23: movabs r10,0x1
    0x0000000003103c2d: sub rsi,r10
    0x0000000003103c30: and rsi,r8
    0x0000000003103c33: movabs rdi,0x0
    0x0000000003103c3d: cmp rsi,rdi
    0x0000000003103c40: movabs rsi,0x175811f0 ; {metadata(method data for {method} {0x0000000017580af0} 'isPowerOfTwoAND' '(J)Z' in 'AndTest')}
    0x0000000003103c4a: movabs rdi,0x140
    0x0000000003103c54: jne 0x0000000003103c64
    0x0000000003103c5a: movabs rdi,0x150
    0x0000000003103c64: mov rbx,QWORD PTR [rsi+rdi*1]
    0x0000000003103c68: lea rbx,[rbx+0x1]
    0x0000000003103c6c: mov QWORD PTR [rsi+rdi*1],rbx
    0x0000000003103c70: jne 0x0000000003103c90 ;*lcmp
    0x0000000003103c76: movabs rsi,0x175811f0 ; {metadata(method data for {method} {0x0000000017580af0} 'isPowerOfTwoAND' '(J)Z' in 'AndTest')}
    0x0000000003103c80: inc DWORD PTR [rsi+0x160]
    0x0000000003103c86: mov esi,0x1
    0x0000000003103c8b: jmp 0x0000000003103c95 ;*goto
    0x0000000003103c90: mov esi,0x0 ;*iand
    0x0000000003103c95: and rsi,rax
    0x0000000003103c98: and esi,0x1
    0x0000000003103c9b: mov rax,rsi
    0x0000000003103c9e: add rsp,0x50
    0x0000000003103ca2: pop rbp
    0x0000000003103ca3: test DWORD PTR [rip+0xfffffffffe44c457],eax # 0x0000000001550100
    0x0000000003103ca9: ret
    英特尔的汇编代码 &&版本
      # {method} {0x0000000017580bd0} 'isPowerOfTwoANDAND' '(J)Z' in 'AndTest'
    # this: rdx:rdx = 'AndTest'
    # parm0: r8:r8 = long
    ...
    0x0000000003103438: movabs rax,0x0
    0x0000000003103442: cmp rax,r8
    0x0000000003103445: jge 0x0000000003103471 ;*lcmp
    0x000000000310344b: mov rax,r8
    0x000000000310344e: movabs r10,0x1
    0x0000000003103458: sub rax,r10
    0x000000000310345b: and rax,r8
    0x000000000310345e: movabs rsi,0x0
    0x0000000003103468: cmp rax,rsi
    0x000000000310346b: je 0x000000000310347b ;*lcmp
    0x0000000003103471: mov eax,0x0
    0x0000000003103476: jmp 0x0000000003103480 ;*ireturn
    0x000000000310347b: mov eax,0x1 ;*goto
    0x0000000003103480: and eax,0x1
    0x0000000003103483: add rsp,0x40
    0x0000000003103487: pop rbp
    0x0000000003103488: test DWORD PTR [rip+0xfffffffffe44cc72],eax # 0x0000000001550100
    0x000000000310348e: ret
    在此特定示例中,JIT 编译器为 && 生成的汇编代码要少得多。版本比 Guava 的 &版本(而且,在昨天的结果之后,老实说,我对此感到惊讶)。
    与 Guava 相比, &&版本转换为 JIT 编译的字节码减少了 25%,汇编指令减少了 50%,并且只有两个条件跳转( & 版本有四个)。
    所以一切都指向 Guava 的 &方法比更“自然”的方法效率低 &&版本。
    ……或者是吗?
    如前所述,我正在使用 Java 8 运行上述示例:
    C:\....>java -version
    java version "1.8.0_91"
    Java(TM) SE Runtime Environment (build 1.8.0_91-b14)
    Java HotSpot(TM) 64-Bit Server VM (build 25.91-b14, mixed mode)
    但是 如果我切换到 Java 7 会怎样 ?
    C:\....>c:\jdk1.7.0_79\bin\java -version
    java version "1.7.0_79"
    Java(TM) SE Runtime Environment (build 1.7.0_79-b15)
    Java HotSpot(TM) 64-Bit Server VM (build 24.79-b02, mixed mode)
    C:\....>c:\jdk1.7.0_79\bin\java -XX:+UnlockDiagnosticVMOptions -XX:CompileCommand=print,*AndTest.isPowerOfTwoAND -XX:PrintAssemblyOptions=intel AndTestMain
    .....
    0x0000000002512bac: xor r10d,r10d
    0x0000000002512baf: mov r11d,0x1
    0x0000000002512bb5: test r8,r8
    0x0000000002512bb8: jle 0x0000000002512bde ;*ifle
    0x0000000002512bba: mov eax,0x1 ;*lload_1
    0x0000000002512bbf: mov r9,r8
    0x0000000002512bc2: dec r9
    0x0000000002512bc5: and r9,r8
    0x0000000002512bc8: test r9,r9
    0x0000000002512bcb: cmovne r11d,r10d
    0x0000000002512bcf: and eax,r11d ;*iand
    0x0000000002512bd2: add rsp,0x10
    0x0000000002512bd6: pop rbp
    0x0000000002512bd7: test DWORD PTR [rip+0xffffffffffc0d423],eax # 0x0000000002120000
    0x0000000002512bdd: ret
    0x0000000002512bde: xor eax,eax
    0x0000000002512be0: jmp 0x0000000002512bbf
    .....
    惊喜!为 & 生成的汇编代码Java 7 中 JIT 编译器的方法,现在只有一个条件跳转,而且更短!而 &&方法(你必须相信我,我不想弄乱结局!)保持大致相同,有两个条件跳转和少几个指令,顶部。
    看起来 Guava 的工程师毕竟知道他们在做什么! (如果他们试图优化 Java 7 的执行时间,那就是 ;-)
    所以回到OP的最新问题:

    is this use of & (where && would be more normal) a real optimization?


    恕我直言 答案是一样的 ,即使对于这个(非常!)特定场景: 这取决于您的 JVM 实现、您的编译器、您的 CPU 和您的输入数据 .

    关于java - 在Java中,&可以比&&更快吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39588251/

    26 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com