svn commit: r903886 - in /lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common: FastByIDMap.java FastIDSet.java

[srowen]

Author: srowen
Date: Wed Jan 27 22:32:03 2010
New Revision: 903886

URL: http://svn.apache.org/viewvc?rev=903886&view=rev
Log:
Optimization to find methods

Modified:
    
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastByIDMap.java
    
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastIDSet.java

Modified: 
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastByIDMap.java
URL: 
http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastByIDMap.java?rev=903886&r1=903885&r2=903886&view=diff
==============================================================================
--- 
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastByIDMap.java
 (original)
+++ 
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastByIDMap.java
 Wed Jan 27 22:32:03 2010
@@ -86,6 +86,9 @@
     this.recentlyAccessed = countingAccesses ? new BitSet(hashSize) : null;
   }
 
+  /**
+   * @see #findForAdd(long)
+   */
   private int find(long key) {
     int theHashCode = (int) key & 0x7FFFFFFF; // make sure it's positive
     long[] keys = this.keys;
@@ -93,7 +96,28 @@
     int jump = 1 + theHashCode % (hashSize - 2);
     int index = theHashCode % hashSize;
     long currentKey = keys[index];
-    while (currentKey != NULL && (currentKey == REMOVED || key != currentKey)) 
{
+    while (currentKey != NULL && key != currentKey) {
+      if (index < jump) {
+        index += hashSize - jump;
+      } else {
+        index -= jump;
+      }
+      currentKey = keys[index];
+    }
+    return index;
+  }
+
+  /**
+   * @see #find(long)
+   */
+  private int findForAdd(long key) {
+    int theHashCode = (int) key & 0x7FFFFFFF; // make sure it's positive
+    long[] keys = this.keys;
+    int hashSize = keys.length;
+    int jump = 1 + theHashCode % (hashSize - 2);
+    int index = theHashCode % hashSize;
+    long currentKey = keys[index];
+    while (currentKey != NULL && currentKey != REMOVED && key != currentKey) { 
// Different here
       if (index < jump) {
         index += hashSize - jump;
       } else {
@@ -157,8 +181,13 @@
       }
     }
     // Here we may later consider implementing Brent's variation described on 
page 532
-    int index = find(key);
-    if (keys[index] == NULL) {
+    int index = findForAdd(key);
+    long keyIndex = keys[index];
+    if (keyIndex == key) {
+      V oldValue = values[index];
+      values[index] = value;
+      return oldValue;
+    } else {
       // If size is limited,
       if (countingAccesses && numEntries >= maxSize) {
         // and we're too large, clear some old-ish entry
@@ -167,12 +196,10 @@
       keys[index] = key;
       values[index] = value;
       numEntries++;
-      numSlotsUsed++;
+      if (keyIndex == NULL) {
+        numSlotsUsed++;
+      }
       return null;
-    } else {
-      V oldValue = values[index];
-      values[index] = value;
-      return oldValue;
     }
   }
 

Modified: 
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastIDSet.java
URL: 
http://svn.apache.org/viewvc/lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastIDSet.java?rev=903886&r1=903885&r2=903886&view=diff
==============================================================================
--- 
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastIDSet.java
 (original)
+++ 
lucene/mahout/trunk/core/src/main/java/org/apache/mahout/cf/taste/impl/common/FastIDSet.java
 Wed Jan 27 22:32:03 2010
@@ -57,6 +57,9 @@
     Arrays.fill(keys, NULL);
   }
 
+  /**
+   * @see #findForAdd(long)
+   */
   private int find(long key) {
     int theHashCode = (int) key & 0x7FFFFFFF; // make sure it's positive
     long[] keys = this.keys;
@@ -64,7 +67,28 @@
     int jump = 1 + theHashCode % (hashSize - 2);
     int index = theHashCode % hashSize;
     long currentKey = keys[index];
-    while (currentKey != NULL && (currentKey == REMOVED || key != currentKey)) 
{
+    while (currentKey != NULL && key != currentKey) { // note: true when 
currentKey == REMOVED
+      if (index < jump) {
+        index += hashSize - jump;
+      } else {
+        index -= jump;
+      }
+      currentKey = keys[index];
+    }
+    return index;
+  }
+
+  /**
+   * @see #find(long)
+   */
+  private int findForAdd(long key) {
+    int theHashCode = (int) key & 0x7FFFFFFF; // make sure it's positive
+    long[] keys = this.keys;
+    int hashSize = keys.length;
+    int jump = 1 + theHashCode % (hashSize - 2);
+    int index = theHashCode % hashSize;
+    long currentKey = keys[index];
+    while (currentKey != NULL && currentKey != REMOVED && key != currentKey) { 
// Different here
       if (index < jump) {
         index += hashSize - jump;
       } else {
@@ -102,11 +126,14 @@
       }
     }
     // Here we may later consider implementing Brent's variation described on 
page 532
-    int index = find(key);
-    if (keys[index] == NULL) {
+    int index = findForAdd(key);
+    long keyIndex = keys[index];
+    if (keyIndex != key) {
       keys[index] = key;
       numEntries++;
-      numSlotsUsed++;
+      if (keyIndex == NULL) {
+        numSlotsUsed++;
+      }
       return true;
     }
     return false;