You are viewing a plain text version of this content. The canonical link for it is here.
Posted to solr-commits@lucene.apache.org by yo...@apache.org on 2007/01/21 06:46:34 UTC
svn commit: r498246 - in /lucene/solr/trunk: CHANGES.txt
src/java/org/apache/solr/search/BitDocSet.java
src/java/org/apache/solr/search/HashDocSet.java
src/test/org/apache/solr/search/TestDocSet.java
Author: yonik
Date: Sat Jan 20 21:46:31 2007
New Revision: 498246
URL: http://svn.apache.org/viewvc?view=rev&rev=498246
Log:
HashDocSet new hash, union, andNot: SOLR-114
Modified:
lucene/solr/trunk/CHANGES.txt
lucene/solr/trunk/src/java/org/apache/solr/search/BitDocSet.java
lucene/solr/trunk/src/java/org/apache/solr/search/HashDocSet.java
lucene/solr/trunk/src/test/org/apache/solr/search/TestDocSet.java
Modified: lucene/solr/trunk/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/solr/trunk/CHANGES.txt?view=diff&rev=498246&r1=498245&r2=498246
==============================================================================
--- lucene/solr/trunk/CHANGES.txt (original)
+++ lucene/solr/trunk/CHANGES.txt Sat Jan 20 21:46:31 2007
@@ -52,7 +52,10 @@
user query, not boost or filter queries (klaas).
Optimizations
- 1.
+ 1. SOLR-114: HashDocSet specific implementations of union() and andNot()
+ for a 20x performance improvement for those set operations, and a new
+ hash algorithm speeds up exists() by 10% and intersectionSize() by 8%.
+ (yonik)
Bug Fixes
1. SOLR-87: Parsing of synonym files did not correctly handle escaped
Modified: lucene/solr/trunk/src/java/org/apache/solr/search/BitDocSet.java
URL: http://svn.apache.org/viewvc/lucene/solr/trunk/src/java/org/apache/solr/search/BitDocSet.java?view=diff&rev=498246&r1=498245&r2=498246
==============================================================================
--- lucene/solr/trunk/src/java/org/apache/solr/search/BitDocSet.java (original)
+++ lucene/solr/trunk/src/java/org/apache/solr/search/BitDocSet.java Sat Jan 20 21:46:31 2007
@@ -177,6 +177,31 @@
}
}
+ @Override
+ public DocSet andNot(DocSet other) {
+ OpenBitSet newbits = (OpenBitSet)(bits.clone());
+ if (other instanceof OpenBitSet) {
+ newbits.andNot(((BitDocSet)other).bits);
+ } else {
+ DocIterator iter = other.iterator();
+ while (iter.hasNext()) newbits.clear(iter.nextDoc());
+ }
+ return new BitDocSet(newbits);
+ }
+
+ @Override
+ public DocSet union(DocSet other) {
+ OpenBitSet newbits = (OpenBitSet)(bits.clone());
+ if (other instanceof BitDocSet) {
+ newbits.union(((BitDocSet)other).bits);
+ } else {
+ DocIterator iter = other.iterator();
+ while (iter.hasNext()) newbits.set(iter.nextDoc());
+ }
+ return new BitDocSet(newbits);
+ }
+
+
public long memSize() {
return (bits.getBits().length << 3) + 16;
}
Modified: lucene/solr/trunk/src/java/org/apache/solr/search/HashDocSet.java
URL: http://svn.apache.org/viewvc/lucene/solr/trunk/src/java/org/apache/solr/search/HashDocSet.java?view=diff&rev=498246&r1=498245&r2=498246
==============================================================================
--- lucene/solr/trunk/src/java/org/apache/solr/search/HashDocSet.java (original)
+++ lucene/solr/trunk/src/java/org/apache/solr/search/HashDocSet.java Sat Jan 20 21:46:31 2007
@@ -31,7 +31,6 @@
* @since solr 0.9
*/
public final class HashDocSet extends DocSetBase {
- // final static float inverseLoadfactor = 1.0f / SolrConfig.config.getFloat("//HashDocSet/@loadFactor",0.75f);
/** Default load factor to use for HashDocSets. We keep track of the inverse
* since multiplication is so much faster than division. The default
* is 1.0f / 0.75f
@@ -45,27 +44,27 @@
// an alternative to having to init the array to EMPTY at the start is
//
private final static int EMPTY=-1;
- private final int tablesize;
private final int[] table;
private final int size;
private final int mask;
+ /** Create a HashDocSet from a list of *unique* ids */
public HashDocSet(int[] docs, int offset, int len) {
this(docs, offset, len, DEFAULT_INVERSE_LOAD_FACTOR);
}
+ /** Create a HashDocSet from a list of *unique* ids */
public HashDocSet(int[] docs, int offset, int len, float inverseLoadFactor) {
int tsize = Math.max(BitUtil.nextHighestPowerOfTwo(len), 1);
if (tsize < len * inverseLoadFactor) {
tsize <<= 1;
}
- tablesize = tsize;
- mask=tablesize-1;
+ mask=tsize-1;
- table = new int[tablesize];
- for (int i=0; i<tablesize; i++) table[i]=EMPTY;
+ table = new int[tsize];
+ for (int i=tsize-1; i>=0; i--) table[i]=EMPTY;
for (int i=offset; i<len; i++) {
put(docs[i]);
@@ -75,104 +74,36 @@
}
void put(int doc) {
- table[getSlot(doc)]=doc;
+ int s = doc & mask;
+ while (table[s]!=EMPTY) {
+ // Adding an odd number to this power-of-two hash table is
+ // guaranteed to do a full traversal, so instead of re-hashing
+ // we jump straight to a "linear" traversal.
+ // The key is that we provide many different ways to do the
+ // traversal (tablesize/2) based on the last hash code (the doc).
+ // Rely on loop invariant code motion to eval ((doc>>7)|1) only once.
+ // otherwise, we would need to pull the first case out of the loop.
+ s = (s + ((doc>>7)|1)) & mask;
+ }
+ table[s]=doc;
}
- private int getSlot(int val) {
- int s,v;
- s=val & mask;
- v=table[s];
- // check for EMPTY first since that value is more likely
- if (v==EMPTY || v==val) return s;
- s=rehash(val);
- return s;
- }
-
-
- // As the size of this int hashtable is expected to be small
- // (thousands at most), I did not try to keep the rehash function
- // reversible (important to avoid collisions in large hash tables).
- private int rehash(int val) {
- int h,s,v;
- final int comp=~val;
-
- // don't left shift too far... the only bits
- // that count in the answer are the ones on the right.
- // We want to put more of the bits on the left
- // into the answer.
- // Keep small tables in mind. We may be only using
- // the first 5 or 6 bits.
-
- // on the first rehash, use complement instead of val to shift
- // so we don't end up with 0 again if val==0.
- h = val ^ (comp>>8);
- s = h & mask;
- v = table[s];
- if (v==EMPTY || v==val) return s;
-
- h ^= (v << 17) | (comp >>> 16); // this is reversible
- s = h & mask;
- v = table[s];
- if (v==EMPTY || v==val) return s;
-
- h ^= (h << 8) | (comp >>> 25); // this is reversible
- s = h & mask;
- v = table[s];
- if (v==EMPTY || v==val) return s;
-
- /**********************
- // Knuth, Thomas Wang, http://www.concentric.net/~Ttwang/tech/inthash.htm
- // This magic number has no common factors with 2^32, and magic/(2^32) approximates
- // the golden ratio.
- private static final int magic = (int)2654435761L;
-
- h = magic*val;
- s = h & mask;
- v=table[s];
- if (v==EMPTY || v==val) return s;
-
- // the mult with magic should have thoroughly mixed the bits.
- // add entropy to the right half from the left half.
- h ^= h>>>16;
- s = h & mask;
- v=table[s];
- if (v==EMPTY || v==val) return s;
- *************************/
-
- // linear scan now... ug.
- final int start=s;
- while (++s<tablesize) {
- v=table[s];
- if (v==EMPTY || v==val) return s;
- }
- s=start;
- while (--s>=0) {
- v=table[s];
- if (v==EMPTY || v==val) return s;
+ public boolean exists(int doc) {
+ int s = doc & mask;
+ for(;;) {
+ int v = table[s];
+ if (v==EMPTY) return false;
+ if (v==doc) return true;
+ // see put() for algorithm details.
+ s = (s + ((doc>>7)|1)) & mask;
}
- return s;
}
- /**
- *
- * @return The number of document ids in the set.
- */
public int size() {
return size;
}
- public boolean exists(int docid) {
- int v = table[docid & mask];
- if (v==EMPTY) return false;
- else if (v==docid) return true;
- else {
- v = table[rehash(docid)];
- if (v==docid) return true;
- else return false;
- }
- }
-
public DocIterator iterator() {
return new DocIterator() {
int pos=0;
@@ -180,7 +111,7 @@
{ goNext(); }
public boolean hasNext() {
- return pos < tablesize;
+ return pos < table.length;
}
public Integer next() {
@@ -191,7 +122,7 @@
}
void goNext() {
- while (pos<tablesize && table[pos]==EMPTY) pos++;
+ while (pos<table.length && table[pos]==EMPTY) pos++;
}
// modify to return -1 at end of iteration?
@@ -208,9 +139,8 @@
};
}
-
public long memSize() {
- return (tablesize<<2) + 20;
+ return (table.length<<2) + 20;
}
@Override
@@ -272,7 +202,49 @@
}
return resultCount;
}
-
+
+ }
+
+
+ @Override
+ public DocSet andNot(DocSet other) {
+ int[] result = new int[size()];
+ int resultCount=0;
+
+ for (int i=0; i<table.length; i++) {
+ int id=table[i];
+ if (id >= 0 && !other.exists(id)) {
+ result[resultCount++]=id;
+ }
+ }
+ return new HashDocSet(result,0,resultCount);
+ }
+
+ @Override
+ public DocSet union(DocSet other) {
+ if (other instanceof HashDocSet) {
+ // set "a" to the smallest doc set
+ final HashDocSet a = size()<=other.size() ? this : (HashDocSet)other;
+ final HashDocSet b = size()<=other.size() ? (HashDocSet)other : this;
+
+ int[] result = new int[a.size()+b.size()];
+ int resultCount=0;
+ // iterate over the largest table first, adding w/o checking.
+ for (int i=0; i<b.table.length; i++) {
+ int id=b.table[i];
+ if (id>=0) result[resultCount++]=id;
+ }
+
+ // now iterate over smaller set, adding all not already in larger set.
+ for (int i=0; i<a.table.length; i++) {
+ int id=a.table[i];
+ if (id>=0 && !b.exists(id)) result[resultCount++]=id;
+ }
+
+ return new HashDocSet(result,0,resultCount);
+ } else {
+ return other.union(this);
+ }
}
Modified: lucene/solr/trunk/src/test/org/apache/solr/search/TestDocSet.java
URL: http://svn.apache.org/viewvc/lucene/solr/trunk/src/test/org/apache/solr/search/TestDocSet.java?view=diff&rev=498246&r1=498245&r2=498246
==============================================================================
--- lucene/solr/trunk/src/test/org/apache/solr/search/TestDocSet.java (original)
+++ lucene/solr/trunk/src/test/org/apache/solr/search/TestDocSet.java Sat Jan 20 21:46:31 2007
@@ -23,6 +23,7 @@
import org.apache.solr.util.OpenBitSet;
import org.apache.solr.util.BitSetIterator;
+import org.apache.solr.util.BitUtil;
/**
* @author yonik
@@ -30,6 +31,7 @@
*/
public class TestDocSet extends TestCase {
Random rand = new Random();
+ float loadfactor;
public OpenBitSet getRandomSet(int sz, int bitsToSet) {
OpenBitSet bs = new OpenBitSet(sz);
@@ -104,5 +106,135 @@
public void testRandomDocSets() {
doMany(300, 5000);
}
+
+
+ public HashDocSet getRandomHashDocset(int maxSetSize, int maxDoc) {
+ int n = rand.nextInt(maxSetSize);
+ OpenBitSet obs = new OpenBitSet(maxDoc);
+ int[] a = new int[n];
+ for (int i=0; i<n; i++) {
+ for(;;) {
+ int idx = rand.nextInt(maxDoc);
+ if (obs.getAndSet(idx)) continue;
+ a[i]=idx;
+ break;
+ }
+ }
+ return loadfactor!=0 ? new HashDocSet(a,0,n,1/loadfactor) : new HashDocSet(a,0,n);
+ }
+
+ public DocSet[] getRandomHashSets(int nSets, int maxSetSize, int maxDoc) {
+ DocSet[] sets = new DocSet[nSets];
+
+ for (int i=0; i<nSets; i++) {
+ sets[i] = getRandomHashDocset(maxSetSize,maxDoc);
+ }
+
+ return sets;
+ }
+
+ /**** needs code insertion into HashDocSet
+ public void testCollisions() {
+ loadfactor=.75f;
+ rand=new Random(12345); // make deterministic
+ int maxSetsize=4000;
+ int nSets=256;
+ int iter=1;
+ int[] maxDocs=new int[] {100000,500000,1000000,5000000,10000000};
+ int ret=0;
+ long start=System.currentTimeMillis();
+ for (int maxDoc : maxDocs) {
+ int cstart = HashDocSet.collisions;
+ DocSet[] sets = getRandomHashSets(nSets,maxSetsize, maxDoc);
+ for (DocSet s1 : sets) {
+ for (DocSet s2 : sets) {
+ if (s1!=s2) ret += s1.intersectionSize(s2);
+ }
+ }
+ int cend = HashDocSet.collisions;
+ System.out.println("maxDoc="+maxDoc+"\tcollisions="+(cend-cstart));
+ }
+ long end=System.currentTimeMillis();
+ System.out.println("testIntersectionSizePerformance="+(end-start)+" ms");
+ if (ret==-1)System.out.println("wow!");
+ System.out.println("collisions="+HashDocSet.collisions);
+
+ }
+ ***/
+
+ /***
+ public void testIntersectionSizePerformance() {
+ loadfactor=.75f;
+ rand=new Random(12345); // make deterministic
+ int maxSetsize=4000;
+ int nSets=128;
+ int iter=10;
+ int maxDoc=1000000;
+ DocSet[] sets = getRandomHashSets(nSets,maxSetsize, maxDoc);
+ int ret=0;
+ long start=System.currentTimeMillis();
+ for (int i=0; i<iter; i++) {
+ for (DocSet s1 : sets) {
+ for (DocSet s2 : sets) {
+ ret += s1.intersectionSize(s2);
+ }
+ }
+ }
+ long end=System.currentTimeMillis();
+ System.out.println("testIntersectionSizePerformance="+(end-start)+" ms");
+ if (ret==-1)System.out.println("wow!");
+ }
+
+
+ public void testExistsPerformance() {
+ loadfactor=.75f;
+ rand=new Random(12345); // make deterministic
+ int maxSetsize=4000;
+ int nSets=512;
+ int iter=1;
+ int maxDoc=1000000;
+ DocSet[] sets = getRandomHashSets(nSets,maxSetsize, maxDoc);
+ int ret=0;
+ long start=System.currentTimeMillis();
+ for (int i=0; i<iter; i++) {
+ for (DocSet s1 : sets) {
+ for (int j=0; j<maxDoc; j++) {
+ ret += s1.exists(j) ? 1 :0;
+ }
+ }
+ }
+ long end=System.currentTimeMillis();
+ System.out.println("testExistsSizePerformance="+(end-start)+" ms");
+ if (ret==-1)System.out.println("wow!");
+ }
+ ***/
+
+ /**** needs code insertion into HashDocSet
+ public void testExistsCollisions() {
+ loadfactor=.75f;
+ rand=new Random(12345); // make deterministic
+ int maxSetsize=4000;
+ int nSets=512;
+ int[] maxDocs=new int[] {100000,500000,1000000,5000000,10000000};
+ int ret=0;
+
+ for (int maxDoc : maxDocs) {
+ int mask = (BitUtil.nextHighestPowerOfTwo(maxDoc)>>1)-1;
+ DocSet[] sets = getRandomHashSets(nSets,maxSetsize, maxDoc);
+ int cstart = HashDocSet.collisions;
+ for (DocSet s1 : sets) {
+ for (int j=0; j<maxDocs[0]; j++) {
+ int idx = rand.nextInt()&mask;
+ ret += s1.exists(idx) ? 1 :0;
+ }
+ }
+ int cend = HashDocSet.collisions;
+ System.out.println("maxDoc="+maxDoc+"\tcollisions="+(cend-cstart));
+ }
+ if (ret==-1)System.out.println("wow!");
+ System.out.println("collisions="+HashDocSet.collisions);
+ }
+ ***/
+
}