39

在处理一些高吞吐量数据结构的内存基准测试时，我意识到我ImmutableMap只需稍作重构就可以使用 an。

认为这将是一个改进，我将它投入到混合中，并惊讶地发现它不仅比 慢HashMap，在单线程环境中它似乎始终比ConcurrentHashMap!

你可以看到完整的基准

测试的内容非常简单，计算获取地图中可能存在的大量随机字符串需要多长时间。

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

HashMap并且针对包含相同值的 a 、 aConcurrentHashMap和 an运行此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.

这是记录/预期的问题吗？Guava Docs表明Immutable***内存效率更高，但没有提到速度。对于这种程度的减速，我倾向于处理内存成本并避免Immutable***速度成为问题（什么时候不是问题？！）。我错过了什么吗？

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

4

2 回答 2

20

正如 Louis Wasserman 所说，ImmutableMap没有针对慢速equals方法的对象进行优化。我认为主要区别在这里：

哈希映射：

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

不图映射：

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

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

于 2013-04-30T15:21:35.313 回答
0

一些可能的原因：

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

  2. 并查看两个地图的 get() 实现： com.google.common.collect.RegularImmutableMap.get(Object) java.util.HashMap.getEntry(Object) java.util.HashMap 尝试与“== 进行比较“ 第一的。RegularImmutableMap 没有。这可能会加快

  3. 一个不同的负载因子会对此负责吗？也许 RegularImmutableMap 需要更多的迭代才能找到正确的条目。

于 2013-04-05T22:04:13.037 回答