java - sirve - ¿Por qué hashCode es más lento que un método similar?

metodo hash java

Question

Normalmente, Java optimiza las llamadas virtuales en función del número de implementaciones encontradas en un lado de la llamada. Esto se puede ver fácilmente en los results de mi benchmark de benchmark , cuando miras myCode , que es un método trivial que devuelve una int almacenada. Hay un trivial

static abstract class Base {
    abstract int myCode();
}

con un par de implementación idéntica como

static class A extends Base {
    @Override int myCode() {
        return n;
    }
    @Override public int hashCode() {
        return n;
    }
    private final int n = nextInt();
}

Con un número creciente de implementaciones, el tiempo de la llamada al método crece de 0.4 ns a 1.2 ns para dos implementaciones a 11.6 ns y luego crece lentamente. Cuando la JVM ha visto una implementación múltiple, es decir, con preload=true los tiempos difieren ligeramente (debido a una instanceof prueba necesaria).

Hasta ahora todo está claro, sin embargo, el hashCode comporta de manera bastante diferente. Especialmente, es 8-10 veces más lento en tres casos. ¿Alguna idea de por qué?

ACTUALIZAR

Tenía curiosidad si el pobre hashCode podría ser ayudado por el envío manual, y podría ser mucho.

Un par de ramas hicieron el trabajo a la perfección:

if (o instanceof A) {
    result += ((A) o).hashCode();
} else if (o instanceof B) {
    result += ((B) o).hashCode();
} else if (o instanceof C) {
    result += ((C) o).hashCode();
} else if (o instanceof D) {
    result += ((D) o).hashCode();
} else { // Actually impossible, but let''s play it safe.
    result += o.hashCode();
}

Tenga en cuenta que el compilador evita tales optimizaciones para más de dos implementaciones, ya que la mayoría de las llamadas a métodos son mucho más costosas que una simple carga de campo y la ganancia sería pequeña en comparación con el código inflado.

La pregunta original " ¿Por qué JIT no optimiza el hashCode como otros métodos? " Permanece y hashCode2 prueba que de hecho podría hacerlo.

ACTUALIZACIÓN 2

Parece que bestsss tiene razón, al menos con esta nota

Llamar a hashCode () de cualquier clase que se extienda Base es lo mismo que llamar a Object.hashCode () y así es como se compila en bytecode, si agrega un hashCode explícito en Base que limitaría los posibles destinos de invocación de Base.hashCode () .

No estoy completamente seguro de lo que está sucediendo, pero al declarar Base.hashCode() vuelve a hashCode un hashCode .

ACTUALIZACIÓN 3

OK, proporcionar una implementación concreta de Base#hashCode ayuda, sin embargo, el JIT debe saber que nunca se llama, ya que todas las subclases definen las suyas (a menos que se cargue otra subclase, lo que puede llevar a una desoptimización, pero esto no es nada nuevo para el JIT).

Por lo tanto, parece una oportunidad de optimización perdida n. ° 1.

Proporcionar una implementación abstracta de Base#hashCode funciona de la misma manera. Esto tiene sentido, ya que proporciona asegura que no se necesita más búsqueda ya que cada subclase debe proporcionar la suya (no pueden simplemente heredar de sus abuelos).

Aún para más de dos implementaciones, myCode es mucho más rápido, el compilador debe hacer algo subobimal. Tal vez una oportunidad de optimización perdida # 2?

Answer 1

Estaba viendo tus invariantes para tu prueba. Tiene scenario.vmSpec.options.hashCode puesto a 0. De acuerdo con this presentación de diapositivas (diapositiva 37) eso significa que Object.hashCode usará un generador de números aleatorios. Esa podría ser la razón por la cual el compilador JIT está menos interesado en optimizar las llamadas a hashCode ya que considera que es probable que tenga que recurrir a una llamada a un método costoso, que compensaría cualquier ganancia de rendimiento al evitar una búsqueda vtable.

Esto también puede ser el motivo por el que configurar Base para tener su propio método de código hash mejora el rendimiento, ya que evita la posibilidad de caer en Object.hashCode .

this

Answer 2

Este es un problema de rendimiento conocido: https://bugs.openjdk.java.net/browse/JDK-8014447
Se ha corregido en JDK 8.

Answer 3

La semántica de hashCode () es más compleja que los métodos regulares, por lo que la JVM y el compilador JIT deben trabajar más cuando se llama a hashCode () que cuando se llama a un método virtual normal.

Una especificidad tiene un impacto negativo en el rendimiento: la llamada a hashCode () en un objeto nulo es válida y devuelve cero. Esto requiere una ramificación más que en una llamada normal, lo que en sí mismo puede explicar la diferencia de rendimiento que ha constatado.

Tenga en cuenta que es cierto, parece solo de Java 7 debido a la introducción de Object.hashCode (target) que tiene esta semántica. Sería interesante saber en qué versión probó este problema y si tendría el mismo en Java6, por ejemplo.

Otra especificidad tiene un impacto positivo en el rendimiento: si no proporciona su propia implementación de hasCode (), el compilador JIT utilizará un código de cálculo hashcode en línea que es más rápido que una llamada compilada Object.hashCode.

MI.

Answer 4

Puedo confirmar los hallazgos. Vea estos resultados (se omiten las recompilaciones):

$ /extra/JDK8u5/jdk1.8.0_05/bin/java Main
overCode :    14.135000000s
hashCode :    14.097000000s

$ /extra/JDK7u21/jdk1.7.0_21/bin/java Main
overCode :    14.282000000s
hashCode :    54.210000000s

$ /extra/JDK6u23/jdk1.6.0_23/bin/java Main
overCode :    14.415000000s
hashCode :   104.746000000s

Los resultados se obtienen llamando a los métodos de la clase SubA extends Base repetidamente. Method overCode() es idéntico a hashCode() , ambos simplemente devuelven un campo int.

Ahora, la parte interesante: si se agrega el siguiente método a la clase Base

@Override
public int hashCode(){
    return super.hashCode();
}

los tiempos de ejecución para hashCode ya no son diferentes a los de overCode .

Base.java:

public class Base {
private int code;
public Base( int x ){
    code = x;
}
public int overCode(){
return code;
}
}

SubA.java:

public class SubA extends Base {
private int code;
public SubA( int x ){
super( 2*x );
    code = x;
}

@Override
public int overCode(){
return code;
}

@Override
public int hashCode(){
    return super.hashCode();
}
}

Answer 5

hashCode se define en java.lang.Object , por lo que definirlo en tu propia clase no hace mucho. (Todavía es un método definido pero no hace diferencia)

JIT tiene varias formas de optimizar los sitios de llamadas (en este caso hashCode() ):

• sin anulaciones - llamada estática (no virtual en absoluto) - mejor escenario posible con optimizaciones completas
• 2 sitios - ByteBuffer por ejemplo: verificación de tipo exacta y luego envío estático. La verificación de tipo es muy simple, pero dependiendo del uso puede o no ser predicho por el hardware.
• cachés en línea: cuando se han utilizado pocas instancias de clase diferentes en el cuerpo de la persona que llama, también es posible mantenerlos en línea; es posible que algunos métodos estén en línea, algunos se pueden llamar a través de tablas virtuales. El presupuesto en línea no es muy alto. Este es exactamente el caso en la pregunta: un método diferente sin nombre hashCode () presentaría las memorias caché en línea ya que solo hay cuatro implementaciones, en lugar de la tabla v
• Al agregar más clases a través de ese órgano llamante, se genera una llamada virtual real a medida que el compilador se da por vencido.

Las llamadas virtuales no están en línea y requieren un direccionamiento indirecto a través de la tabla de métodos virtuales y virtualmente aseguran la falta de caché. La falta de alineación en realidad requiere completas funciones con parámetros pasados ​​a través de la pila. En general, cuando el asesino de rendimiento real es la incapacidad para alinear y aplicar optimizaciones.

Tenga en cuenta: llamar a hashCode() de cualquier extensión de clase Base es lo mismo que llamar a Object.hashCode() y así es como se compila en bytecode, si agrega un hashCode explícito en Base que limitaría los posibles destinos de invocación de Base.hashCode()

Demasiadas clases (en JDK en sí) tienen hashCode() anulado, por lo que en los casos en las estructuras no alineadas HashMap similares, la invocación se realiza a través de vtable, es decir, lenta.

Como extra adicional: al cargar nuevas clases, el JIT tiene que desoptimizar los sitios de llamadas existentes.

Puedo intentar buscar algunas fuentes, si alguien está interesado en seguir leyendo