changeset 5827:b03bbdef3a88

8006593: Peformance and compatibility improvements to hash based Map implementations. Summary: Use ThreadLocalRandom for hash seed rather than shared Random. Initialize HashMap.hashSeed only as needed. Reviewed-by: alanb, bchristi, shade
author mduigou
date Mon, 11 Mar 2013 14:11:30 -0700
parents 1ea1197801d1
children b8009df64dc8
files src/share/classes/java/util/HashMap.java src/share/classes/java/util/Hashtable.java src/share/classes/sun/misc/Hashing.java
diffstat 3 files changed, 71 insertions(+), 128 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/util/HashMap.java	Mon Mar 11 22:27:18 2013 +0400
+++ b/src/share/classes/java/util/HashMap.java	Mon Mar 11 14:11:30 2013 -0700
@@ -192,17 +192,6 @@
      */
     private static class Holder {
 
-            // Unsafe mechanics
-        /**
-         * Unsafe utilities
-         */
-        static final sun.misc.Unsafe UNSAFE;
-
-        /**
-         * Offset of "final" hashSeed field we must set in readObject() method.
-         */
-        static final long HASHSEED_OFFSET;
-
         /**
          * Table capacity above which to switch to use alternative hashing.
          */
@@ -230,29 +219,17 @@
             } catch(IllegalArgumentException failed) {
                 throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
             }
+
             ALTERNATIVE_HASHING_THRESHOLD = threshold;
-
-            try {
-                UNSAFE = sun.misc.Unsafe.getUnsafe();
-                HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
-                    HashMap.class.getDeclaredField("hashSeed"));
-            } catch (NoSuchFieldException | SecurityException e) {
-                throw new Error("Failed to record hashSeed offset", e);
-            }
         }
     }
 
     /**
-     * If {@code true} then perform alternative hashing of String keys to reduce
-     * the incidence of collisions due to weak hash code calculation.
+     * A randomizing value associated with this instance that is applied to
+     * hash code of keys to make hash collisions harder to find. If 0 then
+     * alternative hashing is disabled.
      */
-    transient boolean useAltHashing;
-
-    /**
-     * A randomizing value associated with this instance that is applied to
-     * hash code of keys to make hash collisions harder to find.
-     */
-    transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
+    transient int hashSeed = 0;
 
     /**
      * Constructs an empty <tt>HashMap</tt> with the specified initial
@@ -274,15 +251,15 @@
                                                loadFactor);
 
         // Find a power of 2 >= initialCapacity
-        int capacity = 1;
-        while (capacity < initialCapacity)
-            capacity <<= 1;
+        int capacity = (capacity = Integer.highestOneBit(initialCapacity)) != 0
+                ? capacity
+                : 1;
+        capacity <<= (Integer.bitCount(initialCapacity) > 1) ? 1 : 0;
 
         this.loadFactor = loadFactor;
         threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
         table = new Entry[capacity];
-        useAltHashing = sun.misc.VM.isBooted() &&
-                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
+        initHashSeedAsNeeded(capacity);
         init();
     }
 
@@ -333,6 +310,23 @@
     }
 
     /**
+     * Initialize the hashing mask value. We defer initialization until we
+     * really need it.
+     */
+    final boolean initHashSeedAsNeeded(int capacity) {
+        boolean currentAltHashing = hashSeed != 0;
+        boolean useAltHashing = sun.misc.VM.isBooted() &&
+                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
+        boolean switching = currentAltHashing ^ useAltHashing;
+        if (switching) {
+            hashSeed = useAltHashing
+                ? sun.misc.Hashing.randomHashSeed(this)
+                : 0;
+        }
+        return switching;
+    }
+
+    /**
      * Retrieve object hash code and applies a supplemental hash function to the
      * result hash, which defends against poor quality hash functions.  This is
      * critical because HashMap uses power-of-two length hash tables, that
@@ -340,12 +334,9 @@
      * in lower bits. Note: Null keys always map to hash 0, thus index 0.
      */
     final int hash(Object k) {
-        int h = 0;
-        if (useAltHashing) {
-            if (k instanceof String) {
-                return sun.misc.Hashing.stringHash32((String) k);
-            }
-            h = hashSeed;
+        int h = hashSeed;
+        if (0 != h && k instanceof String) {
+            return sun.misc.Hashing.stringHash32((String) k);
         }
 
         h ^= k.hashCode();
@@ -557,11 +548,7 @@
         }
 
         Entry[] newTable = new Entry[newCapacity];
-        boolean oldAltHashing = useAltHashing;
-        useAltHashing |= sun.misc.VM.isBooted() &&
-                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
-        boolean rehash = oldAltHashing ^ useAltHashing;
-        transfer(newTable, rehash);
+        transfer(newTable, initHashSeedAsNeeded(newCapacity));
         table = newTable;
         threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
     }
@@ -815,8 +802,7 @@
         }
 
         public final int hashCode() {
-            return (key==null   ? 0 : key.hashCode()) ^
-                   (value==null ? 0 : value.hashCode());
+            return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
         }
 
         public final String toString() {
@@ -1117,10 +1103,6 @@
             throw new InvalidObjectException("Illegal load factor: " +
                                                loadFactor);
 
-        // set hashSeed (can only happen after VM boot)
-        Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
-                sun.misc.Hashing.randomHashSeed(this));
-
         // Read in number of buckets and allocate the bucket array;
         s.readInt(); // ignored
 
@@ -1136,16 +1118,15 @@
                 mappings * Math.min(1 / loadFactor, 4.0f),
                 // we have limits...
                 HashMap.MAXIMUM_CAPACITY);
-        int capacity = 1;
         // find smallest power of two which holds all mappings
-        while (capacity < initialCapacity) {
-            capacity <<= 1;
-        }
+        int capacity = (capacity = Integer.highestOneBit(initialCapacity)) != 0
+                ? capacity
+                : 1;
+        capacity <<= (Integer.bitCount(initialCapacity) > 1) ? 1 : 0;
 
         table = new Entry[capacity];
         threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
-        useAltHashing = sun.misc.VM.isBooted() &&
-                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
+        initHashSeedAsNeeded(capacity);
 
         init();  // Give subclass a chance to do its thing.
 
--- a/src/share/classes/java/util/Hashtable.java	Mon Mar 11 22:27:18 2013 +0400
+++ b/src/share/classes/java/util/Hashtable.java	Mon Mar 11 14:11:30 2013 -0700
@@ -213,54 +213,30 @@
     }
 
     /**
-     * If {@code true} then perform alternative hashing of String keys to reduce
-     * the incidence of collisions due to weak hash code calculation.
-     */
-    transient boolean useAltHashing;
-
-    // Unsafe mechanics
-    /**
-    * Unsafe utilities
-    */
-    private static final sun.misc.Unsafe UNSAFE;
-
-    /**
-    * Offset of "final" hashSeed field we must set in readObject() method.
-    */
-    private static final long HASHSEED_OFFSET;
-
-     static {
-        try {
-            UNSAFE = sun.misc.Unsafe.getUnsafe();
-            HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
-                Hashtable.class.getDeclaredField("hashSeed"));
-        } catch (NoSuchFieldException | SecurityException e) {
-            throw new Error("Failed to record hashSeed offset", e);
-        }
-     }
-
-    /**
      * A randomizing value associated with this instance that is applied to
      * hash code of keys to make hash collisions harder to find.
      */
-    transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
+    transient int hashSeed;
+
+    /**
+     * Initialize the hashing mask value.
+     */
+    final boolean initHashSeedAsNeeded(int capacity) {
+        boolean currentAltHashing = hashSeed != 0;
+        boolean useAltHashing = sun.misc.VM.isBooted() &&
+                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
+        boolean switching = currentAltHashing ^ useAltHashing;
+        if (switching) {
+            hashSeed = useAltHashing
+                ? sun.misc.Hashing.randomHashSeed(this)
+                : 0;
+        }
+        return switching;
+    }
 
     private int hash(Object k) {
-        if (useAltHashing) {
-            if (k.getClass() == String.class) {
-                return sun.misc.Hashing.stringHash32((String) k);
-            } else {
-                int h = hashSeed ^ k.hashCode();
-
-                // This function ensures that hashCodes that differ only by
-                // constant multiples at each bit position have a bounded
-                // number of collisions (approximately 8 at default load factor).
-                h ^= (h >>> 20) ^ (h >>> 12);
-                return h ^ (h >>> 7) ^ (h >>> 4);
-             }
-        } else  {
-            return k.hashCode();
-        }
+        // hashSeed will be zero if alternative hashing is disabled.
+        return hashSeed ^ k.hashCode();
     }
 
     /**
@@ -284,8 +260,7 @@
         this.loadFactor = loadFactor;
         table = new Entry[initialCapacity];
         threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
-        useAltHashing = sun.misc.VM.isBooted() &&
-                (initialCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
+        initHashSeedAsNeeded(initialCapacity);
     }
 
     /**
@@ -497,10 +472,7 @@
 
         modCount++;
         threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
-        boolean currentAltHashing = useAltHashing;
-        useAltHashing = sun.misc.VM.isBooted() &&
-                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
-        boolean rehash = currentAltHashing ^ useAltHashing;
+        boolean rehash = initHashSeedAsNeeded(newCapacity);
 
         table = newMap;
 
@@ -999,10 +971,6 @@
         // Read in the length, threshold, and loadfactor
         s.defaultReadObject();
 
-        // set hashSeed
-        UNSAFE.putIntVolatile(this, HASHSEED_OFFSET,
-                sun.misc.Hashing.randomHashSeed(this));
-
         // Read the original length of the array and number of elements
         int origlength = s.readInt();
         int elements = s.readInt();
@@ -1017,20 +985,19 @@
         if (origlength > 0 && length > origlength)
             length = origlength;
 
-        Entry<K,V>[] table = new Entry[length];
+        Entry<K,V>[] newTable = new Entry[length];
         threshold = (int) Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
         count = 0;
-        useAltHashing = sun.misc.VM.isBooted() &&
-                (length >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
+        initHashSeedAsNeeded(length);
 
         // Read the number of elements and then all the key/value objects
         for (; elements > 0; elements--) {
             K key = (K)s.readObject();
             V value = (V)s.readObject();
             // synch could be eliminated for performance
-            reconstitutionPut(table, key, value);
+            reconstitutionPut(newTable, key, value);
         }
-        this.table = table;
+        this.table = newTable;
     }
 
     /**
--- a/src/share/classes/sun/misc/Hashing.java	Mon Mar 11 22:27:18 2013 +0400
+++ b/src/share/classes/sun/misc/Hashing.java	Mon Mar 11 14:11:30 2013 -0700
@@ -24,7 +24,7 @@
  */
 package sun.misc;
 
-import java.util.Random;
+import java.util.concurrent.ThreadLocalRandom;
 
 /**
  * Hashing utilities.
@@ -213,18 +213,6 @@
     private static class Holder {
 
         /**
-         * Used for generating per-instance hash seeds.
-         *
-         * We try to improve upon the default seeding.
-         */
-        static final Random SEED_MAKER = new Random(
-                Double.doubleToRawLongBits(Math.random())
-                ^ System.identityHashCode(Hashing.class)
-                ^ System.currentTimeMillis()
-                ^ System.nanoTime()
-                ^ Runtime.getRuntime().freeMemory());
-
-        /**
          * Access to {@code String.hash32()}
          */
         static final JavaLangAccess LANG_ACCESS;
@@ -248,10 +236,17 @@
         return Holder.LANG_ACCESS.getStringHash32(string);
     }
 
+    /**
+     * Return a non-zero 32-bit pseudo random value. The {@code instance} object
+     * may be used as part of the value.
+     *
+     * @param instance an object to use if desired in choosing value.
+     * @return a non-zero 32-bit pseudo random value.
+     */
     public static int randomHashSeed(Object instance) {
         int seed;
         if (sun.misc.VM.isBooted()) {
-            seed = Holder.SEED_MAKER.nextInt();
+            seed = ThreadLocalRandom.current().nextInt();
         } else {
             // lower quality "random" seed value--still better than zero and not
             // not practically reversible.