В Java может ли & быть быстрее, чем &&?

исходный код 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 (&&) создает два условных перехода:

1. Он загружает value и x в стек и переходит к L1, если value меньше. В противном случае он продолжает работать на следующих строках.
2. Он загружает в стек value и y и также переходит к L1, если value больше. В противном случае он продолжает работать на следующих строках.
3. Который оказывается return true на случай, если ни один из двух прыжков не был сделан.
4. И затем у нас есть строки, отмеченные как L1, которые являются return false.

Однако метод AndNonSC (&) создает три условных перехода!

1. Он загружает value и x в стек и переходит к L1, если value меньше. Поскольку теперь ему нужно сохранить результат, чтобы сравнить его с другой частью И, поэтому он должен выполнить либо сохранение true, либо сохранение false, он не может выполнить оба действия с одной и той же инструкцией.
2. Он загружает value и y в стек и переходит к L1, если value больше. Еще раз нужно сохранить true или false, а это две разные строки в зависимости от результата сравнения.
3. Теперь, когда оба сравнения выполнены, код фактически выполняет операцию И, и если оба они верны, он переходит (в третий раз) и возвращает значение true; или же он продолжает выполнение на следующей строке, чтобы вернуть 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

• Прежде всего, сгенерированный код ASM различается в зависимости от того, выбираем ли мы синтаксис AT&T по умолчанию или синтаксис Intel.
• With AT&T syntax:
  • The ASM code is actually longer for the AndSC method, with every bytecode IF_ICMP* translated to two assembly jump instructions, for a total of 4 conditional jumps.
  • Между тем, для метода AndNonSC компилятор генерирует более простой код, в котором каждый байт-код IF_ICMP* транслируется только в одну инструкцию перехода сборки, сохраняя исходное количество 3 условных переходов.
• With Intel syntax:
  • The ASM code for AndSC is shorter, with just 2 conditional jumps (not counting the non-conditional jmp at the end). Actually it's just two CMP, two JL/E and a XOR/MOV depending on the result.
  • Код ASM для AndNonSC теперь длиннее, чем AndSC! Однако он имеет только 1 условный переход (для первого сравнения), используя регистры для прямого сравнения первого результата со вторым, без дополнительных переходов.

Заключение после анализа кода ASM

• На уровне машинного языка AMD64 оператор &, по-видимому, генерирует код ASM с меньшим количеством условных переходов, что может быть лучше для высоких показателей ошибок прогнозирования (например, случайные values).
• С другой стороны, оператор &&, кажется, генерирует код ASM с меньшим количеством инструкций (во всяком случае, с опцией -XX:PrintAssemblyOptions=intel), что может быть лучше для очень длинных циклов с удобными для прогнозирования входными данными, где меньшее количество Циклы ЦП для каждого сравнения могут иметь значение в долгосрочной перспективе.

Как я уже говорил в некоторых комментариях, это будет сильно различаться между системами, поэтому, если мы говорим об оптимизации прогнозирования ветвлений, единственным реальным ответом будет: это зависит от вашей реализации JVM, вашего компилятора, ваш процессор и ваши входные данные.

Приложение: метод Гуавы isPowerOfTwo

Здесь разработчики Guava придумали изящный способ вычисления, является ли данное число степенью двойки:

public static boolean isPowerOfTwo(long x) {
    return x > 0 & (x & (x - 1)) == 0;
}

Цитирую ОП:

является ли использование & (где && более уместным) настоящей оптимизацией?

Чтобы узнать, так ли это, я добавил в свой тестовый класс два похожих метода:

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 ASM для версии Guava

  # {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    

Asm-код Intel для версии &&

  # {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, версия && переводит на 25% меньше байт-кода для JIT-компиляции, на 50% меньше ассемблерных инструкций и только два условных перехода (версия & имеет четыре из них).

Таким образом, все указывает на то, что метод & Гуавы менее эффективен, чем более естественная версия &&.

... Or is it?

Как отмечалось ранее, я запускаю приведенные выше примеры с 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
  .....

Сюрприз! Ассемблерный код, сгенерированный для метода & JIT-компилятором в Java 7, теперь имеет только один условный переход и стал намного короче! В то время как метод && (поверьте мне в этом, я не хочу загромождать концовку!) остается примерно таким же, с его двумя условными переходами и парой меньше инструкций, топ.
Выглядит как будто инженеры Гуавы знали, что они делали, в конце концов! (если они пытались оптимизировать время выполнения Java 7, то есть ;-)

Итак, вернемся к последнему вопросу OP:

Является ли использование & (где && более уместным) настоящей оптимизацией?

И ИМХО ответ тот же, даже для этого (очень!) конкретного сценария: это зависит от вашей реализации JVM, вашего компилятора, вашего процессора и ваших входных данных.