3

我使用 HashMap 缓存通过递归算法计算的大约 200 万个值。我使用HashMap<Integer, Double>Collections Framework 或TIntDoubleHashMapTrove 库中的一个，由boolean useTrove变量控制，如下面的代码所示。

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

现在，我的整体程序运行时间约为 2.8 秒，使用THashMap6.7 秒HashMap<>。这种差异不能仅用put()andget()调用增加的运行时间来解释。

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

1 回答 1

2

One big thing with Trove is that you'll want to pre-size the collection. Because storage is single-array-based in T*Maps, failing to pre-size the collection will result in a lot of array creation and copying. HashMap doesn't have this problem because it uses linked objects.

So, summary: try sizing your collection with new TIntDoubleHashMap(<expected_size>)

At a grander scope, think about what you're optimizing for. Trove is can be most efficient with overall memory usage and sometimes performance. However, the big performance gains don't come from super-snazzy hashing algorithms, but rather that there can be less GC pressure because less temporary objects (for boxing) are used. Whether or not this matters to you entirely depends on your application. Also the load factor allows you to trade off data "density" in the array at the cost of lookup speed. So, tuning that can be useful. If you get a lot of collisions while doing lookups and want better performance or want to maximize memory at the cost of performance, adjust the factor.

If you have memory to burn and just want lookup performance, HashMap is pretty tough to beat... especially if the contents of the map are static. The JVM is very good at optimizing away temporary objects, so don't discount this too quickly. (Premature optimization, etc...)

Keep in mind that this kind of micro benchmark also isn't necessarily a great indicator of real-world performance. It misses things like GC pressure and JIT compilation. Tools like JMH can help writing more representative tests.

于 2017-01-25T04:17:25.467 回答