CODEWITHSUNDEEP
javaperformancehashmapbenchmarkingjmh
RamValli
RamValli

Reputation: 4485

Is remove() faster than get() in HashMap?

I have written a benchmark for get and remove of HashMap as below:

@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));
  }
}

It produces this result:

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

As per the result, remove() is slight faster than get(). Even to remove an element, first it has to retrieve the element, doesn't it?

How can remove() be faster? Or am I missing something?

Update After using the latest JMH (1.11.3) and here is the result:

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

Upvotes: 13

Views: 2891

Answers (2)

Aleksey Shipilev
Aleksey Shipilev

Reputation: 18847

So the trouble is, these benchmarks measure different things: get() from a populated map, and remove() from an (eventually) empty map. The comparison is meaningless, and you may throw the benchmark away.

You have to guarantee the operation is done against the same HashMap. Unfortunately, that requires either using @Setup(Invocation), which is bad on its own (read the Javadoc!), or sucking up the HashMap construction costs into the benchmark itself:

@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;
    }
}

You can be extra-careful and peel the map creation into a separate non-inlineable method: today's compilers do not optimize across calls. On my i7-4790K, 4.0 GHz, 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

No drastic difference. In fact, if you look into the generated code with -prof perfasm, it would yield a few quantifiable differences in there. Or, you can quickly characterize both workloads with -prof perfnorm.

Note that this case does not answer whether one method or the other better on real maps. The argument could be made for both: get does not modify map, and therefore does not cause memory stores, remove may help load factors so that next remove would get faster, etc. A single benchmark and a paragraph of text is far, far away from any fruitful discussion.

Upvotes: 23

JiriS
JiriS

Reputation: 7540

When you call remove() after the first iteration there is nothing to remove and you don't have to copy the result (or rather reference to the result) anywhere (it's just simply returning null). But when calling get() you have to copy or store returned reference somewhere (Haven't looked up implementation of Blackhole) which requires memory allocation and therefore is more expensive than just simply returning null which might get optimized by JIT after a few iterations.

Upvotes: 7

Related Questions