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 [EMAIL PROTECTED] 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]; > > >
