Почему производительность вызовов get () в HashMaps 10 не в 10 раз хуже, чем производительность get () - PullRequest
Новая
       33

Почему производительность вызовов get () в HashMaps 10 не в 10 раз хуже, чем производительность get ()

2 голосов
/ 02 декабря 2019

У меня есть поле hashmap с 100_000 записями и двумя методами A и B.

  • Метод A : вызовы map.get() один разсо случайным ключом
  • Метод B : Вызов map.get() десять раз с a случайным ключом (один и тот же ключ каждый раз)

Я настроил эти два метода с помощью JMH для многократного запуска (весь тест занял более 1 часа на моем MacBook Pro) и измерения производительности, и получается, что Метод A всего лишь в два раза быстрее, чем Метод B . Я надеялся на 10-кратную разницу.

Я не смог объяснить это поведение, вот результаты 

# Run complete. Total time: 01:08:36

Benchmark                           Mode  Throughput           Units
TestClass.benchmark_with_one_get   thrpt   23819.007   operations/ms
TestClass.benchmark_with_ten_gets  thrpt   12021.025   operations/ms

Затем я хотел поэкспериментировать больше, я отверг метод hashCode() из hashmap * 1032Клавиша * s (TestKey) с константной функцией (всегда возвращает целое число 5), чтобы по существу сделать хэш-карту списком. Только тогда я мог видеть ожидаемые результаты. Я не запускал весь тест, так как для его завершения требуется более 6 часов, но вот приблизительные результаты (только из первых двух итераций) 

Benchmark                           Mode   Throughput             Units
TestClass.benchmark_with_one_get   thrpt      244.266      operations/s
TestClass.benchmark_with_ten_gets  thrpt       24.981      operations/s

А вот исходный класс, который я использовал для оценки производительности. 

package test.benchmark;

import org.openjdk.jmh.annotations.*;

import java.util.*;
import java.util.concurrent.TimeUnit;

@State(Scope.Benchmark)
public class TestClass {

    private Map<TestKey, Integer> map = new HashMap<>();
    private List<TestKey> keyList = new ArrayList<>();
    private int test1 = 0;
    private int test2 = 0;

    public TestClass() {
        Random random = new Random();
        for (int i = 0; i < 100_000; i++) {
            TestKey testKey = new TestKey(i);
            map.put(testKey, i);
            keyList.add(new TestKey(random.nextInt(100_001)));
        }
    }

    @Setup
    public void setup() {
        Random random = new Random();
        int tmp = random.nextInt(100_001);
        test1 = tmp;
        test2 = tmp;
    }

    @Benchmark
    @BenchmarkMode(Mode.Throughput)
    @Measurement(iterations = 20, time = 10)
    @OutputTimeUnit(TimeUnit.MILLISECONDS)
    @Warmup(iterations = 5)
    public boolean benchmark_with_one_get() {

        TestKey testKey = keyList.get(test1);
        map.get(testKey);
        test1++;
        if (test1 >= 100_000) {
            test1 = 0;
        }
        return true;
    }

    @Benchmark
    @OutputTimeUnit(TimeUnit.MILLISECONDS)
    @Measurement(iterations = 20, time = 10)
    @BenchmarkMode(Mode.Throughput)
    @Warmup(iterations = 5)
    public boolean benchmark_with_ten_gets() {

        TestKey testKey = keyList.get(test2);
        map.get(testKey);
        map.get(testKey);
        map.get(testKey);
        map.get(testKey);
        map.get(testKey);
        map.get(testKey);
        map.get(testKey);
        map.get(testKey);
        map.get(testKey);
        map.get(testKey);
        test2++;
        if (test2 >= 100_000) {
            test2 = 0;
        }

        return true;
    }


    public class TestKey {
        private int key;

        public TestKey(int key) {
            this.key = key;
        }

        public int getKey() {
            return key;
        }

        @Override
        public boolean equals(Object obj) {
            return obj instanceof TestKey && ((TestKey) obj).key == this.key;
        }

        @Override
        public int hashCode() {
            return 31 * 17 + key;
        }

    }
}

Любые идеи, объяснения приветствуются. спасибо

...