Является ли remove() быстрее, чем get() в HashMap?

Я написал тест для get и remove of HashMap, как показано ниже:

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class HashMapBenchmark {

  @State(Scope.Benchmark)
  public static class Mystate {
      HashMap<String,String> hashmapVar = new HashMap<String,String>();
      String key0 = "bye";

      @Setup(Level.Iteration)
      public void setup(){
          hashmapVar.put(key0,"bubye");
      }
  }

  @Benchmark
  public void hashmapGet(Mystate state ,Blackhole bh) {
      bh.consume(state.hashmapVar.get(state.key0));
  }

  @Benchmark
  public void hashmapRemove(Mystate state ,Blackhole bh) {
      bh.consume(state.hashmapVar.remove(state.key0));
  }
}

Он производит результат, как показано ниже:

Benchmark                             Mode  Samples  Score  Score error  Units
c.b.HashMapBenchmark.hashmapGet       avgt       60  6.348        0.320  ns/op
c.b.HashMapBenchmark.hashmapRemove    avgt       60  5.180        0.074  ns/op

В соответствии с результатом remove() немного быстрее, чем get(). Даже для удаления элемента сначала нужно извлечь элемент, не так ли?

Тогда как получилось remove() быстрее? Или я что-то упускаю?

Обновление После использования последнего JMH (1.11.3) и вот результат:

Benchmark                                 Mode  Cnt  Score   Error  Units
HashMapBenchmark.hashmapGet               avgt   60  9.713 ± 0.277  ns/op
HashMapBenchmark.hashmapRemove            avgt   60  7.677 ± 0.166  ns/op

Ответ 1

Итак, проблема в том, что эти тесты измеряют разные вещи: get() из населенной карты и remove() из (в конечном счете) пустой карты. Сравнение бессмысленно, и вы можете выбросить отметку.

Вы должны гарантировать, что операция выполняется против того же HashMap. К сожалению, это требует либо использования @Setup(Invocation), что само по себе плохо (прочитайте Javadoc!), Либо вложите затраты на строительство HashMap в сам тест:

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class HashMapBenchmark {

    @Benchmark
    public String get() {
        HashMap<String, String> hm = createMap();
        return hm.get("bye");
    }

    @Benchmark
    public String remove() {
        HashMap<String, String> hm = createMap();
        return hm.remove("bye");
    }

    // extra protection from optimization
    @CompilerControl(CompilerControl.Mode.DONT_INLINE)
    private HashMap<String, String> createMap() {
        HashMap<String, String> hm = new HashMap<>();
        hm.put("bye", "bye");
        return hm;
    }
}

Вы можете быть чрезмерно осторожными и очистить создание карты от отдельного не-встроенного метода: сегодня компиляторы не оптимизируют между вызовами. На моем i7-4790K, 4.0 ГГц, Linux x86_64, JDK 8u66:

Benchmark                Mode  Cnt   Score   Error  Units
HashMapBenchmark.get     avgt   15  24.343 ± 0.351  ns/op
HashMapBenchmark.remove  avgt   15  24.611 ± 0.369  ns/op

Никакой радикальной разницы. Фактически, если вы посмотрите на сгенерированный код с -prof perfasm, это даст несколько количественных различий в нем. Или вы можете быстро охарактеризовать обе рабочие нагрузки с помощью -prof perfnorm.

Обратите внимание, что этот случай не отвечает, лучше ли один метод или другой на реальных картах. Аргумент может быть сделан для обоих: get не изменяет карту и, следовательно, не создает хранилища памяти, remove может помочь загрузить факторы, чтобы следующий remove стал быстрее и т.д. Единый контрольный показатель и параграф текст далеко, далеко от любой плодотворной дискуссии.

Ответ 2

Когда вы вызываете remove() после первой итерации, ничего не удалять, и вам не нужно копировать результат (или, вернее, ссылку на результат) в любом месте (он просто возвращает null). Но при вызове get() вам нужно скопировать или сохранить возвращенную ссылку где-нибудь (не искали реализацию Blackhole), которая требует выделения памяти и, следовательно, дороже, чем просто возврат null, который может быть оптимизирован JIT после несколько итераций.