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
Since HashMap stores its values in hash buckets, you can generally get between O(1) and O(N) for a lookup depending on the amount of hash collisions the map hash.
Performance The speed of HashSet is slower than that of HashMap. The reason that HashMap is faster than HashSet is that the HashMap uses the unique keys to access the values. It stores each value with a corresponding key and we can retrieve these values faster using keys during iteration.
According to a stackoverflow post, "HashMap uses an array underneath so it can never be faster than using an array correctly".
compared the two version, even i used the input which will reach the last of the "if else" statements, the "if else" version is still 4-5 times faster than hashmap (hashmap is initialized at the beginning and cached).
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With