Changeset 12971

Timestamp:

10/10/10 15:48:48 (12 years ago)

Author:

ehuelsmann

Message:

Small performance improvement for non-EQ hash tables;
don't use comparator when key and HashEntry?.key are the
same object. Along the same lines, compare the keys *only*
if the hash values are equal.

File:

• trunk/abcl/src/org/armedbear/lisp/HashTable.java (modified) (4 diffs)

trunk/abcl/src/org/armedbear/lisp/HashTable.java

@@ -250 +250 @@
     protected HashEntry getEntry(LispObject key) {
         HashEntry[] b = buckets;
-        HashEntry e = b[comparator.hash(key) & (b.length - 1)];
+        int hash = comparator.hash(key);
+        HashEntry e = b[hash & (b.length - 1)];
         while (e != null) {
-            if (comparator.keysEqual(key, e.key)) {
+            if (hash == e.hash &&
+                    (key == e.key || comparator.keysEqual(key, e.key))) {
                 return e;
             }
@@ -288 +290 @@
                 }
 
-                int index = comparator.hash(key) & (buckets.length - 1);
-                buckets[index] = new HashEntry(key, value, buckets[index]);
+                int hash = comparator.hash(key);
+                int index = hash & (buckets.length - 1);
+                buckets[index] = new HashEntry(key, hash, value, buckets[index]);
             }
         } finally {
@@ -334 +337 @@
                 while (e != null) {
                     final int index = comparator.hash(e.key) & mask;
-                    newBuckets[index] = new HashEntry(e.key, e.value, newBuckets[index]);
+                    newBuckets[index] = new HashEntry(e.key, e.hash, e.value,
+                            newBuckets[index]);
                     e = e.next;
                 }
@@ -437 +441 @@
 
         LispObject key;
+        int hash;
         volatile LispObject value;
         HashEntry next;
 
-        HashEntry(LispObject key, LispObject value, HashEntry next) {
+        HashEntry(LispObject key, int hash, LispObject value, HashEntry next) {
             this.key = key;
+            this.hash = hash;
             this.value = value;
             this.next = next;