（Trove THashMapと比較して）標準のJava HashMapを使用すると、HashMap以外のコードは遅く実行されます。

Question

私は再帰アルゴリズムによって計算された約200万の値をキャッシュするためにHashMapを使用します。私は、コレクションフレームワークのHashMap<Integer, Double>、またはboolean useTrove変数によって制御されるTroveライブラリのTIntDoubleHashMapのいずれかを以下のコードのように使用します。

私はそれが実際にオートボクシングなどを回避して、put()とget()通話、約300msの約500msのHashMap<>用に比べTHashMapのために（合計で）実行するために取る、トローブライブラリがより速くなることを期待します。

を使用した場合の全体のプログラム実行時間は、HashMap<>を使用した場合は6.7秒です。この違いは、put()とget()コールの実行時間の増加だけでは説明できません。

私は HashMap<>と、この非常に増加したランタイムは、この実装はそれぞれint型/オブジェクトに箱詰めされる二重のニーズ として非効率的なかなりのメモリであり、これは メモリ使用量を増加すると、キャッシュを引き起こすという事実によって を駆動させ疑い

1. プログラムの他の部分ではミスしてしまいます。 この説明は意味がありますが、この 仮説をどのように確認/拒否できますか？

2. 一般的に、このようなシナリオではアルゴリズムの最適化をどのように検討しますか？アルゴリズムのプロファイリングは、少なくともCPU時間だけが と考えられる場合は、 HashMap<>が原因であることを容易に指摘しません。メモリ使用量の多いプログラムでは、メモリ使用量に優先順位を付ける必要があることを事前に知ることは問題なのでしょうか？

コードは以下のとおりです。

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

Troveの大きな点の1つは、コレクションのサイズを事前に設定することです。 T * Mapsではストレージが単一の配列ベースなので、コレクションのサイズを事前に設定しないと、多くの配列の作成とコピーが行われます。 HashMapはリンクされたオブジェクトを使用するため、この問題は発生しません。

ので、要約：あなたが最適化しているものについて考え、壮大な範囲でnew TIntDoubleHashMap(<expected_size>)

であなたのコレクションのサイズを設定してみてください。 Troveは、全体的なメモリ使用量とパフォーマンスによって最も効率的です。しかし、大きなパフォーマンスの向上は、スーパースニーズハッシュアルゴリズムからではなく、一時的なオブジェクト（ボクシング用）の使用が少なくなるため、GCの負荷が少なくなる可能性があります。この問題があなたにとってどれほど重要かどうかは、アプリケーションによって異なります。また、負荷率は、検索速度を犠牲にしてアレイ内のデータ「密度」をトレードオフすることができます。ですから、チューニングすることは有用なことです。ルックアップの実行中に多くの衝突が発生し、パフォーマンスが向上したい場合、またはパフォーマンスを犠牲にしてメモリを最大化したい場合は、係数を調整します。

燃えるメモリがあり、ルックアップのパフォーマンスが必要な場合は、マップの内容が静的な場合は特にHashMapが勝つのがかなり難しいです。 JVMは一時オブジェクトを最適化するのに非常に優れているので、これをあまりにも早く割り引かないでください。 （時期尚早最適化など...）

このようなマイクロベンチマークも必ずしも実際のパフォーマンスを示す大きな指標ではありません。GCの圧力やJITコンパイルなどが欠けている。 JMHのようなツールは、より代表的なテストの作成に役立ちます。