Guava ImmutableMap ha un accesso notevolmente più lento di HashMap

Question

Mentre lavoravo su un benchmark di memoria di alcune strutture di dati ad alto throughput, mi sono reso conto che potevo usare uno ImmutableMap con solo un piccolo refactoring.

Pensando che questo sarebbe stato un miglioramento, l'ho inserito nel mix e sono stato sorpreso di scoprire che non solo era più lento di HashMap, in un ambiente a thread singolo sembra essere sempre più lento anche di ConcurrentHashMap!

si può vedere il punto di riferimento completo qui: https://bitbucket.org/snippets/dimo414/89K7G

La carne del test è piuttosto semplice, quanto tempo ci vuole per ottenere un gran numero di stringhe casuali che possono esistere nella mappa.

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(); 
} 

E l'esecuzione di questo contro un HashMap, un ConcurrentHashMap, e un ImmutableMap, tutti contenenti gli stessi valori, costantemente ha mostrato un rallentamento drammatico quando si utilizza ImmutableMap - spesso verso l'alto di 15% più lento. Più sparsa è la mappa (ad esempio, più spesso è map.get() restituita nulla) maggiore è la disparità. Ecco il risultato di un'esecuzione di esempio:

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. 

Si tratta di un problema documentato/previsto? Il Guava Docs indica che Immutable*** è più efficiente in termini di memoria, ma non dice nulla sulla velocità. Per rallentamenti di questa portata, sono propenso ad affrontare i costi della memoria ed evitare lo Immutable*** quando la velocità è un problema (e quando no ?!). Mi sto perdendo qualcosa?

Consulta anche: https://groups.google.com/forum/?fromgroups=#!topic/guava-discuss/I7yPpa5Hlpg

Answer 1

Alcune possibili ragioni:

1. Potrebbe che dipendono dalla realizzazione di RndString.build()?

2. e dare un'occhiata alla realizzazione get() di entrambe le mappe: com.google.common.collect.RegularImmutableMap.get (Object) java.util.HashMap.getEntry (Object) java.util. HashMap tenta di confrontare prima con "==". RegularImmutableMap non lo fa. Ciò potrebbe accelerare

3. Potrebbe essere responsabile un diverso fattore di carico? Forse la RegularImmutableMap ha bisogno di più iterazioni per trovare la voce corretta.

Answer 2

Come detto Louis Wasserman, ImmutableMap non è ottimizzato per oggetti con metodo lento equals. Penso che la differenza principale è qui:

HashMap:

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

ImmtubleMap:

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

Come si può vedere, per verificare la presenza di collisioni, HashMap prima controllare gli hash. Ciò consente di rifiutare rapidamente i valori con diversi hash. Poiché String non esegue questo controllo nel suo metodo equals, questo rende HashMap più veloce.ImmutableMap non utilizza questa ottimizzazione perché renderebbe il test più lento quando equals è già ottimizzato.