Java Day 2018のセッション『Performance tuning with poor tools and cheap drink』に、「HashMapのキーとして、複数の文字列を連結(firstName + familyName)することより、複合キークラスを作成したほうがパフォーマンスがよい」というテクニックを紹介されたので、本当にそうであろうか検証してみました。

検証内容

検証は以下の内容で実施しました。

連結キーマップ：文字列と数値を連結した文字列をキーとする
複合キーマップ：文字列、数値をメンバー変数とした複合キークラスをキーとする
それぞれのマップに対し、putとgetをそれぞれ2,000,000回で実施し、トータル処理時間を計測
また、マップの作成として、初期容量、負荷係数ともデフォルト(容量の75%になる度にマップが拡張される)のパターンと初期容量が2,000,001で、負荷係数が1(マップの拡張を抑制)のパターンとそれぞれ計測

検討結果

以下は検証結果(単位：ms)となります。

複合キーのhashCodeをInteger.valueOf(index).hashCode()とした場合：
■連結キーマップ(初期容量、負荷係数ともデフォールト)
putComplexKeyMap execution time: 1060
getComplexKeyMap execution time: 312

■連結キーマップ(初期容量：2000001、負荷係数：1.0)
putComplexKeyMap execution time: 303
getComplexKeyMap execution time: 154

■複合キーマップ(初期容量、負荷係数ともデフォールト)
putCompositeKeyMap execution time: 256
複合キーマップキーのequalsメソッド呼び出す回数(put時): 0
key hashcode: 0 value: 0
key hashcode: 1 value: 1
getCompositeKeyMap execution time: 762
複合キーマップキーのequalsメソッド呼び出す回数(get時): 2000000

■複合キーマップ(初期容量：2000001、負荷係数：1.0)
putCompositeKeyMap execution time: 659
複合キーマップキーのequalsメソッド呼び出す回数(put時): 0
key hashcode: 0 value: 0
key hashcode: 1 value: 1
getCompositeKeyMap execution time: 198
複合キーマップキーのequalsメソッド呼び出す回数(get時): 2000000

初期容量、負荷係数ともデフォールトの場合のput処理は複合キーのほうが速かったが、それ以外は連結キーのほうが速いでした。(鵜呑みせずに自分で確かめることも大事ではなかろうか)

複合キーのhashCodeを(prefix + index).hashCode()とした場合：
■連結キーマップ(初期容量、負荷係数ともデフォールト)
putComplexKeyMap execution time: 1071
getComplexKeyMap execution time: 307

■連結キーマップ(初期容量：2000001、負荷係数：1.0)
putComplexKeyMap execution time: 313
getComplexKeyMap execution time: 183

■複合キーマップ(初期容量、負荷係数ともデフォールト)
putCompositeKeyMap execution time: 1483
複合キーマップキーのequalsメソッド呼び出す回数(put時): 0
key hashcode: 3055 value: 0
key hashcode: 3056 value: 1
getCompositeKeyMap execution time: 423
複合キーマップキーのequalsメソッド呼び出す回数(get時): 2000000

■複合キーマップ(初期容量：2000001、負荷係数：1.0)
putCompositeKeyMap execution time: 756
複合キーマップキーのequalsメソッド呼び出す回数(put時): 0
key hashcode: 3055 value: 0
key hashcode: 3056 value: 1
getCompositeKeyMap execution time: 577
複合キーマップキーのequalsメソッド呼び出す回数(get時): 2000000

put処理、get処理も連結キーのほうが速いでした。

複合キーのhashCodeをObjects.hash(prefix, index)とした場合：
■連結キーマップ(初期容量、負荷係数ともデフォールト)
putComplexKeyMap execution time: 1086
getComplexKeyMap execution time: 323

■連結キーマップ(初期容量：2000001、負荷係数：1.0)
putComplexKeyMap execution time: 283
getComplexKeyMap execution time: 182

■複合キーマップ(初期容量、負荷係数ともデフォールト)
putCompositeKeyMap execution time: 913
複合キーマップキーのequalsメソッド呼び出す回数(put時): 0
key hashcode: 3968 value: 0
key hashcode: 3969 value: 1
getCompositeKeyMap execution time: 401
複合キーマップキーのequalsメソッド呼び出す回数(get時): 2000000

■複合キーマップ(初期容量：2000001、負荷係数：1.0)
putCompositeKeyMap execution time: 441
複合キーマップキーのequalsメソッド呼び出す回数(put時): 0
key hashcode: 3968 value: 0
key hashcode: 3969 value: 1
getCompositeKeyMap execution time: 276
複合キーマップキーのequalsメソッド呼び出す回数(get時): 2000000

結果まちまちですが、それほど差が大きくなかった。
hashCode次第で性能への影響が大きいですね。

また、検証結果から以下のこともわかりました。

最初からマップの容量が分かれれば、マップの拡張を抑止することで大幅に性能アップ
複合キーを利用する場合、hashCode、equalsメソッドともに独自実装する必要があり、またその場合、equalsメソッドの呼び出す回数も多い
初期容量、負荷係数はマップの拡張には影響があるが、キーのequalsメソッド呼び出す回数には影響が軽微

検証プログラム

PerformanceHelper.java

package test.pfm;

import java.util.function.Consumer;

public final class PerformanceHelper {

    /**
     * 指定した回数で実行対象メソッドを実行し、総処理時間(ms)を返却。
     * @param times 実行回数
     * @param consumer 実行対象メソッド
     * @return 総処理時間
     */
    public static long getMethodExecutionTime(int times, Consumer<Integer> consumer) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < times; i++) {
            consumer.accept(i);
        }
        long end = System.currentTimeMillis();
        return end- start;
    }

    /**
     * 指定した回数で実行対象メソッドを実行し、総処理時間(ms)を出力する。
     * @param times 実行回数
     * @param consumer 実行対象メソッドを代理するConsumer
     * @param methodName 実行対象メソッド名またはガイドメッセージ
     * @return 総処理時間
     */
    public static void printMethodExecutionTime(int times, Consumer<Integer> consumer, String methodName) {
        System.out.println(methodName + " execution time: " + getMethodExecutionTime(times, consumer));
    }
}

MapPerformanceTest.java

package test.pfm;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class MapPerformanceTest {

    private static final int REPEAT_TIMES = 2000000;
    private static final float MAP_LOAD_FACTOR = 1;
    private static int compositeKeyEqualsInvokeCount;

    private static Map<String, String> complexKeyMap;
    private static Map<CompositeKey, String> compositeKeyMap;

    public static void main(String[] args) {
        System.out.println("■連結キーマップ(初期容量、負荷係数ともデフォールト)");
        complexKeyMap = new HashMap<>();
        PerformanceHelper.printMethodExecutionTime(REPEAT_TIMES, (index) -> putComplexKeyMap(index),
                "putComplexKeyMap");
        PerformanceHelper.printMethodExecutionTime(REPEAT_TIMES, MapPerformanceTest::getComplexKeyMap,
                "getComplexKeyMap");

        System.out.println("");
        System.out.println("■連結キーマップ(初期容量：" + (REPEAT_TIMES + 1) + "、負荷係数：" + MAP_LOAD_FACTOR + ")");
        complexKeyMap = new HashMap<>(REPEAT_TIMES + 1, MAP_LOAD_FACTOR);
        PerformanceHelper.printMethodExecutionTime(REPEAT_TIMES, (index) -> putComplexKeyMap(index),
                "putComplexKeyMap");
        PerformanceHelper.printMethodExecutionTime(REPEAT_TIMES, MapPerformanceTest::getComplexKeyMap,
                "getComplexKeyMap");

        System.out.println("");
        System.out.println("■複合キーマップ(初期容量、負荷係数ともデフォールト)");
        compositeKeyMap = new HashMap<>();
        PerformanceHelper.printMethodExecutionTime(REPEAT_TIMES, (index) -> putCompositeKeyMap(index),
                "putCompositeKeyMap");
        System.out.println("複合キーマップキーのequalsメソッド呼び出す回数(put時): " + compositeKeyEqualsInvokeCount);
        compositeKeyEqualsInvokeCount = 0;
        PerformanceHelper.printMethodExecutionTime(REPEAT_TIMES, MapPerformanceTest::getCompositeKeyMap,
                "getCompositeKeyMap");
        System.out.println("複合キーマップキーのequalsメソッド呼び出す回数(get時): " + compositeKeyEqualsInvokeCount);

        System.out.println("");
        System.out.println("■複合キーマップ(初期容量：" + (REPEAT_TIMES + 1) + "、負荷係数：" + MAP_LOAD_FACTOR + ")");
        compositeKeyEqualsInvokeCount = 0;
        compositeKeyMap = new HashMap<>(REPEAT_TIMES + 1, MAP_LOAD_FACTOR);
        PerformanceHelper.printMethodExecutionTime(REPEAT_TIMES, (index) -> putCompositeKeyMap(index),
                "putCompositeKeyMap");
        System.out.println("複合キーマップキーのequalsメソッド呼び出す回数(put時): " + compositeKeyEqualsInvokeCount);
        compositeKeyEqualsInvokeCount = 0;
        PerformanceHelper.printMethodExecutionTime(REPEAT_TIMES, MapPerformanceTest::getCompositeKeyMap,
                "getCompositeKeyMap");
        System.out.println("複合キーマップキーのequalsメソッド呼び出す回数(get時): " + compositeKeyEqualsInvokeCount);
    }

    private MapPerformanceTest(int mapCapacity) {
        compositeKeyMap = new HashMap<>(mapCapacity, 0.75f);
        compositeKeyEqualsInvokeCount = 0;
    }

    private static void putComplexKeyMap(int index) {
        complexKeyMap.put("a" + index, String.valueOf(index));
    }

    private static String getComplexKeyMap(int index) {
        return complexKeyMap.get("a" + index);
    }

    private static void putCompositeKeyMap(int index) {
        compositeKeyMap.put(new CompositeKey("a", index), String.valueOf(index));
    }

    private static String getCompositeKeyMap(int index) {
        CompositeKey key = new CompositeKey("a", index);
        String value = compositeKeyMap.get(key);
        if (index < 2) {
            System.out.println("key hashcode: " + key.hashCode() + " value: " + value);
        }
        return value;
    }

    private static class CompositeKey {
        private String prefix;

        private int index;

        CompositeKey(String prefix, int index) {
            this.prefix = prefix;
            this.index = index;
        }

        @Override
        public int hashCode() {
//            return Integer.valueOf(index).hashCode();
//            return (prefix + index).hashCode();
            return Objects.hash(prefix, index);
        }

        @Override
        public boolean equals(Object obj) {
            compositeKeyEqualsInvokeCount++;
            CompositeKey key = (CompositeKey) obj;
            if ((index == key.getIndex()) && prefix.equals(key.getPrefix())) {
                return true;
            }
            return false;
        }

        String getPrefix() {
            return prefix;
        }

        int getIndex() {
            return index;
        }

    }
}

おまけ

検証プログラムにはJavaの以下のテクニックを利用しました。まだ詳しくない方はご参考いただきたい。

アクセススコープ修飾子、finalキーワードの使い分け
メソッド参照
ObjectクラスのhashCode、equalsメソッドのオーバーライド
FunctionalInterfaceのConsumerの実装
ラムダ式

周@ソフトシンク