Re: HashMap collision speed (regression 7->8)

[Martin Buchholz]

Why not treeify only when trying to insert an element that is instanceof
Comparable?  That way, we will not attempt to use less efficient treebins
when there will be no benefit.

Something like:

diff --git a/src/java.base/share/classes/java/util/HashMap.java
b/src/java.base/share/classes/java/util/HashMap.java
--- a/src/java.base/share/classes/java/util/HashMap.java
+++ b/src/java.base/share/classes/java/util/HashMap.java
@@ -639,7 +639,8 @@
                 for (int binCount = 0; ; ++binCount) {
                     if ((e = p.next) == null) {
                         p.next = newNode(hash, key, value, null);
-                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for
1st
+                        if (binCount >= TREEIFY_THRESHOLD - 1 // -1 for 1st
+                            && key instanceof Comparable)
                             treeifyBin(tab, hash);
                         break;
                     }
@@ -1127,7 +1128,8 @@
             t.putTreeVal(this, tab, hash, key, v);
         else {
             tab[i] = newNode(hash, key, v, first);
-            if (binCount >= TREEIFY_THRESHOLD - 1)
+            if (binCount >= TREEIFY_THRESHOLD - 1
+                && key instanceof Comparable)
                 treeifyBin(tab, hash);
         }
         ++modCount;
@@ -1199,7 +1201,8 @@
                 t.putTreeVal(this, tab, hash, key, v);
             else {
                 tab[i] = newNode(hash, key, v, first);
-                if (binCount >= TREEIFY_THRESHOLD - 1)
+                if (binCount >= TREEIFY_THRESHOLD - 1
+                    && key instanceof Comparable)
                     treeifyBin(tab, hash);
             }
             ++modCount;
@@ -1258,7 +1261,8 @@
                 t.putTreeVal(this, tab, hash, key, value);
             else {
                 tab[i] = newNode(hash, key, value, first);
-                if (binCount >= TREEIFY_THRESHOLD - 1)
+                if (binCount >= TREEIFY_THRESHOLD - 1
+                    && key instanceof Comparable)
                     treeifyBin(tab, hash);
             }
             ++modCount;