Patch: IdentityHashMap - using null for empty-marker and introducing null-value-marker

[Martin Egholm Nielsen <martin at egholm-nielsen dot dk>]

Hi there,

For those having followed the discussion on the gcj-list, here is a 
patch that replaces the use of a dedicated java.lang.Object as marker 
for empty entries in the map. Instead null is used to indicate these 
empty entries, and a new java.lang.Object is used to represent any 
null-values instead.

And why?
Because the java.util.IdentityHashMap is used to store all the 
method-references (MethodRef in the 3.4 branch, don't know what they are 
named in 4.x) for all classes initialised (e.g. for stacktraces, etc. 
[Bryce]). And that's a bunch! And due to the nature of this hash-map - 
it is at most 1/2*3/4 = 37,5% filled. The rest will "usually" be filled 
with the dedicated Object instance that represents an empty entry.
Even worse, when just crossing the magic 37,5% boundary, the internal 
table doubles, and you end up with using only slightly more than ½*37,5% 
~= 19%. And consequently even more empty-markers are put in.

And each of these empty-markers will be marked and scanned by the 
garbage collector - this is where this patch is justified.
On my embedded target, this patch just saved me 30-40ms for each 
gc-cycle (roughly 20% of total)...

The idea is inspired by Bryce - I cannot take the credit.

BR,
 Martin Egholm

diff -Naur libjava-410/java/util/IdentityHashMap.java libjava/java/util/IdentityHashMap.java
--- libjava-410/java/util/IdentityHashMap.java	2006-04-01 22:05:31.720025600 +0200
+++ libjava/java/util/IdentityHashMap.java	2006-04-01 22:04:46.835484800 +0200
@@ -103,12 +103,20 @@
   static final Object tombstone = new Object();
 
   /**
-   * This object is used to mark empty slots.  We need this because
-   * using null is ambiguous. Package visible for use by nested classes.
+   * This object is used to mark empty slots. This is allowed to be null
+   * now that null-values are mapped into a similar representing object.
+   * Package visible for use by nested classes.
    */
-  static final Object emptyslot = new Object();
+  static final Object emptyslot = null;
 
   /**
+   * This object is used to represent a map-value of null, since null is
+   * being used as emptyslot-marker. Package visible for use by nested
+   * classes.
+   */
+  static final Object nullvalue = new Object();
+  
+  /**
    * Compatible with JDK 1.4.
    */
   private static final long serialVersionUID = 8188218128353913216L;
@@ -241,6 +249,12 @@
    */
   public boolean containsValue(Object value)
   {
+    // If we search for null, we should really be searching for our null-replacement:
+    if ( value == null )
+    {
+      value = nullvalue;
+    } // if
+    
     for (int i = table.length - 1; i > 0; i -= 2)
       if (table[i] == value)
         return true;
@@ -299,7 +313,13 @@
           if (! (o instanceof Map.Entry))
             return false;
           Map.Entry m = (Map.Entry) o;
-          return m.getValue() == table[hash(m.getKey()) + 1];
+          Object compareTo = table[hash(m.getKey()) + 1];
+          // If the value to expect is the null-representative, replace it before comparing:
+          if (compareTo == nullvalue )
+          {
+            compareTo = null;
+          } // if
+          return m.getValue() == compareTo;
         }
 
         public int hashCode()
@@ -361,7 +381,22 @@
   public Object get(Object key)
   {
     int h = hash(key);
-    return table[h] == key ? table[h + 1] : null;
+    if ( table[h] == key )
+    {
+      // If the value is the nullvalue, return null:
+      if ( table[h+1] == nullvalue )
+      {
+        return null;
+      } // if
+      else
+      {
+        return table[h+1];
+      } // else
+    } // if
+    else
+    {
+      return null;
+    } // else
   }
 
   /**
@@ -381,7 +416,7 @@
         if (key == emptyslot || key == tombstone)
           continue;
         hash += (System.identityHashCode(key)
-                 ^ System.identityHashCode(table[i + 1]));
+                 ^ System.identityHashCode(table[i + 1] == nullvalue ? null : table[i+1]));
       }
     return hash;
   }
@@ -509,8 +544,8 @@
     int h = hash(key);
     if (table[h] == key)
       {
-        Object r = table[h + 1];
-        table[h + 1] = value;
+        Object r = table[h + 1] == nullvalue ? null : table[h+1];
+        table[h + 1] = value == null ? nullvalue : value;
         return r;
       }
 
@@ -518,7 +553,7 @@
     modCount++;
     size++;
     table[h] = key;
-    table[h + 1] = value;
+    table[h + 1] = value == null ? nullvalue : value;
     return null;
   }
 
@@ -556,7 +591,7 @@
       {
         modCount++;
         size--;
-        Object r = table[h + 1];
+        Object r = table[h + 1] == nullvalue ? null : table[h + 1];
         table[h] = tombstone;
         table[h + 1] = tombstone;
         return r;
@@ -613,6 +648,12 @@
 
         public boolean remove(Object o)
         {
+          // If the value to remove is null, let's actually look for the representative:
+          if ( o == null )
+          {
+            o = nullvalue;
+          } // if
+          
           for (int i = table.length - 1; i > 0; i -= 2)
             if (table[i] == o)
               {
@@ -736,8 +777,18 @@
         }
       while (key == emptyslot || key == tombstone);
 
-      return type == KEYS ? key : (type == VALUES ? table[loc + 1]
-                                   : new IdentityEntry(loc));
+      if ( type == KEYS )
+      {
+        return key;
+      } // if
+      else if ( type == VALUES )
+      {
+        return table[loc + 1] == nullvalue ? null : table[loc + 1];
+      } // else if
+      else
+      {
+        return new IdentityEntry(loc);
+      } // else
     }
 
     /**
@@ -805,7 +856,8 @@
       if (! (o instanceof Map.Entry))
         return false;
       Map.Entry e = (Map.Entry) o;
-      return table[loc] == e.getKey() && table[loc + 1] == e.getValue();
+      return table[loc] == e.getKey() && 
+        ( table[loc + 1] == nullvalue ? null : table[loc + 1] ) == e.getValue();
     }
 
     /**
@@ -833,7 +885,7 @@
     {
       if (knownMod != modCount || table[loc] == tombstone)
         throw new ConcurrentModificationException();
-      return table[loc + 1];
+      return table[loc + 1] == nullvalue ? null : table[loc + 1];
     }
 
     /**
@@ -850,7 +902,7 @@
       if (knownMod != modCount || table[loc] == tombstone)
         throw new ConcurrentModificationException();
       return (System.identityHashCode(table[loc])
-              ^ System.identityHashCode(table[loc + 1]));
+              ^ System.identityHashCode(table[loc + 1] == nullvalue ? null : table[loc + 1]));
     }
 
     /**
@@ -865,8 +917,8 @@
     {
       if (knownMod != modCount || table[loc] == tombstone)
         throw new ConcurrentModificationException();
-      Object r = table[loc + 1];
-      table[loc + 1] = value;
+      Object r = table[loc + 1] == nullvalue ? null : table[loc + 1];
+      table[loc + 1] = value == null ? nullvalue : value;
       return r;
     }
 
@@ -882,7 +934,7 @@
     {
       if (knownMod != modCount || table[loc] == tombstone)
         throw new ConcurrentModificationException();
-      return table[loc] + "=" + table[loc + 1];
+      return table[loc] + "=" + ( table[loc + 1] == nullvalue ? null : table[loc + 1] );
     }
   } // class IdentityEntry
 
@@ -928,7 +980,7 @@
         if (key != tombstone && key != emptyslot)
           {
             s.writeObject(key);
-            s.writeObject(table[i + 1]);
+            s.writeObject(table[i + 1] == nullvalue ? null : table[i + 1]);
           }
       }
   }