Re: Optimize (Linked-)HashMap lookup when backing array is null

[Christoph Dreis]

Hi Claes,

On 2020-05-19 15:15, Christoph Dreis wrote:
>> Hi Claes,
>> 
>>> unlike CHM, HashMap and LinkedHashMap have constant-time size/isEmpty
>>>   accessors - could this be used to simplify your patch?
>> 
>> I was wondering about that during implementation, but simply took the path I 
>> already chose for the CHM.

> I think we should try to keep any changes here as simple as possible.

Please find an alternative solution attached that does isEmpty() checks for 
get() and containsKey() calls.

With the provided solution and the combined (empty & non-empty maps) 
benchmarks, I get the following results:

MyBenchmarkNew.test                    avgt   10   4,479 ±  0,061   ns/op
MyBenchmarkOld.test                      avgt   10   4,877 ±  0,054   ns/op

I should note that I see a slightly higher average timing with a filled map 
with the isEmpty() version:

MyBenchmarkNew.test                    avgt   10   5,465 ±  0,354   ns/op
MyBenchmarkOld.test                      avgt   10   5,315 ±  0,187   ns/op

Isolated benchmarks on just an empty map show the following results (for 
completeness reasons):

MyBenchmarkNew.test                      avgt   10   2,785 ±  0,191   ns/op
MyBenchmarkOld.test                        avgt   10   3,785 ±  0,436   ns/op

I can somewhat explain the higher average timing on a filled map with this 
solution:
It actually does "more" work by checking for the size, while the previous 
solution shifted only existing work to a place where it's actually needed.

I would probably go for the first version although it is a bit more complicated 
and has the computeIfPresent caveat, because it doesn't slow down the common 
Map.get() case when the map is actually filled.

Let me know what you think.

Cheers,
Christoph 


diff -r f143729ca00e src/java.base/share/classes/java/util/HashMap.java
--- a/src/java.base/share/classes/java/util/HashMap.java        Wed May 13 
16:18:16 2020 +0200
+++ b/src/java.base/share/classes/java/util/HashMap.java        Tue May 19 
19:36:12 2020 +0200
@@ -555,7 +555,7 @@
      */
     public V get(Object key) {
         Node<K,V> e;
-        return (e = getNode(hash(key), key)) == null ? null : e.value;
+        return isEmpty() || (e = getNode(hash(key), key)) == null ? null : 
e.value;
     }
 
     /**
@@ -594,7 +594,7 @@
      * key.
      */
     public boolean containsKey(Object key) {
-        return getNode(hash(key), key) != null;
+        return !isEmpty() && getNode(hash(key), key) != null;
     }
 
     /**
@@ -1141,7 +1141,7 @@
     @Override
     public V getOrDefault(Object key, V defaultValue) {
         Node<K,V> e;
-        return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
+        return isEmpty() || (e = getNode(hash(key), key)) == null ? 
defaultValue : e.value;
     }
 
     @Override
diff -r f143729ca00e src/java.base/share/classes/java/util/LinkedHashMap.java
--- a/src/java.base/share/classes/java/util/LinkedHashMap.java  Wed May 13 
16:18:16 2020 +0200
+++ b/src/java.base/share/classes/java/util/LinkedHashMap.java  Tue May 19 
19:36:12 2020 +0200
@@ -438,7 +438,7 @@
      */
     public V get(Object key) {
         Node<K,V> e;
-        if ((e = getNode(hash(key), key)) == null)
+        if (isEmpty() || (e = getNode(hash(key), key)) == null)
             return null;
         if (accessOrder)
             afterNodeAccess(e);
@@ -450,7 +450,7 @@
      */
     public V getOrDefault(Object key, V defaultValue) {
        Node<K,V> e;
-       if ((e = getNode(hash(key), key)) == null)
+       if (isEmpty() || (e = getNode(hash(key), key)) == null)
            return defaultValue;
        if (accessOrder)
            afterNodeAccess(e);