[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