Guava ImmutableMap的存取速度明显慢于HashMap [英] Guava ImmutableMap has noticeably slower access than HashMap

问题描述

在研究一些高吞吐量数据结构的内存基准时，我意识到我可以使用 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 +string out of+ loop +attempts  - + 
 String.format（％。2f，100.0 * foundCount / loop ）+成功率。）; 
 System.out.println（map.getClass（）。getSimpleName（）+took+ 
 String.format（％。4f，stop / 1_000_000_000.0）+seconds。） ; 
 System.out.println（）; 
} 
  

对 HashMap ，a ConcurrentHashMap 和 ImmutableMap ，都包含相同的值， ImmutableMap - 往往慢15％。地图越稀疏（即更常见 map.get（）返回null），视差越大。以下是运行示例的结果：

 找到35312152个字符串，其中有100000000次尝试 -  35.31次成功率。 
 HashMap耗时29.4538秒。 
 
发现35312152个字符串中有100000000次尝试 -  35.31次成功率。 
 ConcurrentHashMap花了32.1465秒。 
 
发现35312152个字符串中有100000000次尝试 -  35.31次成功率。 
 RegularImmutableMap花了37.9709秒。 
  

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

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

ImmutableMap 并未针对慢等于方法。我认为主要区别在于：

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 不检查它的等于方法，所以 HashMap 更快。 ImmutableMap 不使用此优化，因为当等于已被优化时，它会使测试变慢。

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

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!

You can see the full benchmark here: 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:

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?

See also: https://groups.google.com/forum/?fromgroups=#!topic/guava-discuss/I7yPpa5Hlpg

解决方案

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

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.

这篇关于Guava ImmutableMap的存取速度明显慢于HashMap的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！