39

いくつかの高スループット データ構造のメモリ ベンチマークに取り組んでいるときにImmutableMap、少しリファクタリングするだけで を使用できることに気付きました。

これは改善になると考えて、これをミックスに投入したところ、 よりも遅いだけでなく、シングルスレッド環境では!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();
}

そして、すべて同じ値を含む a HashMap、 a ConcurrentHashMap、および 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 DocsImmutable***はメモリ効率が高いことを示していますが、速度については何も述べていません。この程度の速度低下の場合、私はメモリ コストに対処し、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;

ImmtubeMap :

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

ご覧のとおり、衝突をチェックするには、HashMapまずハッシュをチェックします。これにより、異なるハッシュを持つ値をすばやく拒否できます。メソッドでこのチェックを行わないため、これにより高速Stringになります。が既に最適化されているとテストが遅くなるため、この最適化は使用しません。equalsHashMapImmutableMapequals

于 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 に答える