Сравнительный анализ Java HashMap Get (JMH vs Looping)
Моя конечная цель - создать полный набор тестов для нескольких библиотек примитивных коллекций Java, используя стандартные коллекции Java в качестве основы. В прошлом я использовал циклический метод написания таких микро-тестов. Я поместил функцию, которую я тестирую, в цикл и итерацию более миллиона раз, чтобы у jit была возможность прогреться. Я беру общее время цикла, а затем делю на количество итераций, чтобы получить оценку количества времени, которое потребовалось бы для одного вызова функции, которую я сравниваю. После недавнего прочтения о проекте JMH и, в частности, этого примера: JMHSample_11_Loops я вижу проблему с этим подходом.
Моя машина:
Windows 7 64-bit
Core i7-2760QM @ 2.40 GHz
8.00 GB Ram
jdk1.7.0_45 64-bit
Вот упрощенный пример кода метода цикла, описанного выше:
public static void main(String[] args) {
HashMap<Long, Long> hmap = new HashMap<Long, Long>();
long val = 0;
//populating the hashmap
for (long idx = 0; idx < 10000000; idx++) {
hmap.put(idx, idx);
}
Stopwatch s = Stopwatch.createStarted();
long x = 0;
for (long idx = 0; idx < 10000000; idx++) {
x = hmap.get(idx);
}
s.stop();
System.out.println(s); //5.522 s
System.out.println(x); //9999999
//5.522 seconds / 10000000 = 552.2 nanoseconds
}
Вот моя попытка переписать этот тест с использованием JMH:
package com.test.benchmarks;
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.Thread)
public class MyBenchmark {
private HashMap<Long, Long> hmap = new HashMap<Long, Long>();
private long key;
@Setup(Level.Iteration)
public void setup(){
key = 0;
for(long i = 0; i < 10000000; i++) {
hmap.put(i, i);
}
}
@Benchmark
@BenchmarkMode(Mode.SampleTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public long testGetExistingKey() throws InterruptedException{
if(key >= 10000000) key=0;
return hmap.get(key++);
}
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(".*" + MyBenchmark.class.getSimpleName() + ".*")
.warmupIterations(5)
.measurementIterations(25)
.forks(1)
.build();
new Runner(opt).run();
}
}
Вот результаты:
Result: 31.163 ±(99.9%) 11.732 ns/op [Average]
Statistics: (min, avg, max) = (0.000, 31.163, 939008.000), stdev = 1831.428
Confidence interval (99.9%): [19.431, 42.895]
Samples, N = 263849
mean = 31.163 ±(99.9%) 11.732 ns/op
min = 0.000 ns/op
p( 0.0000) = 0.000 ns/op
p(50.0000) = 0.000 ns/op
p(90.0000) = 0.000 ns/op
p(95.0000) = 427.000 ns/op
p(99.0000) = 428.000 ns/op
p(99.9000) = 428.000 ns/op
p(99.9900) = 856.000 ns/op
p(99.9990) = 9198.716 ns/op
p(99.9999) = 939008.000 ns/op
max = 939008.000 ns/op
# Run complete. Total time: 00:02:07
Benchmark Mode Samples Score Score error Units
c.t.b.MyBenchmark.testGetExistingKey sample 263849 31.163 11.732 ns/op
Насколько я могу судить, тот же эталонный тест в JMH имеет хэш-карту, полученную в 31 наносекунде против 552 наносекунды для циклического теста. 31 наносекунда кажется мне слишком быстрой. Глядя на числа задержки, каждый программист должен знать, что ссылка на основную память составляет около 100 наносекунд. Ссылка на кэш L2 составляет примерно 7 наносекунд, но HashMap с 10 миллионами длинных ключей и значений значительно превышает L2. Также результаты JMH выглядят странно для меня. 90% входящих вызовов занимают 0,0 наносекунд?
Я предполагаю, что это ошибка пользователя. Любая помощь / указатели будут оценены. Благодарю.
ОБНОВИТЬ
Вот результаты выполнения AverageTime запустить. Это намного больше соответствует моим ожиданиям. Спасибо @oleg-estekhin! В комментариях ниже я упомянул, что я сделал AverageTime тестировать ранее и имел аналогичные результаты, как SampleTime, Я полагаю, что при выполнении этого прогона я использовал HashMap с гораздо меньшим количеством записей, и что более быстрый поиск имел смысл.
Result: 266.306 ±(99.9%) 139.359 ns/op [Average]
Statistics: (min, avg, max) = (27.266, 266.306, 1917.271), stdev = 410.904
Confidence interval (99.9%): [126.947, 405.665]
# Run complete. Total time: 00:07:17
Benchmark Mode Samples Score Score error Units
c.t.b.MyBenchmark.testGetExistingKey avgt 100 266.306 139.359 ns/op
1 ответ
Во-первых, циклический тест измеряет среднее время, в то время как ваш код JMH настроен на время выборки. От Mode.SampleTime Javadoc:
Время выборки: выборка времени для каждой операции.
Индивидуальные казни Map.get() довольно быстрые до того момента, когда базовая система измерения времени сообщит 0 для некоторых из выполнений из-за детализации измерения времени (для получения дополнительной информации прочитайте Nanotrusting сообщение в блоге Nanotime автора JMH).
В режиме выборки тесты собирают отдельные значения времени выборки в массив, а затем вычисляют средние значения и процентили, используя этот массив. Когда более половины значений массива равны нулю (в вашей конкретной установке более 90% значений массива равны нулю, как указано p(90.0000) = 0.000 ns/op) среднее значение должно быть довольно низким, но когда вы видите p(50) = 0 (и особенно p(90) = 0) в своем выводе единственный вывод, который вы можете сделать достоверно, заключается в том, что эти результаты являются мусором, и вам нужно найти другой способ измерения этого кода.
Вы должны использовать
Mode.AverageTime(или жеMode.Throughput) режим бенчмарка. ПокидатьMode.SampleTimeдля ситуаций, когда индивидуальный вызов занимает значительное время.Вы можете добавить "базовый" тест, который выполняет
if ()а такжеkey++чтобы выделить время, необходимое дляkeyбухгалтерия и фактическаяMap.get()время, но вам нужно будет объяснить результаты (в сообщении блога, указанном выше, описываются подводные камни с вычитанием "базовых показателей" из "реальных" измерений).Вы можете попробовать использовать
Blackhole.consumeCPU()увеличить время выполнения отдельного вызова (см. предыдущий пункт о "базовых показателях" и связанных с этим подводных камнях).