[jsword-devel] New versification mapping - preload mappings to prevent pauses

Martin Denham mjdenham at gmail.com
Mon Jan 20 07:54:45 MST 2014 

I did some experiments using a RangedPassage and it performs well with the
Versification code.  I removed teh workaround and found there is be a delay
of ~1 sec using RangedPassage, instead of 1.5 mins using the original
RocketPassage/BitwisePassage.

I will leave the workaround in and also set RangedPassage to be the default
passage type for AB.

I needed to change PassageType.MIX to RangedPassage and will commit it
shortly.

Martin


On 19 January 2014 00:56, DM Smith <dmsmith at crosswire.org> wrote:

>
> On Jan 18, 2014, at 5:47 PM, Chris Burrell <chris at burrell.me.uk> wrote:
>
> Presumably if we have a basic osis ref parser, we can easily construct a
> verse range directly. Meaning a lot of the parsing on the versification
> mapping is simplified.
>
>
> We don't have a basic osisID parser. If we did then...
>
>
> The slight complication with the versification mappings is that it
> currently copes for the case as follows:
>
> Gen.1.1=Gen.1-2
> Gen.1.1=Gen.1.4
>
>
> These should be written:
> Gen.1.1=Gen.1.1-Gen.1.2
> Gen.1.1=Gen.1.4
> That is the right hand side of the range should be an osisID.
>
>
> i.e. split ranges, meaning that Gen 1:1 would map to verses 1,2 and 4
> (leaving verse 3 out).
>
> So if we used a osis ref parser, we could two ranges very very quickly
> (Gen.1-2 and Gen.1-4).
>
> Yes.
>
> However, what structure would we use to store the combination of both? I
> was thinking a RangedPassage but you suggested the construction of this
> would be heavy?
>
> The construction of a ranged passage one verse at a time is heavy.
> Especially when the verses are not ordered.
>
> Imagine if we added the verses for Gen 1:1 to Gen 1:6 one verse at a time,
> but in the following order 1, 3, 2, 4, 6, 7, 5, 9, 10, 8.
>
> 1 > Create a VerseRange for Gen 1:1 to Gen 1:1 and add it to the
> collection.
> 3 > Check to see if 3 is already represented or if it is adjacent to any
> existing VerseRange. Since it is not create a new VerseRange for Gen 1:3 to
> Gen 1:3.
> 2 > Do the checks, finding that it is adjacent to Gen 1:1. Extend that
> VerseRange to become Gen 1:1-Gen 1:2. Since it was also adjacent to the
> other, throw that one away and extend the first to encompass all the verses
> in that.
> 4> Extend the one VerseRange.
> 6> Create a new VerseRange.
> 7> Find and extend a VerseRange.
> 5> Find and extend a VerseRange. Find and another adjacent VerseRange and
> extend the other to include it. Then throw it away. (Now we have one verse
> range Gen 1:1-7.
> 9> Create a Verse Range.
> 10> Extend that Verse Range
> 8> Find, extend, find, merge, wack.
>
> If the RangePassage is simply constructed (e.g. construct a verse range
> and add it to an empty RangedPassage) There is no work.
>
> If the RangedPassage is "Gen.1.1-Gen.1.2 Gen.1.4", is built as a
> VerseRange for both Gen.1.1-Gen.1.2 and for Gen.1.4-Gen.1.4 and added to
> the RangedPassage, there will be little overhead.
> (In OSIS a passage is a space separate list of osisIDs and/or osisRefs).
>
> I just don't know if this is directly supported in the RangedPassage code,
> but it should.
>
>
> Presumably we could introduce a constructor that takes a collection of
> VerseRanges, meaning its construction would be also very quick?
>
>
> Yes.
>
>
> One more point, on the osis ref parser. Presumably we would want to use
> BibleBookNames but looks like it already normalizes the booknames to the
> English locale.
>
> Not really. The toUpper and toLower should always be called with an
> explicit Locale. Using Locale.ENGLISH means that it won't use the user's
> Locale. Since we control the text, we know that Locale.ENGLISH is the
> correct thing to do.
>
> The normalizing of the names is a concession of end user text entry, where
> they might not know that Gen is the one and only way to specify Genesis in
> OSIS.
>
> It would be better to have the lookup be exact. Maybe a new hash and a new
> call?
>
> Is there any particular reason for the normalize() method in the static
> initializer?
>
>
>
> Seems redundant to me... (apart from the lowercase).
>
>
> This could be optimized to call toLower directly.
>
> The principle is that the index and the search should be normalized in
> exactly the same way. If we chose, we could change normalize to upper odd
> chars and lower even. The code would continue to work.
>
> But if we change it then comments should be here and in normalize to note
> that a change to the one may require a change to the other.
>
>
> I suggest we optimize that, saving another hosts of pattern matches. (only
> a handful), but on Android it will save a number of method calls which tend
> to be more expensive than expected. Is there a strong reason to have the
> lowercase? or would it be possible to define them lowercase to start with?
>
>
> These values are used to construct osisIDs and the Mixed case is defined
> by the standard.
>
> Presumably our osis parser would want to ignore case...
>
>
> The osis parser should probably not want to ignore case. The specification
> is mixed case. Skipping toLower would be a bit faster.
>
>
> Chris
>
>
>
> On 18 January 2014 22:19, DM Smith <dmsmith at crosswire.org> wrote:
>
>> See embedded.
>> On Jan 18, 2014, at 4:05 PM, Chris Burrell <chris at burrell.me.uk> wrote:
>>
>> I think to encourage the use of the Passages directly we need to make
>> those constructors public. That's the main reason I have stayed away from
>> using it.
>>
>>
>> I see that TallyPassage is fully public and the rest are not. This must
>> have been so that Lucene ranked searches could use them.
>>
>> Maybe, we should modify PassageKeyFactory to take an optional PassageType?
>>
>>
>> Obviously a fast way to construct the versification mappings would be to
>> turn them into verse numbers. But that means losing readability.
>>
>>
>> I think readability is critical to maintenance. You'll note that the v11n
>> tables are readable.
>>
>> The obvious thought here is to generate an intermediary file as part of
>> the build from what we have already code (custom maven plugin/ant task).
>> But that seems rather hacky, but would line up with the way the
>> versifications are defined in code.
>>
>> So basically what we want is:
>> * an easy way of reading in a verse range/passage from text form into
>> Verse/VerseRanges
>>
>>
>> The are a couple of things here that we could benefit from:
>> 1) An osisID parser and an osisRef parser. An osisRef is merely two
>> osisIDs separated by a dash.
>> Note: Gen.1.1-2 is not an osisRef as 2 is not an osisID. To parse "2" the
>> parser has to know that the "basis" (the context) of "2" is Genesis 1:1.
>> Thus 2 is understood as a verse and not a chapter. However, if the basis
>> was Gen.1 then the 2 would be understood as a chapter.
>>
>> By having fully formed OSIS references*, we gain the following:
>> There are no spaces to trim.
>> Splitting on - will split into two parts, both of which are fully formed
>> osisIDs.
>> Splitting an osisID on . will result in 1 to 3 parts. book, book and
>> chapter or book, chapter and verse. The verse is always a number, never
>> "ff" or a roman numeral.
>> Lookup of the book names is simplified. No need to try to figure out that
>> Jo means John (or does it mean Job, or Jonah???). Book names are fixed
>> ascii, never internationalized, never have spaces, dashes, periods or roman
>> numerals.
>>
>> *Later, when we have references with works and grains, we may want to
>> handle those. E.g. ignore them.
>>
>> 2) Today, conceptually a Passage is an ordered list of Verses and
>> VerseRanges that don't overlap. However, JSword does not have a way to
>> build a Verse or a VerseRange from a String. Maybe we need a way to
>> construct a Passage from bottom up. I.e. create a Verse or VerseRange from
>> a String (from osisIDs and osisRefs) and then put them into an initially
>> empty Passage. Since we control the input, we know that the VerseRanges do
>> not overlap, so maybe we can have a smart constructor that takes a List of
>> Verse and VerseRanges and adds them.
>>
>>
>> Basically, the way the code works is to iterate through the properties
>> file and map and reverse-map every verse present to the maximum size
>> available (i.e. 1 verse to a Passage). The idea behind this is that we
>> store less that way.
>>
>> So if a mapping specifies as follows: Gen.1.1=Gen.1.1-2, then we only
>> need to store
>> left to right: Gen.1.1=>Gen.1.1-2
>> right to left: Gen.1=>Gen.1.1, Gen.1.2=>Gen.1.1
>>
>> In that way, we've saved a mapping, and therefore memory (assuming we
>> represent those ranges correctly).
>> Chris
>>
>>
>>
>> On 18 January 2014 20:48, DM Smith <dmsmith at crosswire.org> wrote:
>>
>>>
>>> On Jan 18, 2014, at 3:19 PM, Chris Burrell <chris at burrell.me.uk> wrote:
>>>
>>> Great stuff - helps really explain things. So I think for the
>>> versification mappings, seen as they don't change much as they are mostly
>>> contiguous ranges a RangePassage might be the best bet.
>>>
>>>
>>> A RangedPassage is really good once it is constructed. Building it takes
>>> a lot of time. Certainly not good for canonical ordered search results.
>>>
>>>
>>>
>>> I think the other thing that's quite expensive
>>> is: PassageKeyFactory.instance().getKey(targetVersification,
>>> qualifiedKey.getKey().getOsisRef())
>>>
>>>
>>> I think this is expensive because of how it is done.
>>> From memory: getOsisRef() returns a string, which needs to be parsed
>>> into what getKey() already is. The parser does not handle osisRefs. It
>>> throws an exception and the caller then mungs the reference such that the
>>> parser can handle it. JSword needs an osisRef parser, which would be much
>>> simpler and faster than the current parser that tries to understand what an
>>> end user is trying to provide.
>>>
>>> If the reference is a string (e.g. from a user, from a module, these
>>> methods are appropriate), these are what should be used. If not a string,
>>> then stay away. It is expensive to convert a Passage to a String and it is
>>> expensive to parse a String and to build the Passage.
>>>
>>> It'd be better to get an empty key list and add qualifiedKey.getKey().
>>>
>>>
>>>
>>> I'm not sure what's the best way of dealing with this but I suspect that
>>> we may want to have specific cases for Verses as I believe the above is
>>> quite heavy as well.
>>>
>>> I think I also often
>>> use: PassageKeyFactory.instance().createEmptyKeyList(versification) which
>>> probably should use a RangePassage as well
>>>
>>>
>>> It should use the PassageType that the program finds best. A server side
>>> application has very different requirements from a desktop and that from a
>>> mobile app.
>>>
>>> If you need a specific implementation, don't use the factory. Use what
>>> is best for the particular location.
>>>
>>> Just note that if two different implementations are used (like adding
>>> one passage to another) the result will probably be the program default.
>>>
>>>
>>> Would that make sense?
>>> Chris
>>>
>>>
>>>
>>> On 18 January 2014 20:11, DM Smith <dmsmith at crosswire.org> wrote:
>>>
>>>> There are several different implementations for Passage. They have
>>>> trade-offs.
>>>> BitwisePassage is strictly a BitMap, with one bit for each verse in the
>>>> v11n. It is very space heavy but fast for most operations. Especially
>>>> adding or removing Verses. Iteration is fast as it uses NextSetBit (or
>>>> whatever it is called to find the next set bit).
>>>> RocketPassage is a very heavy implementation. Not appropriate for
>>>> mobile. It occupies lots more space than a BitwisePassage
>>>> PassageTally is basically a weighted set of verses such that you can
>>>> order by weights. This is used to return weighted search results. It is
>>>> probably not much use otherwise. It is used to return a ranked Lucene
>>>> search.
>>>> RangedPassage keeps ranges (start verse and length) ordered in a
>>>> TreeSet. It probably is a good candidate for mobile. Maybe the best
>>>> regarding storage. Works well if the RangedPassage is not modified much. If
>>>> you add a verse (not in the RangedPassage) it may cause two VerseRanges to
>>>> be merged into one, otherwise it'll extend one or create a new one. That
>>>> computation takes time. Removing a verse is also complex.
>>>> DistinctPassage keeps verses ordered in a TreeSet. This can be a good
>>>> candidate for mobile, if there are not many verses in the Passage. If there
>>>> are lots it gets bigger than BitwisePassage.
>>>>
>>>> The PassageKeyFactory is used throughout JSword to create the preferred
>>>> type of Passage. You can set it to one of the above via PassageType
>>>> typically at program startup.
>>>>
>>>> I wrote BitwisePassage; Joe wrote the others.
>>>>
>>>> I've been thinking that there might be another variation of
>>>> BitwisePassage that might make sense. One with testament or book bitmaps.
>>>>
>>>> Hope this helps.
>>>>
>>>>  In Him,
>>>> DM
>>>>
>>>>
>>>> On Jan 18, 2014, at 2:42 PM, Chris Burrell <chris at burrell.me.uk> wrote:
>>>>
>>>> The reason I went for passages is for less memory consumption. I also
>>>> thought it would provide better parsing and we're parsing less.
>>>>
>>>> But I think the way we store passages is to represent every verse by a
>>>> bit. means that iterating through ranges, calculating cardinality or
>>>> initialising them means is expensive.
>>>>
>>>> I wonder if we could have a passage that just stores boundaries rather
>>>> than all its content. That would be very fast to parse and very quick for
>>>> operations on it.
>>>>
>>>> Chris
>>>>  On 18 Jan 2014 19:17, "Martin Denham" <mjdenham at gmail.com> wrote:
>>>>
>>>>> I think I have found a workaround for this problem (using a background
>>>>> thread makes it run very quickly) but it seems to point toward a possible
>>>>> point of improvement in the new JSword mapping data structure.
>>>>>
>>>>> In the old AB v11n mapping code I stored maps of Verses.  However the
>>>>> new JSword code seems to store maps of RocketPassage/BitwisePassage.  Can
>>>>> you verify this is the best data structure for what will normally be a
>>>>> single verse.  I don't know an awful lot about this so I am just asking,
>>>>> but maybe a Passage will always consume more memory than a Verse.
>>>>>
>>>>> Thanks
>>>>> Martin
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> On 18 January 2014 13:30, Martin Denham <mjdenham at gmail.com> wrote:
>>>>>
>>>>>> I tried your patch and it did noticeably improve things, so it is a
>>>>>> worthwhile patch, but did not solve the actual problem.  Still viewing the
>>>>>> RusSynodal straight after download takes well over a minute, whereas to
>>>>>> boot straight into it takes about 2 secs.
>>>>>>
>>>>>> One or 2 things I have noticed:
>>>>>>
>>>>>>    - a huge amount of memory allocation and GC occurs when trying to
>>>>>>    view RusSynodal straight after download
>>>>>>    - I am not great with the profiler but here are my tentative
>>>>>>    observations
>>>>>>       - Seems to be spending about half the time in
>>>>>>       java.util.BitSet.cardinality()
>>>>>>          - called by
>>>>>>          BitwisePassage.countVerses()<-RocketPassage.countVerses()<-AbstractPassage.getCardinality()<-VersificationToKJVMapper.add...
>>>>>>       - I tried caching AbstractPassage.getCardinality but that had
>>>>>>       no affect which would be the case if there were lots of different keys
>>>>>>    - Could it be that a module is in an unusual state after
>>>>>>    download?  I have noticed that a module cannot be deleted directly after
>>>>>>    download, until the app is restarted due to:
>>>>>>       - sbmd.getConfigFile()==null when called by
>>>>>>       SwordBookDriver.isDeletable directly after module download
>>>>>>
>>>>>> Any suggestions are welcome.
>>>>>>
>>>>>> Cheers
>>>>>> Martin
>>>>>>
>>>>>>
>>>>>> On 16 January 2014 23:13, Martin Denham <mjdenham at gmail.com> wrote:
>>>>>>
>>>>>>> I think I will use the old AB v11n mapping for the next release of
>>>>>>> AB and come back to this after the release which has quite a lot of changes
>>>>>>> in it already anyway.
>>>>>>>
>>>>>>> The problem could be AB, Android, or JSword related and it is not
>>>>>>> trivial to reproduce involving repeated re-installs of RusSynodal.  I had a
>>>>>>> similar problem a year or two ago, it took a long time to investigate and
>>>>>>> ended up being a flaw in the Android VM which required a change to JSword.
>>>>>>>
>>>>>>> I keep trying to think what could cause these symptoms and drawing a
>>>>>>> blank.
>>>>>>>
>>>>>>> Cheers
>>>>>>> Martin
>>>>>>>
>>>>>>>
>>>>>>> On 16 January 2014 21:35, Chris Burrell <chris at burrell.me.uk> wrote:
>>>>>>>
>>>>>>>> I'll try profiling it! Nothing comes to mind though.
>>>>>>>>  On 16 Jan 2014 20:04, "Martin Denham" <mjdenham at gmail.com> wrote:
>>>>>>>>
>>>>>>>>> There is something unusual happening with the v11n mapping
>>>>>>>>> creation straight after downloading a file requiring mapping e.g. It takes
>>>>>>>>> over 2 mins to load the mapping (a single call to mapVerse) for RusSynodal
>>>>>>>>> straight after download but a few seconds to load the file normally.
>>>>>>>>>
>>>>>>>>> 1. View ESV and anything else in split screen
>>>>>>>>> 2. Download RusSynodal
>>>>>>>>> 3. Exit download screen after download
>>>>>>>>> 4. select RusSynodal for display (with ESV) in 1 half of split
>>>>>>>>> screen
>>>>>>>>> 5. Mapping code now takes over 2 minutes to load mapping
>>>>>>>>> 6. But there are no errors and then everything seems fine
>>>>>>>>>
>>>>>>>>> 7. Exit and kill And Bible
>>>>>>>>> 8. Restart with ESV/RST in split screens
>>>>>>>>> 9. This time everything is initialised in a few seconds
>>>>>>>>>
>>>>>>>>> Any ideas?
>>>>>>>>>
>>>>>>>>> Martin
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> On 16 January 2014 19:06, Chris Burrell <chris at burrell.me.uk>wrote:
>>>>>>>>>
>>>>>>>>>> Hi Martin
>>>>>>>>>>
>>>>>>>>>> Fine by me. Think it should be opt in if possible.
>>>>>>>>>>
>>>>>>>>>> A couple of thoughts on that note. Do you know of it s the io or
>>>>>>>>>> the cpu time that's the issue?
>>>>>>>>>>
>>>>>>>>>> We probably want to opt in with a list as well as all as there's
>>>>>>>>>> no point in loading the v11n if not required.
>>>>>>>>>>
>>>>>>>>>> I guess especially if we end up with mappings per module
>>>>>>>>>> eventually.
>>>>>>>>>>
>>>>>>>>>> On a separate note, I also found the books.installed call is very
>>>>>>>>>> expensive. Thinking it may be worth partially loading these. With around
>>>>>>>>>> 200 modules we spend almost 15 seconds loading them.
>>>>>>>>>>
>>>>>>>>>> Finally you can apply for a open source license of jprofiler
>>>>>>>>>> which helps massively to work out what's going on. Have got a couple of
>>>>>>>>>> uncommitted fixes for books. Installed find with that.
>>>>>>>>>>
>>>>>>>>>> Chris
>>>>>>>>>> On 16 Jan 2014 18:10, "Martin Denham" <mjdenham at gmail.com> wrote:
>>>>>>>>>>
>>>>>>>>>>>  Hi,
>>>>>>>>>>>
>>>>>>>>>>> I have integrated the new v11n mapping code and find I am
>>>>>>>>>>> getting a pause when doing the initial mapping between any 2 v11ns.
>>>>>>>>>>>
>>>>>>>>>>> I originally had the same problem with the AB mapping code so
>>>>>>>>>>> pre-loaded all mapping required for the installed set of documents at the
>>>>>>>>>>> start in a background thread to prevent delays.  The code I used is in
>>>>>>>>>>> VersificationMappingFactory.initialiseRequiredMappings()<https://github.com/mjdenham/and-bible/blob/master/AndBible/src/net/bible/android/control/versification/mapping/VersificationMappingFactory.java>
>>>>>>>>>>> .
>>>>>>>>>>>
>>>>>>>>>>> I am trying to think of the best way to do this in the new code.
>>>>>>>>>>>  Either i) you could add a method to do it which could be called or ii) you
>>>>>>>>>>> could proeload all required mappings automatically or iii) add a new method
>>>>>>>>>>> to allow AB (or other frontend) to trigger preload of all required mappings
>>>>>>>>>>> by adding a public method a bit like the new
>>>>>>>>>>> VersificationsMapper.ensure(v11ntopreload).
>>>>>>>>>>>
>>>>>>>>>>> This is quite an issue for mobile users.  I have a fast mobile
>>>>>>>>>>> and loading a mapping causes a noticeable delay the first time a verse
>>>>>>>>>>> changes, but the preload fix is fairly simple and worked well.
>>>>>>>>>>>
>>>>>>>>>>> Cheers
>>>>>>>>>>> Martin
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> _______________________________________________
>>>>>>>>>>> jsword-devel mailing list
>>>>>>>>>>> jsword-devel at crosswire.org
>>>>>>>>>>> http://www.crosswire.org/mailman/listinfo/jsword-devel
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>> _______________________________________________
>>>>>>>>>> jsword-devel mailing list
>>>>>>>>>> jsword-devel at crosswire.org
>>>>>>>>>> http://www.crosswire.org/mailman/listinfo/jsword-devel
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>
>>>>>>>
>>>>>>
>>>>>  _______________________________________________
>>>> jsword-devel mailing list
>>>> jsword-devel at crosswire.org
>>>> http://www.crosswire.org/mailman/listinfo/jsword-devel
>>>>
>>>>
>>>>
>>>
>>>
>>
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.crosswire.org/pipermail/jsword-devel/attachments/20140120/439e2d68/attachment-0001.html>

More information about the jsword-devel mailing list