harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Oliver Deakin <oliver.dea...@googlemail.com>
Subject Re: [classlib][luni] FYI hashmap optimization
Date Fri, 14 Sep 2007 15:10:41 GMT
Thanks for the write-up Tim, it was an interesting read.

Regards,
Oliver

Tim Ellison wrote:
> 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];
>>
>>
>>
>>     
>
>   

-- 
Oliver Deakin
Unless stated otherwise above:
IBM United Kingdom Limited - Registered in England and Wales with number 741598. 
Registered office: PO Box 41, North Harbour, Portsmouth, Hampshire PO6 3AU


Mime
View raw message