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

Question

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

Political

Your sample size is way too low to be even remotely meaningful. For such "lightweight" operations, you should generally tr and sample for 5-10 seconds before calculating averages. – Gob

@Norwæ he is doing 60 runs with jmh which should be good enough and the statistical error is also given. – Aura

what java version and jmh version did you use? – Nicaragua

@Nicaragua jdk1.7.0_01 and JMH 1.0. I am not sure about the JHM version as i used maven archetype : mvn archetype:generate -DinteractiveMode=false -DarchetypeGroupId=org.openjdk.jmh -DarchetypeArtifactId=jmh-java-benchmark-archetype – Political

@Ram (I don't think it matters but JMH version is in your POM, it's the dependency jmh-core) And if I remember correctly, it's a property jmh.version defined in the <properties> section. – Cholla

Thanks @Tunaki! Got it! @Nicaragua it is JMH version is 1.0. <jmh.version>1.0</jmh.version> – Political

I tried to run your test and I got an even bigger difference (close to 50%). – Wail

I'm getting the same results with a slightly different approach - also it seems that get gets de-optimised after a few iterations. – Aura

One thing that definitely clutters the measurements is the access to the non-final fields, I made both key0 and hashMapVar public and final, and suddenly the difference is much smaller. – Wail

Answer 1

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.

Boustrophedon

But why inlining map creation is bad, if it is same for both methods? Just because it will not be inlined immediately, only after some warmup? – Nicaragua

Well, it's not bad per se, but I can envision the doomsday scenario where collection implementation is simple enough for compiler to fold a significant part of back-to-back put and get/remove. That's an extra level of protection -- in case you are very lazy in studying the generated code for each and every case. – Boustrophedon

Answer 2

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.

Allegra

performance analysis is not a place where you can talk about JIT optimization without any proofs – Nicaragua

The misunderstanding is about the Level.Iteration setup of the state. The correct level to use would be Invocation, except that doesn't really work here as the benchmark is too short. – Wail

@Nicaragua But the main thing is true, after the first invocation to remove() the map is empty. You don't even need JIT to make it faster, as the loop over the contents of a bucket will be skipped altogether. – Wail

@AdamSkywalker: True. gets -> might get. – Allegra

Well spotted - Changing the setup level to Level.Invocation makes remove slightly slower, as expected... Although the proper explanation is that when the remove method tests whether the map is empty, in which case it returns null. So the code path for empty map is shorter. (I don't think it has to do with null vs. non null reference). – Aura

@Wail this can tell why remove on empty map works faster than remove on full map, but in case of get/remove there's still hashing the key and lookup for it index. The actual thing where get is slower is checking the keys for equality - remove will terminate immediately because no entries will be found – Nicaragua

anyway, I'd like not to judge it without correct tests or clear algorithmic explanation – Nicaragua

@Nicaragua I wasn't arguing with your point, I just pointed out that while your specific objection is valid, the main thrust of the answer (i.e. the remove() test operates on an empty hashmap for all but the first invocations) is correct. – Wail