java - 標準の Java HashMap を使用すると (Trove THashMap と比較して)、非 HashMap コードの実行が遅くなります

Question

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

オートボクシングなどを回避するため、Trove ライブラリはより高速になると思います。実際、put()とのget()呼び出しは、 の実行に約 500 ミリ秒かかるのに対し、 の実行には (合計で) 約 300 ミリ秒かかりTHashMapますHashMap<>。

現在、私の全体的なプログラム実行時間は、 を使用した場合は約 2.8 秒、 を使用した場合は 6.7THashMap秒HashMap<>です。put()この違いは、とのget()呼び出しの実行時間の増加だけでは説明できません。

1. この大幅に増加しHashMap<>た実行時間は、各 int/double をオブジェクトにボックス化する必要があるため、この実装は非常にメモリ効率が低く、このメモリ使用量の増加により、プログラムの他の部分でキャッシュ ミスが発生するという事実によって引き起こされていると思われます。この説明は理にかなっていますか? また、この仮説をどのように確認/拒否できますか?

2. 一般に、このようなシナリオのアルゴリズムの最適化をどのように探せばよいでしょうか? HashMap<>アルゴリズムのプロファイリングは、少なくとも CPU 時間だけを考慮した場合、犯人であることを容易に指摘するものではありません 。メモリを大量に消費するプログラムでは、メモリの使用を優先する必要があることを事前に知っておくだけの問題ですか?

以下の完全なコード。

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