[Poppler-bugs] [Bug 8821] New: Performance Improvement for TextPage:findText()

[bugzilla-daemon at annarchy.freedesktop.org]

Please do not reply to this email: if you want to comment on the bug, go to    
       
the URL shown below and enter yourcomments there.     
   
https://bugs.freedesktop.org/show_bug.cgi?id=8821          
     
           Summary: Performance Improvement for TextPage:findText()
           Product: poppler
           Version: unspecified
          Platform: PC
        OS/Version: Linux
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: general
        AssignedTo: poppler-bugs at lists.freedesktop.org
        ReportedBy: dnas.dnas at gmail.com


(Sorry if I did the patch file wrong or anything like that... this is my first
(and hopefully not the last :-D) contribution to a FOSS project other than a
typo correction, so... yeah. :-) )

Anyways, so I made some minor improvements to TextPage:findText in
poppler/TextOutputDev.cc.

Hopefully I didn't make any mis-optimizations out of misunderstanding bits of
the codebase. :-)

Changes:
- If a block is past what we've already found, then break.
- If a line is past the end of the searching position, break if searching forwards
- If a line is past what we've already found, break if searching forwards,
otherwise just continue
- When searching within a line, instead of searching according to backward,
search via searchBackwards which takes line rotation into account, thus allowing
us to break once the first match in a line is found.

I've also got an implementation of KMP (
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm ) with
caching of failure functions since most programs do find-as-you-type, but I need
to make sure the (minor) extra complexity incurred doesn't outweigh the O()
improvement. Probably will attach that in a couple days.


I hope it's of some use. (Changes made against the 0.5.4 release.)


Hmm... I take it the attach file thing is after commiting the report? (I'm not
that familiar with Bugzilla yet.)          
     
     
--           
Configure bugmail: https://bugs.freedesktop.org/userprefs.cgi?tab=email         
     
------- You are receiving this mail because: -------
You are the assignee for the bug, or are watching the assignee.