Performance Improvement for TextPage:findText()
Submitted by David Benjamin
Assigned to poppler-bugs
Description
(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.)