java - マルチキーマップ - 性能比較

Question

環境

私たちのアプリケーションは、高速なルックアップを可能にするために、さまざまな種類のマップのメモリに大量のデータを格納します。シンプルにするために (プリミティブマップは考慮しない)、常に 1 つ以上のキーを持つマップです。パフォーマンスは私たちにとって大きな要件です。

問題

最もパフォーマンスの高いマップの実装を見つけたかったので、ここで提案されているように、これらの実装を比較しました。

3 つのキー専用の java.util.HashMap に基づくマップ (ネストされたマップ) のマップ:
```
Map<K1, Map<K2, Map<K3, V>>>
```
java.util.HashMap のラッパーキー (キーとしてのタプル)
```
Map<Triple<K1, K2, K3>, V>
```
net.openhft.koloboke.collect.map.hash.HashObjObjMap のキーとしてのタプル。これによると、最速のマップ (の 1 つ) になります。
```
HashObjObjMap<Triple<K1, K2, K3>, V>
```

期待

ネストされたマップは、GET が最も速く、PUT が最も遅くなります。
Koloboke ハッシュマップは、jdk HashMap よりも高速になります。

結果

Benchmark                                                Mode  Cnt   Score   Error  Units
TupleVsNestedMapsBenchmark.benchGetFromNestedMap         avgt   20  11.586 ± 0.205  ns/op
TupleVsNestedMapsBenchmark.benchGetFromTupleKolobokeMap  avgt   20  18.619 ± 0.113  ns/op
TupleVsNestedMapsBenchmark.benchGetFromTupleMap          avgt   20   8.985 ± 0.085  ns/op
TupleVsNestedMapsBenchmark.benchPutToNestedMap           avgt   20  15.106 ± 0.142  ns/op
TupleVsNestedMapsBenchmark.benchPutToTupleKolobokeMap    avgt   20  22.533 ± 0.335  ns/op
TupleVsNestedMapsBenchmark.benchPutToTupleMap            avgt   20   8.884 ± 0.084  ns/op

基準

@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
@OperationsPerInvocation(100000)
@Fork(1)
@Warmup(iterations = 10)
@Measurement(iterations = 20)
public class TupleVsNestedMapsBenchmark {

public static final int N = 10000;

static ObjObjObjObjHashMap<String, String, String, Integer> sourceNestedMap = new ObjObjObjObjHashMap<>();
static Map<Triple<String, String, String>, Integer> sourceTupleMap = new HashMap<>();
static HashObjObjMap<Triple<String, String, String>, Integer> sourceTupleKMap = HashObjObjMaps.newMutableMap();

static {
    for (int i = 0; i < N; i++) {
        sourceNestedMap.put("a-" + i, "b-" + i, "c-" + i, i);
        sourceTupleMap.put(ImmutableTriple.of("a-" + i, "b-" + i, "c-" + i), i);
        sourceTupleKMap.put(ImmutableTriple.of("a-" + i, "b-" + i, "c-" + i), i);
    }
}

@Benchmark
public List<Integer> benchGetFromNestedMap() {
    return benchmarkGet(sourceNestedMap::get);
}

@Benchmark
public List<Integer> benchGetFromTupleMap() {
    return benchmarkGet(((key1, key2, key3) -> sourceTupleMap.get(ImmutableTriple.of(key1, key2, key3))));
}

@Benchmark
public List<Integer> benchGetFromTupleKolobokeMap() {
    return benchmarkGet(((key1, key2, key3) -> sourceTupleKMap.get(ImmutableTriple.of(key1, key2, key3))));
}

@Benchmark
public ObjObjObjObjHashMap<String, String, String, Integer> benchPutToNestedMap() {
    ObjObjObjObjHashMap<String, String, String, Integer> map = new ObjObjObjObjHashMap<>();

    benchmarkPut(map::put);

    return map;
}

@Benchmark
public Map<Triple<String, String, String>, Integer> benchPutToTupleMap() {
    Map<Triple<String, String, String>, Integer> map = new HashMap<>();

    benchmarkPut((key1, key2, key3, value) -> map.put(ImmutableTriple.of(key1, key2, key3), value));

    return map;
}

@Benchmark
public Map<Triple<String, String, String>, Integer> benchPutToTupleKolobokeMap() {
    HashObjObjMap<Triple<String, String, String>, Integer> map = HashObjObjMaps.newMutableMap();

    benchmarkPut((key1, key2, key3, value) -> map.put(ImmutableTriple.of(key1, key2, key3), value));

    return map;
}

private List<Integer> benchmarkGet(MapValueSupplier<Integer> mapValueSupplier) {
    List<Integer> result = new ArrayList<>(N);
    for (int i = 0; i < N; i++) {
        result.add(mapValueSupplier.supply("a-" + i, "b-" + i, "c-" + i));

    }
    return result;
}

private void benchmarkPut(PutValueFunction<Integer> putValueFunction) {
    for (int i = 0; i < N; i++) {
        putValueFunction.apply("a-" + i, "b-" + i, "c-" + i, i);
    }
}

private interface MapValueSupplier<T> {

    T supply(String key1, String key2, String key3);
}

private interface PutValueFunction<T> {

    void apply(String key1, String key2, String key3, T value);
}
}

注:プリミティブマップの使用を提案しないでください。(値) としての整数は、安価なオブジェクトの単なる例です。

質問

koloboke マップが jdk マップの 2.5 倍遅いのはなぜですか?
ネストされたマップが高速にならないのはなぜですか? (タプルキーオブジェクトの割り当てオーバーヘッドが大きくなると予想されます。)
それとも私のベンチマークが間違っていますか？では、どうすればそれを改善できますか？

アップデート

@leventov からの良いアドバイスに基づいて、ベンチマークを変更し、ハッシュコードをキャッシュする (そしてより良い分散を持つ) トリプル実装も試しました - テストは Tuple2 と名付けられました。

@State(Scope.Thread)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
@OperationsPerInvocation(TupleVsNestedMapsBenchmark.TOTAL_OPS)
@Fork(1)
@Warmup(iterations = 5)
@Measurement(iterations = 20)
public class TupleVsNestedMapsBenchmark {

static final int N = 30;
static final int TOTAL_OPS = N * N * N;

private ObjObjObjObjHashMap<String, String, String, Integer> sourceNestedMap;
private Map<Triple<String, String, String>, Integer> sourceTupleMap;
private HashObjObjMap<Triple<String, String, String>, Integer> sourceTupleKMap;
private Map<Triple<String, String, String>, Integer> sourceTuple2Map;
private HashObjObjMap<Triple<String, String, String>, Integer> sourceTuple2KMap;
private String[] keys;

@Setup
public void init() {
    sourceNestedMap = new ObjObjObjObjHashMap<>();
    sourceTupleMap = new HashMap<>(TOTAL_OPS);
    sourceTupleKMap = HashObjObjMaps.newMutableMap(TOTAL_OPS);
    sourceTuple2Map = new HashMap<>(TOTAL_OPS);
    sourceTuple2KMap = HashObjObjMaps.newMutableMap(TOTAL_OPS);
    keys = new String[N];
    for (int i = 0; i < N; i++) {
        keys[i] = "k" + i;
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                sourceNestedMap.put(keys[i], keys[j], keys[k], i);
                sourceTupleMap.put(ImmutableTriple.of(keys[i], keys[j], keys[k]), i); 
                sourceTupleKMap.put(ImmutableTriple.of(keys[i], keys[j], keys[k]), i); 
                sourceTuple2Map.put(ImmutableTriple2.of(keys[i], keys[j], keys[k]), i);
                sourceTuple2KMap.put(ImmutableTriple2.of(keys[i], keys[j], keys[k]), i);
            }
        }
    }
}

@Benchmark
public List<Integer> benchGetFromNestedMap() {
    return benchmarkGet(sourceNestedMap::get);
}

@Benchmark
public List<Integer> benchGetFromTupleMap() {
    return benchmarkGet(((key1, key2, key3) -> sourceTupleMap.get(ImmutableTriple.of(key1, key2, key3))));
}

@Benchmark
public List<Integer> benchGetFromTupleKolobokeMap() {
    return benchmarkGet(((key1, key2, key3) -> sourceTupleKMap.get(ImmutableTriple.of(key1, key2, key3))));
}

@Benchmark
public List<Integer> benchGetFromTuple2Map() {
    return benchmarkGet(((key1, key2, key3) -> sourceTuple2Map.get(ImmutableTriple2.of(key1, key2, key3))));
}

@Benchmark
public List<Integer> benchGetFromTuple2KolobokeMap() {
    return benchmarkGet(((key1, key2, key3) -> sourceTuple2KMap.get(ImmutableTriple2.of(key1, key2, key3))));
}

@Benchmark
public ObjObjObjObjHashMap<String, String, String, Integer> benchPutToNestedMap() {
    ObjObjObjObjHashMap<String, String, String, Integer> map = new ObjObjObjObjHashMap<>();
    benchmarkPut(map::put);
    return map;
}

@Benchmark
public Map<Triple<String, String, String>, Integer> benchPutToTupleMap() {
    Map<Triple<String, String, String>, Integer> map = new HashMap<>();
    benchmarkPut((key1, key2, key3, value) -> map.put(ImmutableTriple.of(key1, key2, key3), value));
    return map;
}

@Benchmark
public Map<Triple<String, String, String>, Integer> benchPutToTupleKolobokeMap() {
    HashObjObjMap<Triple<String, String, String>, Integer> map = HashObjObjMaps.newMutableMap();
    benchmarkPut((key1, key2, key3, value) -> map.put(ImmutableTriple.of(key1, key2, key3), value));
    return map;
}

@Benchmark
public Map<Triple<String, String, String>, Integer> benchPutToTuple2Map() {
    Map<Triple<String, String, String>, Integer> map = new HashMap<>();
    benchmarkPut((key1, key2, key3, value) -> map.put(ImmutableTriple2.of(key1, key2, key3), value));
    return map;
}

@Benchmark
public Map<Triple<String, String, String>, Integer> benchPutToTuple2KolobokeMap() {
    HashObjObjMap<Triple<String, String, String>, Integer> map = HashObjObjMaps.newMutableMap();
    benchmarkPut((key1, key2, key3, value) -> map.put(ImmutableTriple2.of(key1, key2, key3), value));
    return map;
}

private List<Integer> benchmarkGet(MapValueSupplier<Integer> mapValueSupplier) {
    List<Integer> result = new ArrayList<>(TOTAL_OPS);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                Integer value = mapValueSupplier.supply(keys[i], keys[j], keys[k]);
                result.add(value);
            }
        }
    }
    return result;
}

private void benchmarkPut(PutValueFunction<Integer> putValueFunction) {
    Integer value = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                putValueFunction.apply(keys[i], keys[j], keys[k], value);
            }
        }
    }
}

private interface MapValueSupplier<T> {

    T supply(String key1, String key2, String key3);
}

private interface PutValueFunction<T> {

    void apply(String key1, String key2, String key3, T value);
}
}

結果は次のとおりです。

Benchmark                                                 Mode  Cnt      Score      Error  Units
TupleVsNestedMapsBenchmark.benchGetFromNestedMap          avgt   20     24.524 ±    0.144  ns/op
TupleVsNestedMapsBenchmark.benchGetFromTuple2KolobokeMap  avgt   20     65.604 ±    1.135  ns/op
TupleVsNestedMapsBenchmark.benchGetFromTuple2Map          avgt   20     22.653 ±    0.745  ns/op
TupleVsNestedMapsBenchmark.benchGetFromTupleKolobokeMap   avgt   20  34824.901 ± 1718.183  ns/op
TupleVsNestedMapsBenchmark.benchGetFromTupleMap           avgt   20   2565.835 ±   57.402  ns/op
TupleVsNestedMapsBenchmark.benchPutToNestedMap            avgt   20     43.160 ±    0.340  ns/op
TupleVsNestedMapsBenchmark.benchPutToTuple2KolobokeMap    avgt   20    237.300 ±    3.362  ns/op
TupleVsNestedMapsBenchmark.benchPutToTuple2Map            avgt   20     40.952 ±    0.535  ns/op
TupleVsNestedMapsBenchmark.benchPutToTupleKolobokeMap     avgt   20  52315.769 ±  399.769  ns/op
TupleVsNestedMapsBenchmark.benchPutToTupleMap             avgt   20   3205.538 ±   44.306  ns/op

概要

「タプル」アプローチは、キークラスのハッシュコード関数がキャッシュされていないか、十分に分散されていない場合、特に koloboke の場合、非常に遅くなる可能性があります。
ここでも結論付けられているように (この (Obj-Obj) の場合)、 java.util.HashMap は「非常に」高速です。

score 8 · Accepted Answer

[更新された質問への回答。]

さて、ベンチマークにはまだ問題があります。

ライフサイクルを作成するときStateは、状態オブジェクトをパラメーターとして benhcmark メソッドに渡す必要があります (以下のコードを参照)。
ベンチマークput()s は別の方法で行う必要があります: 1) @Setup メソッドで、コレクションを作成する必要があります (十分なcapacityまたはsize引数を指定して) 2) 別の@Setup(Level.Invocation)メソッドで呼び出す必要があります3)ベンチマークメソッドでcollection.clear()純粋な s を測定するput()
ベンチマーク方法では、まだ多くの割り当てを行っています。これはあなたの場合かもしれませんが、コレクションのパフォーマンスへの貢献を隠しています。

だから、私が書いたこと：

package tests;

import net.openhft.koloboke.collect.map.hash.HashObjObjMap;
import net.openhft.koloboke.collect.map.hash.HashObjObjMaps;
import org.apache.commons.lang3.tuple.Triple;
import org.openjdk.jmh.annotations.*;

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.TimeUnit;

@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
@Fork(1)
@Threads(1)
@Warmup(iterations = 10)
@Measurement(iterations = 20)
@State(Scope.Thread)
public class SoMultiMap {

    public static final int N = Integer.getInteger("runs", 100000);

    private static final double kbk = Double.parseDouble(System.getProperty("kbk", "1.0"));

    static class ImmutableTriple<L, M, R> extends Triple<L, M, R> {
        public final L left;
        public final M middle;
        public final R right;
        private int h;

        public static <L, M, R> ImmutableTriple<L, M, R> of(L left, M middle, R right) {
            return new ImmutableTriple(left, middle, right);
        }

        public ImmutableTriple(L left, M middle, R right) {
            this.left = left;
            this.middle = middle;
            this.right = right;
        }

        public L getLeft() {
            return this.left;
        }

        public M getMiddle() {
            return this.middle;
        }

        public R getRight() {
            return this.right;
        }

        private int innerHash() {
            int h = left.hashCode();
            h *= 1000003;
            h += middle.hashCode();
            h *= 1000003;
            h += right.hashCode();
            return h * 1000003;
        }

        @Override
        public int hashCode() {
            return h != 0 ? h : (h = innerHash());
        }

        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof ImmutableTriple))
                return super.equals(obj);
            ImmutableTriple triple = (ImmutableTriple) obj;
            if (h != 0 && triple.h != 0 && h != triple.h)
                return false;
            return super.equals(obj);
        }
    }

    ImmutableTriple<String, String, String>[] keys = new ImmutableTriple[N];
    Integer[] values = new Integer[N];
    Map<Triple<String, String, String>, Integer> sourceTupleMap;
    HashObjObjMap<Triple<String, String, String>, Integer> sourceTupleKMap;

    @Setup
    public void fill() {
        sourceTupleMap = new HashMap<>((int) (N / 0.75));
        sourceTupleKMap = HashObjObjMaps.newUpdatableMap((int) (N * kbk));
        for (int i = 0; i < N; i++) {
            keys[i] = ImmutableTriple.of("a-" + i, "b-" + i, "c-" + i);
            values[i] = i;
            sourceTupleKMap.put(keys[i], values[i]);
            sourceTupleMap.put(keys[i], values[i]);
        }
    }

    @Benchmark
    public int tupleHashMapGet(SoMultiMap st) {
        ImmutableTriple<String, String, String>[] keys = st.keys;
        Map<Triple<String, String, String>, Integer> map = st.sourceTupleMap;
        int s = 0;
        for (int i = 0; i < N; i++) {
            s += map.get(keys[i]);
        }
        return s;
    }

    @Benchmark
    public int tupleKolobokeGet(SoMultiMap st) {
        ImmutableTriple<String, String, String>[] keys = st.keys;
        HashObjObjMap<Triple<String, String, String>, Integer> map = st.sourceTupleKMap;
        int s = 0;
        for (int i = 0; i < N; i++) {
            s += map.get(keys[i]);
        }
        return s;
    }

    public static void main(String[] args) {
        SoMultiMap st = new SoMultiMap();
        st.fill();
        st.tupleKolobokeGet(st);
        st.tupleHashMapGet(st);
    }
}

興味深いのは、結果です。

Java 7u55 の場合:

HashMap:  65 +- 6 ns/op
Koloboke: 46 +- 2

Java 8u51 の場合:

HashMap:  42 +- 0.5
Koloboke: 49 +- 1

そのため、いくつかの VM の変更があり、その間に何かがあり、HashMap大幅に高速になり、Kolobokeマップがわずかに遅くなりました。これには調査が必要ですが、今は時間がありません。https://github.com/OpenHFT/Koloboke/issues/42を参照してください。

また、いくつかの点に注意してください。

サーバー VM でベンチマークを実行する
実行中の CPU スケーリングを無効にする
16 以上のハードウェアスレッドがない限り、負荷の高いアプリ (ブラウザー、Intellij など) を閉じます。

score 1 · Accepted Answer

ベンチマークの問題のリスト:

初期化は静的領域で行われ、@Setupメソッドと@Statesで行う必要があります
ベンチマーク内での大量の割り当て、および文字列の構築! 実際に測定しているものは何ですか？
間違いに注意してください - N10K ですが、operationsPerInvocation100K であるため、実際の時間は非常に憂鬱です
貧弱なStringハッシュコード + 非常に貧弱なTripleハッシュコードにより、ハッシュテーブルでクラスタリングが発生する
ネストされた対タプルをテストするときは、すべてのキーのすべての部分が一意であるように選択したことに注意してください。つまり、ネストされたすべてのマップは単一のキーを持つマップです。これはおそらくあなたが望んでいたものではありません

score 0 · Accepted Answer

抽象化としてのトリプルは問題ありません (少なくとも、明らかに優れた代替手段はありません。Apache Commons のTriple抽象クラスをオーバーライドして、より優れたhashCode()機能を定義できます。

final class ImmutableTriple<L, M, R> extends Triple<L, M, R> {
    public final L left;
    public final M middle;
    public final R right;
    private int h;

    public static <L, M, R> ImmutableTriple<L, M, R> of(L left, M middle, R right) {
        return new ImmutableTriple(left, middle, right);
    }

    public ImmutableTriple(L left, M middle, R right) {
        this.left = left;
        this.middle = middle;
        this.right = right;
    }

    public L getLeft() {
        return this.left;
    }

    public M getMiddle() {
        return this.middle;
    }

    public R getRight() {
        return this.right;
    }

    private int innerHash() {
        int h = left.hashCode();
        h *= 1000003;
        h += middle.hashCode();
        h *= 1000003;
        h += right.hashCode();
        return (int) LongHashFunction.murmur_3().hashInt(h);
    }

    @Override
    public int hashCode() {
        return h != 0 ? h : (h = innerHash());
    }
}

java - マルチキーマップ - 性能比較

環境

問題

期待

結果

基準

質問

アップデート

概要

3 に答える 3

Related

Reference