[jsword-devel] BitwisePassage Patch
Joe Walker
joe at eireneh.com
Wed May 26 13:19:08 MST 2004
Good one.
I've applied it.
I've also applied some changes to bibledesktop - I've killed View
G-HTML, or rather I've killed View HTML and fixed View G-HTML and called
if View HTML. Both view options re-generate the source. This allows us
to delete the silly methods that picked out the HTML and OSIS from the
current component. At the same time I merged FocusablePart into
BibleDataDisplay. This continues the work to move to using Key rather
than Passage where possible. Passage is far more powerful, but where the
power isn't needed Key allows the view component to work with all types
of Book.
I also spent some time fixing jsword-support, but there is more work to
be done there.
I think we need to split the jsword-web project to have a
bibledesktop-web project. The new project can be quite simple, but if it
is a separate project then it would make sense for it to have it's own
web pages, and the only way to have www.crosswire.org/bibledesktop is to
have a new webapp, which to me means new project.
Joe.
DM Smith wrote:
> 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.
>
>
>
>
>
> ------------------------------------------------------------------------
>
> 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;
> }
>
> /**
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> jsword-devel mailing list
> jsword-devel at crosswire.org
> http://www.crosswire.org/mailman/listinfo/jsword-devel
More information about the jsword-devel
mailing list