java - immutable map of

Guava ImmutableMap tiene un acceso notablemente más lento que HashMap

Question

Mientras trabajaba en un benchmark de memoria de algunas estructuras de datos de alto rendimiento, me di cuenta de que podía usar un ImmutableMap con solo un poco de refactorización.

Pensando que esto sería una mejora, lo lancé a la mezcla y me sorprendí al descubrir que no solo era más lento que HashMap , en un entorno de subproceso único, ¡parece ser consistentemente más lento incluso que ConcurrentHashMap !

Puede ver el punto de referencia completo aquí: https://bitbucket.org/snippets/dimo414/89K7G

La carne de la prueba es bastante simple, el tiempo que toma obtener una gran cantidad de cadenas aleatorias que pueden existir en el mapa.

public static void timeAccess(Map<String,String> map) {
    Random rnd = new Random(seed);
    int foundCount = 0;

    long start = System.nanoTime();

    for(int i = 0; i < loop; i++) {
        String s = map.get(RndString.build(rnd));
        if(s != null)
            foundCount++;
    }

    long stop = System.nanoTime() - start;

    System.out.println("Found "+foundCount+" strings out of "+loop+" attempts - "+
        String.format("%.2f",100.0*foundCount/loop)+" success rate.");
    System.out.println(map.getClass().getSimpleName()+" took "+
        String.format("%.4f", stop/1_000_000_000.0)+" seconds.");
    System.out.println();
}

Y al ejecutar esto contra un HashMap , un ConcurrentHashMap y un ImmutableMap , todos con los mismos valores, mostraron una dramática desaceleración al usar ImmutableMap , a menudo más del 15% más lento. Cuanto más disperso es el mapa (es decir, cuanto más a menudo map.get() devuelve nulo), mayor es la disparidad. Este es el resultado de una ejecución de muestra:

Found 35312152 strings out of 100000000 attempts - 35.31 success rate.
HashMap took 29.4538 seconds.

Found 35312152 strings out of 100000000 attempts - 35.31 success rate.
ConcurrentHashMap took 32.1465 seconds.

Found 35312152 strings out of 100000000 attempts - 35.31 success rate.
RegularImmutableMap took 37.9709 seconds.

¿Es esto un problema documentado / esperado? Los documentos de Guava indican que Immutable*** es más eficiente en cuanto a la memoria, pero no dice nada sobre la velocidad. Para desaceleraciones de esta magnitud, me inclino a lidiar con los costos de la memoria y evitar el Immutable*** cuando la velocidad es un problema (¿y cuándo no ?!). ¿Me estoy perdiendo de algo?

Ver también: https://groups.google.com/forum/?fromgroups=#!topic/guava-discuss/I7yPpa5Hlpg

Answer 1

Algunas posibles razones:

1. ¿Podría eso depender de su implementación de RndString.build ()?

2. Y eche un vistazo a la implementación get () de ambos mapas: com.google.common.collect.RegularImmutableMap.get (Object) java.util.HashMap.getEntry (Object) java.util.HashMap intenta comparar con "== " primero. RegularImmutableMap no lo hace. Eso puede acelerar

3. ¿Podría un factor de carga diferente ser responsable de eso? Quizás RegularImmutableMap necesite más iteraciones para encontrar la entrada correcta.

Answer 2

Como dijo Louis Wasserman, ImmutableMap no está optimizado para objetos con método lento equals . Creo que la principal diferencia está aquí:

HashMap :

if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
    return e.value;

ImmtubleMap :

if (key.equals(candidateKey)) {
    return entry.getValue();

Como puede ver, para verificar colisiones, HashMap primero verifica los valores hash. Esto permite rechazar valores con hashes diferentes rápidamente. Como String no hace esta comprobación en su método equals , esto hace que HashMap sea ​​más rápido. ImmutableMap no usa esta optimización porque haría la prueba más lenta cuando los equals ya están optimizados.