RFR: 8006593: Performance and compatibility improvements to hash based Map implementations

[Peter Levart]

Hi Mike,

You could also get rid of boolean useAltHashing field in both HashMap 
and Hashtable. It saves 8 bytes in both HM and HT objects in 32bit 
addressing modes (64bit addressing modes are not affected due to 
different alignment). Like the following (a patch against your webrev):

Index: jdk/src/share/classes/java/util/Hashtable.java
===================================================================
--- jdk/src/share/classes/java/util/Hashtable.java (date 1362469665000)
+++ jdk/src/share/classes/java/util/Hashtable.java (revision )
@@ -213,12 +213,6 @@
      }

      /**
-     * 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 = false;
-
-    /**
       * A randomizing value associated with this instance that is 
applied to
       * hash code of keys to make hash collisions harder to find.
       */
@@ -228,8 +222,8 @@
       * Initialize the hashing mask value.
       */
      final boolean initHashSeedAsNeeded(int capacity) {
-        boolean currentAltHashing = useAltHashing;
-        useAltHashing = sun.misc.VM.isBooted() &&
+        boolean currentAltHashing = hashSeed != 0;
+        boolean useAltHashing = sun.misc.VM.isBooted() &&
                  (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
          boolean switching = currentAltHashing ^ useAltHashing;
          if (switching) {
Index: jdk/src/share/classes/java/util/HashMap.java
===================================================================
--- jdk/src/share/classes/java/util/HashMap.java    (date 1362472425000)
+++ jdk/src/share/classes/java/util/HashMap.java (revision )
@@ -224,17 +224,11 @@
      }

      /**
-     * 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 = false;
-
-    /**
       * A randomizing value associated with this instance that is 
applied to
-     * hash code of keys to make hash collisions harder to find. 
Initialized via
-     * sun.misc.Unsafe when needed.
+     * hash code of keys to make hash collisions harder to find.
+     * Also used (when != 0) to indicate use of alternative String hashing.
       */
-    transient int hashSeed = 0;
+    transient int hashSeed;

      /**
       * Constructs an empty <tt>HashMap</tt> with the specified initial
@@ -319,8 +313,8 @@
       * really need it.
       */
      final boolean initHashSeedAsNeeded(int capacity) {
-        boolean currentAltHashing = useAltHashing;
-        useAltHashing = sun.misc.VM.isBooted() &&
+        boolean currentAltHashing = hashSeed != 0;
+        boolean useAltHashing = sun.misc.VM.isBooted() &&
                  (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
          boolean switching = currentAltHashing ^ useAltHashing;
          if (switching) {
@@ -339,12 +333,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) {
+        int h = hashSeed;
+        if (h != 0 && k instanceof String) {
-                return sun.misc.Hashing.stringHash32((String) k);
+            return sun.misc.Hashing.stringHash32((String) k);
-            }
-            h = hashSeed;
          }

          h ^= k.hashCode();


Regards, Peter

On 03/05/2013 07:08 AM, Mike Duigou wrote:
> After looking more closely at the single read reference to hashSeed I 
> decided to simplify things and make hashSeed non-final in both 
> Hashtable and HashMap.
>
> I've posted a refreshed webrev.
>
> http://cr.openjdk.java.net/~mduigou/JDK-8006593/4/webrev/ 
> <http://cr.openjdk.java.net/%7Emduigou/JDK-8006593/4/webrev/>
>
> Mike
>
> On Mar 4 2013, at 14:25 , Peter Levart wrote:
>
>>
>> On 03/04/2013 11:14 PM, Peter Levart wrote:
>>> Hi mike,
>>>
>>> I doubt (haven't tried it really with your code) that hashSeed will 
>>> be seen by code to be anything else but 0, since it is initialized 
>>> to a constant value. For example, this code:
>>>
>>> public class ModifyingFinalTest {
>>>     static final Unsafe unsafe;
>>>     static final long valueOffset;
>>>
>>>     static {
>>>         try {
>>>             Field f = Unsafe.class.getDeclaredField("theUnsafe");
>>>             f.setAccessible(true);
>>>             unsafe = (Unsafe)f.get(null);
>>>             valueOffset = 
>>> unsafe.objectFieldOffset(ModifyingFinalTest.class.getDeclaredField("value"));
>>>         }
>>>         catch (IllegalAccessException | NoSuchFieldException e) {
>>>             throw new Error(e);
>>>         }
>>>     }
>>>
>>>     final int value = 0;
>>>
>>>     void test() {
>>>         unsafe.putIntVolatile(this, valueOffset, 1);
>>>         printValue();
>>>         unsafe.putIntVolatile(this, valueOffset, 2);
>>>         printValue();
>>>         unsafe.putIntVolatile(this, valueOffset, 3);
>>>         printValue();
>>>     }
>>>
>>>     void printValue() {
>>>         System.out.println(value);
>>>     }
>>>
>>>     public static void main(String[] args) {
>>>         new ModifyingFinalTest().test();
>>>     }
>>> }
>>>
>>>
>>> Prints:
>>>
>>> 0
>>> 0
>>> 0
>>>
>>>
>>> It's a different thing, if the initialization is changed to:
>>>
>>> final int value = "".length();
>>>
>>> But I don't know if each access in source is actually guaranteed to 
>>> translate to a real read of field in this case either. Is 
>>> Unsafe.putIntVolatile() making this happen somehow magically?
>>
>> Well, that's not what I wanted to ask. I wanted to ask if the first 
>> access in source that happens after Unsafe.putIntVolatile() in same 
>> thread is guaranteed to read the field and not re-use a cached value 
>> ready in some register for example. Is Unsafe.putIntVolatile() making 
>> this happen somehow magically?
>>
>>>
>>> Regards, Peter
>>>
>>>
>>> On 03/04/2013 09:21 PM, Mike Duigou wrote:
>>>> Hello all;
>>>>
>>>> The alternative hashing implementation introduced in 7u6 added an unfortunate bottleneck to the initialization of HashMap and Hashtable instances. This patch avoids the performance bottleneck of using a shared Random instance by using a ThreadLocalRandom instead.
>>>>
>>>> Along with this change are some additional performance improvements to further reduce the overhead of the alternative hashing feature and generally improve the performance of Hashtable or HashMap.
>>>>
>>>> c
>>>>
>>>> Once review is completed here this patch will be proposed to JDK7u-dev for integration into the next 7u performance/feature release.
>>>>
>>>> Mike
>>>>
>>>
>>
>