読者です 読者をやめる 読者になる 読者になる

interprism's blog

インタープリズム株式会社の開発者ブログです。

Java8からはHashMapの性能のためにComparableを実装しておいた方がいい

こんにちは、andoです。

ついにJava8がリリースされたのでさっそくインストールしてみました。 Java8になってラムダ式を始め、多くの機能が追加されたのですが、既存機能についても性能改善が行われています。 人気がありそうな新機能の紹介は他の人にお任せして、今回はHashMapの変更点について確認したいと思います。 はたして既存のプログラムはJava8で実行するだけで、その恩恵を享受できるのでしょうか。

java.util.HashMap

HashMapといえば使用頻度1、2を争うコレクションクラスでデータの検索、追加がO(1)で行え、 辞書的に使える事から簡易的なDTOやキャッシュ、データベースのレコード構造、さらにはListですむところでさえ数値をキーにして使う兵もいるというくらい良くも悪くも色々使えます。
それが速くなるのであれば、既存のプログラムも速くなるはず、ということでさっそく変更点を確認してマイクロベンチを作りました。

変更点

キー衝突時のパフォーマンス改善ということです。
実装的にはハッシュコードの衝突ですね。 Map.Entryの単方向リストの連結が深くなると赤黒木に作り変え、検索、追加の走査の回数を削減するようです。 最悪ケースのO(n)がO(log n)になるということでしょうか。

Collections Framework Enhancements in Java SE 8

マイクロベンチ

上記の変更点を踏まえ、ハッシュコード衝突の頻度が低いものと高いもので比較すれば、性能の傾向は掴めそうです。 マイクロベンチにはjmhを使用しました。
可能であれば、オペレーション毎の実行時間を計測したかったのですが@Paramによるデータサイズ、キータイプの組み合わせと@OperationsPerInvocation(ops)に回数(データサイズ)を埋め込む事ができなかったので、後でExcelで計算する事にしました。

  • put測定
package jp.co.interprism;

import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

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

@State(Scope.Benchmark)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class HashMapPutBenchmark {

    @Param({"1", "10", "100", "1000", "10000"})
    public int repeat;

    @Param({"Equal", "Compare_Equal", "Hash_Compare_Equal"})
    public String keyType;

    private HashMap<Object, Object> map;

    private Object[] keys;

    @Setup(Level.Trial)
    public void setup() {
        KeyType keyGen = KeyType.valueOf(keyType);
        map = new HashMap<Object, Object>();
        keys = new Object[repeat];
        for (int i = 0; i < repeat; i++) {
            keys[i] = keyGen.createKey(i);
        }
    }

    private void repeatPut(int num) {
        for (int i = 0; i < num; i++) {
            map.put(keys[i], keys[i]);
        }
    }

    @GenerateMicroBenchmark
    public void repeatPut() {
        repeatPut(repeat);
    }

    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(".*" + HashMapPutBenchmark.class.getSimpleName() + ".*")
                .warmupIterations(5)
                .measurementIterations(5)
                .forks(1)
//                .jvmArgs("-Xbootclasspath/p:./lib/java7hashmap.jar")
                .build();

        new Runner(opt).run();
    }
}
  • get測定
package jp.co.interprism;

import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

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

@State(Scope.Benchmark)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class HashMapGetBenchmark {

    @Param({"1", "10", "100", "1000", "10000"})
    public int repeat;

    @Param({"Equal", "Compare_Equal", "Hash_Compare_Equal"})
    public String keyType;

    private HashMap<Object, Object> map;

    private Object[] keys;

    @Setup(Level.Trial)
    public void setup() {
        KeyType keyGen = KeyType.valueOf(keyType);
        map = new HashMap<Object, Object>();
        keys = new Object[repeat];
        for (int i = 0; i < repeat; i++) {
            keys[i] = keyGen.createKey(i);
            map.put(keys[i], keys[i]);
        }
    }

    private void repeatGet(int num) {
        for (int i = 0; i < num; i++) {
            map.get(keys[i]);
        }
    }

    @GenerateMicroBenchmark
    public void repeatGet() {
        repeatGet(repeat);
    }

    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(".*" + HashMapGetBenchmark.class.getSimpleName() + ".*")
                .warmupIterations(5)
                .measurementIterations(5)
                .forks(1)
//                .jvmArgs("-Xbootclasspath/p:./lib/java7hashmap.jar")
                .build();

        new Runner(opt).run();
    }
}
  • キーの種類
package jp.co.interprism;

public enum KeyType {

    Equal, Compare_Equal, Hash_Compare_Equal;

    public Object createKey(int num) {
        switch (this) {
            case Equal:
                return new EqualKey(num);
            case Compare_Equal:
                return new CompareEqualKey(num);
            case Hash_Compare_Equal:
                return new HashCompareEqualKey(num);
            default:
                throw new RuntimeException();
        }
    }
}
  • equalsのみ、ハッシュコードは0のみ、Comparable実装なし
package jp.co.interprism;

public class EqualKey {

    private int num;

    public EqualKey(int num) {
        this.num = num;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        EqualKey key = (EqualKey) o;
        if (num != key.num) return false;
        return true;
    }

    @Override
    public int hashCode() {
        return 0;
    }
}
  • equalsとComparable実装あり、ハッシュコードは0のみ
package jp.co.interprism;

public class CompareEqualKey implements Comparable<CompareEqualKey> {

    private int num;

    public CompareEqualKey(int num) {
        this.num = num;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        CompareEqualKey key = (CompareEqualKey) o;
        if (num != key.num) return false;
        return true;
    }

    @Override
    public int hashCode() {
        return 0;
    }

    @Override
    public int compareTo(CompareEqualKey o) {
        return Integer.compare(num, o.num);
    }
}
  • equals、ハッシュコード、Comparable実装あり
package jp.co.interprism;

public class HashCompareEqualKey implements Comparable<HashCompareEqualKey> {

    private int num;

    public HashCompareEqualKey(int num) {
        this.num = num;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        HashCompareEqualKey key = (HashCompareEqualKey) o;
        if (num != key.num) return false;
        return true;
    }

    @Override
    public int hashCode() {
        return num;
    }

    @Override
    public int compareTo(HashCompareEqualKey o) {
        return Integer.compare(num, o.num);
    }
}

計測

比較対象ですが、Java8によるVM変更の影響もあるため、Java8*1、Java8(HashMapのコードはJava7)、Java7*2としました。

Benchmark                                                                              Mode   Samples         Mean   Mean error    Units
j.c.i.HashMapPutBenchmark.repeatPut (keyType = Compare_Equal, repeat = 10000)          avgt         5  1335045.139    22330.197    ns/op
j.c.i.HashMapPutBenchmark.repeatPut (keyType = Compare_Equal, repeat = 1000)           avgt         5   101753.126     2922.196    ns/op
j.c.i.HashMapPutBenchmark.repeatPut (keyType = Compare_Equal, repeat = 100)            avgt         5     6371.614       50.721    ns/op
j.c.i.HashMapPutBenchmark.repeatPut (keyType = Compare_Equal, repeat = 10)             avgt         5      229.750        0.851    ns/op
j.c.i.HashMapPutBenchmark.repeatPut (keyType = Compare_Equal, repeat = 1)              avgt         5       11.955        0.238    ns/op
j.c.i.HashMapPutBenchmark.repeatPut (keyType = Equal, repeat = 10000)                  avgt         5 845502751.800  6230999.189    ns/op
j.c.i.HashMapPutBenchmark.repeatPut (keyType = Equal, repeat = 1000)                   avgt         5  5576370.786    39462.795    ns/op
j.c.i.HashMapPutBenchmark.repeatPut (keyType = Equal, repeat = 100)                    avgt         5    56658.763      505.806    ns/op
j.c.i.HashMapPutBenchmark.repeatPut (keyType = Equal, repeat = 10)                     avgt         5      223.430        0.390    ns/op
j.c.i.HashMapPutBenchmark.repeatPut (keyType = Equal, repeat = 1)                      avgt         5       11.939        0.534    ns/op
j.c.i.HashMapPutBenchmark.repeatPut (keyType = Hash_Compare_Equal, repeat = 10000)     avgt         5   114189.288     4365.030    ns/op
j.c.i.HashMapPutBenchmark.repeatPut (keyType = Hash_Compare_Equal, repeat = 1000)      avgt         5    12035.070       35.221    ns/op
j.c.i.HashMapPutBenchmark.repeatPut (keyType = Hash_Compare_Equal, repeat = 100)       avgt         5     1355.500        8.800    ns/op
j.c.i.HashMapPutBenchmark.repeatPut (keyType = Hash_Compare_Equal, repeat = 10)        avgt         5      134.578        2.889    ns/op
j.c.i.HashMapPutBenchmark.repeatPut (keyType = Hash_Compare_Equal, repeat = 1)         avgt         5       12.500        0.344    ns/op

一回の操作にかかる時間を表にしたものがこちらになります。

  • put
JVM HashMap key type 1 10 100 1000 10000
Java8 Java8 hash,compare,equal 12.5 13.5 13.6 12.0 11.4
Java8 Java8 compare,equal 12.0 23.0 63.7 101.8 133.5
Java8 Java8 equal 11.9 22.3 566.6 5576.4 84550.3
Java8 Java7 hash,compare,equal 9.6 9.2 9.3 9.2 9.5
Java8 Java7 compare,equal 9.4 23.6 163.9 1191.5 11756.8
Java8 Java7 equal 9.4 23.4 164.1 1154.5 12155.8
Java7 Java7 hash,compare,equal 9.3 8.8 9.4 9.3 13.2
Java7 Java7 compare,equal 9.3 22.9 137.8 1175.5 11871.8
Java7 Java7 equal 9.4 23.0 138.2 1173.9 11697.8

f:id:interprism:20140404004537p:plain

  • get
JVM HashMap key type 1 10 100 1000 10000
Java8 Java8 hash,compare,equal 7.3 6.9 6.7 6.7 6.9
Java8 Java8 compare,equal 7.3 29.2 61.3 89.9 104.8
Java8 Java8 equal 7.3 29.2 564.1 5890.6 79096.0
Java8 Java7 hash,compare,equal 8.8 8.5 8.2 8.9 7.7
Java8 Java7 compare,equal 8.8 30.7 258.9 2234.0 22581.1
Java8 Java7 equal 8.8 30.8 257.5 2232.8 22542.0
Java7 Java7 hash,compare,equal 8.3 8.0 8.1 8.0 7.8
Java7 Java7 compare,equal 8.2 20.2 127.1 1203.0 13011.9
Java7 Java7 equal 8.2 20.2 126.6 1208.4 13008.7

f:id:interprism:20140404004549p:plain

Java8ではequalのケースがJava7と比べ劣化*3していますが、compare,equalのケースで大きく改善しているのが分かります。
詳細は省略しますが、これはComparableを実装していると赤黒木を走査する際に同じハッシュコードのノードに到達しても、compareTo(T o)を使用して次に辿るべき二分木のノードを決定できるためです。
Comparableが未実装でハッシュコードが衝突する場合、追加にはSystem.identityHashCode(Object x)を使用して、二分木を作成しますが、これは実装上の都合で検索には使用できません。 検索はハッシュコードに対応するMap.Entryの赤黒木の全走査となり、これがequalのケースが遅い原因となります。

Java8のHashMapにおいて最悪ケースはJava7と同様にO(n)のままであり、むしろ赤黒木になったことにより走査のコストが増加していますが、Comparableを実装しているという条件に限定すればO(log n)となり、これは大幅な改善といえます。

おわりに

測定結果から

  • データが多い
  • ハッシュコードの衝突の頻度が高い
  • java.lang.Comparableを実装している

の条件を満たすのあれば大きく改善されると言えそうです。 注意点として、上記からComparable実装の条件を外したケースでは現状よりさらに劣化する可能性が高いです。

キーとなる不変クラスを作成する場合、equalsとhashcodeの実装を行うのは当然として、Comparableの実装までしているかというと当然とはいえなさそうで、そういった点から無条件にパフォーマンスが上がるとはいえません。 とはいえ仮に前述の理由で劣化したとしても、Comparableを実装してしまえば良く、総合的なパフォーマンスについてはJVM自体の改善もありますので、コード修正まで視野に入れるのであれば、見通しは明るそうです。

以上、皆様のJava8移行への検討材料になりましたら幸いです。

*1:1.8.0 Java HotSpot 64-Bit Server VM build 25.0-b70, mixed mode

*2:1.7.0_51 Java HotSpot 64-Bit Server VM build 24.51-b03, mixed mode

*3:サイズ10までの差異が少ないのはJava8でもキーが少ない間は単方向リストのためです。

PAGE TOP