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

[Mike Duigou]

I have updated the webrev to remove the useAltHashing boolean.

http://cr.openjdk.java.net/~mduigou/JDK-8006593/5/webrev/

Mike


On Mar 5 2013, at 00:43 , Peter Levart wrote:

> 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/
>> 
>> 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
>>>>> 
>>>> 
>>> 
>> 
>