[jsword-devel] BitwisePassage Patch
DM Smith
dmsmith555 at yahoo.com
Wed May 26 04:45:55 MST 2004
Attached is a patch for BitwisePassage. I have done boundary testing and
it appears to be good. I have not run the JUnit tests as that is still
broken in ant.
A while ago I noted that BitwisePassage made note that there were some
opportunities for performance optimization. Since I was playing around
with some old code of mine and ran across my implementation of ByteSet.
I thought I would see if it would be appropriate to solve the
performance problem.
Turns out that there have been significant improvements in JDK1.4's
BitSet. It now has isEmpty, clear, cardinality and support for iteration
for the members. So I have updated BitwisePassage to use the new
features of BitSet.
Specifically these are the changes:
I removed the comment's suggestion for optimizations.
BitwisePassage.countVerses() now calls BitSet.cardinality().
BitwisePassage.isEmpty() now calls BitSet.isEmpty().
BitwisePassage.clear() now calls BitSet.clear().
BitwisePassage.retainAll(Passage) has a fixed bug. In the else clause it
did not implement a union, which was done in the then clause. I changed
it to implement a union. It also had a bug where it created the array
one bit too small. This is not a big deal, but if the last verse of
Revelation were included, then the array would grow to twice the needed
size. The Bible is held in 476 array entries of 8 bytes apiece. This is
about 2K core.
BitwisePassage.blur() now uses BitSet.nextSetBit(int). It too had a bug
where it created the array one bit too small.
I rewrote BitwisePassage's inner class VerseIterator to use
BitSet.nextSetBit(int).
In playing with this class I have thought about a further optimization,
this time for space, which I am not sure is worth it. Let each
BitwisePassage hold an offset to the first verse in the passage. Each
BitwisePassage.store would be managed to hold exactly the number of bits
needed: ord(lastVerse) - ord(firstVerse) + 1. The index operations would
add the offset before interrogating its BitSet. Methods which call
BitSet operations on two BitSets (and, andNot, union, ...) would need to
be changed to shift their bits to have the same offset. This would be
affect addAll, removeAll and retainAll. Perhaps others.
-------------- next part --------------
Index: BitwisePassage.java
===================================================================
RCS file: /cvs/jsword/jsword/java/jsword/org/crosswire/jsword/passage/BitwisePassage.java,v
retrieving revision 1.17
diff -u -r1.17 BitwisePassage.java
--- BitwisePassage.java 23 Apr 2004 17:49:11 -0000 1.17
+++ BitwisePassage.java 26 May 2004 11:41:29 -0000
@@ -15,16 +15,6 @@
* <li>Static size, poor for small Passages, good for large Passages
* </ul>
*
- * <p>There is some optimization we could do here: The benchmark I have
- * been using spends a lot of time in VerseEnumeration. There is some
- * inefficiency here due to having to examine the bits of the BitSet
- * one by one, rather than being able to compare the underlying longs
- * with zero (clearing 64 bits in one shot). This would speed up the
- * (usual) case where there are relatively few matches in the BitSet,
- * but be a slowdown for fuller Passages.<br />
- * The bad news is that this would mean re-writing BitSet which I am
- * not all that keen to do right now.</p>
- *
* <p>The BitSet has one more bit than the number of verses in the
* Bible. This would waste 1 bit per BitSet but since this doesn't
* cause BitSet to need an extra long it doesn't, and it saves us some
@@ -49,6 +39,7 @@
* </font></td></tr></table>
* @see gnu.gpl.Licence
* @author Joe Walker [joe at eireneh dot com]
+ * @author DM Smith [dmsmith555 at yahoo dot com]
* @version $Id: BitwisePassage.java,v 1.17 2004/04/23 17:49:11 joe Exp $
*/
public class BitwisePassage extends AbstractPassage
@@ -103,18 +94,7 @@
*/
public int countVerses()
{
- int count = 0;
-
- int vib = BibleInfo.versesInBible();
- for (int i=1; i<=vib; i++)
- {
- if (store.get(i))
- {
- count++;
- }
- }
-
- return count;
+ return store.cardinality();
}
/* (non-Javadoc)
@@ -122,16 +102,7 @@
*/
public boolean isEmpty()
{
- int vib = BibleInfo.versesInBible();
- for (int i=1; i<=vib; i++)
- {
- if (store.get(i))
- {
- return false;
- }
- }
-
- return true;
+ return store.isEmpty();
}
/* (non-Javadoc)
@@ -270,14 +241,14 @@
{
optimizeWrites();
+ BitSet thatStore = null;
if (that instanceof BitwisePassage)
{
- BitSet that_store = ((BitwisePassage) that).store;
- store.and(that_store);
+ thatStore = ((BitwisePassage) that).store;
}
else
{
- BitSet new_store = new BitSet(BibleInfo.versesInBible());
+ thatStore = new BitSet(BibleInfo.versesInBible()+1);
Iterator it = that.verseIterator();
while (it.hasNext())
@@ -285,12 +256,11 @@
int ord = ((Verse) it.next()).getOrdinal();
if (store.get(ord))
{
- new_store.set(ord);
+ thatStore.set(ord);
}
}
-
- store = new_store;
}
+ store.and(thatStore);
fireIntervalRemoved(this, null, null);
}
@@ -302,11 +272,7 @@
{
optimizeWrites();
- int vib = BibleInfo.versesInBible();
- for (int i=1; i<=vib; i++)
- {
- store.clear(i);
- }
+ store.clear();
fireIntervalRemoved(this, null, null);
}
@@ -337,20 +303,16 @@
}
else
{
- BitSet new_store = new BitSet(BibleInfo.versesInBible());
+ int versesInBible = BibleInfo.versesInBible();
+ BitSet new_store = new BitSet(versesInBible + 1);
- int vib = BibleInfo.versesInBible();
- for (int i=1; i<=vib; i++)
- {
- if (store.get(i))
- {
- int start = Math.max(0, i-verses);
- int end = Math.min(BibleInfo.versesInBible(), i+verses);
+ for(int i=store.nextSetBit(0); i>=0; i=store.nextSetBit(i+1)) {
+ int start = Math.max(0, i-verses);
+ int end = Math.min(versesInBible, i+verses);
- for (int j=start; j<=end; j++)
- {
- new_store.set(j);
- }
+ for (int j=start; j<=end; j++)
+ {
+ new_store.set(j);
}
}
@@ -364,6 +326,7 @@
/**
* Iterate over the Verses
* @author Joe Walker
+ * @author DM Smith
*/
private final class VerseIterator implements Iterator
{
@@ -372,6 +335,7 @@
*/
public VerseIterator()
{
+ next = -1;
calculateNext();
}
@@ -380,7 +344,7 @@
*/
public boolean hasNext()
{
- return next <= BibleInfo.versesInBible();
+ return next >= 0;
}
/* (non-Javadoc)
@@ -390,7 +354,7 @@
{
try
{
- if (next > BibleInfo.versesInBible())
+ if (!hasNext())
{
throw new NoSuchElementException();
}
@@ -420,20 +384,13 @@
*/
private void calculateNext()
{
- while (next <= BibleInfo.versesInBible())
- {
- next++;
- if (store.get(next))
- {
- break;
- }
- }
+ next = store.nextSetBit(next+1);
}
/**
* What is the next Verse to be considered
*/
- private int next = 0;
+ private int next;
}
/**
More information about the jsword-devel
mailing list