[poppler] KMP for search
buchner.johannes at gmx.at
Tue Jun 15 22:48:39 PDT 2010
On Tue, 15 Jun 2010 19:05:25 +0100
Albert Astals Cid <aacid at kde.org> wrote:
> > I implemented the KMP search algorithm in  but I feel it doesn't
> > get attention. Please apply  and test it.
> You sent a mail yesterday and already complain you are being ignored?
No, I added the patch the day before, and since only 3 adresses are
notified about it, I thought it would be worth mentioning on the
mailing list aswell.
> >  https://bugs.freedesktop.org/show_bug.cgi?id=8821
> >  https://bugs.freedesktop.org/attachment.cgi?id=36255
> > To be honest, the gain is small;
> If the gain is small i'd prefer to stay with our tested code than to
> switch to something totally new.
I understand where you're coming from; I've seen a improvement of factor
3 for certain cases, and I've never seen a lower speed compared to the
naive implementation. It shows that the factors of O(n*m) are comparable
to the factors of the new O(n). So it has a gain.
I tested the KMP code with several instances before integrating it into
poppler, and afterwards using the glib-demo program. The code is not
"totally new" in the sense that KMP is old, and I kept to
implementations I found on the web. The change  is small (~10
lines changed plus two new functions), although the additional
indentation level makes it look bigger.
So, yes, I think it should go in.
> > I find it odd that the search
> > function is page-based and runs per block (sorry, I'm new to
> > poppler). It strikes me that no wrapped words can ever be found.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Size: 198 bytes
Desc: not available
More information about the poppler