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

Question

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

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

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

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

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

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

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.

这是一个记录/预期的问题吗？该番石榴文件表明Immutable***是更多的内存效率,但没有关于速度说.对于这种程度的减速,我倾向于处理内存成本并避免Immutable***速度成为问题(什么时候不是它？!).我错过了什么吗？

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

Answer 1

正如Louis Wasserman所说,ImmutableMap没有针对具有慢速equals方法的物体进行优化.我认为主要区别在于:

HashMap:

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

ImmtubleMap:

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

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

Answer 2

一些可能的原因：

1. 这可能取决于您对 RndString.build() 的实现吗？

2. 看看两个映射的 get() 实现： com.google.common.collect.RegularImmutableMap.get(Object) java.util.HashMap.getEntry(Object) java.util.HashMap 尝试与“== 进行比较“ 第一的。RegularImmutableMap 则不然。这可能会加快

3. 不同的负载系数可能是造成这种情况的原因吗？也许 RegularImmutableMap 需要更多迭代才能找到正确的条目。