Guava ImmutableMap的访问速度明显慢于HashMap

While working on a memory benchmark of some high-throughput data structures, I realized I could use an ImmutableMap with only a little refactoring.

在研究一些高吞吐量数据结构的内存基准测试时,我意识到我可以使用一个只有一点点重构的ImmutableMap。

Thinking this would be an improvement, I threw it into the mix and was surprised to discover that not only was it slower than HashMap, in a single-threaded environment it appears to be consistently slower even than ConcurrentHashMap!

认为这将是一个改进,我把它扔进了组合中并且惊讶地发现它不仅比HashMap慢,在单线程环境中它看起来一直比ConcurrentHashMap更慢!

You can see the full benchmark here: https://bitbucket.org/snippets/dimo414/89K7G

你可以在这里看到完整的基准:https://bitbucket.org/snippets/dimo414/89K7G

The meat of the test is pretty simple, time how long it takes to get a large number of random strings that may exist in the map.

测试的内容非常简单,需要花费多长时间才能获得地图中可能存在的大量随机字符串。

public static void timeAccess(Map<String,String> map) {
    Random rnd = new Random(seed);
    int foundCount = 0;

    long start = System.nanoTime();

    for(int i = 0; i < loop; i++) {
        String s = map.get(RndString.build(rnd));
        if(s != null)
            foundCount++;
    }

    long stop = System.nanoTime() - start;

    System.out.println("Found "+foundCount+" strings out of "+loop+" attempts - "+
        String.format("%.2f",100.0*foundCount/loop)+" success rate.");
    System.out.println(map.getClass().getSimpleName()+" took "+
        String.format("%.4f", stop/1_000_000_000.0)+" seconds.");
    System.out.println();
}

And running this against a HashMap, a ConcurrentHashMap, and an ImmutableMap, all containing the same values, consistently showed a dramatic slowdown when using ImmutableMap - often upwards of 15% slower. The more sparse the map (i.e. the more often map.get() returned null) the greater the disparity. Here's the result of a sample run:

对HashMap,ConcurrentHashMap和ImmutableMap运行时,所有这些都包含相同的值,在使用ImmutableMap时始终显示出显着的减速 - 通常慢15%。地图越稀疏(即,map.get()返回null的次数越多)视差越大。以下是样本运行的结果:

Found 35312152 strings out of 100000000 attempts - 35.31 success rate.
HashMap took 29.4538 seconds.

Found 35312152 strings out of 100000000 attempts - 35.31 success rate.
ConcurrentHashMap took 32.1465 seconds.

Found 35312152 strings out of 100000000 attempts - 35.31 success rate.
RegularImmutableMap took 37.9709 seconds.

Is this a documented / expected issue? The Guava Docs indicate Immutable*** is more memory efficient, but says nothing about speed. For slowdowns of this magnitude, I'm inclined to deal with the memory costs and avoid Immutable*** when speed is an issue (and when isn't it?!). Am I missing something?

这是一个记录/预期的问题吗? Guava Docs表明Immutable ***更有效,但没有提及速度。对于这种程度的减速,我倾向于处理内存成本并避免在速度成为问题时不可变***(何时不是它?!)。我错过了什么吗?

另请参阅:https://groups.google.com/forum/?fromgroups =#!topic / guava-discuss / I7yPpa5Hlpg

2 个解决方案

#1

As Louis Wasserman said, ImmutableMap is not optimized for objects with slow equals method. I think the main difference is here:

正如Louis Wasserman所说,ImmutableMap没有针对具有慢等于方法的对象进行优化。我认为主要区别在于:

HashMap:

if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
    return e.value;

ImmtubleMap:

if (key.equals(candidateKey)) {
    return entry.getValue();

As you can see, to check for collisions, HashMap first check the hashes. This allows to reject values with different hashes fast. Since String doesn't make this check in its equals method, this makes HashMap faster. ImmutableMap doesn't use this optimization because it would make the test slower when equals is already optimized.

如您所见,为了检查冲突,HashMap首先检查哈希值。这允许快速拒绝具有不同散列的值。由于String不对其equals方法进行此检查,因此这使得HashMap更快。 ImmutableMap不使用此优化,因为当equals已经优化时,它会使测试变慢。

#2

Some possible reasons:

一些可能的原因:

Could that depend on your implementation of RndString.build()?

这可能取决于你的RndString.build()的实现?
And have a look at the get() implementation of both maps: com.google.common.collect.RegularImmutableMap.get(Object) java.util.HashMap.getEntry(Object) java.util.HashMap tries to compare with "==" first. RegularImmutableMap doesn't. That may speed up

并查看两个映射的get()实现:com.google.common.collect.RegularImmutableMap.get(Object)java.util.HashMap.getEntry(Object)java.util.HashMap尝试与“==进行比较“首先。 RegularImmutableMap没有。这可能会加速
Could a different load factor be responsible for that? Perhaps the RegularImmutableMap needs more iterations to find the correct entry.

可能有不同的负载因素吗?也许RegularImmutableMap需要更多迭代才能找到正确的条目。

#1