RFR: 8006593: Performance and compatibility improvements to hash based Map implementations (original) (raw)

Peter Levart peter.levart at gmail.com
Tue Mar 5 08:43:37 UTC 2013

• Previous message: RFR: 8006593: Performance and compatibility improvements to hash based Map implementations
• Next message: RFR: 8006593: Performance and compatibility improvements to hash based Map implementations
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

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

• Previous message: RFR: 8006593: Performance and compatibility improvements to hash based Map implementations
• Next message: RFR: 8006593: Performance and compatibility improvements to hash based Map implementations
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

More information about the core-libs-dev mailing list