harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Tim Ellison <t.p.elli...@gmail.com>
Subject [classlib][luni] FYI hashmap optimization
Date Fri, 14 Sep 2007 13:07:42 GMT
FYI I just committed an optimization to HashMap that treats Integer keys
as a special case, and showed a worthwhile improvement on SPECjbb by
reducing CPU cache misses.

The optimization may not be obvious so I wrote it up on the wiki here:
  http://wiki.apache.org/harmony/HashMapHack

Any questions please ask away.

Regards,
Tim

tellison@apache.org wrote:
> Author: tellison
> Date: Fri Sep 14 05:35:16 2007
> New Revision: 575658
> 
> URL: http://svn.apache.org/viewvc?rev=575658&view=rev
> Log:
> Optimization for Integer keys in HashMap.
> 
> Modified:
>     harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/HashMap.java
> 
> Modified: harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/HashMap.java
> URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/HashMap.java?rev=575658&r1=575657&r2=575658&view=diff
> ==============================================================================
> --- harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/HashMap.java
(original)
> +++ harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/HashMap.java
Fri Sep 14 05:35:16 2007
> @@ -43,18 +43,28 @@
>      private static final int DEFAULT_SIZE = 16;
>  
>      static class Entry<K, V> extends MapEntry<K, V> {
> -        final int origKeyHash;
> +        final int storedKeyHash;
>  
>          Entry<K, V> next;
>  
>          Entry(K theKey, int hash) {
>              super(theKey, null);
> -            this.origKeyHash = hash;
> +            if (theKey instanceof Integer) {
> +                this.storedKeyHash = hash | 0x00000001;
> +            } else {
> +                this.storedKeyHash = hash & 0xFFFFFFFE;
> +            }
>          }
>  
>          Entry(K theKey, V theValue) {
>              super(theKey, theValue);
> -            origKeyHash = (theKey == null ? 0 : theKey.hashCode());
> +            if (theKey == null) {
> +                storedKeyHash = 0;
> +            } else if (theKey instanceof Integer) {
> +                storedKeyHash = theKey.hashCode() | 0x00000001;
> +            } else {
> +                storedKeyHash = theKey.hashCode() & 0xFFFFFFFE;
> +            }
>          }
>  
>          @Override
> @@ -251,13 +261,16 @@
>      }
>      
>      private static final int calculateCapacity(int x) {
> -        if(x >= 1 << 30){
> +        if (x >= 1 << 30) {
>              return 1 << 30;
>          }
> -        if(x == 0){
> +        if (x == 0) {
>              return 16;
>          }
> -        x = x -1;
> +        if (x == 1) {
> +            return 2;
> +        }
> +        x = x - 1;
>          x |= x >> 1;
>          x |= x >> 2;
>          x |= x >> 4;
> @@ -445,16 +458,25 @@
>  
>      final Entry<K,V> findNonNullKeyEntry(Object key, int index, int keyHash) {
>          Entry<K,V> m = elementData[index];
> -        while (m != null && (m.origKeyHash != keyHash || !key.equals(m.key)))
{
> -            m = m.next;
> +        if (key instanceof Integer) {
> +            int storedKeyHash = keyHash | 0x00000001;
> +            while (m != null && (m.storedKeyHash != storedKeyHash)) {
> +                m = m.next;
> +            }
> +        } else {
> +            int storedKeyHash = keyHash & 0xFFFFFFFE;
> +            while (m != null && (m.storedKeyHash != storedKeyHash || !key.equals(m.key)))
{
> +                m = m.next;
> +            }
>          }
>          return m;
>      }
>    
>      final Entry<K,V> findNullKeyEntry() {
>          Entry<K,V> m = elementData[0];
> -        while (m != null && m.key != null)
> +        while (m != null && m.key != null) {
>              m = m.next;
> +        }
>          return m;
>      }
>  
> @@ -569,7 +591,7 @@
>      }
>  
>      Entry<K,V> createHashedEntry(K key, int index, int hash) {
> -        Entry<K,V> entry = new Entry<K,V>(key,hash);
> +        Entry<K,V> entry = new Entry<K,V>(key, hash);
>          entry.next = elementData[index];
>          elementData[index] = entry;
>          return entry;
> @@ -609,7 +631,8 @@
>          for (int i = 0; i < elementData.length; i++) {
>              Entry<K, V> entry = elementData[i];
>              while (entry != null) {
> -                int index = entry.origKeyHash & (length - 1);
> +                int actualHash = (i & 0x00000001) | (entry.storedKeyHash & 0xFFFFFFFE);
> +                int index = actualHash & (length - 1);
>                  Entry<K, V> next = entry.next;
>                  entry.next = newData[index];
>                  newData[index] = entry;
> @@ -646,12 +669,22 @@
>          Entry<K, V> entry;
>          Entry<K, V> last = null;
>          if (key != null) {
> -            int hash = key.hashCode();
> -            index = hash & (elementData.length - 1);
> +            int keyHash = key.hashCode();
> +            index = keyHash & (elementData.length - 1);
>              entry = elementData[index];
> -            while (entry != null && !(entry.origKeyHash == hash && key.equals(entry.key)))
{
> -                last = entry;
> -                entry = entry.next;
> +
> +            if (key instanceof Integer) {
> +                int storedKeyHash = keyHash | 0x00000001;
> +                while (entry != null && (entry.storedKeyHash != storedKeyHash))
{
> +                    last = entry;
> +                    entry = entry.next;
> +                }
> +            } else {
> +                int storedKeyHash = keyHash & 0xFFFFFFFE;
> +                while (entry != null && (entry.storedKeyHash != storedKeyHash
|| !key.equals(entry.key))) {
> +                    last = entry;
> +                    entry = entry.next;
> +                }
>              }
>          } else {
>              entry = elementData[0];
> 
> 
> 

Mime
View raw message