En utilisant Java HashMap standard (comparé à Trove THashMap), le code non-HashMap s'exécute plus lentement

Question

J'utilise un HashMap pour mettre en cache environ 2 millions de valeurs calculées via un algorithme récursif. J'utilise soit HashMap<Integer, Double> de Collections Framework, soit le TIntDoubleHashMap de la bibliothèque Trove, contrôlé par la variable boolean useTrove, comme dans le code ci-dessous.

Je ne vous attendez la bibliothèque Trove soit plus rapide, car il évite etc auto-boxing Et en effet, les appels put() et get() prendre environ 300ms pour exécuter (au total) pour la THashMap par rapport à environ 500 ms pour le HashMap<>. Maintenant, mon temps d'exécution global du programme est d'environ 2,8 secondes lorsque j'utilise THashMap et de 6,7 secondes lorsque j'utilise HashMap<>. Cette différence ne peut pas être expliquée par l'augmentation du temps d'exécution pour les appels put() et get() seuls.

1. Je soupçonne que ce temps d'exécution considérablement augmenté avec HashMap<> est entraîné par le fait que cette mise en œuvre est tout à fait mémoire inefficace chaque int/double a besoin d'être mis en boîte dans un objet, et cette augmentation utilisation de la mémoire provoque cache manque dans d'autres parties du programme. Cette explication a-t-elle un sens et comment puis-je confirmer/rejeter cette hypothèse? ?

2. En général, comment explorer les optimisations algorithmiques pour de tels scénarios? Le profilage de l'algorithme ne permet pas d'identifier le HashMap<> étant le coupable, au moins si seul le temps CPU est considéré. Est-ce simplement une question de savoir à l'avance que l'utilisation de la mémoire doit être prioritaire pour les programmes gourmands en mémoire?

Code entièrement en bas.

import java.util.HashMap; 
import gnu.trove.map.hash.TIntDoubleHashMap; 

class RuntimeStopWatch { 
    long elapsedTime; 
    long startTime; 
    RuntimeStopWatch() { reset(); } 
    void reset() { elapsedTime = 0; } 
    void start() { startTime = System.nanoTime(); } 
    void stop() { 
     long endTime = System.nanoTime(); 
     elapsedTime += (endTime - startTime); 
     startTime = endTime; 
    } 
    void printElapsedTime(String prefix) { 
     System.out.format(prefix + "%dms\n", elapsedTime/1000000); 
    } 
} 

public class HashMapBehaviour { 

    static RuntimeStopWatch programTime = new RuntimeStopWatch(); 
    static RuntimeStopWatch hashMapTime = new RuntimeStopWatch(); 
    static HashMap<Integer, Double> javaHashMapCache; 
    static TIntDoubleHashMap troveHashMapCache; 
    static boolean useTrove; 

    public static void main(String[] args) { 
//  useTrove = true; 
     useTrove = false; 

     javaHashMapCache = new HashMap<>(); 
     troveHashMapCache = new TIntDoubleHashMap(); 

     programTime.start(); 
     recursiveFunction(29, 29, 178956970); 
     programTime.stop(); 

     programTime.printElapsedTime("Program: "); 
     hashMapTime.printElapsedTime("Hashmap: "); 
    } 


    static double recursiveFunction(int n, int k, int bitString) { 
     if (k == 0) return 0.0; 
     if (useTrove) { 
      hashMapTime.start(); 
      if (troveHashMapCache.containsKey(bitString | (1 << n))) return troveHashMapCache.get(bitString | (1 << n)); 
      hashMapTime.stop(); 
     } else { 
      hashMapTime.start(); 
      if (javaHashMapCache.containsKey(bitString | (1 << n))) return javaHashMapCache.get(bitString | (1 << n)); 
      hashMapTime.stop(); 
     } 
     double result = 0.0; 
     for (int i = 0; i < (n >> 1); i++) { 
      double play1 = recursiveFunction(n - 1, k - 1, stripSingleBit(bitString, i)); 
      double play2 = recursiveFunction(n - 1, k - 1, stripSingleBit(bitString, n - i - 1)); 
      result += Math.max(play1, play2); 
     } 
     if (useTrove) { 
      hashMapTime.start(); 
      troveHashMapCache.put(bitString | (1 << n), result); 
      hashMapTime.stop(); 
     } else { 
      hashMapTime.start(); 
      javaHashMapCache.put(bitString | (1 << n), result); 
      hashMapTime.stop(); 
     } 
     return result; 
    } 

    static int stripSingleBit(int bitString, int bitIndex) { 
     return ((bitString >> (bitIndex + 1)) << bitIndex) | (bitString & ((1 << bitIndex) - 1)); 
    } 
} 

Answer 1

Une grande chose avec Trove est que vous aurez envie de pré-dimensionner la collection. Étant donné que le stockage est basé sur un tableau unique dans T * Maps, le fait de ne pas pré-dimensionner la collection entraînera beaucoup de création et de copie de tableaux. HashMap n'a pas ce problème car il utilise des objets liés.

Ainsi, le résumé: essayez la taille de votre collection avec new TIntDoubleHashMap(<expected_size>)

A périmètre plus grand, pensez à ce que vous optimisez pour. Trove est peut être le plus efficace avec l'utilisation de la mémoire globale et parfois la performance. Cependant, les grands gains de performances ne proviennent pas d'algorithmes de hachage super-snazzy, mais plutôt qu'il peut y avoir moins de pression de GC parce que moins d'objets temporaires (pour la boxe) sont utilisés. Que cela vous importe ou non dépend entièrement de votre application. De plus, le facteur de charge vous permet d'échanger la "densité" de données dans la matrice au prix de la vitesse de recherche. Donc, le réglage peut être utile. Si vous rencontrez beaucoup de collisions pendant les recherches et que vous voulez de meilleures performances ou que vous voulez maximiser la mémoire au détriment des performances, ajustez le facteur.

Si vous avez de la mémoire à graver et que vous voulez simplement des performances de recherche, HashMap est assez difficile à battre ... surtout si le contenu de la carte est statique. La JVM est très performante pour optimiser les objets temporaires, donc ne l'évitez pas trop vite. (Optimisation prématurée, etc ...)

Gardez à l'esprit que ce type de micro-benchmark n'est pas forcément un bon indicateur des performances réelles.Il manque des choses comme la pression GC et la compilation JIT. Des outils comme JMH peuvent aider à écrire des tests plus représentatifs.