こんにちは、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 |
- 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 |
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移行への検討材料になりましたら幸いです。
