¿Por qué es mucho más lento que int en Java x64?

90

Estoy ejecutando Windows 8.1 x64 con la actualización de Java 7 45 x64 (sin Java de 32 bits instalado) en una tableta Surface Pro 2.

El siguiente código toma 1688ms cuando el tipo de i es largo y 109ms cuando i es un int. ¿Por qué long (un tipo de 64 bits) es un orden de magnitud más lento que int en una plataforma de 64 bits con una JVM de 64 bits?

Mi única especulación es que la CPU tarda más en agregar un entero de 64 bits que uno de 32 bits, pero eso parece poco probable. Sospecho que Haswell no usa sumadores de transporte de ondas.

Estoy ejecutando esto en Eclipse Kepler SR1, por cierto.

public class Main {

    private static long i = Integer.MAX_VALUE;

    public static void main(String[] args) {    
        System.out.println("Starting the loop");
        long startTime = System.currentTimeMillis();
        while(!decrementAndCheck()){
        }
        long endTime = System.currentTimeMillis();
        System.out.println("Finished the loop in " + (endTime - startTime) + "ms");
    }

    private static boolean decrementAndCheck() {
        return --i < 0;
    }

}

Editar: Aquí están los resultados del código C ++ equivalente compilado por VS 2013 (abajo), mismo sistema. largo: 72265ms int: 74656ms Esos resultados se obtuvieron en el modo de depuración de 32 bits.

En modo de liberación de 64 bits: largo: 875ms largo largo: 906ms int: 1047ms

Esto sugiere que el resultado que observé es una rareza de optimización de JVM en lugar de limitaciones de CPU.

#include "stdafx.h"
#include "iostream"
#include "windows.h"
#include "limits.h"

long long i = INT_MAX;

using namespace std;


boolean decrementAndCheck() {
return --i < 0;
}


int _tmain(int argc, _TCHAR* argv[])
{


cout << "Starting the loop" << endl;

unsigned long startTime = GetTickCount64();
while (!decrementAndCheck()){
}
unsigned long endTime = GetTickCount64();

cout << "Finished the loop in " << (endTime - startTime) << "ms" << endl;



}

Editar: Intenté esto nuevamente en Java 8 RTM, sin cambios significativos.

Techrocket9
fuente
8
El sospechoso más probable es su configuración, no la CPU o las distintas partes de la JVM. ¿Puede reproducir de forma fiable esta medida? No repetir el ciclo, no calentar el JIT, usar currentTimeMillis(), ejecutar código que trivialmente se puede optimizar completamente, etc. huele a resultados poco confiables.
1
Hace un tiempo estaba haciendo una evaluación comparativa, tuve que usar a longcomo contador de bucle, porque el compilador JIT optimizó el bucle, cuando usé un int. Habría que mirar el desmontaje del código de máquina generado.
Sam
7
Este no es un microbenchmark correcto y no esperaría que sus resultados reflejen la realidad de ninguna manera.
Louis Wasserman
7
Todos los comentarios que critican al OP por no escribir un microbenchmark Java adecuado son indeciblemente perezosos. Este es el tipo de cosas que son muy fáciles de entender si solo miras y ves lo que la JVM hace con el código.
tmyklebu
2
@maaartinus: La práctica aceptada es una práctica aceptada porque trabaja en torno a una lista de escollos conocidos. En el caso de Proper Java Benchmarks, desea asegurarse de que está midiendo el código optimizado correctamente, no un reemplazo en la pila, y desea asegurarse de que sus medidas estén limpias al final. OP encontró un problema completamente diferente y el punto de referencia que proporcionó lo demostró adecuadamente. Y, como se señaló, convertir este código en un punto de referencia de Java adecuado no hace que desaparezca la rareza. Y leer el código ensamblador no es difícil.
tmyklebu

Respuestas:

80

Mi JVM hace esto bastante sencillo en el bucle interno cuando usa longs:

0x00007fdd859dbb80: test   %eax,0x5f7847a(%rip)  /* fun JVM hack */
0x00007fdd859dbb86: dec    %r11                  /* i-- */
0x00007fdd859dbb89: mov    %r11,0x258(%r10)      /* store i to memory */
0x00007fdd859dbb90: test   %r11,%r11             /* unnecessary test */
0x00007fdd859dbb93: jge    0x00007fdd859dbb80    /* go back to the loop top */

Hace trampa, duro, cuando usas ints; primero hay algo de locura que no pretendo entender, pero parece una configuración para un bucle desenrollado:

0x00007f3dc290b5a1: mov    %r11d,%r9d
0x00007f3dc290b5a4: dec    %r9d
0x00007f3dc290b5a7: mov    %r9d,0x258(%r10)
0x00007f3dc290b5ae: test   %r9d,%r9d
0x00007f3dc290b5b1: jl     0x00007f3dc290b662
0x00007f3dc290b5b7: add    $0xfffffffffffffffe,%r11d
0x00007f3dc290b5bb: mov    %r9d,%ecx
0x00007f3dc290b5be: dec    %ecx              
0x00007f3dc290b5c0: mov    %ecx,0x258(%r10)   
0x00007f3dc290b5c7: cmp    %r11d,%ecx
0x00007f3dc290b5ca: jle    0x00007f3dc290b5d1
0x00007f3dc290b5cc: mov    %ecx,%r9d
0x00007f3dc290b5cf: jmp    0x00007f3dc290b5bb
0x00007f3dc290b5d1: and    $0xfffffffffffffffe,%r9d
0x00007f3dc290b5d5: mov    %r9d,%r8d
0x00007f3dc290b5d8: neg    %r8d
0x00007f3dc290b5db: sar    $0x1f,%r8d
0x00007f3dc290b5df: shr    $0x1f,%r8d
0x00007f3dc290b5e3: sub    %r9d,%r8d
0x00007f3dc290b5e6: sar    %r8d
0x00007f3dc290b5e9: neg    %r8d
0x00007f3dc290b5ec: and    $0xfffffffffffffffe,%r8d
0x00007f3dc290b5f0: shl    %r8d
0x00007f3dc290b5f3: mov    %r8d,%r11d
0x00007f3dc290b5f6: neg    %r11d
0x00007f3dc290b5f9: sar    $0x1f,%r11d
0x00007f3dc290b5fd: shr    $0x1e,%r11d
0x00007f3dc290b601: sub    %r8d,%r11d
0x00007f3dc290b604: sar    $0x2,%r11d
0x00007f3dc290b608: neg    %r11d
0x00007f3dc290b60b: and    $0xfffffffffffffffe,%r11d
0x00007f3dc290b60f: shl    $0x2,%r11d
0x00007f3dc290b613: mov    %r11d,%r9d
0x00007f3dc290b616: neg    %r9d
0x00007f3dc290b619: sar    $0x1f,%r9d
0x00007f3dc290b61d: shr    $0x1d,%r9d
0x00007f3dc290b621: sub    %r11d,%r9d
0x00007f3dc290b624: sar    $0x3,%r9d
0x00007f3dc290b628: neg    %r9d
0x00007f3dc290b62b: and    $0xfffffffffffffffe,%r9d
0x00007f3dc290b62f: shl    $0x3,%r9d
0x00007f3dc290b633: mov    %ecx,%r11d
0x00007f3dc290b636: sub    %r9d,%r11d
0x00007f3dc290b639: cmp    %r11d,%ecx
0x00007f3dc290b63c: jle    0x00007f3dc290b64f
0x00007f3dc290b63e: xchg   %ax,%ax /* OK, fine; I know what a nop looks like */

luego el bucle desenrollado en sí:

0x00007f3dc290b640: add    $0xfffffffffffffff0,%ecx
0x00007f3dc290b643: mov    %ecx,0x258(%r10)
0x00007f3dc290b64a: cmp    %r11d,%ecx
0x00007f3dc290b64d: jg     0x00007f3dc290b640

luego, el código de desmontaje para el bucle desenrollado, en sí mismo una prueba y un bucle directo:

0x00007f3dc290b64f: cmp    $0xffffffffffffffff,%ecx
0x00007f3dc290b652: jle    0x00007f3dc290b662
0x00007f3dc290b654: dec    %ecx
0x00007f3dc290b656: mov    %ecx,0x258(%r10)
0x00007f3dc290b65d: cmp    $0xffffffffffffffff,%ecx
0x00007f3dc290b660: jg     0x00007f3dc290b654

Así que va 16 veces más rápido para los ints porque el JIT desenrolló el intbucle 16 veces, pero no desenrolló el longbucle en absoluto.

Para completar, aquí está el código que realmente probé:

public class foo136 {
  private static int i = Integer.MAX_VALUE;
  public static void main(String[] args) {
    System.out.println("Starting the loop");
    for (int foo = 0; foo < 100; foo++)
      doit();
  }

  static void doit() {
    i = Integer.MAX_VALUE;
    long startTime = System.currentTimeMillis();
    while(!decrementAndCheck()){
    }
    long endTime = System.currentTimeMillis();
    System.out.println("Finished the loop in " + (endTime - startTime) + "ms");
  }

  private static boolean decrementAndCheck() {
    return --i < 0;
  }
}

Los volcados de ensamblaje se generaron utilizando las opciones -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly. Tenga en cuenta que necesita perder el tiempo con la instalación de su JVM para que esto funcione también para usted; necesita poner alguna biblioteca compartida aleatoria en el lugar correcto o fallará.

tmyklebu
fuente
8
Bien, entonces la net-net no es que la longversión sea más lenta, sino que la intversión sea más rápida. Eso tiene sentido. Probablemente no se invirtió tanto esfuerzo en hacer que el JIT optimizara las longexpresiones.
Hot Licks
1
... perdona mi ignorancia, pero ¿qué es "funrolled"? Ni siquiera puedo buscar en Google el término correctamente, y eso hace que sea la primera vez que tengo que preguntarle a alguien qué significa una palabra en Internet.
BrianH
1
@BrianDHall gccusa -fcomo el interruptor de línea de comando para "bandera", y la unroll-loopsoptimización se activa diciendo -funroll-loops. Solo uso "desenrollar" para describir la optimización.
chrylis -cautelyoptimistic-
4
@BRPocock: El compilador de Java no puede, pero el JIT seguro que sí.
tmyklebu
1
Para ser claros, no lo "funcionó". Lo desenrolló Y convirtió el bucle desenrollado en i-=16, que por supuesto es 16 veces más rápido.
Aleksandr Dubinsky
22

La pila de JVM se define en términos de palabras , cuyo tamaño es un detalle de implementación pero debe tener al menos 32 bits de ancho. El implementador de JVM puede usar palabras de 64 bits, pero el código de bytes no puede depender de esto, por lo que las operaciones con valores longo doubledeben manejarse con especial cuidado. En particular, las instrucciones de bifurcación de enteros de JVM se definen exactamente en el tipo int.

En el caso de su código, el desmontaje es instructivo. Aquí está el código de bytes para la intversión compilada por Oracle JDK 7:

private static boolean decrementAndCheck();
  Code:
     0: getstatic     #14  // Field i:I
     3: iconst_1      
     4: isub          
     5: dup           
     6: putstatic     #14  // Field i:I
     9: ifge          16
    12: iconst_1      
    13: goto          17
    16: iconst_0      
    17: ireturn       

Tenga en cuenta que la JVM cargará el valor de su estática i(0), restará uno (3-4), duplicará el valor en la pila (5) y lo devolverá a la variable (6). Luego hace una bifurcación de comparación con cero y regresa.

La versión con el longes un poco más complicada:

private static boolean decrementAndCheck();
  Code:
     0: getstatic     #14  // Field i:J
     3: lconst_1      
     4: lsub          
     5: dup2          
     6: putstatic     #14  // Field i:J
     9: lconst_0      
    10: lcmp          
    11: ifge          18
    14: iconst_1      
    15: goto          19
    18: iconst_0      
    19: ireturn       

Primero, cuando la JVM duplica el nuevo valor en la pila (5), tiene que duplicar dos palabras de pila. En su caso, es muy posible que esto no sea más caro que duplicar uno, ya que la JVM es libre de usar una palabra de 64 bits si es conveniente. Sin embargo, notará que la lógica de la rama es más larga aquí. La JVM no tiene una instrucción para comparar a longcon cero, por lo que tiene que insertar una constante 0Len la pila (9), hacer una longcomparación general (10) y luego bifurcar en el valor de ese cálculo.

Aquí hay dos escenarios plausibles:

  • La JVM sigue exactamente la ruta del código de bytes. En este caso, está haciendo más trabajo en la longversión, presionando y haciendo estallar varios valores adicionales, y estos están en la pila administrada virtual , no en la pila de CPU asistida por hardware real. Si este es el caso, aún verá una diferencia de rendimiento significativa después del calentamiento.
  • La JVM se da cuenta de que puede optimizar este código. En este caso, se necesita más tiempo para optimizar parte de la lógica de empujar / comparar prácticamente innecesaria. Si este es el caso, verá muy poca diferencia de rendimiento después del calentamiento.

Le recomiendo que escriba un microbenchmark correcto para eliminar el efecto de activar el JIT, y también intentar esto con una condición final que no sea cero, para obligar a la JVM a hacer la misma comparación intque hace con el long.

chrylis -cautelosamente optimista-
fuente
1
@Katona No necesariamente. Muy especialmente, las JVM de HotSpot de Cliente y Servidor son implementaciones completamente diferentes, e Ilya no indicó seleccionar Servidor (el Cliente suele ser el predeterminado de 32 bits).
chrylis -cautntlyoptimistic-
1
@tmyklebu El problema es que el punto de referencia mide varias cosas diferentes a la vez. El uso de una condición terminal distinta de cero reduce el número de variables.
chrylis -cautelyoptimistic-
1
@tmyklebu El punto es que el OP tenía la intención de comparar la velocidad de los incrementos, disminuciones y comparaciones en ints vs longs. En cambio (asumiendo que esta respuesta es correcta) estaban midiendo solo comparaciones, y solo contra 0, que es un caso especial. Por lo menos, hace que el índice de referencia original sea engañoso: parece que mide tres casos generales, cuando en realidad mide un caso específico.
yshavit
1
@tmyklebu No me malinterpretes, voté a favor de la pregunta, esta respuesta y tu respuesta. Pero no estoy de acuerdo con su afirmación de que @chrylis está ajustando el punto de referencia para dejar de medir la diferencia que está tratando de medir. OP puede corregirme si me equivoco, pero no parece que estén tratando de medir solo / principalmente == 0, lo que parece ser una parte desproporcionadamente grande de los resultados de referencia. Me parece más probable que OP esté tratando de medir un rango más general de operaciones, y esta respuesta señala que el punto de referencia está muy sesgado hacia solo una de esas operaciones.
yshavit
2
@tmyklebu Para nada. Estoy totalmente a favor de comprender las causas fundamentales. Pero, habiendo identificado que una de las principales causas es que el punto de referencia estaba sesgado, no es inválido cambiar el punto de referencia para eliminar el sesgo, así como profundizar y comprender más sobre ese sesgo (por ejemplo, que puede permitir una bytecode, que puede facilitar el desenrollado de bucles, etc.). Es por eso que voté a favor de esta respuesta (que identificó el sesgo) y la suya (que profundiza en el sesgo con más detalle).
yshavit
8

La unidad básica de datos en una máquina virtual Java es la palabra. La elección del tamaño de palabra correcto se deja en la implementación de la JVM. Una implementación de JVM debe elegir un tamaño de palabra mínimo de 32 bits. Puede elegir un tamaño de palabra más alto para ganar eficiencia. Tampoco existe ninguna restricción de que una JVM de 64 bits deba elegir solo palabras de 64 bits.

La arquitectura subyacente no establece que el tamaño de la palabra también deba ser el mismo. JVM lee / escribe datos palabra por palabra. Esta es la razón por la que podría estar tomando más tiempo para una larga que un int .

Aquí puede encontrar más sobre el mismo tema.

Vaibhav Raj
fuente
4

Acabo de escribir un punto de referencia usando caliper .

Los resultados son bastante consistentes con el código original: una aceleración de ~ 12x para usar intover long. Ciertamente parece que está ocurriendo el desenrollamiento del bucle informado por tmyklebu o algo muy similar.

timeIntDecrements         195,266,845.000
timeLongDecrements      2,321,447,978.000

Este es mi código; tenga en cuenta que utiliza una instantánea recién construida de caliper, ya que no pude averiguar cómo codificar contra su versión beta existente.

package test;

import com.google.caliper.Benchmark;
import com.google.caliper.Param;

public final class App {

    @Param({""+1}) int number;

    private static class IntTest {
        public static int v;
        public static void reset() {
            v = Integer.MAX_VALUE;
        }
        public static boolean decrementAndCheck() {
            return --v < 0;
        }
    }

    private static class LongTest {
        public static long v;
        public static void reset() {
            v = Integer.MAX_VALUE;
        }
        public static boolean decrementAndCheck() {
            return --v < 0;
        }
    }

    @Benchmark
    int timeLongDecrements(int reps) {
        int k=0;
        for (int i=0; i<reps; i++) {
            LongTest.reset();
            while (!LongTest.decrementAndCheck()) { k++; }
        }
        return (int)LongTest.v | k;
    }    

    @Benchmark
    int timeIntDecrements(int reps) {
        int k=0;
        for (int i=0; i<reps; i++) {
            IntTest.reset();
            while (!IntTest.decrementAndCheck()) { k++; }
        }
        return IntTest.v | k;
    }
}
tucuxi
fuente
1

Para el registro, esta versión hace un crudo "calentamiento":

public class LongSpeed {

    private static long i = Integer.MAX_VALUE;
    private static int j = Integer.MAX_VALUE;

    public static void main(String[] args) {

        for (int x = 0; x < 10; x++) {
            runLong();
            runWord();
        }
    }

    private static void runLong() {
        System.out.println("Starting the long loop");
        i = Integer.MAX_VALUE;
        long startTime = System.currentTimeMillis();
        while(!decrementAndCheckI()){

        }
        long endTime = System.currentTimeMillis();

        System.out.println("Finished the long loop in " + (endTime - startTime) + "ms");
    }

    private static void runWord() {
        System.out.println("Starting the word loop");
        j = Integer.MAX_VALUE;
        long startTime = System.currentTimeMillis();
        while(!decrementAndCheckJ()){

        }
        long endTime = System.currentTimeMillis();

        System.out.println("Finished the word loop in " + (endTime - startTime) + "ms");
    }

    private static boolean decrementAndCheckI() {
        return --i < 0;
    }

    private static boolean decrementAndCheckJ() {
        return --j < 0;
    }

}

Los tiempos generales mejoran alrededor del 30%, pero la relación entre los dos sigue siendo aproximadamente la misma.

Lamidas calientes
fuente
@TedHopp - Intenté cambiar los límites de bucle en el mío y permaneció esencialmente sin cambios.
Hot Licks
@ Techrocket9: obtengo números similares ( intes 20 veces más rápido) con este código.
tmyklebu
1

Por los récords:

si uso

boolean decrementAndCheckLong() {
    lo = lo - 1l;
    return lo < -1l;
}

(cambiado "l--" a "l = l - 1l") el rendimiento prolongado mejora en ~ 50%

R.Moeller
fuente
0

No tengo una máquina de 64 bits para probar, pero la diferencia bastante grande sugiere que hay más que el código de bytes un poco más largo en el trabajo.

Veo tiempos muy cercanos para long / int (4400 vs 4800ms) en mi 1.7.0_45 de 32 bits.

Esto es solo una suposición , pero sospecho firmemente que es el efecto de una penalización por desalineación de la memoria. Para confirmar / negar la sospecha, intente agregar un public static int dummy = 0; antes de la declaración de i. Eso reducirá 4 bytes en el diseño de la memoria y puede alinearlo correctamente para un mejor rendimiento. Confirmado que no está causando el problema.

EDITAR: El razonamiento detrás de esto es que la VM no puede reordenar los campos en su tiempo libre agregando relleno para una alineación óptima, ya que eso puede interferir con JNI (No es el caso).

Durandal
fuente
El VM sin duda se permitió a los campos de reabastecimiento y el relleno complemento.
Hot Licks
JNI tiene que acceder a los objetos a través de estos molestos y lentos métodos de acceso que requieren algunos identificadores opacos de todos modos, ya que GC puede ocurrir mientras se ejecuta el código nativo. Es bastante gratuito reordenar campos y agregar relleno.
tmyklebu