java - 使用标准 Java HashMap(与 Trove THashMap 相比)导致非 HashMap 代码运行速度变慢

Question

我使用 HashMap 来缓存通过递归算法计算的大约 200 万个值。我使用 HashMap<Integer, Double>来自集合框架，或 TIntDoubleHashMap来自 Trove 图书馆，由 boolean useTrove 控制变量，如下面的代码所示。

我确实希望 Trove 库更快，因为它避免了自动装箱等。事实上，put()和 get() THashMap 调用大约需要 300 毫秒才能运行(总共)与 HashMap<> 的大约 500 毫秒相比.

现在，使用 THashMap 时，我的整体程序运行时间约为 2.8 秒, 使用 HashMap<> 时为 6.7s . 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));
    }
}

Answer 1

Trove 的一大特点是您需要预先确定 Collection 的大小。因为在 T*Maps 中存储是基于单个数组的，所以无法预先确定集合的大小将导致大量的数组创建和复制。 HashMap 没有这个问题，因为它使用链接对象。

因此，总结:尝试使用 new TIntDoubleHashMap(<expected_size>) 调整您的 Collection 的大小

在更大的范围内，考虑您要优化的内容。 Trove 在整体内存使用和有时性能方面可能是最有效的。然而，巨大的性能提升并非来自 super 时髦的哈希算法，而是因为使用了较少的临时对象(用于装箱)，因此可以减少 GC 压力。这对您是否重要完全取决于您的应用程序。此外，加载因子允许您以查找速度为代价来权衡数组中的数据“密度”。因此，调整可能很有用。如果您在进行查找时遇到很多冲突并且想要更好的性能或者想要以牺牲性能为代价来最大化内存，请调整该因子。

如果您有内存需要消耗并且只想要查找性能，那么 HashMap 很难被击败……尤其是当映射的内容是静态的时候。 JVM 非常擅长优化临时对象，所以不要过快地打折。 (过早优化等...)

请记住，这种微观基准也不一定是真实世界表现的重要指标。它遗漏了 GC 压力和 JIT 编译之类的东西。 JMH 等工具可以帮助编写更具代表性的测试。