[sword-devel] Question for Optimization / speed experts

[Glen Prideaux]

Joachim Ansorg wrote:

>Hi!
>Some questiosn for optimizations experts :)
>
>I'm working on a piece of code in BibleTime which gives me headaches.
>BibleTime supports displaying different lexicons side by side, it offers only 
>the keys which are available in all of the chosen lexicons.
>
>The function which creates the list of entries which  are available in all 
>modules is ways too slow and too CPU consuming.
>I implemented it the following way:
>
> 1. Sort the modules by number of entries (from small to large)
> 2. Use the modules with the fewest entries and go through all of it's 
>entries:
>	 3. Is the entry in all other modules? Add the entry to a list of good 
>entries it it is, otherwise continue with the next entry of the smallest list 
>and compare it with all other chosen modules.
>
>Assume the user selected BDB together with StrongsHebrew. Each of the modules 
>has around 10000 entries. So the outer loop would have 10000 iterations, the 
>inner loop would have another 10000 iterations. So we get 
>10.000*10.000=100.000.000 = one hunred million iterations. This is ways too 
>slow and ways too much.
>This needs on my 1.2GHz Atlon with 512 MB Ram more then five seconds. 
>
>If there are three, four or even five modules side by side we get much more 
>loops.
>
>Are the other ways to do such a task? Since the entry lists are sorted by the 
>alaphabet this would be a good point to start. But I don't know how to do it 
>best.
>
>I'd be really glad for help with this case!
>
>Thank you!
>Joachim
>  
>
My thoughts:

initialise a marker to the first entry in each module
FOR each entry in module A
    flag the entry as (potentially) good
    FOR each other module
        WHILE the marked entry in module is BEFORE the marked entry in A
            move the marker forward an entry
        IF the marked entry is AFTER the marked entry in A
            flag the entry as bad
            EXIT inner loop
    IF the entry is not flagged as bad
        add entry to list of good entries
    move marker in module A forward an entry

This will iterate exactly once through each entry in each module. It 
depends on the modules being sorted, but I understand that's a given anyway.

Glen